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

• Autorzy: Thanases Pheidas , Xavier Vidaux
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 03C60: Model-theoretic algebra
• 12L05: Decidability

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2005
• Tom: 185
• Numer: 2
• Strony: 171-194

Daty

wydano

2005

Twórcy

autor

Thanases Pheidas

• Department of Mathematics, University of Crete, 71 409 Heraklion, Crete, Greece

autor

Xavier Vidaux

• Departamento de Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Concepción, Casilla 160C, Concepción, Chile

Identyfikatory

DOI

10.4064/fm185-2-4