Small gaps in the Ulam sequence

François Clément; Stefan Steinerberger

doi:10.5802/crmath.746

Article de recherche - Théorie des nombres

Small gaps in the Ulam sequence
[Sur la présence de petits intervalles dans la suite d’Ulam]

François Clément ¹ ; Stefan Steinerberger ¹

¹ Department of Mathematics, University of Washington, Seattle, USA

Comptes Rendus. Mathématique, Volume 363 (2025), pp. 941-949

Abstract (VO)
Résumé

The Ulam sequence, described by Stanisław Ulam in the 1960s, starts 1, 2 and then iteratively adds the smallest integer that can be uniquely written as the sum of two distinct earlier terms: this gives $1,2,3,4,6,8,11,\dots $ Already in 1972 the great French poet Raymond Queneau wrote that it “gives an impression of great irregularity”. This irregularity appears to have a lot of structure and has inspired a great deal of work; nonetheless, very little is actually known. We improve the best upper bound on its growth and show that some small gaps have to exist: for some $c>0$ and all $n \in \mathbb{N}$,

\[ \min _{1 \le k \le n} \frac{a_{k+1}}{a_k} \le 1 + c\frac{\log {n}}{n}. \]

La séquence d’Ulam, introduite par Stanisław Ulam dans les années 1960, commence par 1, 2, puis rajoute itérativement à la séquence le plus petit entier s’écrivant comme une somme unique de deux termes distincts de la séquence. La séquence débute donc par $1,2,3,4,6,8,11,\dots $ Dès 1972, le poète Raymond Queneau écrivait qu’“elle donne l’impression de grande irrégularité”. Cette irrégularité semble avoir une structure particulière, inspirant de nombreux travaux, mais ayant débouché sur peu de résultats formels. Nous améliorons ici le meilleur majorant pour sa croissance asymptotique, ainsi que l’existence de “petits” intervalles entre deux éléments consécutifs : pour $c>0$ et pour tout $n \in \mathbb{N}$,

\[ \min _{1 \le k \le n} \frac{a_{k+1}}{a_k} \le 1 + c\frac{\log {n}}{n}. \]

Reçu le : 2025-01-30
Révisé le : 2025-02-24
Accepté le : 2025-03-29
Publié le : 2025-09-05

DOI : 10.5802/crmath.746

Keywords: Ulam sequence, $s$-additive sequence
Mots-clés : Suite d’Ulam, suites $s$-additives

Affiliations des auteurs :

François Clément ¹ ; Stefan Steinerberger ¹

¹ Department of Mathematics, University of Washington, Seattle, USA

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2025__363_G10_941_0,
     author = {Fran\c{c}ois Cl\'ement and Stefan Steinerberger},
     title = {Small gaps in the {Ulam} sequence},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {941--949},
     year = {2025},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {363},
     doi = {10.5802/crmath.746},
     language = {en},
}

TY  - JOUR
AU  - François Clément
AU  - Stefan Steinerberger
TI  - Small gaps in the Ulam sequence
JO  - Comptes Rendus. Mathématique
PY  - 2025
SP  - 941
EP  - 949
VL  - 363
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.746
LA  - en
ID  - CRMATH_2025__363_G10_941_0
ER  -

%0 Journal Article
%A François Clément
%A Stefan Steinerberger
%T Small gaps in the Ulam sequence
%J Comptes Rendus. Mathématique
%D 2025
%P 941-949
%V 363
%I Académie des sciences, Paris
%R 10.5802/crmath.746
%G en
%F CRMATH_2025__363_G10_941_0

François Clément; Stefan Steinerberger. Small gaps in the Ulam sequence. Comptes Rendus. Mathématique, Volume 363 (2025), pp. 941-949. doi: 10.5802/crmath.746

Bibliographie
Cité par

[1] Paul Adutwum; Clark Hopper; Emerson Ro; Alexandra Sheydvasser; Arseniy Sheydvasser; Axelle Tougouma Distributions of Ulam words up to length 30 (2024) | arXiv

[2] Rodrigo Angelo A hidden signal in Hofstadter’s $H$ sequence (2022) | arXiv | Zbl

[3] Tej Bade; Kelly Cui; Antoine Labelle; Deyuan Li Ulam sets in new settings, Integers, Volume 20 (2020), A102, 40 pages | MR | Zbl

