These are equations of the form
| EL (x1,...,xm) = ER(x1,...,xm), | (1) |
where EL(x1,...,xm) and ER(x1,...,xm) are so-called exponential polynomials, i.e., expressions constructed by conventional rules from particular natural numbers and unknowns x1,...,xm by addition, multiplication and exponentiation. Subtraction is not allowed in exponential Diophantine equations and the domain of the unknowns is restricted to natural numbers in order to avoid expressions having no reasonable sense like
| ( x - y ) 2 2 x - y | (2) |
for x=1 and y=3.
Exponential Diophantine equations are natural
generalizations of genuine
Diophantine equations, which explains the
name.
One can also consider parametric exponential Diophantine equations
| EL (a1,...,an,x1,. ..,xm) = ER(a1,...,an,x1,. ..,xm) | (3) |
where EL (a1,...,an,x1,...,xm) and ER(a1,...,an,x1,...,xm) are exponential polynomials in all variables a1,...,an (the parameters) and x1,...,xm (the unknowns).
Given an arbitrary exponential Diophantine equation (3) one can construct a
genuine Diophantine equation
| D (a1,...,an,y1,...,ys) = 0 , | (4) |
where D (a1,...,an,y1,...,ys) is a polynomial with integer coefficients, which for given values of the parameters a1,...,an has a solution in its unknowns y1,...,ys if and only if the original exponential Diophantine equations has a solution in x1,...,xm for the same values of the parameters a1,...,an (see Davis's conjecture ).
Given an arbitrary exponential Diophantine equation (3) one can construct another exponential Diophantine equation
| FL(a1,...,an,x,y,z) = FR(a1,...,an,x,y,z), | (5) |
which for given values of the parameters a1,...,an has a solution in its three unknowns x, y and z if and only if the original exponential Diophantine equation has a solution in its m unknowns x1,...,xm for the same values of the parameters a1,...,an. Such reduction of the number of unknowns was originally obtained in [Matiyasevich79], the proof is reproduced in [Smorynski91] and [Matiyasevich93] .