betaFeedback

WorksMathematics

The Ulam sequence grows subexponentially

Abstract

We prove that the nn-th element of the Ulam sequence, a somewhat mysterious recursively-defined sequence of positive integers, has size eO(n)e^{O(\sqrt{n})}; previous upper bounds were exponential in nn. 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 u1:=1u_1 := 1 and u2:=2u_2 := 2; then, for each n≥3n \ge3, let unu_n be the smallest integer greater than un−1u_{n-1} 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

1,2,3,4,6,8,11,13,16,18,26.1,2,3,4,6,8,11,13,16,18,26.

Write U:={u1,u2,u3,…}\mathcal{U} := \{u_1,u_2,u_3,\ldots\} for the set of all of the elements of the Ulam sequence.

Despite the simplicity of Ulam’s definition, the behavior of the sequence unu_n is somewhat erratic and mysterious. Even the asymptotic growth rate remains unknown. Computations in the 1960’s initially suggested that unu_n might grow super-linearly in nn, 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 un≤un−1+un−2u_n \le u_{n-1}+u_{n-2}, is that unu_n is at most the (n+1)(n+1)-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 C>0C > 0 such that un≤eCnu_n \le e^{C\sqrt{n}} for all nn.

The proof uses only the following two properties of the Ulam sequence:

  • consecutive elements of U\mathcal{U} have quotient at most 2;

  • every element of N∖U\mathbb{N} \setminus\mathcal{U} has either zero or at least two different representations as a sum of two distinct elements of U\mathcal{U}.

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 nn-th smallest element is 2O(n)2^{O(\sqrt{n})}. So to obtain a qualitatively stronger result, one would have to make essential use of the omission from U\mathcal{U} of integers with multiple representations in U+U\mathcal{U}+\mathcal{U}.

The proof idea, in a nutshell, is to show that if U\mathcal{U} has many large gaps in the interval [1,x][1,x], then it also contains many elements either moderately smaller than xx or slightly larger than xx; in other words, if U\mathcal{U} 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 xx.

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 C>0C > 0 such that the following holds. Let 0<ε≤0.990 < \varepsilon\le0.99, and let A⊆RA \subseteq\mathbb{R} be a finite set. Then (A−A)∩R>0(A - A) \cap\mathbb{R}_{>0} can be covered by at most

Cε−1/2(log⁡ε−1)1/2∣A∣C\varepsilon^{-1/2}(\log\varepsilon^{-1})^{1/2}|A|

intervals of the form [z,(1+ε)z)[z,(1+\varepsilon)z).

We remark that for our application to Theorem 1.1, it would suffice to have a bound of the form ε−1+γ∣A∣\varepsilon^{-1+\gamma}|A| for any fixed γ>0\gamma> 0. 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 (A−A)∩R>0(A-A)\cap\mathbb{R}_{>0} as the set of distances among the elements of AA. 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 AA in a metric space can be covered by O(ε−1/2(log⁡ε−1)1/2∣A∣)O(\varepsilon^{-1/2}(\log\varepsilon^{-1})^{1/2}|A|) intervals of the form [z,(1+ε)z)[z,(1+\varepsilon)z).

A precursor of Proposition 2.1 appears in an influential 1995 paper of Callahan and Kosaraju [3], which implies the proposition with ε−1/2(log⁡ε−1)1/2\varepsilon^{-1/2}(\log\varepsilon^{-1})^{1/2} replaced by ε−1\varepsilon^{-1}. 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 ε\varepsilon tending to 0. The range of constant ε\varepsilon 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 A,B⊆RA,B\subseteq\mathbb{R} are finite sets, then A−BA-B has additive dimension at most ∣A∣+∣B∣−1|A|+|B|-1. To see this, let

{a1−b1,…,am−bm}\{a_1-b_1,\ldots,a_m-b_m\}

be a dissociated subset of A−BA-B. Consider the bipartite graph on the vertex set A⊔BA\sqcup B, where ai,bia_i,b_i are adjacent for each 1≤i≤m1\le i\le m. We claim that this graph is acyclic. Indeed, any cycle would (after relabeling) correspond to a relation of the form

(a1−b1)−(a2−b2)+⋯+(a2ℓ−1−b2ℓ−1)−(a2ℓ−b2ℓ)=0(a_1-b_1)-(a_2-b_2)+\cdots+(a_{2\ell-1}-b_{2\ell-1})-(a_{2\ell}-b_{2\ell})=0

for some ℓ≤m/2\ell\le m/2, but this is impossible by dissociativity. Thus the graph is a forest, and its number mm of edges is at most ∣A∣+∣B∣−1|A|+|B|-1, as desired. (A similar idea appears in [9].)

An immediate consequence of this observation is that (A−B)∩R>0(A-B)\cap\mathbb{R}_{>0} can be covered by at most ∣A∣+∣B∣−1|A|+|B|-1 intervals of the form [z,2z)[z,2z). Indeed, in a left-to-right greedy disjoint covering by such intervals, taking the smallest element of A−BA-B in each interval gives a dissociated set, so the number of such intervals is at most ∣A∣+∣B∣−1|A|+|B|-1. Moreover, each interval [z,2z)[z,2z) can be covered by O(ε−1)O(\varepsilon^{-1}) intervals of the form [z,(1+ε)z)[z,(1+\varepsilon)z), so more generally (A−B)∩R>0(A-B)\cap\mathbb{R}_{>0} can be covered by O(ε−1(∣A∣+∣B∣))O(\varepsilon^{-1}(|A|+|B|)) intervals of the form [z,(1+ε)z)[z,(1+\varepsilon)z). The point of Proposition 2.1 is improving the ε\varepsilon dependence. (To obtain an asymmetric statement about A−BA-B, one can apply Proposition 2.1 with A∪BA\cup B playing the role of AA.)

Proof of the proposition

We finally turn to the proof of Proposition 2.1. The new character entering our story here is K(t)K(t), the minimum number of intervals of the form [z,z+t)[z,z+t) needed to cover the set AA. We analyze A−AA-A at different scales one at a time. Let R:=1000ε−1R:=1000\varepsilon^{-1}. Suppose we want to understand the elements of (A−A)∩[Ri,Ri+1)(A-A)\cap[R^i,R^{i+1}) for some i∈Zi\in\mathbb{Z}. Such elements can be written as a−ba-b, where a,b∈Aa,b\in A differ by around RiR^i. Take a covering of AA by K(Ri−1)K(R^{i-1}) intervals of length Ri−1R^{i-1}. Then a,ba,b must lie in different intervals. If instead we want to cover AA by intervals of length Ri+2R^{i+2}, then we can use one long interval to cover both of the short intervals that originally covered a,ba,b. So elements of A−AA-A at scale RiR^i force K(Ri+2)K(R^{i+2}) to be smaller than K(Ri−1)K(R^{i-1}).

We will see that even though a single “merging” of length-Ri−1R^{i-1} intervals into a length-Ri+2R^{i+2} interval can correspond to many elements of (A−A)∩[Ri,Ri+1)(A-A)\cap[R^i,R^{i+1}), it cannot correspond to too many multiplicatively (1+ε)(1+\varepsilon)-separated elements of (A−A)∩[Ri,Ri+1)(A-A)\cap[R^i,R^{i+1}). Making this argument precise yields that every multiplicatively (1+ε)(1+\varepsilon)-separated subset of (A−A)∩[Ri,Ri+1)(A-A)\cap[R^i,R^{i+1}) has size

≪ε−1/2(log⁡ε−1)1/2(K(Ri−1)−K(Ri+2)).\ll\varepsilon^{-1/2}(\log\varepsilon^{-1})^{1/2}\bigl(K(R^{i-1})-K(R^{i+2})\bigr).

Summing over i∈Zi\in\mathbb{Z} gives a telescoping sum that yields a further factor of ∣A∣|A|. The details follow.

Proof of Proposition 2.1. Define the scale

R:=100ε−1.R:=100\varepsilon^{-1}.

Let i∈Zi\in\mathbb{Z}, and consider (A−A)∩[Ri,Ri+1)(A-A)\cap[R^i,R^{i+1}). Extract a maximum-size multiplicatively (1+ε)(1+\varepsilon)-separated subset XiX_i of (A−A)∩[Ri,Ri+1)(A-A)\cap[R^i,R^{i+1}) greedily from left to right. Then XiX_i is additively εRi\varepsilon R^i-separated, and (A−A)∩[Ri,Ri+1)(A-A)\cap[R^i,R^{i+1}) is covered by the ∣Xi∣|X_i| intervals of the form [z,(1+ε)z)[z,(1+\varepsilon)z) for z∈Xiz\in X_i.

Take a covering

{I1,…,IK(Ri−1)}\{I_1,\ldots,I_{K(R^{i-1})}\}

of AA by intervals of length Ri−1R^{i-1}, listed from left to right. Each element of XiX_i is contained in Ij−IkI_j-I_k for some j<kj<k; fix one such pair (j,k)(j,k) for each element of XiX_i. Since Ij−IkI_j-I_k is an interval of length 2Ri−1<εRi2R^{i-1}<\varepsilon R^i, it contains at most one element of XiX_i. So we have exactly ∣Xi∣|X_i| distinct pairs (j,k)(j,k) associated to the elements of XiX_i. Consider the graph GG on the vertex set [K(Ri−1)][K(R^{i-1})] with this edge set. Within each connected component of GG, consecutive intervals have their left endpoints at most Ri+1+Ri−1<Ri+2−Ri−1R^{i+1}+R^{i-1}<R^{i+2}-R^{i-1} apart. So the intervals in a connected component of size s≥2s\ge2 can be covered by at most ⌈s/2⌉\lceil s/2\rceil intervals of length Ri+2R^{i+2}. Note that ⌈s/2⌉≤s−s/3\lceil s/2\rceil\le s-s/3 for s≥2s\ge2. Since GG has ∣Xi∣|X_i| edges in total, its connected components of size at least 2 must together span at least ∣Xi∣1/2|X_i|^{1/2} (say) vertices. It follows that

K(Ri+2)≤K(Ri−1)−∣Xi∣1/2/3.K(R^{i+2})\le K(R^{i-1})-|X_i|^{1/2}/3.

At the same time, we trivially have ∣Xi∣≪ε−1log⁡ε−1|X_i|\ll\varepsilon^{-1}\log\varepsilon^{-1} by multiplicative volume-packing. Thus

∣Xi∣≪ε−1/2(log⁡ε−1)1/2∣Xi∣1/2≪ε−1/2(log⁡ε−1)1/2(K(Ri−1)−K(Ri+2)).|X_i|\ll\varepsilon^{-1/2}(\log\varepsilon^{-1})^{1/2}|X_i|^{1/2}\ll\varepsilon^{-1/2}(\log\varepsilon^{-1})^{1/2}\bigl(K(R^{i-1})-K(R^{i+2})\bigr).

Summing over i∈Zi\in\mathbb{Z}, we find that (A−A)∩R>0(A-A)\cap\mathbb{R}_{>0} can be covered with

∑i∈Z∣Xi∣≪ε−1/2(log⁡ε−1)1/2∑i∈Z(K(Ri−1)−K(Ri+2))\sum_{i\in\mathbb{Z}}|X_i|\ll\varepsilon^{-1/2}(\log\varepsilon^{-1})^{1/2}\sum_{i\in\mathbb{Z}}\bigl(K(R^{i-1})-K(R^{i+2})\bigr)

intervals of the form [z,(1+ε)z)[z,(1+\varepsilon)z). Note that K(Ri)=1K(R^i)=1 for ii sufficiently large, and K(Ri)=∣A∣K(R^i)=|A| for ii sufficiently small. So the previous sum telescopes to

∑i∈Z(K(Ri−1)−K(Ri+2))=3(∣A∣−1)≪∣A∣,\sum_{i\in\mathbb{Z}}\bigl(K(R^{i-1})-K(R^{i+2})\bigr)=3(|A|-1)\ll|A|,

as desired. □

Note that our choice of RR was dictated by the constraint 2Ri−1<εRi2R^{i-1}<\varepsilon R^i in the second paragraph of the proof. For a smaller choice of RR, one would need to replace the “short” scale Ri−1R^{i-1} with Ri−hR^{i-h} for some hh large enough that 2Ri−h<εRi2R^{i-h}<\varepsilon R^i. Then our volume-packing upper bound would be ∣Xi∣≪ε−1log⁡R|X_i|\ll\varepsilon^{-1}\log R, and the final telescoping step would pick up a factor h+2h+2 instead of 3. Carrying through these changes would lead to a bound of the shape

∑i∈Z∣Xi∣≪ε−1/2(log⁡R)1/2(log⁡ε−1log⁡R+1)∣A∣,\sum_{i\in\mathbb{Z}}|X_i|\ll\varepsilon^{-1/2}(\log R)^{1/2}\left(\frac{\log\varepsilon^{-1}}{\log R}+1\right)|A|,

where the two terms are balanced when R=ε−Θ(1)R=\varepsilon^{-\Theta(1)}.

Proof of Theorem 1.1

Throughout this section, fix a large positive integer nn. We will upper-bound unu_n.

Large and small gaps

We start from the telescoping identity

log⁡un=∑i=2nlog⁡(ui/ui−1).\log u_n=\sum_{i=2}^{n}\log(u_i/u_{i-1}).

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 ui≤2ui−1u_i\le2u_{i-1}. Our main business will be showing that ui/ui−1u_i/u_{i-1} is rarely large. To this end, define the sets

S(δ):={ui:(1−δ)ui≥ui−1, i∈[2,n]}S(\delta):=\{u_i:(1-\delta)u_i\ge u_{i-1},\ i\in[2,n]\}

for 0<δ≤1/20<\delta\le1/2, which record which uiu_i’s are preceded by large gaps. We now rewrite our telescoping identity as

log⁡un=∑i=2nlog⁡(ui/ui−1)=∑i=2n∫1ui/ui−11x dx=∫12∣{2≤i≤n:ui/ui−1≥x}∣x dx=∫01/2∣S(δ)∣1−δ dδ≤2∫01/2∣S(δ)∣ dδ,\begin{aligned} \log u_n &=\sum_{i=2}^{n}\log(u_i/u_{i-1}) =\sum_{i=2}^{n}\int_{1}^{u_i/u_{i-1}}\frac{1}{x}\,dx\\ &=\int_{1}^{2}\frac{|\{2\le i\le n:u_i/u_{i-1}\ge x\}|}{x}\,dx\\ &=\int_{0}^{1/2}\frac{|S(\delta)|}{1-\delta}\,d\delta \le2\int_{0}^{1/2}|S(\delta)|\,d\delta, \end{aligned}

where in passing to the third line we changed variables to δ:=1−1/x\delta:=1-1/x. We will show that

∣S(δ)∣≪δ−3/4(log⁡δ−1)3/4⋅n|S(\delta)|\ll\delta^{-3/4}(\log\delta^{-1})^{3/4}\cdot\sqrt{n}

(see Lemma 3.2 below), whence we will conclude that

log⁡un≪2n∫01/2δ−3/4(log⁡δ−1)3/4 dδ≪n\log u_n\ll2\sqrt{n}\int_{0}^{1/2}\delta^{-3/4}(\log\delta^{-1})^{3/4}\,d\delta\ll\sqrt{n}

since the integral converges (for this convergence, we care only that the power of δ−1\delta^{-1} is below 1).

The key combinatorial step

Fix 0<δ≤1/20<\delta\le1/2. The crux is obtaining an upper bound on ∣S(δ)∩(0,x)∣|S(\delta)\cap(0,x)| in terms of the number of elements of U\mathcal{U} near xx. To do this, we show that many sums x+yx+y with y∈S(δ)∩(0,δx)y\in S(\delta)\cap(0,\delta x) can fail to be in U\mathcal{U} only if other elements of U\mathcal{U} cluster around xx.

Lemma 3.1. Let x∈S(δ)x\in S(\delta). Then

∣S(δ)∩(0,x)∣≪δ−1/2(log⁡δ−1)1/2⋅∣U∩(δx,x)∣+δ−1log⁡δ−1⋅∣U∩[x,(1+δ)x)∣.|S(\delta)\cap(0,x)|\ll\delta^{-1/2}(\log\delta^{-1})^{1/2}\cdot|\mathcal{U}\cap(\delta x,x)|+\delta^{-1}\log\delta^{-1}\cdot|\mathcal{U}\cap[x,(1+\delta)x)|.

Proof. We can trivially bound

∣S(δ)∩[δx,x)∣≤1+log⁡δ−1log⁡((1−δ)−1)≪δ−1log⁡δ−1,|S(\delta)\cap[\delta x,x)|\le1+\frac{\log\delta^{-1}}{\log((1-\delta)^{-1})}\ll\delta^{-1}\log\delta^{-1},

since the elements of SS are separated by multiplicative factors of at least (1−δ)−1(1-\delta)^{-1}. We now restrict our attention to the elements y∈S(δ)∩(0,δx)y\in S(\delta)\cap(0,\delta x).

The number of such yy’s with x+y∈Ux+y\in\mathcal{U} is at most

∣U∩(x,(1+δ)x)∣.|\mathcal{U}\cap(x,(1+\delta)x)|.

For the remaining yy’s, there are two ways that x+yx+y could fail to be in U\mathcal{U}. First, consider the yy’s where x+yx+y fails to be in U\mathcal{U} because x+yx+y has a second representation in U+U\mathcal{U}+\mathcal{U} with one summand greater than xx. We obtain an expression

x+y=(x+c)+(y−c)x+y=(x+c)+(y-c)

for some 0<c<y0<c<y with x+c,y−c∈Ux+c,y-c\in\mathcal{U}. Note that in fact

δy≤c<y\delta y\le c<y

since y∈S(δ)y\in S(\delta) has a large gap before it. The number of such cc’s is trivially at most ∣U∩(x,(1+δ)x)∣|\mathcal{U}\cap(x,(1+\delta)x)| due to the constraints x+c∈Ux+c\in\mathcal{U} and c<y<δxc<y<\delta x. Each cc corresponds to values of yy contained in the interval (c,δ−1c](c,\delta^{-1}c], and the number of such yy’s is ≪δ−1log⁡δ−1\ll\delta^{-1}\log\delta^{-1} by the multiplicative separation of S(δ)S(\delta). Summing over the choices of cc gives a total contribution of

≪δ−1log⁡δ−1⋅∣U∩(x,(1+δ)x)∣.\ll\delta^{-1}\log\delta^{-1}\cdot|\mathcal{U}\cap(x,(1+\delta)x)|.

Second, consider the yy’s where x+yx+y fails to be in U\mathcal{U} because x+yx+y has a second representation in U+U\mathcal{U}+\mathcal{U} with both summands smaller than xx. We obtain an expression

x+y=a+bx+y=a+b

for some distinct a,b∈Ua,b\in\mathcal{U} with a,b<xa,b<x. From x∈S(δ)x\in S(\delta) we see that a,b≤(1−δ)xa,b\le(1-\delta)x and hence also a,b>δxa,b>\delta x (since a+b>xa+b>x). So y=a−(x−b)y=a-(x-b) is contained in the difference set A−AA-A for

A:=(U∩(δx,x))∪(x−(U∩(δx,x))).A:=(\mathcal{U}\cap(\delta x,x))\cup(x-(\mathcal{U}\cap(\delta x,x))).

Proposition 2.1 tells us that the set of such yy’s can be covered by

≪δ−1/2(log⁡δ−1)1/2⋅∣U∩(δx,x)∣\ll\delta^{-1/2}(\log\delta^{-1})^{1/2}\cdot|\mathcal{U}\cap(\delta x,x)|

intervals of the form [z,(1+δ)z)[z,(1+\delta)z). Each such interval contains at most a single yy, 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 ∣U∩[x,(1+δ)x)∣=∣U∩(x,(1+δ)x)∣+1|\mathcal{U}\cap[x,(1+\delta)x)|=|\mathcal{U}\cap(x,(1+\delta)x)|+1. □

One can understand this lemma conceptually as follows. The element x+yx+y can fail to be in U\mathcal{U} only if it has another representation in U+U\mathcal{U}+\mathcal{U} as either (x+d)+(y−d)(x+d)+(y-d) or (x−d)+(y+d)(x-d)+(y+d) for some positive dd. The large gaps before x,yx,y (due to x,y∈Sx,y\in S) force dd to be somewhat large. This in turn restricts yy to a fairly small set, where “fairly small” depends on the elements of U\mathcal{U} near xx.

Clean-up

Lemma 3.1 gives information about U\mathcal{U} near a single element x∈S(δ)x\in S(\delta). Summing over x∈S(δ)x\in S(\delta) and rearranging yields the desired upper bound on ∣S(δ)∣|S(\delta)|.

Lemma 3.2. We have ∣S(δ)∣≪δ−3/4(log⁡δ−1)3/4⋅n|S(\delta)|\ll\delta^{-3/4}(\log\delta^{-1})^{3/4}\cdot\sqrt{n}.

Proof. Let x1<⋯<xRx_1<\cdots<x_R denote the elements of S(δ)S(\delta). Apply Lemma 3.1 for x=xjx=x_j and sum over 1≤j≤R−11\le j\le R-1 to obtain

(R−12)≪δ−1/2(log⁡δ−1)1/2∑j=1R−1∣U∩(δxj,xj)∣+δ−1log⁡δ−1∑j=1R−1∣U∩[xj,(1+δ)xj)∣.\left(\frac{R-1}{2}\right)\ll\delta^{-1/2}(\log\delta^{-1})^{1/2}\sum_{j=1}^{R-1}|\mathcal{U}\cap(\delta x_j,x_j)|+\delta^{-1}\log\delta^{-1}\sum_{j=1}^{R-1}|\mathcal{U}\cap[x_j,(1+\delta)x_j)|.

For the first sum, swapping the order of summation gives

∑j=1R−1∣U∩(δxj,xj)∣=∑k=1n∣{j≤R−1:uk<xj<δ−1uk}∣≪nδ−1log⁡δ−1,\sum_{j=1}^{R-1}|\mathcal{U}\cap(\delta x_j,x_j)|=\sum_{k=1}^{n}|\{j\le R-1:u_k<x_j<\delta^{-1}u_k\}|\ll n\delta^{-1}\log\delta^{-1},

as usual due to the multiplicative separation of S(δ)S(\delta). For the second sum, notice that the intervals [xj,(1+δ)xj)[x_j,(1+\delta)x_j) are disjoint (since all elements of SS are preceded by long gaps) and contained in [1,un][1,u_n]. Thus

∑j=1R−1∣U∩[xj,(1+δ)xj)∣≤∣U∩[1,un]∣=n.\sum_{j=1}^{R-1}|\mathcal{U}\cap[x_j,(1+\delta)x_j)|\le|\mathcal{U}\cap[1,u_n]|=n.

We conclude that

R2≪1+(R−12)≪nδ−3/2(log⁡δ−1)3/2,R^2\ll1+\left(\frac{R-1}{2}\right)\ll n\delta^{-3/2}(\log\delta^{-1})^{3/2},

and the result follows on taking square roots. □\square

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 Mε(A)M_{\varepsilon}(A) denote the minimum number of intervals of the form [z,(1+ε)z)[z,(1+\varepsilon)z) needed to cover (A−A)∩R>0(A-A)\cap\mathbb{R}_{>0}.

We first record that if A1,A2⊆R≥0A_1,A_2\subseteq\mathbb{R}_{\geq0} are finite sets satisfying

min⁡{(A2−A2)∩R>0}≥2max⁡{A1},\min\{(A_2-A_2)\cap\mathbb{R}_{>0}\}\geq2\max\{A_1\},

then

Mε(A1∪A2)≥Mε(A1)+Mε(A2),M_{\varepsilon}(A_1\cup A_2)\geq M_{\varepsilon}(A_1)+M_{\varepsilon}(A_2),

since no interval [z,(1+ε)z)[z,(1+\varepsilon)z) can simultaneously contain points of both A1−A1,A2−A2A_1-A_1,A_2-A_2. In particular, given A⊆R≥0A\subseteq\mathbb{R}_{\geq0}, there is some λ>1\lambda>1 such that for all positive integers nn, we have

Mε(A∪λ⋅A∪⋯∪λn⋅A)∣A∪λ⋅A∪⋯∪λn⋅A∣≥Mε(A)∣A∣.\frac{M_{\varepsilon}(A\cup\lambda\cdot A\cup\cdots\cup\lambda^n\cdot A)}{|A\cup\lambda\cdot A\cup\cdots\cup\lambda^n\cdot A|} \geq \frac{M_{\varepsilon}(A)}{|A|}.

This shows that once we have a single example AA for which Proposition 2.1 is tight up to constants, we can produce larger examples with the same property (for the same value of ε\varepsilon).

To see that ε−1/2\varepsilon^{-1/2} is the necessary power of ε\varepsilon in the proposition, one can take N:=⌊ε−1/2⌋N:=\lfloor\varepsilon^{-1/2}\rfloor and consider the 2N2N-element set

A:={0,1,2,…,N−1}∪{N,2N,…,N2},A:=\{0,1,2,\ldots,N-1\}\cup\{N,2N,\ldots,N^2\},

which has Mε(A)=N2≫ε−1/2∣A∣M_{\varepsilon}(A)=N^2\gg\varepsilon^{-1/2}|A|. Obtaining the further factor of (log⁡ε−1)1/2(\log\varepsilon^{-1})^{1/2} requires more care, as follows.

Let NN be a large positive integer. Set T:=N⋅8N+1T:=N\cdot8^N+1, and define the set

A:={t/T:1≤t≤T}∪{8n(1+h/8N):1≤n≤N, 1≤h≤8N}.A:=\{t/T:1\leq t\leq T\}\cup\{8^n(1+h/8^N):1\leq n\leq N,\ 1\leq h\leq8^N\}.

The first constituent part of AA 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

∣A∣=T+N⋅8N≍N⋅8N.|A|=T+N\cdot8^N\asymp N\cdot8^N.

Consider the elements of (A−A)∩R>0(A-A)\cap\mathbb{R}_{>0} of the form

x(n,h,t):=8n(1+h/8N)−t/T.x(n,h,t):=8^n(1+h/8^N)-t/T.

Note that x(n,h,t)∈[(1/2)⋅8n,2⋅8n]x(n,h,t)\in[(1/2)\cdot8^n,2\cdot8^n] subsists at scale 8n8^n. In particular, elements x(n,h,t)x(n,h,t) with different values of nn are multiplicatively separated by factors of at least 22, so they must be covered by disjoint sets of intervals [z,(1+ε)z)[z,(1+\varepsilon)z).

Fix a single value of nn, and let h,th,t vary. We claim that the resulting elements x(n,h,t)x(n,h,t) are all distinct. Indeed, if x(n,h,t)=x(n,h′,t′)x(n,h,t)=x(n,h',t'), then rearranging gives

h−h′8N−n=t−t′T.\frac{h-h'}{8^{N-n}}=\frac{t-t'}{T}.

The coprimality of 8N−n,T8^{N-n},T (since TT is odd) implies that TT divides t−t′t-t'. But then in fact t=t′t=t', and thence also h=h′h=h', as desired. Next, the number x(n,h,t)/8nx(n,h,t)/8^n is rational with denominator dividing 8N⋅T8^N\cdot T. So different choices of h,th,t give elements x(n,h,t)x(n,h,t) that are additively 8n/(8N⋅T)8^n/(8^N\cdot T)-separated and hence multiplicatively (1+ε)(1+\varepsilon)-separated for the choice

ε:=12⋅8N⋅T≲182N⋅N.\varepsilon:=\frac{1}{2\cdot8^N\cdot T}\lesssim\frac{1}{8^{2N}\cdot N}.

We conclude that Mε(A)M_{\varepsilon}(A) is at least the total number of elements x(n,h,t)x(n,h,t). This gives

Mε(A)∣A∣≫N⋅8N⋅(N⋅8N)N⋅8N=(N⋅82N)1/2⋅N1/2≳ε−1/2(log⁡ε−1)1/2,\frac{M_{\varepsilon}(A)}{\lvert A\rvert} \gg\frac{N \cdot8^{N} \cdot(N \cdot8^{N})}{N \cdot8^{N}} = (N \cdot8^{2N})^{1/2} \cdot N^{1/2} \gtrsim\varepsilon^{-1/2}(\log\varepsilon^{-1})^{1/2},

which matches the bound in Proposition 2.1 up to a constant factor. Note that ∣A∣=ε−(1/2+o(1))\lvert A\rvert= \varepsilon^{-(1/2+o(1))} 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 unu_n of the shape eO(n2/3)e^{O(n^{2/3})}, then eO(nlog⁡n)e^{O(\sqrt{n\log n})}, and finally eO(n)e^{O(\sqrt n)}. 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. [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. [2]J. Bourgain, On the Erdős–Volkmann and Katz–Tao ring conjectures. GAFA, 13 (2003), 334–365.DOI
  3. [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. [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. [5]L. Guth, N. H. Katz, and J. Zahl, On the discretized sum-product problem. IMRN, 13 (2021), 9769–9785.
  6. [6]J. Jinman, B. Kuca, A. Schlesinger, and A. Sheydvasser, The unreasonable rigidity of Ulam sequences. J. Number Theory, 194 (2019), 409–425.
  7. [7]N. Kravitz and S. Steinerberger, Ulam sequences and Ulam sets. Integers 18 (2018), #A80.
  8. [8]A. Mandelshtam, On fractal patterns in Ulam words. Adv. Appl. Math., 172 (2026), #102954.arxiv.org/abs/2211.14229
  9. [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. [10]S. Steinerberger, A Hidden Signal in the Ulam Sequence. Experiment. Math., 26.4 (2017), 460–467.arxiv.org/abs/1507.00267
  11. [11]S. Ulam, Combinatorial analysis in infinite sets and some physical theories. SIAM Rev., 6.4 (1964), 343–355.DOI

Paper details

vlnc:W_gb7958tv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT 6

View statement
Looking for related papers…
Contents