Small gaps in the Ulam sequence

Fran\c{c}ois Cl\'ement; Stefan Steinerberger

REVIEW 2 major objections 5 minor 26 references

Small gaps in the Ulam sequence

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The Ulam sequence is forced to contain small ratio gaps, and its growth is bounded by 1.454^n.

desk verdict A real but modest improvement on the Ulam growth bound plus a small-gap theorem, with Theorem 1's constant resting on an unreported finite computation that needs to be made reproducible. read the letter →

arxiv 2501.16285 v1 pith:2XEYPZPC submitted 2025-01-27 math.CO

François Clément , Stefan Steinerberger This is my paper · ORCID

classification math.CO MSC 11B8315A60

keywords Ulamsequences-additivesequencessmallgapsgrowthboundjointspectralradiuspigeonholecountingoperatornormscombinatorialnumbertheory

topics The Collatz Conjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The Ulam sequence (1, 2, 3, 4, 6, 8, 11, ...) is built by repeatedly appending the smallest integer that can be written as a sum of two distinct earlier terms in exactly one way. This paper proves that, for every n, at least one of the first n ratios a_{k+1}/a_k is at most 1 + c log n / n, with c = 7 for large n. It also improves the known upper bound on the nth term from 1.466^n to 1.454^n. These results are steps toward the conjecture that the sequence grows only linearly, which remains open.

What carries the argument

For the growth bound, the central machinery consists of the three linear recurrences Type I (b_{n+1} = b_n + b_{n-3}), Type II (b_{n+1} = b_{n-1} + b_{n-2}), and Eggleton (b_{n+1} = b_n + b_{n-2}), written as 4×4 matrices T1, T2, T3. Submultiplicativity of the operator norm reduces the joint spectral radius over admissible words (where Eggleton cannot be repeated consecutively) to a finite check of all admissible words of length 15, yielding the constant 1.4539. For the small-gap theorem, the load-bearing mechanism is a pigeonhole count: the assumption that all early ratios exceed 1+δ forces many candidate sums a_n + a_i to fall into a short interval, while the number of alternative representations a_j + a_k that could block them is bounded by a δ-dependent quantity; these bounds contradict each other unless δ ≤ c log n / n.

What would settle it

Independently enumerate all admissible words of length 15 over T1, T2, T3, compute the operator norm of each product (a finite, explicit computation), and check whether the maximum 15th root is indeed ≤ 1.4539; any larger value invalidates the proof of Theorem 1.

Watch

Extended reading notes

Core claim

The paper establishes a small-gap theorem: there is a constant c (the proof gives c = 7 eventually) such that for every n one has min_{1≤k≤n} a_{k+1}/a_k ≤ 1 + c log n / n. It also improves the best growth bound to a_n ≤ 1.454^n for all sufficiently large n. The growth bound is obtained by showing that Eggleton's recurrence cannot be applied twice in a row, leaving three possible linear recurrences whose products are controlled through submultiplicativity of operator norms and a finite check over all admissible words of length 15. The small-gap result is obtained by a counting argument that compares candidate sums a_n + a_i with alternative representations a_j + a_k.

Load-bearing premise

The numerical factor 1.4539 in Section 2 is obtained by 'checking all admissible words' of length 15 over the three matrices T1, T2, T3, and the paper does not specify the enumeration procedure, provide code, or list the full table of operator norms; if that finite computation contains an error, the stated constant 1.454 in Theorem 1 is not established.

Editorial extensions

If this is right

No product of admissible words from the three recurrences grows faster than 1.454^n, so any future improvement must go beyond these recurrences.
For every sufficiently large n, some ratio a_{k+1}/a_k is below 1 + 7 log n / n, so relative gaps of size O(log n / n) are unavoidable.
If the Ulam sequence grows linearly as conjectured, this small-gap bound is sharp up to the logarithmic factor.
The spectral-radius lower bound from the word T3 T1^2 shows the present method cannot prove a_n ≤ ρ^n for any ρ < 1.4146.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The counting argument for small gaps likely carries over to other 1-additive sequences with subexponential growth, provided their early terms satisfy similar density estimates.
Making the length-15 word enumeration reproducible with explicit code and tables would remove the one non-transparent step in Theorem 1.
An exact computation of the joint spectral radius of the three matrices might reveal an asymptotically periodic extremal word, which would suggest a route toward subexponential growth.
The small-gap theorem offers a quantitative obstruction to 'clump-and-gap' structures, which may be useful for classifying other Ulam-like sequences.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The two theorems are both genuine advances. Theorem 1 improves the longstanding 1.466^n upper bound to 1.454^n, and the matrix-product reduction with the no-33 admissibility condition is a clever way to exploit the fact that Eggleton's bound cannot hold twice in a row. Theorem 2 is a clean pigeonhole/counting argument that gives an explicit c=7, and the proof appears self-contained and correct. The paper is honest about its limits: the method cannot prove a bound below 1.4146, and the small-gap statement does not rule out exponential growth.

