The Diophantine problem for systems of algebraic equations with exponents

Richard Mandel; Alexander Ushakov

doi:10.1016/j.jalgebra.2023.08.025

The Diophantine problem for systems of algebraic equations with exponents

Richard Mandel
, Alexander Ushakov

Department of Mathematical Sciences

University of the Basque Country

Research output: Contribution to journal › Article › peer-review

Abstract

Consider the equation q₁α^x₁+…+q_kα^x_k=q, with constants α∈Q‾∖{0,1}, q₁,…,q_k,q∈Q‾ and unknowns x₁,…,x_k, referred to in this paper as an algebraic equation with exponents. We prove that the problem to decide if a given equation has an integer solution is NP-complete, and that the same holds for systems of equations (whether α is fixed or given as part of the input). Furthermore, we describe the set of all solutions for a given system of algebraic equations with exponents and prove that it is semilinear.

Original language	English
Pages (from-to)	779-803
Number of pages	25
Journal	Journal of Algebra
Volume	636
DOIs	https://doi.org/10.1016/j.jalgebra.2023.08.025
State	Published - 15 Dec 2023

Keywords

Algebraic equations
Complexity
Diophantine problem
Exponents
NP-completeness
Systems of equations

Access to Document

10.1016/j.jalgebra.2023.08.025

Cite this

@article{c28a561835ec46978286da65e880a289,

title = "The Diophantine problem for systems of algebraic equations with exponents",

abstract = "Consider the equation q1αx1+…+qkαxk=q, with constants α∈Q‾∖\{0,1\}, q1,…,qk,q∈Q‾ and unknowns x1,…,xk, referred to in this paper as an algebraic equation with exponents. We prove that the problem to decide if a given equation has an integer solution is NP-complete, and that the same holds for systems of equations (whether α is fixed or given as part of the input). Furthermore, we describe the set of all solutions for a given system of algebraic equations with exponents and prove that it is semilinear.",

keywords = "Algebraic equations, Complexity, Diophantine problem, Exponents, NP-completeness, Systems of equations",

author = "Richard Mandel and Alexander Ushakov",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier Inc.",

year = "2023",

month = dec,

day = "15",

doi = "10.1016/j.jalgebra.2023.08.025",

language = "English",

volume = "636",

pages = "779--803",

}

TY - JOUR

T1 - The Diophantine problem for systems of algebraic equations with exponents

AU - Mandel, Richard

AU - Ushakov, Alexander

PY - 2023/12/15

Y1 - 2023/12/15

N2 - Consider the equation q1αx1+…+qkαxk=q, with constants α∈Q‾∖{0,1}, q1,…,qk,q∈Q‾ and unknowns x1,…,xk, referred to in this paper as an algebraic equation with exponents. We prove that the problem to decide if a given equation has an integer solution is NP-complete, and that the same holds for systems of equations (whether α is fixed or given as part of the input). Furthermore, we describe the set of all solutions for a given system of algebraic equations with exponents and prove that it is semilinear.

AB - Consider the equation q1αx1+…+qkαxk=q, with constants α∈Q‾∖{0,1}, q1,…,qk,q∈Q‾ and unknowns x1,…,xk, referred to in this paper as an algebraic equation with exponents. We prove that the problem to decide if a given equation has an integer solution is NP-complete, and that the same holds for systems of equations (whether α is fixed or given as part of the input). Furthermore, we describe the set of all solutions for a given system of algebraic equations with exponents and prove that it is semilinear.

KW - Algebraic equations

KW - Complexity

KW - Diophantine problem

KW - Exponents

KW - NP-completeness

KW - Systems of equations

UR - https://www.scopus.com/pages/publications/85171991281

UR - https://www.scopus.com/pages/publications/85171991281#tab=citedBy

U2 - 10.1016/j.jalgebra.2023.08.025

DO - 10.1016/j.jalgebra.2023.08.025

M3 - Article

AN - SCOPUS:85171991281

SN - 0021-8693

VL - 636

SP - 779

EP - 803

JO - Journal of Algebra

JF - Journal of Algebra

ER -

The Diophantine problem for systems of algebraic equations with exponents

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this