Extensions of Büchi's problem: Questions of decidability for addition and $k$th powers
Volume 185 / 2005
Fundamenta Mathematicae 185 (2005), 171-194
MSC: Primary 03C60; Secondary 12L05.
DOI: 10.4064/fm185-2-4
Abstract
We generalize a question of Büchi: Let $R$ be an integral domain, $C$ a subring and $k\geq2$ an integer. Is there an algorithm to decide the solvability in $R$ of any given system of polynomial equations, each of which is linear in the $k$th powers of the unknowns, with coefficients in $C$?
We state a number-theoretical problem, depending on $k$, a positive answer to which would imply a negative answer to the question for $R=C={\mathbb Z}$.
We reduce a negative answer for $k=2$ and for $R=F(t)$, the field of rational functions over a field of zero characteristic, to the undecidability of the ring theory of $F(t)$.
We address a similar question where we allow, along with the equations, also conditions of the form “$x$ is a constant” and “$x$ takes the value $0$ at $t=0$”, for $k=3$ and for function fields $R=F(t)$ of zero characteristic, with $C={\mathbb Z}[t]$. We prove that a negative answer to this question would follow from a negative answer for a ring between ${\mathbb Z}$ and the extension of ${\mathbb Z}$ by a primitive cube root of~$1$.