The soft spot is where the reader and the stress-test note land: the numerical constant 1.4539 in Section 2 is obtained by "checking all admissible words" of length 15, but no code, pseudocode, or table of operator norms is supplied. The displayed extremal word W has only 13 letters, not 15, which looks like a transcription slip but makes the whole computation impossible to verify from the text. Since that constant is load-bearing for Theorem 1, the theorem is not independently checkable as written. This is a specific, addressable gap, not a fundamental flaw. The structural argument is sound, and the counting proof in Theorem 2 stands on its own.

I largely agree with the reader's conditional verdict. The paper deserves a serious referee, but the referee should ask for the enumeration script or a table of norms for all admissible length-15 words. That is a minor-to-moderate revision, not a rejection. The citation pattern looks fine; the prior work is cited appropriately, and the new contribution is clear.

Who gets value from this? Specialists in Ulam sequences and people working on growth of s-additive sequences. It is not a breakthrough that changes the big picture, but it is a solid, honest step forward on a notoriously intractable problem. I would send it to peer review, and if the computational artifact is supplied, I would happily see it published.

Referee Report

2 major / 5 minor

Summary. The paper studies the Ulam sequence a_1=1, a_2=2, ... defined by adding the smallest integer that is uniquely representable as the sum of two distinct earlier terms. It claims two results: Theorem 1 improves the known growth bound to a_n ≤ 1.454^n for all sufficiently large n, down from the previous 1.466^n bound; Theorem 2 shows that for some c>0, min_{1≤k≤n} a_{k+1}/a_k ≤ 1 + c log n / n, with c=7 admissible for large n. The proof of Theorem 2 is a self-contained counting argument: assuming all ratios up to n exceed 1+δ, the paper counts many candidate sums a_n+a_i lying in a short interval and bounds the number of alternative representations, forcing δ ≤ c log n/n. The proof of Theorem 1 reduces the growth problem to bounding products of three 4×4 matrices T1, T2, T3 with the admissibility restriction that T3 cannot appear twice consecutively, and then invokes an exhaustive check of admissible words of length 15 to obtain the numerical constant.

Significance. If correct, Theorem 1 is a genuine if modest improvement over the Eggleton bound, and the reduction to an admissible-word joint-spectral-radius problem is an interesting technique. Theorem 2 is the more substantial contribution: it gives the first rigorous proof that arbitrarily small ratio gaps must occur somewhere among the first n terms, and the argument is elementary, explicit, and fully checkable. The credit for the paper rests mainly on Theorem 2, whose counting proof appears sound, and on the clean structural reduction in Section 2. The main weakness is that the numerical constant in Theorem 1 is asserted on the basis of a finite enumeration that is neither described nor supplied, so Theorem 1 as written is not reproducible.

major comments (2)

[Section 2, proof of Theorem 1] The claim 'Using this with L = 15 and checking all admissible words gives C ≤ 1.4539 . . .' is load-bearing for Theorem 1, but the manuscript provides no enumeration algorithm, no code, no table of computed norms, and no count of words checked. Moreover, the displayed extremal word W = (T3T1)^3(T1T3)^3T2 has length 13, not the announced L = 15. As written, the numerical constant 1.454 cannot be independently verified. Please supply a reproducible enumeration (code or a complete table/case analysis) and correct the length discrepancy, or explicitly state that the computation was performed with L = 13.
[Section 3, proof of Theorem 2] The step 'We require # {1 ≤ k < n : a_n + a_k ∈ [a_n, a_n + δ/2 a_n]} ≤ X' is stated without justification. The inequality is in fact a consequence of the definitions, since each candidate sum (n,i) corresponds to a distinct pair (i,n) counted in X; however, the proof does not explain this and the sentence reads like an assumption. Please clarify the subset/injection argument so that the subsequent contradiction is transparent.

