Abstract

Büchi's problem asked whether there exists an integer M such that the surface defined by a system of equations of the form xn 2 + xn-2 2 = 2xn-1 2 + 2, n = 2,..., M - 1, has no integer points other than those that satisfy ±xn = ±x0 + n (the ± signs are independent). If answered positively, it would imply that there is no algorithm which decides, given an arbitrary system Q = (q1,...,qr) of integral quadratic forms and an arbitrary r-tuple B = (b1,...,br) of integers, whether Q represents B (see T. Pheidas and X. Vidaux, Fund. Math. 185 (2005) 171-194). Thus it would imply the following strengthening of the negative answer to Hillbert's tenth problem: the positive-existential theory of the rational integers in the language of addition and a predicate for the property 'x is a square' would be undecidable. Despite some progress, including a conditional positive answer (depending on conjectures of Lang), Büchi's problem remains open. In this paper we prove the following: (A) an analogue of Büchi's problem in rings of polynomials of characteristic either 0 or p ≥ 17 and for fields of rational functions of characteristic 0; and (B) an analogue of Büchi's problem in fields of rational functions of characteristic p ≥ 19, but only for sequences that satisfy 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 and let t be a variable. Let Lt be the first order language which contains symbols for 0 and 1, a symbol for addition, a symbol for the property 'x is a square' and symbols for multiplication by each element of the image of ℤ[t] in F[t]. Let R be a subring of F(t), containing the natural image of ℤ[t] in F(t). Assume that one of the following is true: (i) R ⊂ F[t]; (ii) the characteristic of F is either 0 or p ≥ 19. Then multiplication is positive-existentially definable over the ring R, in the language Lt. Hence the positive-existential theory of R in Lt is decidable if and only if the positive-existential ring-theory of R in the language of rings, augmented by a constant-symbol for t, is decidable. © 2006 London Mathematical Society.