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

In a commutative ring with a unit, a Buchi sequence is a sequence such that the second difference of the sequence of its squares is the constant sequence (2). Sequences of elements x n satisfying x n 2 = (x + n) 2 for some fixed x are Buchi sequences, which 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. Buchi’s problem for a ring asks whether there exists a positive integer M such that any Buchi sequence of length M or more is trivial.We survey the current status of knowledge for Buchi’s problem and its analogs 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 Buchi’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. Bibliography: 30 titles.