minor comments (5)

[Section 3] There is a typo in 'for some j < k ≤ n = 1'; this should presumably read 'j < k ≤ n'.
[Section 3] The text refers to 'Figure 2', but only one figure ('Figure 1. Clumps followed by a big jump') is included; please renumber or add the missing figure.
[Section 2] The passage from block-length estimates to 'C ≤ max_admissible_word ||...||^{1/L}' glosses over the additive constant for products whose length is not a multiple of L; the statement should be phrased as a limsup or with an explicit constant that is absorbed for large n.
[Section 1.2 and Section 3] The statement of Theorem 2 says 'for all n ∈ N_{≥2}', while the proof only shows that c = 7 works for n sufficiently large; the finitely many small n should be checked explicitly or the theorem statement adjusted.
[Section 2, Lemma 1] In the proof of Lemma 1, the sentence 'we are only left with i = n − 3 which is too small' compresses the case analysis; adding a line explaining that j ≤ n−2 implies a_i + a_j ≤ a_{n−3} + a_{n−2} ≤ a_{n−1} + a_{n−2} would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: both theorems derive upper bounds from the Ulam uniqueness rule via Eggleton's bound and explicit counting; the unreported L=15 enumeration is a reproducibility issue, not circularity.

full rationale

The derivation chain is self-contained with respect to the paper's inputs. Theorem 1 constructs an upper-envelope sequence b_n with b_n = a_n for n ≤ 5 and defines b_{n+1} by the same Eggleton/Type-I/Type-II recursion used for a_{n+1}, or by an admissible Type-I/Type-II upper bound when a_{n+1} arises differently. The growth constant is then bounded by the joint spectral radius of the three matrices T1, T2, T3 subject to the admissibility rule that T3 cannot repeat. Nothing is fitted to Ulam data: the operator norms are computed from the matrices encoding the recursions, and the extremal word is a candidate for the maximum, not a parameter fitted to the sequence. The only fragile step is the sentence 'Using this with L = 15 and checking all admissible words gives C ≤ 1.4539 . . . with the extremal word being W = (T3T1)^3(T1T3)^3T2', whose enumeration is not documented and whose displayed word has 13 letters rather than L=15; however, that is a reproducibility/computation gap, not a reduction of the conclusion to its inputs. Theorem 2 is an independent counting argument: under the temporary assumption that min_{k≤n} a_{k+1}/a_k = 1+δ, it counts candidate sums a_n+a_i and blocking representations a_j+a_k using only the δ-gap and the uniqueness of Ulam representations, then derives a contradiction for large n unless δ ≤ c log n/n. The bound c=7 is obtained by explicit inequalities, not by calibrating to known values of the Ulam sequence. No load-bearing self-citation occurs: the author's earlier work [23] and [13] is motivational/contextual, while Eggleton's bound, joint spectral radius, and Gelfand's formula are cited from external sources. I therefore find no circular step and score 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The results do not rely on fitted data or invented entities. Theorem 2 uses only the definition of Ulam sequence, elementary inequalities, and counting. Theorem 1 additionally uses standard facts about operator norms and a finite computer-assisted enumeration. The enumeration is the only load-bearing computational assumption.

assumptions (3)

domain assumption The Ulam sequence is infinite and every term is the smallest integer uniquely expressible as a sum of two distinct earlier terms.
Used throughout as the defining property of the sequence; the paper sketches the standard proof of infinitude.
standard math Submultiplicativity of the operator norm and the Gelfand formula for spectral radius.
Invoked in Section 2 to convert a finite check over length-15 matrix words into a global growth bound for all n.
ad hoc to paper The exhaustive enumeration of all admissible words of length 15 over T1,T2,T3 is error-free and yields the claimed maximum operator norm 1.4539...
This computational step is load-bearing for Theorem 1, but the paper does not provide code, a script, or a full table of norms to verify it independently.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Small gaps in the Ulam sequence." pith.science (2026). https://pith.science/paper/2XEYPZPC

