A survey on Büchi's problem: new presentations and open problems

H. Pasten   ; T. Pheidas   ; X. Vidaux

Zapiski Nauchnykh Seminarov POMI, Studies in number theory. Part 10, Tome 377 (2010), pp. 111-140

Résumé

In a commutative ring with a unit, Büchi sequences are those sequences whose second difference of squares is the constant sequence (2). Sequences of elements $x_n$, satisfying $x_n^2=(x+n)^2$ for some fixed $x$ are Büchi sequences that we call trivial. Since we want to study sequences whose elements do not belong to certain subrings (e.g. for fields of rational functions $F(z)$ over a field $F$, we are interested in sequences that are not over $F$), the concept of trivial sequences may vary. Büchi's Problem for a ring asks, whether there exists a positive integer $M$ such that any Büchi sequence of length $M$ or more is trivial. We survey the current status of knowledge for Büchi's problem and its analogues for higher-order differences and higher powers. We propose several new and old open problems. We present a few new results and various sketches of proofs of old results (in particular Vojta's conditional proof for the case of integers and a rather detailed proof for the case of polynomial rings in characteristic zero), and present a new and short proof of the positive answer to Büchi's problem over finite fields with $p$ elements (originally proved by Hensley). We discuss applications to logic, which were the initial aim for solving these problems. Bibl. 30 titles.

Bibliographie

[1] D. Allison, “On square values of quadratics”, Math. Proc. Camb. Philos. Soc., 99:3 (1986), 381–383 | DOI | MR | Zbl

[2] A. Bremner, “On square values of quadratics”, Acta Arith., 108:2 (2003), 95–111 | DOI | MR | Zbl

[3] J. L. Britton, “Integers solutions of systems of quadratic equations”, Math. Proc. of the Cambridge Phil. Soc., 86 (1979), 385–389 | DOI | MR | Zbl

[4] J. Browkin, J. Brzeziński, “On sequences of squares with constant second differences”, Canad. Math. Bull., 49:4 (2006), 481–491 | DOI | MR | Zbl

[5] M. Davis, “Hilbert's tenth problem is unsolvable”, Amer. Math. Monthly, 80 (1973), 233–269 | DOI | MR | Zbl

[6] J. Denef, “The Diophantine Problem for polynomial rings and fields of rational functions”, Trans. Amer. Math. Soc., 242 (1978), 391–399 | DOI | MR | Zbl

[7] J. Denef, L. Lipshitz, T. Pheidas, J. Van Geel (Eds.), Hilbert's Tenth Problem, Relations with Arithmetic and Algebraic Geometry (Ghent 1999), Contemporary Mathematics, 270, 2000 | DOI | MR | Zbl

[8] F. Grunewald, D. Segal, “How to solve a quadratic equation in integers”, Math. Proc. Cambridge Philosophical Soc., 89 (1981), 1–5 | DOI | MR | Zbl

[9] D. Hensley, Sequences of squares with second difference of two and a problem of logic, unpublished, 1980–1983 | Zbl

[10] D. Hensley, Sequences of squares with second difference of two and a conjecture of Büchi, unpublished, 1980–1983

[11] L. Lipshitz, “Quadratic forms, the five square problem, and diophantine equations”, The collected works of J. Richard Büchi, eds. S. MacLane, Dirk Siefkes, Springer, 1990, 677–680

[12] L. Lipshitz, T. Pheidas, “An analogue of Hilbert's tenth problem for $p$-adic entire functions”, J. Symb. Logic, 60:4 (1995), 1301–1309 | DOI | MR | Zbl

[13] Yu. Matiyasevic, “Enumerable sets are diophantine”, Soviet Mathematics Doklady, 11 (1970), 354–358 | MR | Zbl

[14] B. Mazur, “Questions of decidability and undecidability in number theory”, J. Symbolic Logic, 59:2 (1994), 353–371 | DOI | MR

[15] L. Moret-Bailly, A. Shlapentokh, “Diophantine Undecidability of Holomorphy Rings of Function Fields of Characteristic Zero”, Annales de l'Institut Fourier, 59:5 (2009), 2103–2118 | DOI | MR | Zbl

[16] H. Pasten, “An extension of Büchi's Problem for polynomial rings in zero characteristic”, Proc. Amer. Math. Soc., 138 (2010), 1549–1557 | DOI | MR | Zbl

[17] H. Pasten, Representation of squares by monic second degree polynomials in the field of $p$-adic meromorphic functions, arXiv: 1003.1969

[18] T. Pheidas, X. Vidaux, “Extensions of Büchi's problem: Questions of decidability for addition and $n$th powers”, Fundamenta Mathmaticae, 185 (2005), 171–194 | DOI | MR | Zbl

[19] T. Pheidas, X. Vidaux, “The analogue of Büchi's problem for rational functions”, J. London Math. Soc., 74:3 (2006), 545–565 | DOI | MR | Zbl

[20] T. Pheidas, X. Vidaux, “Corrigendum: The analogue of Büchi's problem for rational functions”, the Journal of the London Mathematical Society, 2010 (to appear)

[21] T. Pheidas, X. Vidaux, “The analogue of Büchi's problem for cubes in rings of polynomials”, Pacific J. Math., 238:2 (2008), 349–366 | DOI | MR | Zbl

[22] T. Pheidas, K. Zahidi, “Undecidable existential theories of polynomial rings and function fields”, Commun. Algebra, 27:10 (1999), 4993–5010 | DOI | MR | Zbl

[23] R. G. E. Pinch, “Squares in Quadratic Progression”, Math. Comput., 60:202 (1993), 841–845 | DOI | MR | Zbl

[24] B. Poonen, Hilbert's Tenth Problem over rings of number-theoretic interest downloadable from http://math.mit.edu/~poonen/papers/aws2003.pdf

[25] A. Shlapentokh, Hilbert's tenth problem Diophantine classes and extensions to global fields, New Mathematical Monographs, 7, Cambridge Univ. Press, 2007 | MR | Zbl

[26] A. Shlapentokh, X. Vidaux, The analogue of Büchi's problem for function fields, arXiv: 1004.0731v1

[27] Th. Skolem, Diophantische Gleichungen, Ergebnisse d. Math. u. Ihrer Grenzgebiete, 5, Julius Springer, 1938 | Zbl

[28] X. Vidaux, “An analogue of Hilbert's tenth problem for fields of meromorphic functions over non-Archimedean valued fields”, J. Number Theory, 101:1 (2003), 48–73 | DOI | MR | Zbl

[29] P. Vojta, “Diagonal quadratic forms and Hilbert's Tenth Problem”, Contemporary Math., 270 (2000), 261–274 | DOI | MR | Zbl

[30] H. Yamagishi, “On the solutions of certain diagonal quadratic equations and Lang's conjecture”, Acta Arithmetica, 109:2 (2003), 159–168 | DOI | MR | Zbl