Hilbert’s tenth problem for systems of diagonal quadratic forms, and Büchi’s problem
Stanley Yao Xiao · 2024
Read Hilbert’s tenth problem for systems of diagonal quadratic forms, and Büchi’s problem by Stanley Yao Xiao (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-16740.txt.
Introduction
Stanley Yao Xiao completes a proof that no algorithm can decide whether systems of diagonal quadratic equations have whole-number solutions. The result settles the problem for this class of equations, a case of Hilbert's tenth problem. It also finishes an older proof attempt by Büchi.
The missing piece concerned five squares whose second differences all equal two. Xiao proves that any such run of five squares must be consecutive squares. That fact closes the gap in Büchi's argument. The study answers a question Büchi had posed directly. It places diagonal quadratic systems among the equation families known to be undecidable.
Catalog record
| CREATOR | Stanley Yao Xiao |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-16740
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hilbert’s tenth problem for systems of diagonal quadratic forms, and Büchi’s problem Thanks: The author is supported by NSERC Discovery Grant RGPIN-2024-06810. Stanley Yao Xiao Abstract . In this paper we complete Büchi’s proof that there is no decision algorithm for the solubility in integers of arbitrary systems of diagonal quadratic form equations, by proving the assertion that whenever x 1 2 , ⋯ , x 5 2 x_{1}^{2},\cdots,x_{5}^{2} are five squares such that the second differences satisfy x k + 2 2 − 2 x k + 1 2 + x k 2 = 2 x_{k+2}^{2}-2x_{k+1}^{2}+x_{k}^{2}=2 for k = 1 , 2 , 3 k=1,2,3 , then they must be consecutive. This answers a question of J. Richard Büchi. 1. Introduction In this paper we prove the following theorem: Theorem 1.1 . There is no algorithm which decides the existence of integer solutions to an arbitrary system of diagonal quadratic form equations. Theorem 1.1 is a refinement of the negative solution to Hilbert’s tenth problem, proved by the celebrated work of Davis, Putnam, and Robinson and Matiyasevich (see [ 3 ] ). In particular, as opposed to an arbitrary system of polynomial equations defined over {\mathbb{Z}} , the solubility of even the simplest non-linear systems, namely those defined by a system of diagonal quadratic forms, cannot be decided. This also answers a question of J. L. Britton in [ 1 ] . J. Richard Büchi proved Theorem 1.1 , provided that the following statement, known as Büchi’s problem , holds: Conjecture 1.2 (Büchi’s problem) . There exists a positive integer N such that if x_{1}^{2},\cdots,x_{n}^{2} is a sequence of increasing squares with constant second difference equal to 2 , then n\leq N . Conjecture 1.2 was proved by P. Vojta [ 8 ] with N=8 under the assumption of the Bombieri–Lang conjecture. Büchi’s argument was reproduced in [ 8 ] . Our principal contribution is an unconditional proof of Conjecture 1.2 , with N=4 : Theorem 1.3 . Let x_{1}^{2},\cdots,x_{5}^{2} be integer squares with constant second difference equal to 2 . Then there exists an integer x_{0} such that x_{j}^{2}=(x_{0}+j)^{2} for j=1,2,3,4,5 . Theorem 1.3 directly answers a question of J. R. Büchi in its original form (see [ 2 ] and [ 4 ] , and [ 5 ] for a more recent account). Büchi proved that there is no algorithm which decides the existence of integral solutions to systems of diagonal quadratic form equations of the shape (1.1) \sum_{j=1}^{N}a_{ij}x_{j}^{2}=b_{i} for i=1,\cdots,M and j=1,\cdots,N,a_{ij},b_{i}\in{\mathbb{Z}} , provided that Conjecture 1.2 holds. Theorem 1.3 is the best possible, since it is known that there exist infinitely many quadruples of squares with second difference equal to 2 , which do not consist of consecutive squares. Geometrically, the homogeneous system of equations (1.2) \begin{matrix}x_{3}^{2}&-&2x_{2}^{2}&+&x_{1}^{2}&=&2x_{0}^{2}\\ \vdots&&\vdots&&\ddots&&\vdots\\ x_{n}^{2}&-&2x_{n-1}^{2}&+&x_{n-2}^{2}&=&2x_{0}^{2}\end{matrix} defines a projective surface X_{n} of general type when n\geq 6 , but not when n\leq 5 . Indeed X_{3} is simply a quadric surface. X_{4} is a del Pezzo surface of degree 4 , and X_{5} is a K3 surface. Thus, it is expected that there may be infinitely many non-trivial solutions when n\leq 4 . Indeed, infinite parametric families exist. A classical example, due to D. Hensley (unpublished), is given by the parametrization (1.3) (x_{1},x_{2},x_{3},x_{4})=(2t^{3}+12t^{2}+19t+6,2t^{3}+14t^{2}+31t+23,2t^{3}+16t^{2}+41t+32,2t^{3}+18t^{2}+49t+39),t\in{\mathbb{Z}}. A generalization which produces many other polynomial parametrized families of non-trivial quadruples of four squares with finite difference equal to 2 was produced by X. Vidaux in [ 7 ] . We note that the proof of Theorem 1.3 shows that the affine variety \widetilde{X_{5}} defined by specializing x_{0}=1 has no integer points outside the closed subset consisting of trivial tuples. Since X_{5} is a K3 surface, \widetilde{X_{5}} is log-general type , so an analogue of Lang’s conjecture, interpreted as a higher dimensional analogue of Siegel’s theorem on integer points on algebraic curves of positive genus, would indicate that \widetilde{X_{5}} has no integer points outside of a finite union of curves. Since X_{5} is a K3 surface and not a surface of general type, the Bombieri–Lang conjecture does not apply, and so our argument is necessarily quite disjoint from that of Vojta in [ 8 ] . We go further than previous authors in the triple and quadruple cases, where we obtain a complete description of all possible tuples. To this end, we define: Definition 1.4 . Let n be a positive integer. We say an n -tuple (u_{1},\cdots,u_{n}) of positive integers is a Büchi n -tuple if u_{1}^{2},\cdots,u_{n}^{2} is an increasing sequence of squares with second difference equal to 2 . We have the following characterization of Büchi triples. Theorem 1.5 . Let (u_{1},u_{2},u_{3}) be a Büchi triple. Then there exist non-negative integers s_{1},s_{3},s_{4},s_{6} and \beta\in\{1,2\} satisfying s_{1}s_{3}-s_{4}s_{6}=\beta , such that u_{1}=\frac{s_{1}s_{3}-s_{3}s_{4}+s_{1}s_{6}+s_{4}s_{6}}{2\beta},u_{2}=\frac{s_{3}s_{4}+s_{1}s_{6}}{2\beta},u_{3}=\frac{s_{1}s_{3}+s_{3}s_{4}-s_{1}s_{6}+s_{4}s_{6}}{2\beta}. Similarly, we obtain the following theorem capturing Büchi quadruples. Theorem 1.6 . Let (u_{1},u_{2},u_{3},u_{4}) be a Büchi quadruple. Then there exist non-negative integers s_{0},s_{1},\cdots,s_{15} , \beta_{1},\beta_{2}\in\{1,2\} , and \delta\in\{1,3\} satisfying the relations (1.4) \begin{matrix}s_{8}&=&\dfrac{(3/\delta)s_{4}s_{11}-s_{1}s_{14}}{\beta_{1}(2/\beta_{2})s_{7}}&s_{13}&=&\dfrac{s_{4}s_{11}+\delta s_{1}s_{14}}{\beta_{1}(2/\beta_{2})s_{2}}\\ \\ s_{3}&=&\dfrac{(s_{1}s_{14}+(3/\delta)s_{4}s_{11})s_{9}-2s_{4}s_{14}s_{12}}{2s_{2}s_{7}}&s_{6}&=&\dfrac{2s_{1}s_{11}s_{9}-(\delta s_{1}s_{14}-s_{4}s_{11})s_{12}}{2s_{2}s_{7}}\\ \\ s_{0}&=&\dfrac{s_{9}s_{11}-\delta s_{12}s_{14}}{\beta_{1}s_{2}}&s_{5}&=&\dfrac{(3/\delta)s_{9}s_{11}-s_{12}s_{14}}{\beta_{1}s_{7}}\\ \\ s_{10}&=&\dfrac{s_{1}s_{9}+s_{4}s_{12}}{\beta_{1}s_{2}}&s_{15}&=&\dfrac{-s_{1}s_{9}+s_{4}s_{12}}{\beta_{1}s_{7}}\end{matrix} with \begin{matrix}x_{1}&=&s_{0}s_{2}s_{4}s_{6}s_{8}s_{10}s_{12}s_{14},&y_{1}&=&s_{1}s_{3}s_{5}s_{7}s_{9}s_{11}s_{13}s_{15},\\ x_{2}&=&s_{0}s_{1}s_{4}s_{5}s_{8}s_{9}s_{12}s_{13},&y_{2}&=&s_{2}s_{3}s_{6}s_{7}s_{10}s_{11}s_{14}s_{15},\\ x_{3}&=&s_{0}s_{1}s_{2}s_{3}s_{8}s_{9}s_{10}s_{11},&y_{3}&=&s_{4}s_{5}s_{6}s_{7}s_{12}s_{13}s_{14}s_{15},\\ x_{4}&=&s_{0}s_{1}s_{2}s_{3}s_{4}s_{5}s_{6}s_{7},&y_{4}&=&s_{8}s_{9}s_{10}s_{11}s_{12}s_{13}s_{14}s_{15}.\end{matrix} such that u_{k}=x_{k}-y_{k} for k=1,2,3,4 . Theorems 1.5 and 1.6 are crucial to show the non-existence of non-trivial Büchi quintuples. In particular, the same argument used to prove Theorem 1.6 is also used to prove the so-called calibration lemmas , namely Lemmas 6.3 , 6.4 , and 6.5 . 1.1. Outline of proof of Theorem 1.3 In this subsection we describe our strategy to proving Theorem 1.3 . We begin by considering a slightly more general problem: in Proposition 2.5 we show that to obtain a non-trivial sequence of squares with finite second difference equal to 2 is tantamount to showing that a certain monic quadratic polynomial takes on square values at consecutive integer inputs. This compels Definition 3.1 , which gives our notion of an n -tuple of Büchi pairs . Next, we go step-by-step towards our goal by understanding triples and quadruples of Büchi pairs. We introduce a bijection \sigma_{n} between {\mathbb{F}}_{2}^{n} and \{0,1,\cdots,2^{n}-1\} given by ( 4.1 ). This allows us to introduce the notion of a parametrizing sequence of an n -tuple of Büchi pairs; see ( 4.3 ). We note that a non-trivial n -tuple of Büchi pairs must necessarily have a parametrizing sequence consisting of only positive entries; see Proposition 4.2 . We already know that there are infinitely many non-trivial Büchi quadruples thanks to the work of Hensley and more recently Vidaux [ 7 ] , so we know a priori to expect plenty of quadruples of Büchi pairs. However, Definition 3.1 provides us with sufficient structure that we can parametrize all triples. The statement is given as Proposition 4.4 . We then use the crucial observation that a quadruple of Büchi pairs is obtained by weaving two triples together, with each triple given by a parametrization supplied by Proposition 4.4 . This allows us to obtain substantial control over the structure of the quadruples. In particular, the parametrizing sequence of a non-trivial quadruple of Büchi pairs must satisfy the so-called Pfaffian equation , namely ( 5.7 ). Finally, to address the non-existence of non-trivial quintuples of Büchi pairs, it suffices to show that there is no parametrizing sequence of a quintuple of Büchi pairs consisting of only positive entries.