A survey on B\"uchi'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.