[4] Vincent D. Blondel; John N. Tsitsiklis The boundedness of all products of a pair of matrices is undecidable, Syst. Control Lett., Volume 41 (2000) no. 2, pp. 135-140 | DOI | MR | Zbl

[5] Julien Cassaigne; Steven R. Finch A class of 1-additive sequences and quadratic recurrences, Exp. Math., Volume 4 (1995) no. 1, pp. 49-60 | MR | DOI | Zbl

[6] Steven R. Finch Conjectures about $s$ -additive sequences, Fibonacci Q., Volume 29 (1991) no. 3, pp. 209-214 | MR | DOI | Zbl

[7] Steven R. Finch On the regularity of certain 1-additive sequences, J. Comb. Theory, Ser. A, Volume 60 (1992) no. 1, pp. 123-130 | DOI | MR | Zbl

[8] Steven R. Finch Patterns in 1-additive sequences, Exp. Math., Volume 1 (1992) no. 1, pp. 57-63 | MR | Zbl

[9] Steven R. Finch Unsolved problems: are 0-additive sequences always regular?, Am. Math. Mon., Volume 99 (1992) no. 7, pp. 671-673 | DOI | MR | Zbl

[10] Izrailʹ Moiseevich Gelfand Normierte Ringe, Mat. Sb., N. Ser., Volume 9/51 (1941), pp. 3-24 | MR | Zbl

[11] Joshua Hinman; Borys Kuca; Alexander Schlesinger; Arseniy Sheydvasser Rigidity of Ulam sets and sequences, Involve, Volume 12 (2019) no. 3, pp. 521-539 | DOI | MR | Zbl

[12] Joshua Hinman; Borys Kuca; Alexander Schlesinger; Arseniy Sheydvasser The unreasonable rigidity of Ulam sequences, J. Number Theory, Volume 194 (2019), pp. 409-425 | MR | DOI | Zbl

[13] Noah Kravitz; Stefan Steinerberger Ulam sequences and Ulam sets, Integers, Volume 18 (2018), A80, 22 pages | MR | Zbl

[14] Borys Kuca Structures in additive sequences, Acta Arith., Volume 186 (2018) no. 3, pp. 273-300 | DOI | MR | Zbl

[15] Andrei Mandelshtam On fractal patterns in Ulam words (2022) | arXiv | Zbl

[16] R. Daniel Mauldin; Stanisław Marcin Ulam Mathematical problems and games, Adv. Appl. Math., Volume 8 (1987) no. 3, pp. 281-344 | Zbl | DOI | MR

[17] Raymond Queneau Sur les suites $s$ -additives, C. R. Math., Volume 266 (1968), p. A957-A958 | MR | Zbl

[18] Raymond Queneau Sur les suites $s$ -additives, J. Comb. Theory, Ser. A, Volume 12 (1972), pp. 31-71 | DOI | MR | Zbl

[19] Raymond Queneau Morale élémentaire, Gallimard, 1975, 146 pages

[20] Bernardo Recaman Research problems: questions on a sequence of Ulam, Am. Math. Mon., Volume 80 (1973) no. 8, pp. 919-920 | MR | DOI

[21] Gian-Carlo Rota; Gilbert Strang A note on the joint spectral radius, Indag. Math., Volume 22 (1960), pp. 379-381 | DOI | Zbl | MR

[22] James Schmerl; Eugene Spiegel The regularity of some 1-additive sequences, J. Comb. Theory, Ser. A, Volume 66 (1994) no. 1, pp. 172-175 | DOI | MR | Zbl

[23] Arseniy Sheydvasser The Ulam sequence of linear integer polynomials, J. Integer Seq., Volume 24 (2021) no. 10, 21.10.8, 23 pages | MR | Zbl

[24] Stefan Steinerberger A hidden signal in the Ulam sequence, Exp. Math., Volume 26 (2017) no. 4, pp. 460-467 | DOI | MR | Zbl

[25] Stanisław Marcin Ulam On some mathematical problems connected with patterns of growth of figures, Proceedings of Symposia in Applied Mathematics. Vol. XIV. Mathematical problems in the biological sciences, American Mathematical Society (1962), pp. 215-224 | MR

[26] Stanisław Marcin Ulam Combinatorial analysis in infinite sets and some physical theories, SIAM Rev., Volume 6 (1964), pp. 343-355 | DOI | MR | Zbl

Cité par Sources :

Commentaires - Politique