The Analogue of Buchi's Problem for Rational Functions

Büchi's problem asked whether there exists an integer Msuch that the surface defined by a system of equations of theform has no integer pointsother than those that satisfy ±x_n = ± x₀ + n (the± signs are independent). If answered positively, itwould imply that there is no algorithm which decides, givenan arbitrary system Q = (q1,...,q_r) of integral quadratic formsand an arbitrary r-tuple B = (b₁,...,b_r) of integers, whetherQ represents B (see T. Pheidas and X. Vidaux, Fund. Math. 185(2005) 171–194). Thus it would imply the following strengtheningof the negative answer to Hilbert's tenth problem: the positive-existentialtheory of the rational integers in the language of additionand a predicate for the property ‘x is a square’would be undecidable. Despite some progress, including a conditionalpositive answer (depending on conjectures of Lang), Büchi'sproblem remains open. In this paper we prove the following: (A) an analogue of Büchi's problem in rings of polynomialsof characteristic either 0 or p 17 and for fields of rationalfunctions of characteristic 0; and (B) an analogue of Büchi's problem in fields of rationalfunctions of characteristic p 19, but only for sequences thatsatisfy a certain additional hypothesis. As a consequence we prove the following result in logic. Let F be a field of characteristic either 0 or at least 17 andlet t be a variable. Let L_t be the first order language whichcontains symbols for 0 and 1, a symbol for addition, a symbolfor the property ‘x is a square’ and symbols formultiplication by each element of the image of t] in Ft].Let R be a subring of F(t), containing the natural image oft] in F(t). Assume that one of the following is true: (i) R Ft]; (ii) the characteristic of F is either 0 or p 19. Then multiplication is positive-existentially definable overthe ring R, in the language L_t. Hence the positive-existentialtheory of R in L_t is decidable if and only if the positive-existentialring-theory of R in the language of rings, augmented by a constant-symbolfor t, is decidable.