Extensions of Büchi's problem: Questions of decidability for addition and $k$th powers

Thanases Pheidas¹ ; Xavier Vidaux²

¹ Department of Mathematics University of Crete 71 409 Heraklion, Crete, Greece
² Departamento de Matemática Facultad de Ciencias Físicas y Matemáticas Universidad de Concepción Casilla 160C Concepción, Chile

Fundamenta Mathematicae, Tome 185 (2005) no. 2, pp. 171-194.

Résumé

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$.

Détail

DOI : 10.4064/fm185-2-4

Keywords: generalize question chi integral domain subring geq integer there algorithm decide solvability given system polynomial equations each which linear kth powers unknowns coefficients state number theoretical problem depending positive answer which would imply negative answer question mathbb reduce negative answer field rational functions field zero characteristic undecidability ring theory address similar question where allow along equations conditions form constant takes value function fields zero characteristic mathbb prove negative answer question would follow negative answer ring between mathbb extension mathbb primitive cube root