plain

# The Diophantine problem for systems of algebraic equations with exponents

Richard Mandel  Department of Mathematics, University of the Basque Country,
Bilbao, Spain<EMAIL_ADDRESS>and  Alexander Ushakov  Department of
Mathematical Sciences, Stevens Institute of Technology, Hoboken NJ 07030
<EMAIL_ADDRESS>
###### Abstract.

Consider the equation $q_{1}\alpha^{x_{1}}+\dots+q_{k}\alpha^{x_{k}}=q$, with
constants $\alpha\in\overline{\mathbb{Q}}\setminus\\{0,1\\}$,
$q_{1},\ldots,q_{k},q\in\overline{\mathbb{Q}}$ and unknowns
$x_{1},\ldots,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 $\alpha$ 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.

The first author was partially supported by the Basque Government Grant
IT1483-22 and the Spanish Government grants PID2019-107444GA-I00 and
PID2020-117281GB-I00.

00footnotetext: _2020 Mathematics Subject Classification._ Primary 11Y16,
68Q15, 68W30.00footnotetext: _Key words and phrases._ Diophantine problem,
algebraic equations, systems of equations, exponents, complexity,
${\mathbf{NP}}$-completeness.

##  1\. Introduction

A classical _Diophantine equation_ is an equation with integer coefficients
and one or more unknowns, for which only the integer solutions are of
interest. Such equations have been studied since antiquity, motivating much
fruitful work in diverse areas of mathematics (Fermat’s last theorem is a
particularly famous example). For a class ${\mathcal{C}}$ of Diophantine
equations (or of systems of Diophantine equations), one can study three
related algorithmic problems:

  1. (i)

decide whether a given equation from ${\mathcal{C}}$ has a solution or not;

  2. (ii)

find a solution for a given equation from ${\mathcal{C}}$, assuming one
exists;

  3. (iii)

describe the set of all solutions for a given equation from ${\mathcal{C}}$.

The first problem is called the _Diophantine problem for_ ${\mathcal{C}}$, and
is denoted ${\mathbf{DP}}_{\mathcal{C}}$. In modern mathematics, the notion is
extended to any algebraic structure (or a class of algebraic structures)
${\mathcal{S}}$, where the notation
${\mathbf{DP}}_{{\mathcal{C}}}({\mathcal{S}})$ may be used. For instance, we
may speak of the Diophantine problem
${\mathbf{DP}}_{\mathcal{P}}({\mathbb{Q}})$ for systems of polynomial
equations over $\mathbb{Q}$, or the Diophantine problem
${\mathbf{DP}}({\mathcal{N}}_{3})$ for systems of arbitrary equations in the
class ${\mathcal{N}}_{3}$ of nilpotent groups of step $3$.

The most well studied classes of Diophantine equations are the classes
${\mathcal{L}}$ of linear systems and $\mathcal{P}$ of polynomial systems. The
problem ${\mathbf{DP}}_{{\mathcal{L}}}$ has an efficient (polynomial time)
solution: it may be solved by computing the Hermite (or Smith) normal form of
the corresponding matrix (see [14]). On the other hand,
${\mathbf{DP}}_{\mathcal{P}}({\mathbb{Z}})$ is Hilbert’s famous tenth problem,
first proposed in 1900 and only shown to have no algorithmic solution in 1970,
as a result of the combined work of Y. Matiyasevich, J. Robinson, M. Davis,
and H. Putnam, spanning 21 years (with Matiyasevich completing the
theorem—known as the MRDP theorem—in 1970 [12]). Notably, the decidability of
${\mathbf{DP}}_{\mathcal{P}}({\mathbb{Q}})$ remains an open question.

In this paper we study the class ${\mathcal{E}}$ of systems of Diophantine
equations of the following form:

