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

Tom 185 / 2005

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

Streszczenie

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

Autorzy

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

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek