Variation of information

Büchi's problem, also known as the n squares' problem, is an open problem from number theory 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)², 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)² + a cannot be a square for more than M consecutive values of n, unless a = 0?

Statement of Büchi's problem

Büchi's problem can be stated in the following way: Does there exist a positive integer M such that the system of equations

${\begin{cases}x_{2}^{2}-2x_{1}^{2}+x_{0}^{2}=2\\x_{3}^{2}-2x_{2}^{2}+x_{1}^{2}=2\\{}\quad \vdots \\x_{M-1}^{2}-2x_{M-2}^{2}+x_{M-3}^{2}=2\end{cases}}$

has only solutions satisfying $x_{n}^{2}=(x_{0}+n)^{2}.$

Since the first difference of the sequence $\sigma =(x_{n}^{2})_{n=0,\dots ,M-1}$ is the sequence $\Delta ^{(1)}(\sigma )=(x_{n+1}^{2}-x_{n}^{2})_{n=0,\dots ,M-2}$, the second difference of $\sigma$ is

$\Delta ^{(2)}(\sigma )=((x_{n+2}^{2}-x_{n+1}^{2})-(x_{n+1}^{2}-x_{n}^{2}))_{n=0,\dots ,M-3}=(x_{n+2}^{2}-2x_{n+1}^{2}+x_{n}^{2})_{n=0,\dots ,M-3}.$

Therefore, the above system of equations is equivalent to the single equation

$\Delta ^{(2)}(\sigma )=(2)_{n=0,\dots ,M-3}$

where the unknown is the sequence $\sigma$.

Examples

Observe that for any integer x we have

$(\star )\qquad (x+2)^{2}-2(x+1)^{2}+x^{2}=2.$

Hence the equation $x_{2}^{2}-2x_{1}^{2}+x_{0}^{2}=2$ has solutions, called trivial Büchi sequences of length three, such that $x_{2}^{2}=(x_{0}+2)^{2}$ and $x_{1}^{2}=(x_{0}+1)^{2}$. 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 10² − 2·7² + 0² = 2, while 0², 7² and 10² are not consecutive squares.

Replacing x by x + 1 in equation $(\star )$, we obtain $(x+3)^{2}-2(x+2)^{2}+(x+1)^{2}=2$. Hence the system of equations

${\begin{cases}x_{2}^{2}-2x_{1}^{2}+x_{0}^{2}=2\\x_{3}^{2}-2x_{2}^{2}+x_{1}^{2}=2\end{cases}}$

has trivial Büchi solutions of length 4, namely the one satisfying $x_{n}^{2}=(x_{0}+n)^{2}$ 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

A 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

Paul 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 x_n are constant).

References

• 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 Papers 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.