@misc{pith2026250116285,
  author       = {Pith},
  title        = {Pith review of: Small gaps in the Ulam sequence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2XEYPZPC}},
  note         = {Machine review of arXiv:2501.16285}
}

abstract

The Ulam sequence, described by Stanislaw 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 which has inspired a great deal of work; nonetheless, very little is rigorously proven. We improve the best upper bound on its growth and show that at least some small gaps have to exist: for some $c>0$ and all $n \in \mathbb{N}$ $$ \min_{1 \leq k \leq n} \frac{a_{k+1}}{a_k} \leq 1 + c\frac{\log{n}}{n}.$$

Figures

Figures reproduced from arXiv: 2501.16285 by the authors.

**Figure 1.** ‘Clumps’ followed by a big jump. References [1] P. Adutwum, C. Hopper, E. Ro and A. Tougouma, Distributions of Ulam Words up to Length 30, arXiv preprint arXiv:2410.01217 (2024). [2] R. Angelo, A hidden signal in Hofstadter’s H sequence. arXiv preprint arXiv:2206.00750. [3] T. Bade, K., Cui, A. Labelle and D. Li, Ulam Sets in New Settings, Integers (20), 2020. [4] Vincent D. Blondel, John N. Tsitsiklis, The boundedn… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

[1]

Distributions of Ulam Words up to Length 30

P. Adutwum, C. Hopper, E. Ro and A. Tougouma, Distributio ns of Ulam W ords up to Length 30, arXiv preprint arXiv:2410.01217 (2024)

work page Pith review arXiv 2024
[2]

A hidden signal in Hofstadter's $H$ sequence

R. Angelo, A hidden signal in Hofstadter’s H sequence. arXiv preprint arXiv:2206.00750

work page Pith review arXiv
[3]

Bade, K., Cui, A

T. Bade, K., Cui, A. Labelle and D. Li, Ulam Sets in New Sett ings, Integers (20), 2020

work page 2020
[4]

Blondel, John N

Vincent D. Blondel, John N. Tsitsiklis, The boundedness of all products of a pair of matrices is undecidable, Systems and Control Letters, 41:2, pp. 135– 140, 2000

work page 2000
[5]

Cassaigne and S

J. Cassaigne and S. Finch, A class of 1-additive sequence s and quadratic recurrences. Experi- ment. Math. 4 (1995), no. 1, 49-60

work page 1995
[6]

Finch, Conjectures about s-additive sequences

S. Finch, Conjectures about s-additive sequences. Fibo nacci Quart. 29 (1991), no. 3, 209-214

work page 1991
[7]

Finch, Patterns in 1-additive sequences

S. Finch, Patterns in 1-additive sequences. Experiment . Math. 1 (1992), no. 1, 57-63

work page 1992
[8]

Finch, On the regularity of certain 1-additive sequen ces

S. Finch, On the regularity of certain 1-additive sequen ces. J. Combin. Theory Ser. A 60 (1992), no. 1, 123-130

work page 1992

Show all 26 references

[9]

Finch, Are 0-Additive Sequences Always Regular? The A merican Mathematical Monthly, vol

S. Finch, Are 0-Additive Sequences Always Regular? The A merican Mathematical Monthly, vol. 99 (1992), p. 671-673

1992
[10]

Gelfand, Normierte ringe, Rech

I. Gelfand, Normierte ringe, Rech. Math. [Mat. Sbornik ] N.S. 9 (51) (1941) 3–24

1941
[11]

Hinman, B

J. Hinman, B. Kuca, A. Schlesinger & A. Sheydvasser, The unreasonable rigidity of Ulam sequences. Journal of Number Theory, 194, 409-425
[12]

Hinman, B

J. Hinman, B. Kuca, A. Schlesinger & A. Sheydvasser,. Ri gidity of Ulam sets and sequences. Involve, a Journal of Mathematics, 12(3), 521-539
[13]

Kravitz and S

N. Kravitz and S. Steinerberger, Ulam sequences and Ula m sets, Integers 18 (2018)

2018
[14]

Kuca, Structures in additive sequences, Acta Arith

B. Kuca, Structures in additive sequences, Acta Arith. 186.3 (2018), 273–300

2018
[15]

Mandelshtam, On fractal patterns in Ulam words

