WorksMathematics
The Ulam sequence grows subexponentially
Abstract
We prove that the -th element of the Ulam sequence, a somewhat mysterious recursively-defined sequence of positive integers, has size ; previous upper bounds were exponential in . Our argument uses an additive-combinatorial lemma, possibly of independent interest, about covering finite difference sets with multiplicatively short intervals. The proofs are due to ChatGPT.
Introduction
In 1964, Stanislaw Ulam [11] introduced the following curious integer sequence that has since come to be known as the Ulam sequence. Start with and ; then, for each , let be the smallest integer greater than that has a unique representation as a sum of two distinct previous elements of the sequence. The first few terms of the Ulam sequence are
Write for the set of all of the elements of the Ulam sequence.
Despite the simplicity of Ulam’s definition, the behavior of the sequence is somewhat erratic and mysterious. Even the asymptotic growth rate remains unknown. Computations in the 1960’s initially suggested that might grow super-linearly in , but more extensive recent computations indicate that a linear growth rate is more likely. For more on this problem’s surprisingly extensive historical background, see the discussions in [4, 10] (see also [1, 6, 7, 8] for some generalizations to settings other than the integers).
The trivial upper bound, from the observation , is that is at most the -th Fibonacci number. This is an exponential upper bound, where the base of the exponential is the golden ratio (around 1.618). Successive improvements reduced the base of the exponential, with the record of 1.454 due to Clément and Steinerberger in 2025 [4]. ChatGPT (see AI statement below) has provided a short and clever argument for a subexponential upper bound.
Theorem 1.1. There is a constant such that for all .
The proof uses only the following two properties of the Ulam sequence:
consecutive elements of have quotient at most 2;
every element of has either zero or at least two different representations as a sum of two distinct elements of .
In particular, the argument uses only the fact that the Ulam sequence includes every positive integer with a unique representation as a sum of two distinct smaller elements of the sequence, and it does not make use of the fact that the Ulam sequence omits every positive integer with multiple representations as a sum of two distinct smaller elements of the sequence. The set of positive integers with at most two 1’s in their binary expansions also satisfies the two bullet-pointed conditions, and its -th smallest element is . So to obtain a qualitatively stronger result, one would have to make essential use of the omission from of integers with multiple representations in .
The proof idea, in a nutshell, is to show that if has many large gaps in the interval , then it also contains many elements either moderately smaller than or slightly larger than ; in other words, if has many sparse spots at a given scale, then it must have some dense spots nearby. One then averages this statement over different choices of .
Additive-combinatorial input
The proof of Theorem 1.1 makes use of an independently interesting additive-combinatorial fact about covering finite difference sets with multiplicatively short intervals.
Proposition 2.1. There is a constant such that the following holds. Let , and let be a finite set. Then can be covered by at most
intervals of the form .
We remark that for our application to Theorem 1.1, it would suffice to have a bound of the form for any fixed . The quantitative dependence in the conclusion of the proposition is tight up to a constant factor; see Appendix § 4 for a matching construction.
One can interpret as the set of distances among the elements of . Proposition 2.1 also applies, with essentially an identical proof, to the more general setting of metric spaces: The set of (nonzero) distances among the elements of a finite set in a metric space can be covered by intervals of the form .
A precursor of Proposition 2.1 appears in an influential 1995 paper of Callahan and Kosaraju [3], which implies the proposition with replaced by . Some thematically similar ideas appear in the work of Bourgain [2] on the discretized sum-product problem (see also [5]).
A simpler result
Proposition 2.1 is most interesting for tending to 0. The range of constant can be handled by a simpler argument. Say that a finite set of real numbers is dissociated if all of its subset sums are distinct. The additive dimension of a set is the largest size of a dissociated subset. We observe that if are finite sets, then has additive dimension at most . To see this, let
be a dissociated subset of . Consider the bipartite graph on the vertex set , where are adjacent for each . We claim that this graph is acyclic. Indeed, any cycle would (after relabeling) correspond to a relation of the form
for some , but this is impossible by dissociativity. Thus the graph is a forest, and its number of edges is at most , as desired. (A similar idea appears in [9].)
An immediate consequence of this observation is that can be covered by at most intervals of the form . Indeed, in a left-to-right greedy disjoint covering by such intervals, taking the smallest element of in each interval gives a dissociated set, so the number of such intervals is at most . Moreover, each interval can be covered by intervals of the form , so more generally can be covered by intervals of the form . The point of Proposition 2.1 is improving the dependence. (To obtain an asymmetric statement about , one can apply Proposition 2.1 with playing the role of .)
Proof of the proposition
We finally turn to the proof of Proposition 2.1. The new character entering our story here is , the minimum number of intervals of the form needed to cover the set . We analyze at different scales one at a time. Let . Suppose we want to understand the elements of for some . Such elements can be written as , where differ by around . Take a covering of by intervals of length . Then must lie in different intervals. If instead we want to cover by intervals of length , then we can use one long interval to cover both of the short intervals that originally covered . So elements of at scale force to be smaller than .
We will see that even though a single “merging” of length- intervals into a length- interval can correspond to many elements of , it cannot correspond to too many multiplicatively -separated elements of . Making this argument precise yields that every multiplicatively -separated subset of has size
Summing over gives a telescoping sum that yields a further factor of . The details follow.
Proof of Proposition 2.1. Define the scale
Let , and consider . Extract a maximum-size multiplicatively -separated subset of greedily from left to right. Then is additively -separated, and is covered by the intervals of the form for .
Take a covering
of by intervals of length , listed from left to right. Each element of is contained in for some ; fix one such pair for each element of . Since is an interval of length , it contains at most one element of . So we have exactly distinct pairs associated to the elements of . Consider the graph on the vertex set with this edge set. Within each connected component of , consecutive intervals have their left endpoints at most apart. So the intervals in a connected component of size can be covered by at most intervals of length . Note that for . Since has edges in total, its connected components of size at least 2 must together span at least (say) vertices. It follows that
At the same time, we trivially have by multiplicative volume-packing. Thus
Summing over , we find that can be covered with
intervals of the form . Note that for sufficiently large, and for sufficiently small. So the previous sum telescopes to
as desired. □
Note that our choice of was dictated by the constraint in the second paragraph of the proof. For a smaller choice of , one would need to replace the “short” scale with for some large enough that . Then our volume-packing upper bound would be , and the final telescoping step would pick up a factor instead of 3. Carrying through these changes would lead to a bound of the shape
where the two terms are balanced when .
Proof of Theorem 1.1
Throughout this section, fix a large positive integer . We will upper-bound .
Large and small gaps
We start from the telescoping identity
It is natural to look at multiplicative telescoping (rather than additive telescoping) since we are working on a scale that is closer to exponential than to polynomial. Note that every . Our main business will be showing that is rarely large. To this end, define the sets
for , which record which ’s are preceded by large gaps. We now rewrite our telescoping identity as
where in passing to the third line we changed variables to . We will show that
(see Lemma 3.2 below), whence we will conclude that
since the integral converges (for this convergence, we care only that the power of is below 1).
The key combinatorial step
Fix . The crux is obtaining an upper bound on in terms of the number of elements of near . To do this, we show that many sums with can fail to be in only if other elements of cluster around .
Lemma 3.1. Let . Then
Proof. We can trivially bound
since the elements of are separated by multiplicative factors of at least . We now restrict our attention to the elements .
The number of such ’s with is at most
For the remaining ’s, there are two ways that could fail to be in . First, consider the ’s where fails to be in because has a second representation in with one summand greater than . We obtain an expression
for some with . Note that in fact
since has a large gap before it. The number of such ’s is trivially at most due to the constraints and . Each corresponds to values of contained in the interval , and the number of such ’s is by the multiplicative separation of . Summing over the choices of gives a total contribution of
Second, consider the ’s where fails to be in because has a second representation in with both summands smaller than . We obtain an expression
for some distinct with . From we see that and hence also (since ). So is contained in the difference set for
Proposition 2.1 tells us that the set of such ’s can be covered by
intervals of the form . Each such interval contains at most a single , again due to multiplicative separation.
We obtain the conclusion of the lemma by summing the final centered expressions from the previous four paragraphs and noting that . □
One can understand this lemma conceptually as follows. The element can fail to be in only if it has another representation in as either or for some positive . The large gaps before (due to ) force to be somewhat large. This in turn restricts to a fairly small set, where “fairly small” depends on the elements of near .
Clean-up
Lemma 3.1 gives information about near a single element . Summing over and rearranging yields the desired upper bound on .
Lemma 3.2. We have .
Proof. Let denote the elements of . Apply Lemma 3.1 for and sum over to obtain
For the first sum, swapping the order of summation gives
as usual due to the multiplicative separation of . For the second sum, notice that the intervals are disjoint (since all elements of are preceded by long gaps) and contained in . Thus
We conclude that
and the result follows on taking square roots.
We described at the beginning of this section how Theorem 1.1 follows from Lemma 3.2.
Tightness of Proposition 2.1
In this appendix we demonstrate the tightness of Proposition 2.1. For brevity, let denote the minimum number of intervals of the form needed to cover .
We first record that if are finite sets satisfying
then
since no interval can simultaneously contain points of both . In particular, given , there is some such that for all positive integers , we have
This shows that once we have a single example for which Proposition 2.1 is tight up to constants, we can produce larger examples with the same property (for the same value of ).
To see that is the necessary power of in the proposition, one can take and consider the -element set
which has . Obtaining the further factor of requires more care, as follows.
Let be a large positive integer. Set , and define the set
The first constituent part of is an arithmetic progression at a small scale, and the second constituent is essentially a perturbation of a geometric progression at a large scale. Our set has size
Consider the elements of of the form
Note that subsists at scale . In particular, elements with different values of are multiplicatively separated by factors of at least , so they must be covered by disjoint sets of intervals .
Fix a single value of , and let vary. We claim that the resulting elements are all distinct. Indeed, if , then rearranging gives
The coprimality of (since is odd) implies that divides . But then in fact , and thence also , as desired. Next, the number is rational with denominator dividing . So different choices of give elements that are additively -separated and hence multiplicatively -separated for the choice
We conclude that is at least the total number of elements . This gives
which matches the bound in Proposition 2.1 up to a constant factor. Note that in this construction.
Acknowledgments and AI statement
The author was supported in part by a NSF Mathematical Sciences Postdoctoral Research Fellowship under grant DMS-2501336.
With minimal substantive human input, ChatGPT 6 successively produced upper bounds for of the shape , then , and finally . The argument initially made do with a suboptimal form of the crucial Proposition 2.1, and further prompting produced the sharp form of this proposition. For this human-written note, I refashioned all of the proofs by hand and added commentary and motivation.
References
St John’s College, Oxford and Mathematical Institute, University of Oxford; St Giles’, Oxford OX1 3JP, UK
Email address: [email protected]
References
- [1]T. Bade, K. Cui, A. Labelle, and D. Li, Ulam sets in new settings. Integers, 20 (2020), #A102.arxiv.org/abs/2008.02762
- [2]J. Bourgain, On the Erdős–Volkmann and Katz–Tao ring conjectures. GAFA, 13 (2003), 334–365.DOI
- [3]P. B. Callahan and S. Rao Kosaraju, A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields. Journal of the Association of Computing Machinery (JACM), 42.1 (1995), 67–90.DOI
- [4]F. Clément and S. Steinerberger, Small gaps in the Ulam sequence. C. R. Math. Acad. Sci. Paris, 363 (2025), 941–949.arxiv.org/abs/2501.16285
- [5]L. Guth, N. H. Katz, and J. Zahl, On the discretized sum-product problem. IMRN, 13 (2021), 9769–9785.
- [6]J. Jinman, B. Kuca, A. Schlesinger, and A. Sheydvasser, The unreasonable rigidity of Ulam sequences. J. Number Theory, 194 (2019), 409–425.
- [7]N. Kravitz and S. Steinerberger, Ulam sequences and Ulam sets. Integers 18 (2018), #A80.
- [8]A. Mandelshtam, On fractal patterns in Ulam words. Adv. Appl. Math., 172 (2026), #102954.arxiv.org/abs/2211.14229
- [9]I. D. Shkredov and S. Yekhanin, Sets with large additive energy and symmetric sets. JCTA, 118.3 (2011), 1086–1093.arxiv.org/abs/1004.2294
- [10]S. Steinerberger, A Hidden Signal in the Ulam Sequence. Experiment. Math., 26.4 (2017), 460–467.arxiv.org/abs/1507.00267
- [11]S. Ulam, Combinatorial analysis in infinite sets and some physical theories. SIAM Rev., 6.4 (1964), 343–355.DOI