1
$\begingroup$

I want to ask about decidability of exponential Diophantine equation:

$z_12^{\eta_1} + \ldots + z_n2^{\eta_n} = z$, where $z_i,\eta_i,z \in \mathbb{Z}$, and $\eta_i$ - are variables.

Can we find solution in $\mathbb{Z}$ in general case or this type of equations is undecidable? What you advise to read on this problem?

Very grateful for any help.

$\endgroup$

3 Answers 3

2
$\begingroup$

Are the $\eta_i$ supposed to be non-negative integers? In any case, writing the $z_i$ as sums of powers of two, i.e., write out their binary expansion, and expanding $z_12^{\eta_1}+\cdots+z_n2^{\eta_n}$, you can reduce to the case that all of the $z_i$ are equal to $\pm1$. So you're asking, for a fixed $m\ge0$ and $n\ge0$, can one determine, for every $z\in\mathbb{Z}$, if $z$ can be expressed in the form $$ z=\hbox{(sum of $n$ powers of 2)}-\hbox{(sum of $m$ powers of 2)} $$ This isn't meant to be a solution, but maybe it's a helpful simplification.

$\endgroup$
2
$\begingroup$

If $\eta_i$ are nonnegative, then there is an algorithm (though not very efficient) finding all the solutions. First note that there is one $\eta_i$ such that $v_2(\eta_i)\le v_2(z)$. where $v_2$ denotes the 2-adic valuation. Then you loop through $1\le i\le n$ and $0\le\eta_i\le v_2(z)$. Plug that $\eta_i$ in and you get an equation with $n-1$ variables. Recurse.

$\endgroup$
1
$\begingroup$

See Section 2 of Semenov's paper "Logical theories of one-place functions on the set of natural numbers".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.