Extensions of Büchi's problem: Questions of decidability for addition and kth powers

Thanases Pheidas, and Xavier Vidaux. "Extensions of Büchi's problem: Questions of decidability for addition and kth powers." Fundamenta Mathematicae 185.2 (2005): 171-194. <http://eudml.org/doc/283265>.

@article{ThanasesPheidas2005,
abstract = { We generalize a question of Büchi: Let R be an integral domain, C a subring and k ≥ 2 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 kth 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 = ℤ. 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 = ℤ[t]. We prove that a negative answer to this question would follow from a negative answer for a ring between ℤ and the extension of ℤ by a primitive cube root of 1. },
author = {Thanases Pheidas, Xavier Vidaux},
journal = {Fundamenta Mathematicae},
keywords = {decidability; systems of polynomial equations},
language = {eng},
number = {2},
pages = {171-194},
title = {Extensions of Büchi's problem: Questions of decidability for addition and kth powers},
url = {http://eudml.org/doc/283265},
volume = {185},
year = {2005},
}

TY - JOUR
AU - Thanases Pheidas
AU - Xavier Vidaux
TI - Extensions of Büchi's problem: Questions of decidability for addition and kth powers
JO - Fundamenta Mathematicae
PY - 2005
VL - 185
IS - 2
SP - 171
EP - 194
AB - We generalize a question of Büchi: Let R be an integral domain, C a subring and k ≥ 2 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 kth 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 = ℤ. 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 = ℤ[t]. We prove that a negative answer to this question would follow from a negative answer for a ring between ℤ and the extension of ℤ by a primitive cube root of 1.
LA - eng
KW - decidability; systems of polynomial equations
UR - http://eudml.org/doc/283265
ER -