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

${\displaystyle {\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 ${\displaystyle x_{n}^{2}=(x_{0}+n)^{2}.}$

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

${\displaystyle \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

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

where the unknown is the sequence ${\displaystyle \sigma }$.

Observe that for any integer x we have

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

Hence the equation ${\displaystyle x_{2}^{2}-2x_{1}^{2}+x_{0}^{2}=2}$ has solutions, called trivial Büchi sequences of length three, such that ${\displaystyle x_{2}^{2}=(x_{0}+2)^{2}}$ and ${\displaystyle 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 ${\displaystyle (\star )}$, we obtain ${\displaystyle (x+3)^{2}-2(x+2)^{2}+(x+1)^{2}=2}$. Hence the system of equations

${\displaystyle {\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 ${\displaystyle 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.).

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.

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).

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