In number theory, Büchi's problem, also known as the n squares' problem, is an open problem named after the Swiss mathematician Julius Richard Büchi. It asks whether there is a positive integer M such that every sequence of M or more integer squares, whose second difference is constant and equal to 2, is necessarily a sequence of squares of the form (x + i)2, i = 1, 2, ..., M,... for some integer x. In 1983, Douglas Hensley observed that Büchi's problem is equivalent to the following: Does there exist a positive integer M such that, for all integers x and a, the quantity (x + n)2 + a cannot be a square for more than M consecutive values of n, unless a = 0?
Statement of Büchi's problem
editBüchi's problem can be stated in the following way: Does there exist a positive integer M such that the system of equations
has only solutions satisfying
Since the first difference of the sequence is the sequence , the second difference of is
Therefore, the above system of equations is equivalent to the single equation
where the unknown is the sequence .
Examples
editObserve that for any integer x we have
Hence the equation has solutions, called trivial Büchi sequences of length three, such that and . For example, the sequences (2, 3, 4) and (2, −3, 4) are trivial Büchi sequences. A nontrivial Büchi sequence of length three is given for example by the sequence (0, 7, 10), as it satisfies 102 − 2·72 + 02 = 2, while 02, 72 and 102 are not consecutive squares.
Replacing x by x + 1 in equation , we obtain . Hence the system of equations
has trivial Büchi solutions of length 4, namely the one satisfying for n = 0, 1, 2, 3. In 1983, D. Hensley showed that there are infinitely many nontrivial Büchi sequences of length four. It is not known whether there exist any non-trivial Büchi sequence of length five (Indeed, Büchi asked originally the question only for M = 5.).
Original motivation
editA positive answer to Büchi's problem would imply, using the negative answer to Hilbert's tenth problem by Yuri Matiyasevich, that there is no algorithm to decide whether a system of diagonal quadratic forms with integer coefficients represents an integer tuple. Indeed, Büchi observed that squaring, therefore multiplication, would be existentially definable in the integers over the first-order language having two symbols of constant for 0 and 1, a symbol of function for the sum, and a symbol of relation P to express that an integer is a square.
Some results
editPaul Vojta proved in 1999 that a positive answer to Büchi's Problem would follow from a positive answer to a weak version of the Bombieri–Lang conjecture. In the same article, he proves that the analogue of Büchi's Problem for the field of meromorphic functions over the complex numbers has a positive answer. Positive answers to analogues of Büchi's Problem in various other rings of functions have been obtained since then (in the case of rings of functions, one adds the hypothesis that not all xn are constant).
References
edit- Vojta, Paul (1999), Diagonal quadratic forms and Hilbert’s tenth problem, pp. 261–274 in Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), edited by J. Denef et al., Contemp. Math. 270, Amer. Math. Soc., Providence, RI, 2000.
- Lipshitz, Leonard (1990), "Quadratic forms, the five square problem, and diophantine equations" in Collected Works of J. Richard Büchi. Edited by Saunders Mac Lane and Dirk Siefkes. Springer, New York.
- Hensley, Douglas (1983), “Sequences of squares with second difference of two and a conjecture of Büchi”, unpublished.