(1)
$\left\\{\begin{array}[]{cl}q_{11}\alpha_{1}^{x_{1}}+\dots+q_{1k}\alpha_{1}^{x_{k}}&=q_{10}\\\
\vdots&\\\ q_{s1}\alpha_{s}^{x_{1}}+\dots+q_{sk}\alpha_{s}^{x_{k}}&=q_{s0}\\\
\end{array}\right.$

with constants
$\alpha_{1},\ldots,\alpha_{s}\in{\overline{\mathbb{Q}}}\setminus\\{0,1\\}$
(where ${\overline{\mathbb{Q}}}$ denotes an algebraic closure of
${\mathbb{Q}}$), $q_{ij}\in{\mathbb{Q}}(\alpha_{i})$, unknowns
$x_{1},\ldots,x_{k}$, and whose solutions must be in ${\mathbb{Z}}^{k}$. We
call these equations _algebraic equations with exponents_. The Diophantine
problem for ${\mathcal{E}}$ may be considered in two distinct forms: the
_uniform problem_ , where the $\alpha_{i}$ are given as part of the input, and
the _fixed base_ problem, where the $\alpha_{i}$ are fixed beforehand.

Notice that there is no loss of generality in requiring that the coefficients
for the $i$th equation be contained in ${\mathbb{Q}}(\alpha_{i})$. In fact,
the more general problem in which
$q_{i1},\ldots,q_{ik}\in{\overline{\mathbb{Q}}}$ (with the input given in a
natural form described below) is polynomial-time equivalent to
${\mathbf{DP}}_{{\mathcal{E}}}$. This may be seen from the example of a single
equation

(2) $q_{1}\alpha^{x_{1}}+\cdots+q_{k}\alpha^{x_{k}}=q_{0}$

in the following manner. Let $K/{\mathbb{Q}}(\alpha)$ be a proper finite
degree extension such that $q_{0},q_{1},\ldots,q_{k}\in K$, and let
$m=[K:{\mathbb{Q}}(\alpha)]$. Let $\beta$ be a primitive element which
generates $K$ over ${\mathbb{Q}}(\alpha)$, and suppose that each $q_{i}$ is
given as a vector $(f_{i1},\ldots,f_{im})\in{\mathbb{Q}}(\alpha)^{m}$ such
that $q_{i}=\sum_{j=1}^{m}f_{ij}\beta^{j-1}$. Then (2) has a solution if and
only if the system

(3)
$\left\\{\begin{array}[]{cl}f_{11}\alpha^{x_{1}}+\dots+f_{k1}\alpha^{x_{k}}&=f_{01}\\\
\vdots&\\\ f_{1m}\alpha^{x_{1}}+\dots+f_{km}\alpha^{x_{k}}&=f_{0m}\\\
\end{array}\right.$

has a solution. Observe that (3) is an instance of
${\mathbf{DP}}_{{\mathcal{E}}}$ whose input is roughly the same size as that
of (2). Moreover, it is clear that we can transform one into the other in
polynomial time.

###  1.1. Encoding the input of ${\mathbf{DP}}_{{\mathcal{E}}}$

The constants $\alpha_{1},\ldots,\alpha_{s}$ are algebraic numbers (other than
0 and 1) called the _bases_ of the system; in what follows, we use the
notation $\deg(w)$ to denote the degree of the minimal polynomial of an
algebraic number $w\in{\overline{\mathbb{Q}}}$. An instance of
${\mathbf{DP}}_{{\mathcal{E}}}$ is given with the following data.

  * •

The bases $\alpha_{i}$ are specified (either as part of the input, or fixed in
advance) as lists of the integer coefficients of their minimal polynomials
$p_{\alpha_{i}}(x)=\sum_{j=0}^{d_{i}}c_{ij}x^{j}$, where
$d_{i}=\deg(\alpha_{i})$.

  * •

The coefficients $q_{ij}\in{\mathbb{Q}}(\alpha_{i})$ are given as vectors
$(r_{ij}^{0},\ldots,r_{ij}^{d_{i}-1})\in{\mathbb{Q}}^{d_{i}}$ such that
$q_{ij}=\sum_{h=0}^{d_{i}-1}r_{ij}^{h}\alpha^{h}$, with $r_{ij}^{h}$ given as
a quotient (in lowest terms) $r_{ij}^{h}=\frac{a_{ij}^{h}}{b_{ij}^{h}}$.

This naturally defines the size of an instance $E$ of the problem as

(4)
$\operatorname{{size}}(E)=\sum_{i=1}^{s}\sum_{j=1}^{k}\sum_{h=0}^{d_{i}-1}\Big{(}\log_{2}(|a_{ij}^{h}|+1)+\log_{2}(|b_{ij}^{h}|+1)\Big{)}+\sum_{i=1}^{s}\sum_{j=0}^{d_{i}}\log_{2}(|c_{ij}|+2),$

if $E$ is an instance of the uniform problem, and

(5)
$\operatorname{{size}}(E)=\sum_{i=1}^{s}\sum_{j=1}^{k}\sum_{h=0}^{d_{i}-1}\Big{(}\log_{2}(|a_{ij}^{h}|+1)+\log_{2}(|b_{ij}^{h}|+1)\Big{)}$

if $E$ is an instance of the fixed base problem. This is roughly the number of
bits required to encode $E$ (the terms $\log_{2}(|c_{ij}|+2)$ are needed to
count the zero coefficients of $p_{\alpha_{i}}$, and to ensure that
$\deg(\alpha_{i})<\operatorname{{size}}(E)$).

The minimal polynomials of $\alpha_{i}$ are assumed to be irreducible, which
means that ${\mathbf{DP}}_{{\mathcal{E}}}$, as defined above, is a _promise
problem_ (i.e. the input is “promised” to belong to a certain subset of all
possible inputs). However, this is only a matter of convenience, since D. G.
Cantor has shown that the problem of deciding whether a given polynomial is
irreducible is in ${\mathbf{NP}}$ (see [2]). Thus, our proof that
${\mathbf{DP}}_{{\mathcal{E}}}\in{\mathbf{NP}}$ can easily be adapted to allow
for arbitrary input by combining Cantor’s ${\mathbf{NP}}$-certificate with our
own.

We assume a basic background in complexity theory and
${\mathbf{NP}}$-completeness, as may be found in [5].

###  1.2. Main results

We prove that the Diophantine problem for ${\mathcal{E}}$ is
${\mathbf{NP}}$-complete, and that it remains ${\mathbf{NP}}$-complete for
single equations with any fixed choice of
$\alpha\in{\overline{\mathbb{Q}}}\setminus\\{0,1\\}$. Additionally, we
describe the solution set for a given instance, and prove that it is
semilinear. On a finer scale, we show that the Diophantine problem for a
system $E\in{\mathcal{E}}$ can be solved in polynomial time as long as the
number of equations is bounded by a fixed constant. In other words, it is a
_fixed-parameter tractable problem_.

###  1.3. Related results and applications

Equations of a similar form were considered by A. Semenov in 1984, in the
course of his investigation of the first-order theory of the algebraic
structure ${\left\langle{\mathbb{N}};+,k^{x}\right\rangle}$ (where
$k\in{\mathbb{N}}$ is a fixed base for the exponential). Using methods
involving quantifier elimination, Semenov proved the decidability of this
theory in [13]. Notably, while it is a simple matter to solve (1) over the
real or complex numbers, the first-order theory of
${\left\langle\mathbb{C};+,k^{x}\right\rangle}$ is undecidable (since
${\left\langle{\mathbb{Z}};+,\cdot\right\rangle}$ is interpretable in this
structure), and the decidability of
${\left\langle{\mathbb{R}};+,k^{x}\right\rangle}$ is an open question (but
known to follow from Schanuel’s conjecture; see [11]).

Equations with exponents play a very important role in study of discrete
optimization problems (such as the knapsack problem, the power word problem,
see [4, 9]) and decision problems over certain groups. In fact, our present
interest in the class of equations ${\mathcal{E}}$ arose from studying the
Diophantine problem over the Baumslag-Solitar groups. There turns out to be a
close connection between algebraic equations with exponents in base
$\frac{m}{n}$ and equations in ${\mathbf{BS}}(m,n)$, suggesting the importance
of decidability and complexity results for ${\mathbf{DP}}_{{\mathcal{E}}}$. In
a forthcoming paper [10], we employ some of the present results to prove, for
instance, that the quadratic Diophantine problem for ${\mathbf{BS}}(1,n)$ is
${\mathbf{NP}}$-complete for $n\neq 1$, and we expect further applications to
the study of equations (quadratic and otherwise) in ${\mathbf{BS}}(m,n)$ and
related groups. For background and recent results on the Diophantine problem
in various classes of groups, see, for instance, [7] and [6], as well as [3]
for the decidability of the Diophantine problem in groups that are virtually a
direct product of hyperbolic groups (including the unimodular Baumslag-Solitar
groups ${\mathbf{BS}}(n,\pm n)$).

###  1.4. Outline and general approach

In Section 2, we prove that the Diophantine problem for a single equation with
$\alpha\in{\overline{\mathbb{Q}}}\setminus\\{0,1\\}$ is ${\mathbf{NP}}$-hard.
This is accomplished via a reduction of either the _partition problem_ (in
case $\alpha$ is a root of unity) or the _3-partition problem_ (both well-
known ${\mathbf{NP}}$-complete problems) to ${\mathbf{DP}}$. In Section 3, we
prove that the Diophantine problem for a single equation with
$\alpha\in{\overline{\mathbb{Q}}}\setminus\\{0,1\\}$ belongs to
${\mathbf{NP}}$.

Sections 4 and 5 extend the above results to finite systems of equations, and
in Section 6 we describe the solution set for a system of equations. Finally,
Section 7 addresses the parameterized complexity of the problem.

##  2\. Complexity lower bound for a single equation

Fix $\alpha\in{\overline{\mathbb{Q}}}\setminus\\{0,1\\}$ and consider the
equation

(6) $q_{1}\alpha^{x_{1}}+\dots+q_{k}\alpha^{x_{k}}=q_{0}$

with $q_{1},\ldots,q_{k},q_{0}\in\mathbb{Q}(\alpha)$, unknowns
$x_{1},\ldots,x_{k}$ and solutions sought in ${\mathbb{Z}}$. In this section,
we prove that the Diophantine problem for (6) is ${\mathbf{NP}}$-hard. We
first handle the special case where $\alpha$ is a root of unity.

###  2.1. $\alpha$ is a root of unity

Let $\alpha=e^{2\pi i/n}\neq 1$ for $n\geq 2$. Below, we prove
${\mathbf{NP}}$-hardness by reducing the partition problem (which is known to
be ${\mathbf{NP}}$-complete) to the decidability of (6). Recall that the
_partition problem_ is the problem to decide if a given multiset
$\\{q_{1},\ldots,q_{k}\\}$ of positive integers can be partitioned into two
submultisets $S_{0}$ and $S_{1}$ such that $\sum_{x\in S_{0}}x=\sum_{x\in
S_{1}}x$, see [5].

For an instance $Q=\\{q_{1},\ldots,q_{k}\\}$ of the partition problem, define
$L=\frac{1}{2}\sum q_{i}$ (we may assume that $L\in{\mathbb{Z}}$), and let
$E_{Q}$ denote the following equation:

(7) $\sum q_{i}\alpha^{x_{i}}=L+L\alpha.$

Note that
$\operatorname{{size}}(E_{Q})=\sum_{i=1}^{k}\log_{2}(q_{i}+1)+2\log_{2}(L+1)$,
which is linear in the size of $Q$ (with $Q$ represented in binary).

######  Proposition 2.1.

$Q$ is a positive instance of the partition problem if and only if $E_{Q}$ has
a solution.

###### Proof.

Consider two cases. Suppose that $\alpha=-1$. Then the right-hand side of (7)
is equal to zero, $\alpha^{x_{i}}=\pm 1$, and (7) translates to the equation

$\sum\varepsilon_{i}q_{i}=0,$

with unknowns $\varepsilon_{1}\dots,\varepsilon_{k}=\pm 1$, which is
equivalent to the partition problem. The converse is also true.

Suppose that $\alpha\neq-1$. If $Q$ is a positive instance, then it is clear
that $E_{Q}$ has a solution (with $x_{i}\in\\{0,1\\}$). Conversely, assume
that $E_{Q}$ has a solution ${\overline{x}}=(x_{1},\ldots,x_{k})$. Consider
the complex number $u=1+\alpha$ as a vector in ${\mathbb{R}}^{2}$, and let
$\pi_{u}(z)$ denote the signed scalar projection of $z$ onto $u$, defined by

$\pi_{u}(z)=\tfrac{\Re({\overline{u}}z)}{|u|}.$

It is easily verified that

$\pi_{u}(1)=\pi_{u}(\alpha)=\tfrac{|u|}{2}>\max\\{\pi_{u}(\alpha^{2}),\dots,\pi_{u}(\alpha^{n-1})\\}.$

Since the projection of the right-hand side of (7) onto $u$ is equal to
$L|u|$, and since $\sum_{i=1}^{k}q_{i}=2L$, it follows that the $x_{i}$ must
all be either 0 or 1 (otherwise the left-hand side would have a projection
strictly less than $L|u|$). Letting $S_{0}=\\{i\in\\{1,\ldots,k\\}|x_{i}=0\\}$
and $S_{1}=\\{i\in\\{1,\ldots,k\\}|x_{i}=1\\}$, the ${\mathbb{Q}}$-linear
independence of $\\{1,\alpha\\}$ implies that

$\sum_{i\in S_{0}}q_{i}=L=\sum_{i\in S_{1}}q_{i},$

proving that $Q$ is a positive instance. ∎

######  Corollary 2.2.

Then the (fixed base) Diophantine problem for equations (6) is
${\mathbf{NP}}$-complete.∎

###### Proof.

${\mathbf{NP}}$-hardness is proved above. To establish that the problem is in
${\mathbf{NP}}$, observe that if there is a solution, there must be one
satisfying

$0\leq x_{1},\ldots,x_{k}<n,$

where $n$ is the order of $\alpha$, and it is easily seen that $n$ is
$O(\operatorname{{size}}^{2}(E))$. It is shown in Lemma 3.1 that such a
solution may be verified in time polynomial in $\operatorname{{size}}(E)$. ∎

There exist polynomial-time algorithms (see, for instance [1]) to determine,
based on its minimal polynomial, whether $\alpha\in{\overline{\mathbb{Q}}}$ is
a root of unity (and if so, to find its order). Thus, it is valid to consider
this case separately for the uniform Diophantine problem (when $\alpha$ is a
part of the input), and we may consequently assume that $\alpha$ is _not_ a
root of unity in Section 3 (where it is proved that the Diophantine problem
for a single equation is in ${\mathbf{NP}}$).

###  2.2. $\alpha$ is not a root of unity

The following proposition is the main technical result of this section. In
what follows, ${\mathcal{U}}$ always denotes the set of roots of unity and
${\overline{\mathbb{Q}}}^{\ast}={\overline{\mathbb{Q}}}\setminus\\{0\\}$.

######  Proposition 2.3.

Let $\alpha\in{\overline{\mathbb{Q}}}^{*}\setminus{\mathcal{U}}$ and
$d=\deg(\alpha)$. For $s\in{\mathbb{N}}$, define the positive integer

(8) $c(\alpha,s)=\left\lceil\frac{3(\ln 2+2\ln s)}{\kappa(d)}\right\rceil,$

where

$\kappa(d)=\begin{cases}\ln 2&\mbox{for }\ d=1,\\\
\frac{2}{d\cdot(\ln(3d))^{3}}&\mbox{for }\ d\geq 2.\end{cases}$

Then for any integers $0\leq p_{1}<p_{2}<\dots<p_{s}$ satisfying
$p_{i+1}-p_{i}\geq c(\alpha,s)$, the equation

(9) $\alpha^{x_{1}}+\dots+\alpha^{x_{s}}=\alpha^{p_{1}}+\dots+\alpha^{p_{s}}$

has (up to a permutation) the unique integer solution $x_{i}=p_{i}$.

For the proof, we make use of the following lemma, proved by H. W. Lenstra,
see [8, Proposition 2.3]. Note that Lenstra’s original result is more general,
as it applies to polynomials in ${\overline{\mathbb{Q}}}[x]$; we only require
the slightly weaker version for polynomials in ${\mathbb{Z}}[x]$ stated below.
For a polynomial $f(x)=\sum_{i=1}^{h}c_{i}x^{i}\in{\mathbb{Z}}[x]$ define

$\operatorname{height}(f)=\max(|c_{1}|,\ldots,|c_{h}|).$

######  Lemma 2.4 (Lenstra).

Let $\alpha,d$ and $\kappa(d)$ be as in Proposition 2.3, and suppose that a
polynomial $P(x)=P_{0}(x)+x^{r}P_{1}(x)\in{\mathbb{Z}}[x]$ contains $k$
monomials and satisfies

(10) $r-\deg(P_{0})>\frac{\ln(k-1)+\ln(\operatorname{height}(P))}{\kappa(d)}.$

Then $P(\alpha)=0$ if and only if $P_{0}(\alpha)=0$ and $P_{1}(\alpha)=0$. ∎

###### Proof of Proposition 2.3.

By way of contradiction, let $0\leq p_{1}<p_{2}<\dots<p_{s}$ satisfy
$p_{i+1}-p_{i}\geq c(\alpha,s)$, and suppose there is a solution
$x_{1}\leq\dots\leq x_{s}\in{\mathbb{Z}}$ to (9) such that
$\\{x_{1},\ldots,x_{s}\\}\neq\\{p_{1},\ldots,p_{s}\\}$. Multiplying by an
appropriate power of $\alpha$ if necessary, we may assume that the $x_{i}$ are
nonnegative. Eliminating terms that appear on both sides and reindexing, we
obtain $x_{1},\ldots,x_{s^{\prime}}$ and $p_{1},\ldots,p_{s^{\prime}}$ such
that $\\{x_{1},\ldots,x_{s}\\}\cap\\{p_{1},\ldots,p_{s}\\}=\emptyset$ and
$s^{\prime}\leq s$. Hence, the polynomial

$P(x)=\sum_{i=1}^{s}x^{p_{i}}-\sum_{i=1}^{s}x^{x_{i}}$

has $k=2s^{\prime}$ monomials, with $k\leq 2s$, and satisfies $P(\alpha)=0$.
Since the coefficients of $P$ are bounded in absolute value by $s$ (this bound
is realized if $s=s^{\prime}$ and $x_{1}=\cdots=x_{s}$), we have
$\operatorname{height}(P)\leq s$. Hence, the right-hand side of the inequality
in Lemma 2.4 corresponding to $P$ is less than

$K=\frac{\ln 2+2\ln s}{\kappa(d)},$

and we notice that $c(\alpha,s)=\lceil 3K\rceil\geq 3K$. Now suppose that
there is some $t\in\\{1,\ldots,s\\}$ such that none of the $x_{i}$ are
contained in the interval $[p_{t}-K,p_{t}+K]$. Applying Lemma 2.4 twice, this
implies that $\alpha^{p_{t}}=0$, a contradiction. Thus, by a pigeonhole
argument there is exactly one $x_{i}$ contained in each of the $s$ disjoint
$K$-neighborhoods of $p_{1},\ldots,p_{s}$. This means that $P(x)$ is a sum of
$s$ polynomials of the form $B_{i}(x)=x^{p_{i}}-x^{x_{i}}$, such that

$\min(p_{i+1},x_{i+1})-\max(p_{i},x_{i})>K.$

Hence, Lemma 2.4 shows that $B_{1}(\alpha)=0$, implying that $\alpha$ is a
root of unity, which contradicts our assumption. ∎

Fix $\alpha\in{\overline{\mathbb{Q}}}^{\ast}\setminus{\mathcal{U}}$. Below we
prove ${\mathbf{NP}}$-hardness of the Diophantine problem for (6) by reducing
the $3$-partition problem to the decidability of (6). For a given multiset
$S=\\{a_{1},\ldots,a_{3k}\\}$ of $3k$ integers, define

$L=\frac{1}{k}\sum_{i=1}^{3k}a_{i}.$

The $3$-partition problem (abbreviated as $\operatorname{3PART}$) is the
problem of deciding whether an integer multiset $S=\\{a_{1},\ldots,a_{3k}\\}$,
where $L/4<a_{i}<L/2$, can be partitioned into $k$ triples, each of which sums
to $L$. This problem is known to be _strongly_ ${\mathbf{NP}}$-complete, which
means that it remains ${\mathbf{NP}}$-complete even when the input is
represented in unary. A thorough treatment of this problem may be found in
[5]. Below we reduce an instance of $\operatorname{3PART}$ to an instance of
the Diophantine problem for (6). Note that because of the restriction
$L/4<a_{i}<L/2$, we may assume that $S$ contains only positive integers.

Let $S=\\{a_{1},\ldots,a_{3k}\\}$ be an instance of $\operatorname{3PART}$,
with $L=\frac{1}{k}\sum_{i=1}^{3k}a_{i}$ the anticipated sum and
$L/4<a_{i}<L/2$ (we may assume that $L\in{\mathbb{N}}$). Let $c=c(\alpha,Lk)$
be defined as in Proposition 2.3, and define the numbers

$\displaystyle q_{y}$
$\displaystyle=1+\alpha^{c}+\alpha^{2c}+\dots+\alpha^{(y-1)c}\ \ \ \ \ \
\mbox{ for }\ \ y\in{\mathbb{N}}$ $\displaystyle r$
$\displaystyle=q_{L}{\left(1+\alpha^{2cL}+\alpha^{4cL}+\dots+\alpha^{2(k-1)cL}\right)}$

and the equation

(11) $q_{a_{1}}\alpha^{x_{1}}+\cdots+q_{a_{3k}}\alpha^{x_{3k}}=r.$

######  Proposition 2.5.

$S$ is a positive instance of $\operatorname{3PART}$ if and only if (11) has a
solution. Furthermore, a solution $x_{1},\ldots,x_{3k}$ for (11), if it
exists, is unique up to a permutation and satisfies

(12) $0\leq x_{1},\ldots,x_{3k}\leq 2ckL.$

###### Proof.

Suppose that $S$ is a positive instance of $\operatorname{3PART}$. Reindexing
the $a_{i}$ and $x_{i}$ if necessary, we may assume that
$\sum_{j=1}^{3}a_{3i+j}=L$ for $i=0,1,\ldots,k-1$. It is now easily checked
that

$\displaystyle x_{3i+1}$ $\displaystyle=2icL$ $\displaystyle x_{3i+2}$
$\displaystyle=c(2iL+a_{3i+1})$ $\displaystyle x_{3i+3}$
$\displaystyle=c(2iL+a_{3i+1}+a_{3i+2})$

for $i=0,1,\ldots,k-1$ satisfies (11) and (12).

For the other direction, suppose that $x_{1},\ldots,x_{3k}$ is a solution of
(11). By construction, the left-hand side of (11) is a sum of $Lk$ powers of
$\alpha$, while the right-hand side is a sum of $Lk$ distinct powers of
$\alpha^{c}$. In particular, the sum on the right-hand side contains blocks of
consecutive powers of $\alpha^{c}$, with gaps between $\alpha^{(2i-1)c(L-1)}$
and $\alpha^{2icL}$ for $i=1,\ldots,k-1$. Proposition 2.3 implies that the
left-hand side consists of the same distinct powers of $\alpha$, and the proof
follows from a careful comparison of the powers on each side. First of all, it
is clear that we must have $x_{i_{1}}=0$ for exactly one $x_{i_{1}}$, and
$q_{a_{i_{1}}}\alpha^{x_{i_{1}}}=1+\alpha^{c}+\ldots+\alpha^{c(a_{i_{1}}-1)}$.
Since $ca_{i_{1}}<cL$ by assumption, the right-hand side of (11) contains
$\alpha^{ca_{i_{1}}}$ and so we must have $x_{i_{2}}=ca_{i_{1}}$ for some
(unique) $x_{i_{2}}$. Similarly, the highest degree term of
$q_{a_{i_{1}}}\alpha^{x_{i_{1}}}+q_{a_{i_{2}}}\alpha^{x_{i_{2}}}$ is
$\alpha^{c(a_{i_{1}}+a_{i_{2}}-1)}$, and since $c(a_{i_{1}}+a_{i_{2}})<cL$, we
must have the next consecutive power of $\alpha^{c}$ on the left-hand side.
Hence, there must be $x_{i_{3}}=c(a_{i_{1}}+a_{i_{2}})$. Finally, the highest
power of
$q_{a_{i_{1}}}\alpha^{x_{i_{1}}}+q_{a_{i_{2}}}\alpha^{x_{i_{2}}}+q_{a_{i_{3}}}\alpha^{x_{i_{3}}}$
is $\alpha^{c(a_{i_{1}}+a_{i_{2}}+a_{i_{3}}-1)}$, which must be the last term
in the first block of consecutive powers of $\alpha^{c}$ (since for any
$a_{l}$ we have $cL<c(a_{i_{1}}+a_{i_{2}}+a_{i_{3}}+a_{l})$). This implies
that $c(a_{i_{1}}+a_{i_{2}}+a_{i_{3}})=cL$, and the next largest $x_{i}$ is
equal to $2cL$. It is clear that this process may be continued to show that
$S$ is a positive instance, and that $x_{1},\ldots,x_{3k}$ satisfies (12). ∎

######  Corollary 2.6.

For $\alpha\in{\overline{\mathbb{Q}}}\setminus\\{0,1\\}$, the Diophantine
problem for equations (6) is ${\mathbf{NP}}$-hard.

###### Proof.

If $\alpha\in{\overline{\mathbb{Q}}}\setminus\\{0,1\\}$ is not a root of
unity, Proposition 2.5 provides a polynomial-time (Karp) reduction from
$\operatorname{3PART}$ to the Diophantine problem for (6). The case where
$\alpha\in{\mathcal{U}}$ was proved in Proposition 2.2. ∎

##  3\. Complexity upper bound for a single equation

In this section, we prove that the Diophantine problem for single algebraic
equations with exponents is in ${\mathbf{NP}}$. The following lemma is
required to establish a polynomial time procedure for checking a candidate
solution. Note that the proof extends easily to the case of a system of
equations; however, for convenience we state it for a single equation.

######  Lemma 3.1.

Consider an equation $E$ of type (6). Let
${\overline{z}}=(z_{1},\ldots,z_{k})\in{\mathbb{Z}}^{k}$, and set

$\displaystyle M$ $\displaystyle=\max\\{1,|z_{1}|,\ldots,|z_{k}|\\},$
$\displaystyle{\mathcal{M}}(E,{\overline{z}})$
$\displaystyle=\max\\{\operatorname{{size}}(E),\log M\\}.$

Then there is an algorithm that checks whether $x_{i}=z_{i}$ is a solution of
$E$ in time polynomial in ${\mathcal{M}}(E,{\overline{z}})$.

###### Proof.

Let $d=\deg(\alpha)$, so that each $q_{i}$ is equal to
$\sum_{j=0}^{d-1}r_{ij}\alpha^{j}$ for some $r_{ij}\in{\mathbb{Q}}$.
Multiplying $E$ by the product of all denominators, which is less than
$2^{\operatorname{{size}}(E)}$, we can ensure that each
$r_{ij}\in{\mathbb{Z}}$. This can be done in time polynomial in
$\operatorname{{size}}(E)$, and the new equation $E^{\prime}$ satisfies
$\operatorname{{size}}(E^{\prime})=O(\operatorname{{size}}^{2}(E))$.

Set $\underline{m}=\min\\{z_{1},\ldots,z_{k}\\}$ and
$\overline{m}=\max\\{z_{1},\ldots,z_{k}\\}$, and let
$z_{i}^{\prime}=z_{i}-\underline{m}$ (so that each $z_{i}^{\prime}$ is non-
negative and $\min z_{i}^{\prime}=0$); note that
$z_{1}^{\prime},\ldots,z_{k}^{\prime}$ may be computed in time polynomial in
$\log M$. Define $f_{i}(x)=\sum_{j=0}^{d-1}r_{ij}x^{j}$ for $i=0,\dots,k$, and

$F(x)=f_{1}(x)x^{z_{1}^{\prime}}+\cdots+f_{k}(x)x^{z_{k}^{\prime}}-f_{0}(x)\
\in\ {\mathbb{Z}}[x].$

To compute the coefficients of $F(x)$, we must perform comparisons and
addition on $d(k+1)$ terms, with coefficients and exponents encoded as binary
numbers of length bounded by $\operatorname{{size}}(E)$ and $\log
d+\log(\overline{m}-\underline{m}+1)$, respectively. That can be done in time
polynomial in ${\mathcal{M}}(E,{\overline{z}})$, because $d,k$ are bounded by
$\operatorname{{size}}(E)$. In this way, we end up with the _sparse
representation_ of $F$, i.e., the list of pairs $(c_{n},n)$, where $c_{n}$ is
the coefficient of $x^{n}$ in $F(x)$ and $c_{n}\neq 0$, with $c_{n}$ and $n$
given in binary. Moreover, it is encoded in space that is polynomial in
${\mathcal{M}}(E,{\overline{z}})$.

By construction, $z_{1}^{\prime},\dots,z_{k}^{\prime}$ satisfy (6) if and only
if $\alpha$ is a zero of $F(x)$. By [9, Theorem 2.1], the problem to decide if
$F(\alpha)=0$ (where the input consists of $F(x)$ and the minimal polynomial
of $\alpha$, encoded as above) belongs to $\bf{TC}^{0}$. In particular, it is
polynomial-time decidable, so the result follows. ∎

Let $\alpha\in{\overline{\mathbb{Q}}}^{*}\setminus{\mathcal{U}}$, and let
$d=\deg(\alpha)$. Consider, instead of (6), the equation

(13) $q_{1}\alpha^{x_{1}}+\dots+q_{k}\alpha^{x_{k}}=0$

with coefficients $q_{1},\ldots,q_{k}\in{\mathbb{Z}}[\alpha]\setminus\\{0\\}$,
and each coefficient given as

$q_{i}=r_{i0}+r_{i1}\alpha+\cdots+r_{i(d-1)}\alpha^{d-1},\ \
r_{ij}\in{\mathbb{Z}}.$

We call (13) a _homogeneous_ equation with exponents. The Diophantine problem
for (13) is easily seen to be polynomial-time equivalent (in terms of
$\operatorname{{size}}(E)$) to the Diophantine problem for (6).

###  3.1. Block structure of a solution

Let $x_{1},\ldots,x_{k}\in{\mathbb{Z}}$ be a solution for (13). Denote the
vector of the solution $(x_{1},\ldots,x_{k})\in{\mathbb{Z}}^{k}$ by
${\overline{x}}$. A nonempty set $I\subseteq\\{1,\ldots,k\\}$ is called a
_block_ for ${\overline{x}}$ if the following conditions hold:

  * (B1)

$\sum_{i\in I}q_{i}\alpha^{x_{i}}=0$;

  * (B2)

$I$ does not have a nonempty proper subset satisfying (B1).

For a given solution ${\overline{x}}$, the set of indices $\\{1,\ldots,k\\}$
can be represented as a disjoint union $\bigsqcup_{j=1}^{m}I_{j}$ of blocks,
perhaps in more than one way. Such a collection
${\mathcal{I}}=\\{I_{1},\ldots,I_{m}\\}$ is called a _block structure_ for a
solution ${\overline{x}}$. For a block $I$, define

  * •

$\Delta_{I}=(\delta_{1},\ldots,\delta_{k})\in{\mathbb{Z}}^{k}$, where

$\delta_{i}=\begin{cases}1&\mbox{if }i\in I\\\ 0&\mbox{if }i\notin
I\end{cases},$

  * •

${\overline{x}}_{I}=\left\\{\,x_{i}\;\middle|\;i\in
I\,\right\\}\subseteq{\mathbb{Z}}$.

  * •

$\operatorname{{span}}_{I}({\overline{x}})=\max({\overline{x}}_{I})-\min({\overline{x}}_{I})$,
called the _span_ of $I$.

The next lemma follows immediately from the definition of $\Delta_{I}$.

######  Lemma 3.2.

If $\\{I_{1},\ldots,I_{m}\\}$ is a block structure for a solution
${\overline{x}}$ for (13), then

${\overline{x}}+b_{1}\Delta_{I_{1}}+\dots+b_{m}\Delta_{I_{m}}$

is a solution for (13) for any $b_{1},\ldots,b_{m}\in{\mathbb{Z}}$. ∎

###  3.2. Gap and maximum span of an equation

Consider an equation $E$ of type (13). Define $\operatorname{gap}(E)$ to be
the least $n\in{\mathbb{N}}$ such that for every solution
$x_{1},\dots,x_{k}\in{\mathbb{Z}}$ for (13) and for every partition
$\\{1,\dots,k\\}=S_{1}\sqcup S_{2}$ the following holds:

(14) $\min_{i\in S_{2}}x_{i}-\max_{i\in S_{1}}x_{i}>n\ \ \Rightarrow\ \
S_{1}\mbox{ and }S_{2}\mbox{ are unions of blocks.}$

If $E$ has no solutions, then set $\operatorname{gap}(E)=0$. The following
lemma shows that $\operatorname{gap}(E)$ is well-defined.

######  Lemma 3.3.

For equations of type (13),
$\operatorname{gap}(E)=O(\operatorname{{size}}^{3}(E))$. If the base $\alpha$
is fixed, or if $\alpha$ is restricted to rational values, then
$\operatorname{gap}(E)=O(\operatorname{{size}}(E))$.

###### Proof.

If $E$ has no solutions, then $\operatorname{gap}(E)=0$ and the statement
holds. Let ${\overline{x}}=(x_{1},\dots,x_{k})\in{\mathbb{Z}}^{k}$ be a
solution for (13) and ${\mathcal{I}}$ a block structure for ${\overline{x}}$.
As in the proof of Lemma 3.1, construct the polynomial
$F(x)\in{\mathbb{Z}}[x]$ corresponding to ${\overline{x}}$. The number of
monomials in $F$ is not greater than $dk$ and

$\operatorname{height}(F)\leq\sum_{i=1}^{k}\sum_{j=0}^{d-1}|r_{ij}|,$

which gives the following upper bound on the “gap bound” (i.e. the right-hand
side of inequality (10)) of Lemma 2.4 for $F(x)$:

$\displaystyle\tfrac{d\ln^{3}(3d)}{2}\bigg{(}\ln(kd-1)+\ln\bigg{(}\sum_{i=1}^{k}\sum_{j=0}^{d-1}|r_{ij}|\bigg{)}\bigg{)}$
$\displaystyle\leq$
$\displaystyle\tfrac{d\ln^{3}(3d)}{2}\bigg{(}\ln(k)+\ln(d)+\ln\bigg{(}\prod_{i=1}^{k}\prod_{j=0}^{d-1}(|r_{ij}|+1)\bigg{)}\bigg{)}$
$\displaystyle\leq$
$\displaystyle\underbrace{\tfrac{d\ln^{3}(3d)}{2}}_{O(\operatorname{{size}}^{2}(E))}\underbrace{\bigg{(}\ln(k)+\ln(d)+\sum_{i=1}^{k}\sum_{j=0}^{d-1}\ln(|r_{ij}|+1)\bigg{)}}_{O(\operatorname{{size}}(E))}.$

By construction, each monomial in $F(x)$ is of the form $cx^{x_{i}+j}$, where
$0\leq j<d$. Hence, for a partition $\\{1,\dots,k\\}=S_{1}\sqcup S_{2}$
satisfying

(15) $\min_{i\in S_{2}}x_{i}-\max_{i\in
S_{1}}x_{i}>d+\tfrac{d\ln^{3}(3d)}{2}\bigg{(}\ln(k)+\ln(d)+\sum_{i=1}^{k}\sum_{j=0}^{d-1}\ln(|r_{ij}|+1)\bigg{)},$

we may write $F(x)$ as a sum $F_{1}(x)+F_{2}(x)$ which satisfies the
assumptions of Lemma 2.4, where $F_{1}$ contains the terms of degree less than
$d+\max_{i\in S_{1}}x_{i}$ and $F_{2}$ contains the terms of degree at least
$\min_{i\in S_{2}}x_{i}$. Therefore, Lemma 2.4 implies that
$F_{1}(\alpha)=F_{2}(\alpha)=0$, so each block in ${\mathcal{I}}$ belongs
either to $S_{1}$ or to $S_{2}$. The right-hand side of (15) is
$O(\operatorname{{size}}^{3}(E))$, which completes the proof in the general
case (where $\alpha$ is part of the input). In the case where $\alpha$ (hence,
$d$) is fixed, the right-hand side of (15) is $O(\operatorname{{size}}(E))$.
If $\alpha\in{\mathbb{Q}}$, then $\frac{1}{\ln 2}$ replaces
$\frac{d\ln^{3}(3d)}{2}$ in (15), so we obtain $O(\operatorname{{size}}(E))$
in this case as well. ∎

For an equation $E$ of type (13) define

$\operatorname{{max\;\\!span}}(E)=\max\left\\{\,\operatorname{{span}}_{I}({\overline{x}})\;\middle|\;I\mbox{
is a block in a solution ${\overline{x}}$ for $E$}\,\right\\},$

called the _maximum span_ of $E$. If $E$ has no solutions, then
$\operatorname{{max\;\\!span}}(E)=0$. The following lemma shows that the
maximum span is well-defined.

######  Lemma 3.4.

$\operatorname{{max\;\\!span}}(E)=O(\operatorname{{size}}^{4}(E))$ for every
equation $E$ of type (13). If the base $\alpha$ is fixed, then
$\operatorname{{max\;\\!span}}(E)=O(\operatorname{{size}}^{2}(E)),$ and if
$\alpha$ is restricted to rational values then
$\operatorname{{max\;\\!span}}(E)=O(\operatorname{{size}}(E)).$

###### Proof.

If $I$ is a block in a solution ${\overline{x}}=(x_{1},\ldots,x_{k})$ of an
equation $E$ of type (13), then it is clear from the definitions that
$|x_{i_{1}}-x_{i_{2}}|\leq\operatorname{gap}(E)$ for any $i_{1},i_{2}\in I$.
Thus, we obtain

(16)
$\operatorname{{span}}_{I}({\overline{x}})\leq|I|\operatorname{gap}(E)\leq(k-1)\operatorname{gap}(E).$

Therefore,

$\operatorname{{max\;\\!span}}(E)\leq(k-1)\operatorname{gap}(E),$

whence the first and second statements follow immediately from Lemma 3.3
(together with the fact that $k\leq\operatorname{{size}}(E)$). For the case
where $\alpha$ is restricted to rational values, we defer the proof to Section
3.4. ∎

###  3.3. An ${\mathbf{NP}}$-certificate for (13)

In this section, we establish a polynomial upper bound on a minimal solution
of (13), and demonstrate that such a solution may be checked in polynomial
time.

######  Theorem 3.5.

If an equation $E$ of type (13) has a solution, then there is a solution
$(x_{1},\ldots,x_{k})\in{\mathbb{Z}}^{k}$ satisfying

$0\leq x_{1},\ldots,x_{k}\leq\operatorname{{max\;\\!span}}(E).$

###### Proof.

Consider any solution ${\overline{x}}=(x_{1},\ldots,x_{k})\in{\mathbb{Z}}^{k}$
and a block structure ${\mathcal{I}}=\\{I_{1},\ldots,I_{m}\\}$ for
${\overline{x}}$. By Lemma 3.2

$(x_{1}^{\prime},\ldots,x_{k}^{\prime})={\overline{x}}-\sum_{j=1}^{m}\min({\overline{x}}_{I_{j}})\cdot\Delta_{I_{j}}$

is also a solution. By construction, it satisfies $0\leq
x_{1}^{\prime},\ldots,x_{k}^{\prime}\leq\operatorname{{max\;\\!span}}(E)$, as
claimed. ∎

######  Corollary 3.6.

The Diophantine problem for equations (13) belongs to ${\mathbf{NP}}$.

###### Proof.

By Lemma 3.1, a solution for (13) satisfying the conclusion of Theorem 3.5
constitutes an ${\mathbf{NP}}$-certificate. ∎

######  Corollary 3.7.

The (uniform or fixed base) Diophantine problem for (13) is
${\mathbf{NP}}$-complete for
$\alpha\in{\overline{\mathbb{Q}}}\setminus\\{0,1\\}$.

###### Proof.

This follows from Proposition 2.2 and Corollaries 2.6 and 3.6. ∎

###  3.4. An improved bound on maximum span for $\alpha\in{\mathbb{Q}}$

It turns out that in the special case where $\alpha\in{\mathbb{Q}}$, one can
obtain the following improved bound on $\operatorname{{max\;\\!span}}(E)$.

######  Theorem 3.8.

Let $E$ be an equation of type (13), such that
$\alpha\in{\mathbb{Q}}\setminus\\{-1,0,1\\}$. Then

  1. (a)

$\operatorname{{max\;\\!span}}(E)\leq\left|{}\log_{|\alpha|}(|q_{i}|+1)\right|$

  2. (b)

$\operatorname{{max\;\\!span}}(E)=O(\operatorname{{size}}(E))$ for fixed
$\alpha$.

This is very useful in certain applications in which the base $\alpha$ is
fixed (e.g., the authors make use of this result in [10]). Note that statement
(b) of Theorem 3.8 is an immediate consequence of (a), which we prove in the
remainder of this section. However, we do not refer to this material anywhere
else in the present work. For convenience, we sometimes assume that a solution
$x_{1},\ldots,x_{k}$ has a block structure consisting of a single block, and
that $x_{1}\geq x_{2}\geq\cdots\geq x_{k}=0$. The following technical lemma is
required.

######  Lemma 3.9.

Let $k\geq 2$, $\alpha>1$, and
$q_{1},\ldots,q_{k}\in{\mathbb{Z}}\setminus\\{0\\}$. The maximum value of the
sum $\delta_{1}+\cdots+\delta_{k-1}$, for
$\delta_{1},\ldots,\delta_{k-1}\in{\mathbb{R}}$ constrained by

(17)
$\resizebox{0.91}{!}{\begin{array}[]{l}0\leq\delta_{i}\leq\log_{\alpha}{\left(|q_{i+1}|+|q_{i+2}|\alpha^{-\delta_{i+1}}+\cdots+|q_{k}|\alpha^{-(\delta_{i+1}+\cdots+\delta_{k-1})}\right)}\
\mbox{ for }i=1,\ldots,k-2,\\\
0\leq\delta_{k-1}\leq\log_{\alpha}(|q_{k}|),\end{array}}$

is attained at
$\delta_{1}=\log_{\alpha}(|q_{2}|+1),\ldots,\delta_{k-2}=\log_{\alpha}(|q_{k-1}|+1),\delta_{k-1}=\log_{\alpha}(|q_{k}|)$.

###### Proof.

Since (17) defines a non-empty compact set, the sum attains the maximum value
at some point $(\delta_{1},\ldots,\delta_{k-1})$. Fix
$\delta_{3},\ldots,\delta_{k-1}$, define

$q^{\ast}=|q_{3}|+|q_{4}|\alpha^{-\delta_{3}}+\ldots+|q_{k}|\alpha^{-(\delta_{3}+\cdots+\delta_{k-1})},$

and notice that $\delta_{1},\delta_{2}$ must maximize $\delta_{1}+\delta_{2}$
while satisfying

$\displaystyle 0\leq\delta_{1}\leq$
$\displaystyle\log_{\alpha}{\left(|q_{2}|+|q^{\ast}|\alpha^{-\delta_{2}}\right)},$
$\displaystyle 0\leq\delta_{2}\leq$
$\displaystyle\log_{\alpha}{\left(|q^{\ast}|\right)}.$

Obviously,
$\delta_{1}=\log_{\alpha}{\left(|q_{2}|+|q^{\ast}|\alpha^{-\delta_{2}}\right)}$.
Thus, the value of $\delta_{2}$ must maximize the value of the function

$\displaystyle
f(\delta_{2})=\delta_{2}+\log_{\alpha}{\left(|q_{2}|+|q^{\ast}|\alpha^{-\delta_{2}}\right)}$

for $\delta_{2}\in[0,\log_{\alpha}(|q^{\ast}|)]$. It is easily seen that $f$
is monotonically increasing, so the maximum is attained at
$\delta_{2}=\log_{\alpha}(|q^{\ast}|)$, and
$\delta_{1}=\log_{\alpha}{\left(|q_{2}|+1\right)}$.

Once the optimal value of $\delta_{1}$ is found, we can eliminate $\delta_{1}$
from the sum and remove the bounds on $\delta_{1}$ from (17) (notice that
$\delta_{1}$ is not involved in the other bounds). That produces an
optimization problem of the same type with $k-1$ variables. Hence, the result
follows by induction on $k$. ∎

######  Lemma 3.10.

Suppose that $1<\alpha\in{\mathbb{Q}}$ and
${\overline{x}}=(x_{1},\ldots,x_{k})$ is a solution for an equation $E$ of
type (13) with a single block $I=\\{1,\ldots,k\\}$ satisfying $x_{1}\geq
x_{2}\geq\dots\geq x_{k}=0$. Define $\delta_{i}=x_{i}-x_{i+1}$ for
$i=1,\ldots,k-1$. Then we have

  * (a)

$0\leq\delta_{i}\leq\log_{\alpha}{\left(|q_{i+1}|+|q_{i+2}|\alpha^{-\delta_{i+1}}+\cdots+|q_{k}|\alpha^{-(\delta_{i+1}+\cdots+\delta_{k-1})}\right)}$

  * (b)

$\operatorname{{span}}_{I}({\overline{x}})=x_{1}\leq\sum_{i=1}^{k}\log_{\alpha}(|q_{i}|+1)$.

###### Proof.

Let $\alpha=\tfrac{c}{d}$, where $\gcd(c,d)=1$, $c\geq 2$ and $c>d$.
Multiplying (13) by $d^{x_{1}}$ we get

(18)
$q_{1}c^{x_{1}}+q_{2}c^{x_{2}}d^{x_{1}-x_{2}}+\cdots+q_{k-1}c^{x_{k-1}}d^{x_{1}-x_{k-1}}+q_{k}c^{x_{k}}d^{x_{1}-x_{k}}=0.$

Taking (18) modulo $c^{x_{k-1}}$ we get

$\displaystyle q_{k}c^{x_{k}}d^{x_{1}-x_{k}}\equiv 0\bmod c^{x_{k-1}}$
$\displaystyle\ \ \Rightarrow\ \ c^{x_{k-1}-x_{k}}\mid q_{k}$ $\displaystyle\
\ \Rightarrow\ \ \delta_{k-1}=x_{k-1}-x_{k}\leq\log_{c}(|q_{k}|)$
$\displaystyle\ \ \Rightarrow\ \ \delta_{k-1}\leq\log_{\alpha}(|q_{k}|),$

which proves (a) for $i=k-1$. Writing (18) as

(19)
$q_{1}c^{x_{1}}+q_{2}c^{x_{2}}d^{x_{1}-x_{2}}+\cdots+\underbrace{{\left(q_{k-1}+q_{k}{\left(\tfrac{d}{c}\right)}^{\delta_{k-1}}\right)}}_{\
\ \ {}^{\parallel}_{q_{k-1}^{\prime}}}c^{x_{k-1}}d^{x_{1}-x_{k-1}}=0,$

we obtain an expression of the same form as (18), with one fewer term and a
new rightmost coefficient $q_{k-1}^{\prime}\in{\mathbb{Z}}$ that satisfies the
following:

  * •

$q_{k-1}^{\prime}=0\ \ \Leftrightarrow\ \ k=2$ (because, by our assumption,
${\overline{x}}$ has a single block);

  * •

$|q_{k-1}^{\prime}|\leq|q_{k-1}|+|q_{k}|$.

Assuming $k>2$, we may apply the same argument to (19). That is, take (19)
modulo $c^{x_{k-2}}$, and follow the same steps as above to obtain
$\delta_{k-2}\leq\log_{\alpha}(|q_{k-1}^{\prime}|)$, proving (a) for $i=k-2$.
This process can be continued to yield, at each iteration, a new rightmost
(non-trivial unless $i=1$) coefficient

$q_{i}^{\prime}=q_{i}+q_{i+1}^{\prime}\alpha^{-\delta_{i}}=q_{i}+q_{i+1}\alpha^{-\delta_{i}}+\cdots+q_{k}\alpha^{-(\delta_{i}+\cdots+\delta_{k-1})}$

satisfying (a) for each $i=1,\ldots,k-1$.

To prove (b), notice that $x_{1}$ can be expressed as

$x_{1}=\delta_{1}+\dots+\delta_{k-1}$

and by (a) each $\delta_{i}$ satisfies the constraints of Lemma 3.9. Hence, it
follows from Lemma 3.9 that $x_{1}\leq\sum_{i=1}^{k}\log_{\alpha}(|q_{i}|+1)$.
∎

Lemma 3.10 was proved under the assumption that $\alpha>1$. Below we show that
it holds with minor modifications for any
$\alpha\in{\mathbb{Q}}\setminus\\{-1,0,1\\}$.

######  Proposition 3.11.

Suppose that $\alpha\in{\mathbb{Q}}\setminus\\{-1,0,1\\}$ and
${\overline{x}}=(x_{1},\ldots,x_{k})$ is a solution for an equation $E$ of
type (13) with a single block $I=\\{1,\ldots,k\\}$ satisfying $x_{1}\geq
x_{2}\geq\dots\geq x_{k}=0$. Define $\delta_{i}=x_{i}-x_{i+1}$ for
$i=1,\ldots,k-1$. Then we have

$\operatorname{{span}}_{I}({\overline{x}})=x_{1}\leq\sum_{i=1}^{k}\left|{}\log_{|\alpha|}(|q_{i}|+1)\right|.$

###### Proof.

We consider four cases.

######  Case 1:

Suppose that $\alpha>1$. Then the statement follows from Lemma 3.10.

######  Case 2:

The case when $0<\alpha<1$ is reduced to Case 1 by replacing $x_{i}$ with
$-x_{i}$ and $\alpha$ with $1/\alpha$. This transformation changes the order
of $x_{i}$’s and $\delta_{i}$’s, which also modifies the inequalities in item
(a) of Lemma 3.10 in the following way:

$\delta_{1}\leq\log_{1/\alpha}(|q_{1}|),\ \
\delta_{2}\leq\log_{1/\alpha}(|q_{2}|+|q_{1}|(\tfrac{1}{\alpha})^{-\delta_{1}}),\
\ \mbox{etc.}$

Since the obtained inequalities are of the same type, Lemma 3.9 remains
applicable and gives the claimed bound

$x_{1}\leq\sum_{i=1}^{k}\log_{1/\alpha}(|q_{i}|+1)=\sum_{i=1}^{k}\left|{}\log_{\alpha}(|q_{i}|+1)\right|.$

######  Case 3:

Suppose that $\alpha<-1$. It is easy to see that Lemma 3.10 holds in that case
with minor modifications (with $\alpha$ replaced with $|\alpha|$).

######  Case 4:

The case when $-1<\alpha<0$ is reduced to Case 3 by replacing $x_{i}$ with
$-x_{i}$ and $\alpha$ with $1/\alpha$. ∎

Theorem 3.8 now follows from Proposition 3.11.

##  4\. Complexity upper bound for a system of homogeneous equations

Let
$\alpha_{1},\ldots,\alpha_{s}\in{\overline{\mathbb{Q}}}^{*}\setminus{\mathcal{U}}$
and $d_{i}=\deg(\alpha_{i})$. Consider a system of equations

(20)
$\left\\{\begin{array}[]{cl}q_{11}\alpha_{1}^{x_{1}}+\dots+q_{1k}\alpha_{1}^{x_{k}}&=0\\\
\vdots&\\\ q_{s1}\alpha_{s}^{x_{1}}+\dots+q_{sk}\alpha_{s}^{x_{k}}&=0\\\
\end{array}\right.$

with coefficients $q_{ij}\in{\mathbb{Z}}[\alpha_{i}]$ and each coefficient
given as
$q_{ij}=r_{ij}^{0}+r_{ij}^{1}\alpha_{i}+\cdots+r_{ij}^{d_{i}-1}\alpha^{d_{i}-1}$.
Let us also require that at least one of $q_{1j},q_{2j},\dots,q_{sj}$ is
nonzero for each $j$. Let
${\overline{x}}=(x_{1},\ldots,x_{k})\in{\mathbb{Z}}^{k}$ be a solution for
(20). A nonempty $J\subseteq\\{1,\ldots,k\\}$ is called a _cluster_ for the
solution ${\overline{x}}$ if the following conditions hold:

  * (C1)

$\sum_{j\in J}q_{ij}\alpha_{i}^{x_{j}}=0$ for every $i=1,\ldots,s$;

  * (C2)

$J$ does not have a nonempty proper subset $J$ satisfying (C1).

The set of indices $\\{1,\ldots,k\\}$ can be represented as a union of
disjoint clusters, perhaps in more than one way; a choice
${\mathcal{J}}=\\{J_{1},\ldots,J_{m}\\}$ of one such union is called a
_cluster structure_ for a solution ${\overline{x}}$. For a cluster $J$, we
define ${\overline{x}}_{J}$, $\operatorname{{span}}_{J}({\overline{x}})$ and
$\Delta_{J}$ analogously to the case of a block. The next lemma follows
immediately from the definitions.

######  Lemma 4.1.

If ${\overline{x}}$ is a solution for (20) with cluster structure
$J_{1},\ldots,J_{m}$, then

${\overline{x}}+\beta_{1}\Delta_{J_{1}}+\dots+\beta_{m}\Delta_{J_{m}}$

is a solution for (20) with the same cluster structure for any
$\beta_{1},\ldots,\beta_{m}\in{\mathbb{Z}}$. ∎

###  4.1. Max span of a system

For a system $E$ of type (20), the definition of the maximum span is extended
in the natural way, as follows:

$\operatorname{{max\;\\!span}}(E)=\max\left\\{\,\operatorname{{span}}_{J}({\overline{x}})\;\middle|\;J\mbox{
is a cluster in a solution ${\overline{x}}$ for $E$}\,\right\\}.$

If $E$ has no solutions, then $\operatorname{{max\;\\!span}}(E)=0$. We obtain
an upper bound on $\operatorname{{max\;\\!span}}(E)$ below.

A collection $A_{1},\ldots,A_{m}$ (where $m\geq 2$) of finite nonempty subsets
of ${\mathbb{Z}}$ is _non-separable_ if the union of closed intervals

$\bigcup_{i=1}^{m}\ [\min(A_{i}),\max(A_{i})]$

is an interval. Otherwise it is separable. The following lemma follows easily
from this definition.

######  Lemma 4.2.

If finite nonempty subsets $A_{1},\ldots,A_{m}\subseteq{\mathbb{Z}}$ are non-
separable, then the following inequality holds:

$\max\big{(}\bigcup_{i=1}^{m}A_{i}\big{)}-\min\big{(}\bigcup_{i=1}^{m}A_{i}\big{)}\
\leq\ \sum_{i=1}^{m}\big{(}\max(A_{i})-\min(A_{i})\big{)}.$

Let ${\overline{x}}$ be a solution for (20) and ${\mathcal{J}}$ a cluster
structure for ${\overline{x}}$. Then ${\overline{x}}$ is a solution for each
individual equation in (20). Hence, each equation in (20) has a block
structure ${\mathcal{I}}_{i}=\\{I_{i1},\ldots,I_{i\,m_{i}}\\}$ for
${\overline{x}}$. We say that ${\mathcal{I}}_{1},\ldots,{\mathcal{I}}_{s}$ are
_compatible_ with ${\mathcal{J}}$ if for any cluster $J\in{\mathcal{J}}$ and
any block $I_{ij}\in{\mathcal{I}}_{i}$ we have

$I_{ij}\subseteq J\mbox{ or }I_{ij}\cap J=\emptyset.$

For any cluster structure ${\mathcal{J}}$, (C1) obviously implies the
existence of a compatible block structure ${\mathcal{I}}_{i}$ for each
individual equation in (20), and the identity

(21) $J=\bigcup_{I_{ij}\subseteq J}I_{ij}$

holds for every $J\in{\mathcal{J}}$ because every index in $\\{1,\ldots,k\\}$
belongs to at least one block $I_{ij}$ (since we assume that there is at least
one nonzero $q_{ij}$ corresponding to each $x_{i}$).

######  Lemma 4.3.

If ${\mathcal{J}}$ and ${\mathcal{I}}_{1},\ldots,{\mathcal{I}}_{s}$ are
compatible, then for every $J\in{\mathcal{J}}$, the collection of sets
$\left\\{\,{\overline{x}}_{I_{ij}}\;\middle|\;I_{ij}\subseteq J\,\right\\}$ is
non-separable.

###### Proof.

Separability contradicts the property (C2) of $J$. ∎

######  Proposition 4.4.

Let $E$ be a system of type (20), and let $E_{i}$ denote the $i$th equation in
$E$. Then we have

$\operatorname{{max\;\\!span}}(E)\leq sk\max_{1\leq i\leq
s}(\operatorname{{max\;\\!span}}(E_{i})).$

###### Proof.

Let ${\mathcal{J}}$ be a cluster structure for a solution ${\overline{x}}$ of
$E$, and let $J\in{\mathcal{J}}$. We have

$\displaystyle\max({\overline{x}}_{J})-\min({\overline{x}}_{J})$
$\displaystyle=\max\Big{(}\bigcup_{I_{ij}\subseteq
J}{\overline{x}}_{I_{ij}}\Big{)}-\min\Big{(}\bigcup_{I_{ij}\subseteq
J}{\overline{x}}_{I_{ij}}\Big{)}$ (the identity (21))
$\displaystyle\leq\sum_{I_{ij}\subseteq
J}\operatorname{{span}}_{I_{ij}}({\overline{x}})$ $\displaystyle\mbox{(Lemmas
\ref{le:non-separable-length} and \ref{le:non-separable-blocks}})$
$\displaystyle\leq\sum_{I_{ij}\subseteq
J}\operatorname{{max\;\\!span}}(E_{i})$ $\displaystyle\leq sk\max_{1\leq i\leq
s}(\operatorname{{max\;\\!span}}(E_{i})).$

∎

######  Corollary 4.5.

For systems $E$ of type (20), $\operatorname{{max\;\\!span}}(E)$ is bounded by
a polynomial in $\operatorname{{size}}(E)$.

###### Proof.

Follows immediately from Proposition 4.4 and Lemma 3.4. ∎

###  4.2. An ${\mathbf{NP}}$-certificate for (20)

######  Theorem 4.6.

If a system $E$ of type (20) has a solution, then it has a solution
$x_{1},\ldots,x_{k}\in{\mathbb{Z}}$ satisfying

(22) $0\ \leq\ x_{1},\ldots,x_{k}\ \leq\operatorname{{max\;\\!span}}(E).$

###### Proof.

Same as the proof of Theorem 3.5, using Lemma 4.1 instead of Lemma 3.2. ∎

Finally, from Lemma 3.1, Corollary 4.5 and Theorem 22, we obtain the
following.

######  Corollary 4.7.

The Diophantine problem for systems of type (20) belongs to ${\mathbf{NP}}$.

##  5\. Complexity upper bound for general systems of equations

###  5.1. Non-homogeneous equations

Let
$\alpha_{1},\ldots,\alpha_{s}\in{\overline{\mathbb{Q}}}^{*}\setminus{\mathcal{U}}$,
and consider a system of non-homogeneous equations

(23)
$\left\\{\begin{array}[]{cl}q_{11}\alpha_{1}^{x_{1}}+\dots+q_{1k}\alpha_{1}^{x_{k}}&=q_{10},\\\
\vdots&\\\ q_{s1}\alpha_{s}^{x_{1}}+\dots+q_{sk}\alpha_{s}^{x_{k}}&=q_{s0},\\\
\end{array}\right.$

with $q_{ij}\in{\mathbb{Z}}[\alpha_{i}]$. It is easy to see that a system $E$
of this form has a solution if and only if the homogeneous system $E^{\prime}$

(24)
$\left\\{\begin{array}[]{cl}q_{11}\alpha_{1}^{x_{1}}+\dots+q_{1k}\alpha_{1}^{x_{k}}-q_{10}\alpha_{1}^{x_{0}}&=0\\\
\vdots&\\\
q_{s1}\alpha_{s}^{x_{1}}+\dots+q_{sk}\alpha_{s}^{x_{k}}-q_{s0}\alpha_{s}^{x_{0}}&=0\\\
\end{array}\right.$

has a solution. Hence, an ${\mathbf{NP}}$-certificate for $E^{\prime}$ can be
used as an ${\mathbf{NP}}$-certificate for $E$. Since
$\operatorname{{size}}(E^{\prime})=\operatorname{{size}}(E)$, it follows from
Corollary 4.7 that the Diophantine problem for non-homogeneous systems of type
(23) belongs to ${\mathbf{NP}}$.

###  5.2. Systems of equations with roots of unity

Finally, we consider the most general systems of equations with exponents,
where $\alpha_{1},\ldots,\alpha_{s}$ are allowed to be roots of unity. As
above, the non-homogeneous case can be reduced to the homogeneous one, so in
fact we need only consider homogeneous systems. Recall that there is a
polynomial-time algorithm (see [1]) that takes as input the minimal polynomial
of $\alpha_{i}$ and determines whether $\alpha_{i}$ is a root of unity. If it
is a root of unity, this algorithm also provides the order of $\alpha_{i}$ in
the group ${\mathcal{U}}$. Hence, we consider systems of the form

(25)
$\left\\{\begin{array}[]{cl}q_{11}\alpha_{1}^{x_{1}}+\dots+q_{1k}\alpha_{1}^{x_{k}}&=0\\\
\vdots&\\\ q_{t1}\alpha_{t}^{x_{1}}+\dots+q_{tk}\alpha_{t}^{x_{k}}&=0\\\
\vdots&\\\ q_{s1}\alpha_{s}^{x_{1}}+\dots+q_{sk}\alpha_{s}^{x_{k}}&=0\\\
\end{array}\right.$

with $\alpha_{1},\ldots,\alpha_{t}\not\in{\mathcal{U}}$ and
$\alpha_{t+1},\ldots,\alpha_{s}\in{\mathcal{U}}$ for some
$t\in\\{0,\ldots,s\\}$, and $q_{ij}\in{\mathbb{Z}}[\alpha_{i}]$. We may assume
that $n_{i}$ is the order of $\alpha_{i}$ in ${\mathcal{U}}$ for $t<i\leq s$.
From the fact that $\deg(\alpha_{i})=\varphi(n_{i})$ (where $\varphi$ denotes
Euler’s totient function), and using the well-known lower bound
$\varphi(n)\geq\sqrt{\frac{n}{2}}$, we obtain the following bound on $n_{i}$.

(26) $n_{i}<2(\deg(\alpha_{i}))^{2}<2\operatorname{{size}}^{2}(E).$

We also assume that every unknown $x_{i}$ is non-trivially involved in $E$,
i.e. for every $j\in\\{1,\ldots,k\\}$ there exists $i\in\\{1,\ldots,s\\}$ such
that $q_{ij}\neq 0$.

First, assume that $E$ is an equation of type (25) in which all of the bases
are roots of unity, and let $N=\operatorname{{lcm}}(n_{1},\ldots,n_{s})$.
Clearly, if ${\overline{x}}=(x_{1},\ldots,x_{k})$ is a solution to $E$, and
$x_{i}\equiv x_{i}^{\prime}\bmod N$, then
${\overline{x}}^{\prime}=(x_{1}^{\prime},\ldots,x_{k}^{\prime})$ is another
solution to $E$. Hence, if $E$ has a solution, then it has a solution
${\overline{x}}=(x_{1},\ldots,x_{k})$ such that $0\leq x_{1},\ldots,x_{k}<N$.
From (26) we have

(27) $N<2^{k}\operatorname{{size}}^{2k}(E),$

so that

(28) $\log
N=O(2k\log(\operatorname{{size}}(E)))=O(\operatorname{{size}}^{2}(E)).$

By Lemma 3.1, ${\overline{x}}$ is an ${\mathbf{NP}}$-certificate for
decidability of $E$.

Now suppose that at least one, but not all, of the bases are roots of unity,
and consider the subsystem $E_{\leq t}$ of the first $t$ equations (i.e. the
equations where $\alpha_{i}\not\in{\mathcal{U}}$). Let
${\overline{x}}=(x_{1},\ldots,x_{k})$ be a solution to $E$. In particular,
${\overline{x}}$ is a solution to $E_{\leq t}$, and we may choose a cluster
structure ${\mathcal{J}}=\\{J_{1},\ldots,J_{m}\\}$ corresponding to
${\overline{x}}$ and $E_{\leq t}$ (i.e. ${\mathcal{J}}$ is not necessarily a
cluster structure with respect to $E$). The following variation on Lemma 4.1
follows easily from the preceding discussion.

######  Lemma 5.1.

Let $E$ be a system of type (25) as described above (i.e. where $1\leq t<s$),
and let ${\overline{x}}$ be a solution of $E$. Let $\\{J_{1},\ldots,J_{m}\\}$
be a cluster structure corresponding to ${\overline{x}}$ and $E_{\leq t}$, and
let $N=\operatorname{{lcm}}(n_{t+1},\ldots,n_{s})$. Then

${\overline{x}}+N\beta_{1}\Delta_{J_{1}}+\dots+N\beta_{m}\Delta_{J_{m}}$

is a solution for $E$ with the same cluster structure for any
$\beta_{1},\ldots,\beta_{m}\in{\mathbb{Z}}$.

######  Theorem 5.2.

If a system $E$ of type (25) has a solution, then it has a solution
${\overline{x}}$ (with the same cluster structure) satisfying

(29) $0\leq x_{1},\ldots,x_{k}<N+\operatorname{{max\;\\!span}}(E_{\leq t})$

where $N=\operatorname{{lcm}}(n_{t+1},\ldots,n_{s})$.

###### Proof.

Suppose that ${\overline{y}}$ is a solution to $E$, and set $\beta_{i}$ so
that $0\leq\min({\overline{y}}_{J_{i}})+N\beta_{i}<N$ (i.e. reduce
$\min({\overline{y}}_{J_{i}})$ modulo $N$). Then it follows from the
definition of $\operatorname{{max\;\\!span}}(E_{\leq t})$ that

${\overline{x}}={\overline{y}}+N\beta_{1}\Delta_{J_{1}}+\dots+N\beta_{m}\Delta_{J_{m}}$

satisfies (29), and by Lemma 5.1 it is also a solution to $E$. ∎

By (28), Corollary 4.5 and Lemma 3.1, a solution $x_{1},\ldots,x_{k}$ for (25)
satisfying (29) is an ${\mathbf{NP}}$-certificate; thus, we have proved the
following.

######  Corollary 5.3.

The Diophantine problem for systems (25) belongs to ${\mathbf{NP}}$.

Finally, from Corollary 2.6 we obtain

######  Corollary 5.4.

The Diophantine problem for systems (25) is ${\mathbf{NP}}$-complete.

##  6\. Structure of the solution set

We say that a set $S\subseteq{\mathbb{Z}}^{k}$ is _semilinear_ if $S$ is a
finite union of cosets, i.e.,

$S=\bigcup_{i=1}^{n}({\overline{\delta}}_{i}+A_{i}),\ \ \mbox{ for some
${\overline{\delta}}_{1},\ldots,{\overline{\delta}}_{n}\in{\mathbb{Z}}^{k}$
and $A_{1},\ldots,A_{n}\leq{\mathbb{Z}}^{k}$.}$

Let ${\overline{x}}=(x_{1},\ldots,x_{k})$ be a solution for a system $E$ of
type (25). Following Section 5.2, let ${\mathcal{J}}=\\{J_{1},\ldots,J_{m}\\}$
be a cluster structure corresponding to ${\overline{x}}$ and $E_{\leq t}$, and
let us define

$N_{E}=\begin{cases}1&\mbox{ if }t=s\\\
\operatorname{{lcm}}(n_{t+1},\ldots,n_{s})&\mbox{ otherwise}.\end{cases}$

The set ${\mathcal{J}}$ defines the tuples
$\Delta_{J_{1}},\ldots,\Delta_{J_{m}}\in\\{0,1\\}^{k}$, so by Lemma 5.1 the
pair $({\overline{x}},{\mathcal{J}})$ defines the following set of solutions
for $E$

$S_{{\overline{x}},{\mathcal{J}}}=\left\\{\,{\overline{x}}+N_{E}\beta_{1}\Delta_{J_{1}}+\dots+N_{E}\beta_{m}\Delta_{J_{m}}\;\middle|\;\beta_{1},\ldots,\beta_{m}\in{\mathbb{Z}}\,\right\\}\
\subseteq\ {\mathbb{Z}}^{k}$

(note that $S_{{\overline{x}},{\mathcal{J}}}$ is a coset of
${\mathbb{Z}}^{k}$). Define ${\mathcal{T}}(E)$ to be the set of all pairs
$({\overline{x}},{\mathcal{J}})$ such that

  * •

${\overline{x}}$ is a solution for $E$;

  * •

${\mathcal{J}}$ is a cluster structure for ${\overline{x}}$ and $E_{\leq t}$;

  * •

(boundedness) ${\overline{x}}=(x_{1},\ldots,x_{k})$ satisfies (29).

By construction, ${\mathcal{T}}(E)$ is finite.

######  Proposition 6.1 (Completeness).

The set of all solutions of a system $E$ of type (25) is equal to

$S(E)=\bigcup_{({\overline{x}},{\mathcal{J}})\in{\mathcal{T}}(E)}S_{{\overline{x}},{\mathcal{J}}}.$

###### Proof.

By Lemma 5.1,
$\bigcup_{({\overline{x}},{\mathcal{J}})\in{\mathcal{T}}}S_{{\overline{x}},{\mathcal{J}}}$
is a set of solutions for $E$. Conversely, if ${\overline{y}}$ is a solution
for $E$ and ${\mathcal{J}}$ is a cluster structure for ${\overline{x}}$ and
$E_{\leq t}$, then (as in the proof of Theorem 5.2) the set
$S_{{\overline{y}},{\mathcal{J}}}$ contains a solution ${\overline{x}}$
satisfying (29) with the same cluster structure ${\mathcal{J}}$. Hence,
$({\overline{x}},{\mathcal{J}})\in{\mathcal{T}}(E)$ and ${\overline{y}}\in
S_{{\overline{y}},{\mathcal{J}}}=S_{{\overline{x}},{\mathcal{J}}}$, proving
that ${\overline{y}}\in S(E)$. ∎

######  Corollary 6.2.

The set of all solutions of (25) is semilinear.

With minor adjustments, the foregoing arguments apply to non-homogeneous
systems as well. Specifically, if $E$ is a non-homogeneous system, then we
form the associated homogeneous system $E^{\prime}$ with auxiliary variable
$x_{0}$, as in (24). We now consider the set of ${\overline{x}}$ which are
solutions to both $E$ and $E^{\prime}$, and cluster structures ${\mathcal{J}}$
asscociated to ${\overline{x}}$ and $E_{\leq t}^{\prime}$, where each
${\mathcal{J}}$ is of the form $\\{J_{1},\ldots,J_{k},J_{0}\\}$ and $0\in
J_{0}$. We further stipulate that only the clusters $J_{1},\ldots,J_{k}$ can
be shifted (but not $J_{0}$). Hence, the definition of
$S_{{\overline{x}},{\mathcal{J}}}$ remains the same, and the proof of
Proposition 6.1 goes through unchanged.

##  7\. Parameterized complexity of the Diophantine problem

In this section, we show that the Diophantine problem for systems (25) can be
solved in polynomial time if the number of variables $k$ is bounded by a fixed
constant. In other words, the Diophantine problem for (25) is _fixed-parameter
tractable_.

Let $q$ be a polynomial such that the time complexity for validating an
${\mathbf{NP}}$-certificate ${\overline{x}}=(x_{1},\ldots,x_{k})$ for a system
$E$ of type (25) (i.e. for checking that ${\overline{x}}$ is a solution) is
$O(q(\operatorname{{size}}(E)))$, and let $p$ be a polynomial such that

$\operatorname{{max\;\\!span}}(E)<p(\operatorname{{size}}(E)).$

By Corollaries 5.3 and 4.5, such polynomials exist.

######  Proposition 7.1.

There exists an algorithm that decides if a given system $E$ of type (25) has
a solution in time

(30) $O{\left(2^{k^{2}}\\!\operatorname{{size}}^{2k^{2}}(E)\cdot
p(\operatorname{{size}}(E))^{k}\cdot q(\operatorname{{size}}(E))\right)}.$

###### Proof.

Using (27), we see that the total number of ${\mathbf{NP}}$-certificates
${\overline{x}}=(x_{1},\ldots,x_{k})$ satisfying (29) is

$(N_{E}+\operatorname{{max\;\\!span}}(E_{\leq
t}))^{k}<(2^{k}\operatorname{{size}}^{2k}(E)+p(\operatorname{{size}}(E)))^{k},$

which is $O{\left(2^{k^{2}}\\!\operatorname{{size}}^{2k^{2}}(E)\cdot
p(\operatorname{{size}}(E))^{k}\right)}$. It is straightforward to enumerate
all such certificates, and the time required to check each one is
$O(q(\operatorname{{size}}(E)))$, so the result follows. ∎

######  Corollary 7.2.

Fix $K\in{\mathbb{N}}$. The Diophantine problem for systems (25) with the
number of variables bounded by $K$ can be solved in polynomial time. Hence,
the Diophantine problem for systems (25) is a fixed-parameter tractable
problem.

###### Proof.

The complexity bound (30) of Proposition 7.1 is polynomial if $k$ is bounded
by the given constant $K$. ∎

## References

  * [1] R. J. Bradford and J. H. Davenport.  Effective tests for cyclotomic polynomials.  In International Symposium on Symbolic and Algebraic Computation, 1988.
  * [2] D. G Cantor.  Irreducible polynomials with integral coefficients have succinct certificates.  Journal of Algorithms, 2(4):385–392, 1981.
  * [3] L. Ciobanu, D. Holt, and S. Rees.  Equations in groups that are virtually direct products.  Journal of Algebra, 545:88–99, 2020.  Special Issue in Memory of Charles Sims.
  * [4] F. Dudkin and A. Treyer.  Knapsack problem for Baumslag–Solitar groups.  Sibirskii zhurnal chistoi i prikladnoi matematiki, 18:43–56, 12 2018.
  * [5] M. Garey and J. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [6] A. Garreta, A. Miasnikov, and D. Ovchinnikov.  Diophantine problems in solvable groups.  Bulletin of Mathematical Sciences, 10, 2020.
  * [7] O. Kharlampovich, A. Mohajeri, A. Taam, and A. Vdovina.  Quadratic equations in hyperbolic groups are NP-complete.  Transactions of the American Mathematical Society, 369:6207–6238, 09 2017.
  * [8] H. W. Lenstra.  Finding small degree factors of lacunary polynomials.  In Number Theory in Progress, pages 267–276, Berlin, Boston, 1999\. De Gruyter.
  * [9] M. Lohrey, G. Zetzsche, and M Ganardi.  Knapsack and the power word problem in solvable Baumslag-Solitar groups.  In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67:1–67:15, Dagstuhl, Germany, 2020\. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [10] R. Mandel and A. Ushakov.  Quadratic equations in metabelian Baumslag–Solitar groups.  Submitted, 2023.
  * [11] David Marker.  Model theory and exponentiation.  1996\.
  * [12] Yu. V. Matiyasevich.  Hilbert’s 10th Problem (Foundations of Computing).  The MIT Press, 1993.
  * [13] A. L. Semenov.  Logical theories of one-place functions on the set on natural numbers.  Math. USSR Izv., 22:587–618, 1984.
  * [14] A. Storjohann and G. Labahn.  Asymptotically fast computation of Hermite normal forms of integer matrices.  In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC ’96, pages 259–266, 1996.