A. Mandelshtam, On fractal patterns in Ulam words. arXi v preprint arXiv:2211.14229

arXiv
[16]

R. D. Mauldin and S. M. Ulam, Mathematical problems and g ames. Advances in Applied Mathematics, 8 (1987), p. 281-344

1987
[17]

Queneau, Sur les suites s-additives

R. Queneau, Sur les suites s-additives. C. R. Acad. Sci. Paris S´ er. A-B 266 (1968), A957–A958

1968
[18]

Queneau, Sur les suites s-additives, J

R. Queneau, Sur les suites s-additives, J. Combinatori al Theory Ser. A 12 (1972), 31-71

1972
[19]

Recaman, Research Problems: Questions on a Sequence of Ulam

B. Recaman, Research Problems: Questions on a Sequence of Ulam. Amer. Math. Monthly 80 (1973), 919-920

1973
[20]

G. C. Rota and G. Strang, A note on the joint spectral radi us, Proceedings of the Netherlands Academy, 22:379–381, 1960

1960
[21]

Schmerl and E

J. Schmerl and E. Spiegel, The regularity of some 1-addi tive sequences. J. Combin. Theory Ser. A 66 (1994), no. 1, 172-175

1994
[22]

Sheydvasser, The Ulam Sequence of Linear Integer Pol ynomials

A. Sheydvasser, The Ulam Sequence of Linear Integer Pol ynomials. Journal of Integer Se- quences, 24 (2021), 3

2021
[23]

Steinerberger, A hidden signal in the Ulam sequence

S. Steinerberger, A hidden signal in the Ulam sequence. Experimental Mathematics, 26 (2017), 460-467. 8

2017
[24]

Ulam, Ulam, On some mathematical problems connected with patterns of growth of ﬁgures

S. Ulam, Ulam, On some mathematical problems connected with patterns of growth of ﬁgures. In Proceedings of symposia in applied mathematics (Vol. 14, No. 14, pp. 215-224). Providence: Am. Math. Soc. Vol. 14, 1962

1962
[25]

Ulam, Combinatorial analysis in inﬁnite sets and som e physical theories

S. Ulam, Combinatorial analysis in inﬁnite sets and som e physical theories. SIAM Rev. 6 1964 343-355

1964
[26]

S. M. Ulam, Problems in Modern Mathematics. Science Edi tions John Wiley & Sons, Inc., New York 1964 Department of Mathematics, University of W ashington, Seatt le Email address : fclement@uw.edu Email address : steinerb@uw.edu

1964

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Distributions of Ulam Words up to Length 30

P. Adutwum, C. Hopper, E. Ro and A. Tougouma, Distributio ns of Ulam W ords up to Length 30, arXiv preprint arXiv:2410.01217 (2024)

work page Pith review arXiv 2024

[2] [2]

A hidden signal in Hofstadter's $H$ sequence

R. Angelo, A hidden signal in Hofstadter’s H sequence. arXiv preprint arXiv:2206.00750

work page Pith review arXiv

[3] [3]

Bade, K., Cui, A

T. Bade, K., Cui, A. Labelle and D. Li, Ulam Sets in New Sett ings, Integers (20), 2020

work page 2020

[4] [4]

Blondel, John N

Vincent D. Blondel, John N. Tsitsiklis, The boundedness of all products of a pair of matrices is undecidable, Systems and Control Letters, 41:2, pp. 135– 140, 2000

work page 2000

[5] [5]

Cassaigne and S

J. Cassaigne and S. Finch, A class of 1-additive sequence s and quadratic recurrences. Experi- ment. Math. 4 (1995), no. 1, 49-60

work page 1995

[6] [6]

Finch, Conjectures about s-additive sequences

S. Finch, Conjectures about s-additive sequences. Fibo nacci Quart. 29 (1991), no. 3, 209-214

work page 1991

[7] [7]

Finch, Patterns in 1-additive sequences

S. Finch, Patterns in 1-additive sequences. Experiment . Math. 1 (1992), no. 1, 57-63

work page 1992

[8] [8]

Finch, On the regularity of certain 1-additive sequen ces

S. Finch, On the regularity of certain 1-additive sequen ces. J. Combin. Theory Ser. A 60 (1992), no. 1, 123-130

work page 1992