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

Volume 185 / 2005

Thanases Pheidas, Xavier Vidaux Fundamenta Mathematicae 185 (2005), 171-194 MSC: Primary 03C60; Secondary 12L05. DOI: 10.4064/fm185-2-4


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


  • Thanases PheidasDepartment of Mathematics
    University of Crete
    71 409 Heraklion, Crete, Greece
  • Xavier VidauxDepartamento de Matemática
    Facultad de Ciencias Físicas y Matemáticas
    Universidad de Concepción
    Casilla 160C
    Concepción, Chile

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image