RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zap. Nauchn. Sem. POMI: Year: Volume: Issue: Page: Find

 Zap. Nauchn. Sem. POMI, 2010, Volume 377, Pages 111–140 (Mi znsl3818)

A survey on Büchi's problem: new presentations and open problems

H. Pastena, T. Pheidasb, X. Vidauxa

b University of Crete

Abstract: In a commutative ring with a unit, Bü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 Bü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. Büchi's Problem for a ring asks, whether there exists a positive integer $M$ such that any Büchi sequence of length $M$ or more is trivial.
We survey the current status of knowledge for Bü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 Bü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.

Key words and phrases: Büchi, “n squares problem”, Diophantine equations, Hilbert's tenth problem, undecidability.

Full text: PDF file (714 kB)
References: PDF file   HTML file

English version:
Journal of Mathematical Sciences (New York), 2010, 171:6, 765–781

Document Type: Article
UDC: 511.522+510.53
Language: English

Citation: H. Pasten, T. Pheidas, X. Vidaux, “A survey on Büchi's problem: new presentations and open problems”, Studies in number theory. Part 10, Zap. Nauchn. Sem. POMI, 377, POMI, St. Petersburg, 2010, 111–140; J. Math. Sci. (N. Y.), 171:6 (2010), 765–781

Citation in format AMSBIB
\Bibitem{PasPheVid10} \by H.~Pasten, T.~Pheidas, X.~Vidaux \paper A survey on B\"uchi's problem: new presentations and open problems \inbook Studies in number theory. Part~10 \serial Zap. Nauchn. Sem. POMI \yr 2010 \vol 377 \pages 111--140 \publ POMI \publaddr St.~Petersburg \mathnet{http://mi.mathnet.ru/znsl3818} \transl \jour J. Math. Sci. (N. Y.) \yr 2010 \vol 171 \issue 6 \pages 765--781 \crossref{https://doi.org/10.1007/s10958-010-0181-x} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-78650059119} 

• http://mi.mathnet.ru/eng/znsl3818
• http://mi.mathnet.ru/eng/znsl/v377/p111

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Shlapentokh A., Vidaux X., “The analogue of Buchi's Problem for function fields”, J. Algebra, 330:1 (2011), 482–506
2. Vidaux X., “Polynomial parametrizations of length 4 Büchi sequences”, Acta Arith., 150:3 (2011), 209–226
3. Sáez P., Vidaux X., “A characterization of Büchi's integer sequences of length 3”, Acta Arith., 149:1 (2011), 37–56
4. Pasten H., “Büchi's problem in any power for finite fields”, Acta Arith., 149:1 (2011), 57–63
5. An Ta Thi Hoai, Wang J.T.-Y., “Hensley's problem for complex and non-Archimedean meromorphic functions”, J. Math. Anal. Appl., 381:2 (2011), 661–677
6. Wang J.T.-Yu., “Hensley's problem for function fields”, Int. J. Number Theory, 8:2 (2012), 507–524
7. Ta Thi Hoai An, Huang H.-L., Wang J.T.-Yu., “Generalized Buchi's Problem for Algebraic Functions and Meromorphic Functions”, Math. Z., 273:1-2 (2013), 95–122
8. Pasten H., Pheidas T., Vidaux X., “Uniform Existential Interpretation of Arithmetic in Rings of Functions of Positive Characteristic”, Invent. Math., 196:2 (2014), 453–484
9. Garcia-Fritz N., Pasten H., “Uniform Positive Existential Interpretation of the Integers in Rings of Entire Functions of Positive Characteristic”, J. Number Theory, 156 (2015), 368–393
10. Pasten H., Vidaux X., “Positive existential definability of multiplication from addition and the range of a polynomial”, Isr. J. Math., 216:1 (2016), 273–306
11. Buser P., Scarpellini B., “Undecidability through Fourier series”, Ann. Pure Appl. Log., 167:7 (2016), 507–524
12. Garcia-Fritz N., “Sequences of Powers With Second Differences Equal to Two and Hyperbolicity”, Trans. Am. Math. Soc., 370:5 (2018), 3441–3466
•  Number of views: This page: 165 Full text: 68 References: 10