General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Zap. Nauchn. Sem. POMI:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 12 scientific papers (total in 12 papers)

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

H. Pastena, T. Pheidasb, X. Vidauxa

a Universidad de Concepción
b University of Crete

Abstract: 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.

Key words and phrases: Bü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
Received: 02.06.2010
Language: English

Citation: H. Pasten, T. Pheidas, X. Vidaux, “A survey on Bü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
\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
\jour J. Math. Sci. (N. Y.)
\yr 2010
\vol 171
\issue 6
\pages 765--781

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  crossref  mathscinet  zmath  isi  scopus
    2. Vidaux X., “Polynomial parametrizations of length 4 Büchi sequences”, Acta Arith., 150:3 (2011), 209–226  crossref  mathscinet  zmath  isi  scopus
    3. Sáez P., Vidaux X., “A characterization of Büchi's integer sequences of length 3”, Acta Arith., 149:1 (2011), 37–56  crossref  mathscinet  zmath  isi  scopus
    4. Pasten H., “Büchi's problem in any power for finite fields”, Acta Arith., 149:1 (2011), 57–63  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    6. Wang J.T.-Yu., “Hensley's problem for function fields”, Int. J. Number Theory, 8:2 (2012), 507–524  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    11. Buser P., Scarpellini B., “Undecidability through Fourier series”, Ann. Pure Appl. Log., 167:7 (2016), 507–524  crossref  mathscinet  zmath  isi  scopus
    12. Garcia-Fritz N., “Sequences of Powers With Second Differences Equal to Two and Hyperbolicity”, Trans. Am. Math. Soc., 370:5 (2018), 3441–3466  crossref  mathscinet  zmath  isi  scopus
  • Записки научных семинаров ПОМИ
    Number of views:
    This page:165
    Full text:68

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019