%~Mouliné par MaN_auto v.0.34.0 (b272df1a) 2025-06-13 11:26:13
\documentclass[CRMATH,Unicode,XML,biblatex]{cedram}

\TopicFR{Théorie des nombres}
\TopicEN{Number theory}

\addbibresource{CRMATH_Clement_20250088.bib}

\usepackage{mathtools}

%%%---------------------------------------------------------------------------

%%% DELIMITERS

\DeclarePairedDelimiter{\parens}{\lparen}{\rparen}
\DeclarePairedDelimiter{\braces}{\{}{\}}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
\DeclarePairedDelimiter{\bracks}{[}{]}

%%%---------------------------------------------------------------------------

\graphicspath{{./figures/}}

\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}

\title{Small gaps in the Ulam sequence}
\alttitle{Sur la présence de petits intervalles dans la suite d'Ulam}

\author{\firstname{Fran\c{c}ois} \lastname{Cl\'{e}ment}}
\address{Department of Mathematics, University of Washington, Seattle, USA}
\email{fclement@uw.edu}

\author{\firstname{Stefan} \lastname{Steinerberger}}
\address[1]{Department of Mathematics, University of Washington, Seattle, USA}
\email{steinerb@uw.edu}

\keywords{\kwd{Ulam sequence} \kwd{$s$-additive sequence}}
\altkeywords{\kwd{Suite d'Ulam} \kwd{suites $s$-additives}}

\begin{abstract}
The Ulam sequence, described by Stanis{\l}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 \emph{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}.
\]
\end{abstract}

\begin{altabstract}
La séquence d'Ulam, introduite par Stanis{\l}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 \leq k \leq n} \frac{a_{k+1}}{a_k} \leq 1 + c\frac{\log{n}}{n}.
\]
\end{altabstract}

\begin{document}

\maketitle

\section{Introduction and results}

\subsection{Introduction}

The origins of the Ulam sequence are mysterious. It is mentioned in a 1962 paper of Ulam~\cite{ulam0}. Two years later, Ulam~\cite{ulam} writes:
\begin{quote}
One can consider a rule for growth of patterns -- in one dimension it would be merely a rule for obtaining successive integers. [...] Another one-dimensional sequence was studied recently. This one was defined purely additively: one starts, say, with integers 1, 2 and considers in turn all integers which are obtainable as the sum of two different ones previously defined but only if they are so expressible in a unique way. The sequence would start as follows:
\[
1,2,3,4,6,8,11,13,\dotsc
\]
\end{quote}
No additional motivation is given and it is not at all clear why the arising sequence should be of interest. A few years later, Raymond Queneau, one of the most famous French poets of the twentieth century (and a co-founder of Oulipo), published the article ``Sur les suites $s$-additives''~\cite{q0} followed by a more extensive article with the same name~\cite{q}. Queneau considers $s$-additive sequences, sequences of integers where each new term is the sum of exactly $s$ previous terms. He shows that these can exhibit very interesting behavior. For $s=1$, he remarks that we get the sequence ``studied by S.~ M.~Ulam. It gives the impression of great irregularity''~\cite{q}. The Ulam sequence and, more generally, $s$-additive sequences were then studied by Cassaigne--Finch~\cite{cas}, Finch~\cite{finch1, finch3, finch2, finch0}, Mauldin--Ulam~\cite{mauldin}, Recaman~\cite{recaman}, Schmerl--Spiegel~\cite{schm} and others. Around ten years ago, one of the authors discovered (numerically) that the ``great irregularity'' already observed by Queneau seems to exhibit a great degree of regularity: there seems to exist a real number $\alpha \sim 2.57145\dots$ so that the sequence $\alpha a_n \pmod{2\pi}$ exhibits a most curious distribution~\cite{stein}. This inspired subsequent work~\cite{adut,angelo, bade, hinman, hinman2, kravitz, kuca, mandel, sen} but remains unexplained to this day.

\subsection{Results}

Despite all of this, \emph{very} little is actually rigorously known about the Ulam sequence. We present two new results (that are independent of each other). It is known that the sequence is infinite: if it were finite, $a_1,\dotsc, a_n$, then $a_{n-1} + a_n$ has a unique representation as the sum of two distinct earlier terms. This proves $a_{n+1} \leq a_n + a_{n-1}$ which can be used to show that $a_n \leq F_n$ where $F_n$ is the $n$-th Fibonacci number implying $a_n \leq 1.62^n$. A further refinement is possible.

\begin{proposition}[R.~B.~Eggleton, \cite{recaman}] For $n \geq 3$, we have
\[
a_{n+1} \leq a_n + a_{n-2}.
\]
This implies $a_n \leq 1.466^n$ where $1.46\dots$ is the root of $x^3 - x^2 - 1=0$.
\end{proposition}

\begin{proof}
The number $a_n + a_{n-2}$ can be written as the sum of two distinct earlier terms. It remains to show that there is no other representation. If $a_{n-2} + a_n = a_i + a_j$ with $1 \leq i < j \leq n$, then $j$ cannot be $n$ and $j$ cannot be smaller than $n-2$. If $j=n-1$, then $i \leq n-2$ which is a contradiction.
\end{proof}

To the best of our knowledge, this is the only rigorously proven result about the growth of the Ulam sequence. Our first contribution is a small improvement.

\begin{theorem}\label{theorem}
We have, for all $n$ sufficiently large,
\[
a_n \leq 1.454^n.
\]
\end{theorem}

This small improvement requires a surprising amount of work; the main idea is that Eggleton's bound cannot be sharp twice in a row. This leads us to consider two near-Eggleton recursions and the potential order in which they could be applied; after some reductions, we are faced with a variation of the joint spectral radius problem with an additional restriction on allowed words; we circumvent the problem by using submultiplicativity of the operator norm to reduce it to a finite case distinction. Studying more cases would lead to a (slightly) improved constant; however, we also prove that our argument in its current form cannot prove $a_n \leq \rho^n$ for $\rho < 1.4146$ (which might, in principle, be achievable with our approach and more computation). We believe that there might be a limit to how much one can obtain via these types of arguments. It feels unlikely that one could prove subexponential growth this way. Numerical experiments suggest that the sequence grows \emph{linearly}. The massive gulf between what is known and what seems to be true is a \emph{very} unsatisfying state of affairs. We will prove that at least some small gaps exist.

\begin{theorem}\label{theorem2}
There exists $c>0$ such that for all $n \in \mathbb{N}_{\geq 2}$
\[
\min_{1 \leq k \leq n} \frac{a_{k+1}}{a_k} \leq 1 + c \frac{\log{n}}{n}.
\]
\end{theorem}

The proof shows that $c=7$ would work for $n$ sufficiently large. The inequality appears to be close to sharp: if $a_k$ grows linearly (as is expected), then the result would be sharp up to the logarithmic factor. Needless to say, the result does not exclude exponential growth. It feels appropriate, this being the subject of his mathematical publications, to conclude with Queneau (from his \emph{Morale \'el\'ementaire}~\cite{queneau}):
\begin{quote}
If he looked up, he would see beyond the clouds the arithmetical truths, but it is only at night that he falls into the vertigo of stars.\footnote{\emph{S'il levait le nez, il verrait au-del\`a des nuages les v\'erit\'es arithm\'etiques, mais ce n'est que la nuit qu'il sombre dans le vertige des \'etoiles} (English translation by the editor).}
\end{quote}

\section{Proof of Theorem~\ref{theorem}}

We start with a bit of terminology. We always have Eggleton's bound
\[
a_{n+1} \leq a_n + a_{n-2} \tag{E}
\]
at our disposal. The entire idea behind the argument is that Eggleton's bound is a worst case scenario and we will try to avoid using it as much as possible. The next two lexicographic terms are $a_n + a_{n-3}$ (which we refer to as Type I) and $a_{n-1} + a_{n-2}$ (which we refer to as Type II). These are some of the largest sums that can be attained in the next step: Eggleton's bound being the largest and Type I and Type II being incomparable between each other.

\begin{lemma}\label{lemma1}
Let\/ $1 \leq i < j \leq n$. If $a_i + a_j < a_n + a_{n-2}$, then
\[
a_{i} + a_j \leq \max\braces[\big]{ a_n + a_{n-3}, a_{n-1} + a_{n-2}}
\]
with equality if and only if $(i,j) = (n-3, n)$ or $(i,j) = (n-2, n-1)$. If $a_{n+1} = a_n + a_{n-2}$, then Type I and Type II coincide, i.e.\ $ a_n + a_{n-3} = a_{n-1} + a_{n-2}$.
\end{lemma}
\begin{proof}
If $j=n$, then $a_i + a_j < a_n + a_{n-2}$ forces $i \leq n-3$ and the result follows. If $j = n-1$, then $i \leq n-2$ and the result follows. If $j\leq n-2$, then $i \leq n-3$ and the result follows. If Eggleton's bound is attained, then Type I and Type II have to coincide: if they were different numbers, then Type I, $a_n + a_{n-3}$, would have a unique representation which can be seen as follows: suppose
\[
a_n + a_{n-3} = a_i + a_j.
\]
If $j = n$, then this forces $i = n-3$ which is the same representation. If $j = n-1$, then $i = n-2$, which is Type II which is different by assumption. But if $j =n-2$, we are only left with $i=n-3$ which is too small. Therefore $a_n + a_{n-3}$ has a unique representation and therefore $a_{n+1} \leq a_n + a_{n-3}$. Then $a_{n+1} \leq a_n + a_{n-3} < a_n + a_{n-2}$ which is a contradiction.
\end{proof}

\begin{lemma}
The Eggleton bound cannot be attained twice in a row.
\end{lemma}
\begin{proof}

Suppose this is false: after two applications of Eggleton's bound, we have
\[
a_{n-2}, a_{n-1}, a_n, \qquad a_n + a_{n-2}, \qquad a_n + a_{n-1} + a_{n-2}.
\]
Since Eggleton's bound is exact both times, we have from Lemma~\ref{lemma1} that the Type I and Type II bound coincide each time. This means that, for the second application,
\[
a_{n-2} + (a_n + a_{n-2}) = a_n + a_{n-1}.
\]
Then $2 a_{n-2} = a_{n-1}$ contradicting Eggleton bound's $a_{n-1} \leq a_{n-2} + a_{n-4}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{theorem}]
We know that the Ulam sequence $a_1, a_2,\dotsc$ exists and construct a new sequence $b_1, b_2,\dotsc$ such that $a_n \leq b_n$. We set $b_n = a_n$ for $1 \leq n \leq 5$. After that, we construct $b_{n+1}$ as follows. The Ulam element $a_{n+1}$ is either obtained via Eggleton ($a_{n+1} = a_{n} + a_{n-2}$), via Type I ($a_{n+1} = a_n + a_{n-3}$), via Type II ($a_{n+1} = a_{n-1} + a_{n-2}$) or via some other method $a_{n+1} = a_i + a_j$. If it is any of the first three, then we use the exact same recursion for $b_{n+1}$ which then guarantees $a_{n+1} \leq b_{n+1}$. If it is none of these three recursions, then we know (Lemma~\ref{lemma1}) that $a_{n+1} = a_i + a_j$ is either bounded by Type I or Type II and we use that corresponding recursion (if both Type I and Type II are upper bounds, then either choice is admissible) to define $b_{n+1}$. We also note that $b_n$ only uses Eggleton when $a_n$ uses Eggleton and this cannot happen twice in a row. The remaining question is: how quickly can such a sequence $(b_n)_{n=1}^{\infty}$ grow? At this point, we start using matrices. The language of matrices allows us to write an application of these bounds as
\begingroup
\setlength\arraycolsep{3pt}
%\[
%\begin{pmatrix} b_{n+1} \\ b_n \\ b_{n-1} \\ b_{n-2}
%\end{pmatrix} =
%\begin{pmatrix}
%1 & 0 & 0 & 1 \\
%1 & 0 & 0 & 0 \\
%0& 1 & 0 & 0 \\
%0& 0 & 1 & 0
%\end{pmatrix}
%\begin{pmatrix} b_{n} \\ b_{n-1} \\ b_{n-2} \\ b_{n-3}
%\end{pmatrix} \qquad (T_1 = \text{Type I})
%\]
%and
%\[
%\begin{pmatrix} b_{n+1} \\ b_n \\ b_{n-1} \\ b_{n-2}
%\end{pmatrix} =
%\begin{pmatrix}
%0 & 1 & 1 & 0 \\
%1 & 0 & 0 & 0 \\
%0& 1 & 0 & 0 \\
%0& 0 & 1 & 0 \\
%\end{pmatrix}
%\begin{pmatrix} b_{n} \\ b_{n-1} \\ b_{n-2} \\ b_{n-3}
%\end{pmatrix} \qquad (T_2 = \text{Type II})
%\]
%and
%\[
%\begin{pmatrix} b_{n+1} \\ b_n \\ b_{n-1} \\ b_{n-2}
%\end{pmatrix} =
%\begin{pmatrix}
%1 & 0 & 1 & 0 \\
%1 & 0 & 0 & 0 \\
%0& 1 & 0 & 0 \\
%0& 0 & 1 & 0
%\end{pmatrix}
%\begin{pmatrix} b_{n} \\ b_{n-1} \\ b_{n-2} \\ b_{n-3}
%\end{pmatrix} \qquad (T_3 = \text{Eggleton}).
%\]
\begin{align*}
\begin{pmatrix}
b_{n+1} \\ b_n \\ b_{n-1} \\ b_{n-2}
\end{pmatrix}
& =
\begin{pmatrix}
1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0& 1 & 0 & 0 \\
0& 0 & 1 & 0
\end{pmatrix}
\begin{pmatrix} b_{n} \\ b_{n-1} \\ b_{n-2} \\ b_{n-3}
\end{pmatrix} \qquad (T_1 = \text{Type I})
\intertext{and}
\begin{pmatrix}
b_{n+1} \\ b_n \\ b_{n-1} \\ b_{n-2}
\end{pmatrix}
& =
\begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0& 1 & 0 & 0 \\
0& 0 & 1 & 0 \\
\end{pmatrix}
\begin{pmatrix} b_{n} \\ b_{n-1} \\ b_{n-2} \\ b_{n-3}
\end{pmatrix} \qquad (T_2 = \text{Type II})
\intertext{and}
%\[
\begin{pmatrix} b_{n+1} \\ b_n \\ b_{n-1} \\ b_{n-2}
\end{pmatrix}
& =
\begin{pmatrix}
1 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0& 1 & 0 & 0 \\
0& 0 & 1 & 0
\end{pmatrix}
\begin{pmatrix} b_{n} \\ b_{n-1} \\ b_{n-2} \\ b_{n-3}
\end{pmatrix} \qquad (T_3 = \text{Eggleton}).
\end{align*}
\endgroup

We refer to these matrices as $T_1$, $T_2$ and $T_3$. The remaining problem is to understand the possible behavior of the growth of the operator norm of products of these forms; more precisely, we are interested in bounds along the lines of
\begin{equation}\label{eq:c}
\norm[\Bigg]{ \prod_{i=1}^{n} T_{k_i} } \leq C^n \quad \text{where $k_i \in \braces{1,2,3}$},
\end{equation}
where $n$ may be assumed to be large. This leads us naturally to the \emph{joint spectral problem}~\cite{rota} with the notable difference that not all sequences $(k_i)$ are admissible (because $k_i = 3 = k_{i+1}$ is not admissible, Eggleton cannot arise twice in a row). The joint spectral problem is known to be difficult even without such constraints~\cite{bl} and we do not aim to resolve it exactly and will instead focus on approximate solutions. Fixing the segment's length $L$, we can always use the submultiplicativity of the operator norm to bound, for $n \geq L$,
\[
\norm[\Bigg]{ \prod_{i=1}^{n} T_{k_i} } \leq C_L \parens*{\max_{\substack{\text{\tiny admissible word} \\ \text{\tiny of length $L$}}} \norm[\Bigg]{ \prod_{i=1}^{L} T_{k_i} } }^{n/L},
\]
where the maximum ranges over all admissible words on $T_1$, $T_2$, $T_3$ of length $L$. ``Admissible word'' refers to the sequence of the $k_i$ which has to be such that $k_i = 3 \implies k_{i+1} \neq 3$. This inequality can be seen as follows: for any arbitrary product of $n$ matrices, we can group it into $\lfloor n/L \rfloor$ groups of products of $L$ matrices with at most $L-1$ matrices left over,
\[
\norm[\Bigg]{ \prod_{i=1}^{n} T_{k_i} } = \norm[\Bigg]{ \prod_{i=1}^{\lfloor n/L \rfloor} \prod_{s=1}^{L} T_{i,s} \cdot R } \leq \parens*{\prod_{i=1}^{\lfloor n/L \rfloor}\norm[\Bigg]{ \prod_{s=1}^{L} T_{i,s} }} \cdot \norm{R},
\]
where $R$ is either the identity matrix or a product of at most $L-1$ matrices. This is a finite set and thus $\norm{R} \leq C_{L}$. As for the remaining product, we may simply assume the worst case at each step giving
\[
\prod_{i=1}^{\lfloor n/L \rfloor}\norm[\Bigg]{ \prod_{s=1}^{L} T_{i,s} } \leq \prod_{i=1}^{\lfloor n/L \rfloor} \max_{\substack{\text{\tiny admissible word} \\ \text{\tiny of length $L$}}} \norm[\Bigg]{ \prod_{i=1}^{L} T_{k_i} } = \parens*{\max_{\substack{\text{\tiny admissible word} \\ \text{\tiny of length $L$}}} \norm[\Bigg]{ \prod_{i=1}^{L} T_{k_i} } }^{n/L}.
\]
Therefore, for all lengths $L \in \mathbb{N}$, the constant in~\eqref{eq:c} is bounded from above by
\[
C \leq \max_{\substack{\text{\tiny admissible word} \\ \text{\tiny of length $L$}}} \norm[\Bigg]{ \prod_{i=1}^{n} T_{k_i} }^{1/L} + o(1),
\]
where $o(1) \to 0$ as $n \to \infty$. Using this with $L=15$ and checking all admissible words gives
\[
C \leq 1.4539\dots
\]
with the extremal word being $ W = (T_3 T_1)^3 (T_1 T_3)^3 T_2.$
\end{proof}

One naturally wonders how far this is from the truth. Here we use the Gelfand formula~\cite{gelfand} stating that the spectral radius is connected to the asymptotic behavior via
\[
\rho(A) = \lim_{n \to \infty} \norm{A^n}^{1/n}.
\]
For any admissible word $W = \prod_{i=1}^{L} T_{n_i}$ of length $L$ (whose concatenation with itself remains an admissible word) we cannot hope to do better than $ \rho(W)^{1/L}$. The word $W = T_3 T_1^{2}$ satisfies $\rho(W)^{1/3} \sim 1.4146\dots$ (the $1/3$-power of a root of a cubic polynomial). It is worth noting that $\rho(T_3 T_1)^{1/2} = \sqrt{2}$ is just a tiny bit smaller than $\rho(T_3 T_1^2)^{1/3} $. This leads to a number of near-minimizers when truncating after $L=14$ words, the extremal structure is difficult to discern at that stage. It is maybe the case that the optimal solution is asymptotically given by powers of $T_3 T_1^2$ which would give the asymptotic rate $\rho(T_3 T_1^2)^{1/3} \sim 1.4146$.

\section{Proof of Theorem~\ref{theorem2}}

The proof of Theorem~\ref{theorem2} is based on the following idea: set $\delta$ to be
\[
\min_{1 \leq k \leq n} \frac{a_{k+1}}{a_k} = 1 + \delta.
\]
It may help to think of $\delta$ as ``very large'' (say $\delta = 0.5$) to understand the idea behind the argument: the proof is then constructed in such a manner that it will end up telling us for which value of $\delta$ the argument starts to work (and the final result follows computing that threshold). Any two consecutive elements of the sequence can be thought of as ``on almost different scales'' and, in particular, almost all elements in the sequence are much, much smaller than $a_n$. We show that all but very few elements are smaller than $\delta a_n/2$ and this shows that there exist many sums of the type $a_n + a_1, a_n + a_2, a_n + a_3,\dotsc$ that lie in the range $[a_n, a_n + \delta a_n/2]$. However, $a_{n+1} \geq (1+\delta) a_n$ and therefore none of these sums have a unique representation, they all have to have yet another representation $a_n + a_k = a_i + a_j$. It thus remains to consider the number of representations of the form $a_i + a_j$ that end up in $[a_n, a_n + \delta a_n/2]$. When $\delta$ is ``large'', then there are fewer such sums than there are sums of the type $a_n + a_1, a_n + a_2, a_n + a_3,\dotsc$ and this shows that at least one of these sums has to have a unique representation. This is a contradiction since it would show that the next Ulam number is small $a_{n+1} \leq (1+\delta/2)a_n$ which contradicts the definition of $\delta$.

\begin{proof}
Let us fix $n$ and define $\delta$ by
\[
\min_{1 \leq k \leq n} \frac{a_{k+1}}{a_k} = 1 + \delta.
\]
We know, since $a_2 = 2$ and $a_3 = 3$, that $\delta \leq 1/2$ once $n \geq 3$. As a first consequence, for all $1 \leq k \leq n$ we have that $a_{k+1} \geq (1+\delta) a_k$. Applying this iteratively, we see that, for $1 \leq \ell \leq n-1$,
\[
a_{n-\ell} \leq \frac{a_n}{(1+\delta)^{\ell}}.
\]
This inequality implies
\[
\# \braces[\Big]{1 \leq k \leq n: a_k \geq \tfrac{a_n}{(1+\delta)^{\ell}} } \leq \ell + 1
\]
which, in turn, can be rewritten as, for all $1 \leq x \leq a_n$,
\[
\# \braces[\big]{1 \leq k \leq n: a_k \geq x } \leq \frac{\log{(a_n/x)}}{\log{(1+\delta)}} + 1 \leq \frac{2}{\delta} \log{\parens[\Bigg]{\frac{a_n}{x} }} + 1,
\]
where the second inequality used $0 < \delta < 1$. There are many Ulam numbers smaller than $\delta a_n/2$ since
\[
\# \braces[\Big]{1 \leq k \leq n: a_k \geq \tfrac{\delta a_n}{2} } \leq \frac{2}{\delta} \log\parens[\Bigg]{\frac{2}{\delta}} + 1
\]
and therefore
\[
\# \braces[\Big]{1 \leq k \leq n: a_k \leq \tfrac{\delta a_n}{2} } \geq n - \frac{2}{\delta} \log\parens[\Bigg]{\frac{2}{\delta}} - 1.
\]
Thus, there are many small Ulam numbers that we could add to $a_n$ that yield a sum that is not much larger than $a_n$. Rewriting the previous bound, we have
\[
\# \braces[\Big]{ 1 \leq k < n: a_n + a_k \in \bracks[\Big]{a_n, a_n + \tfrac{\delta}{2} a_n} } \geq n - \frac{2}{\delta} \log\parens[\Bigg]{\frac{2}{\delta}} - 1.
\]
However, none of these numbers are in the Ulam sequence since $a_{n+1} \geq (1+\delta) a_n$ is much larger. The only way this is possible is if for each of these sums there exists an alternative representation $a_n + a_k = a_i + a_j$ for some $i < j \leq n-1$. We will argue that for $\delta$ large, the number of sums of the form $a_n + a_k$ with $a_k \leq a_n \delta/2$ (already bounded from below) is larger than the number of (relevant) sums $a_i + a_j$: then, by pigeonholing, there must exist one ``unblocked'' sum $a_n + a_k$ which arises only once; this sum would then be an upper bound on $a_{n+1}$ which is a contradiction. This requires us to bound
\[
X = \# \braces[\Big]{ (i,j) \in \mathbb{N}^2: i <j \ \text{and} \ a_n \leq a_i + a_j \leq a_n + \tfrac{\delta}{2} a_n }.
\]
We may think of the sum $a_i + a_j$ as the sum of two terms where $a_j$ is ``large'' and $a_i$ is ``small''. The ``large'' one has to be at least $\geq a_n/2$ and a ``smaller'' one that has to be in a precise regime. Using the estimate
\[
\frac{a_n}{(1+\delta)^{j}} \geq a_{n-j} \geq \frac{a_n}{2}
\]
one deduces
\[
j \leq \frac{2 \log{2}}{\delta}.
\]
Therefore
\[
X \leq \sum_{j=1}^{2 \log{(2)}/\delta} \# \braces[\Big]{ 1 \leq i \leq n: a_n - a_{n - j} \leq a_i \leq a_n - a_{n- j} + \tfrac{\delta}{2} a_n }.
\]
By the $\delta$-gap assumption, we have for any interval $1 \leq a < b \leq a_{n+1}$ that
\[
\# \braces[\big]{ 1 \leq i \leq n: a \leq a_i \leq b} \leq \frac{\log{(b/a)}}{\log(1+\delta)} + 1 \leq \frac{2}{\delta}\log{\parens[\Bigg]{\frac{b}{a}}} + 1.
\]
Before combining these inequalities, we simplify the algebra. First,
\[
\frac{a_n - a_{n- j} + \frac{\delta}{2} a_n}{a_n - a_{n - j} } = 1 + \frac{\delta}{2} \frac{a_n}{a_n - a_{n-j}}.
\]
Using the inequality from above,
\[
\frac{a_n}{a_n - a_{n-j}} \leq \frac{a_n}{a_n - \frac{a_n}{(1+\delta)^{j}}} = \frac{1}{1 - \frac{1}{(1+\delta)^{j}}} = \frac{(1+\delta)^{j}}{(1+\delta)^{j} - 1}.
\]
Since $j \leq 2 \log{(2)} /\delta$, we have
\[
(1 + \delta)^{\frac{2 \log{2}}{\delta}} \leq \parens[\big]{(1+\delta)^{\frac{1}{\delta}} }^{2 \log{2}} \leq e^{2 \log{(2)}} =4.
\]
We also have Bernoulli's inequality $(1+\delta)^{j} \geq 1 + j \delta$ which implies
\[
\frac{a_n}{a_n - a_{n-j}} \leq \frac{(1+\delta)^{j}}{(1+\delta)^{j} - 1} \leq \frac{4}{\delta j}
\]
and thus
\[
\# \braces[\Big]{ 1 \leq i \leq n: a_n - a_{n - j} \leq a_i \leq a_n - a_{n- j} + \tfrac{\delta}{2} a_n } \leq \frac{2}{\delta} \log\parens[\Bigg]{1 + \frac{\delta}{2} \frac{4}{\delta j} } +1 \leq \frac{2}{\delta} \log\parens[\Bigg]{1 + \frac{2}{j} } + 1 \leq \frac{4}{\delta j} + 1.
\]

Collecting all these bounds, we get
\[
\begin{split}
X
	& \leq \sum_{j=1}^{2 \log{(2)}/\delta} \# \braces[\Big]{ 1 \leq i \leq n: a_n - a_{n - j} \leq a_i \leq a_n - a_{n- j} + \tfrac{\delta}{2} a_n }
\\	& \leq \sum_{j=1}^{2 \log{(2)}/\delta} \parens[\Bigg]{1 + \frac{4}{\delta j}} 
\\	& = \frac{2\log{(2)}}{\delta} + \frac{4}{\delta} \sum_{j=1}^{2 \log{(2)}/\delta} \frac{1}{j}
\\	& \leq \frac{2\log{(2)}}{\delta} + \frac{4}{\delta} \log\parens[\Bigg]{\frac{10}{\delta}}.
\end{split}
\]
We require
\[
\# \braces[\Big]{ 1 \leq i < n: a_n + a_i \in \bracks[\Big]{a_n, a_n + \tfrac{\delta}{2} a_n} } \leq X
\]
and with the lower bound on the first set derived above and the upper bound on $X$ just derived
\[
n - \frac{2}{\delta} \log\parens[\Bigg]{\frac{2}{\delta}} - 1 \leq X \leq \frac{2\log{(2)}}{\delta} + \frac{4}{\delta} \log\parens[\Bigg]{\frac{10}{\delta}}.
\]
As $n$ becomes large, this forces
\[
\delta \leq c\frac{\log{n}}{n}
\]
and a short computation shows that $c = 7$ is admissible for $n$ sufficiently large.
\end{proof}

The proof both suggests a certain strategy and also the difficulty faced by that strategy. If the sequence were to grow quickly, say exponentially, then $a_k \ll a_n$ is true for ``almost all'' $1 \leq k \leq n$.

This means that there are many ``candidate sums'' $a_n + a_k$ that should potentially be in the sequence and that are not much larger than $a_n$ (leading to slow growth). Moreover, there should be few $a_i + a_j$ sums in the same range and they should not be able to ``block'' all the $a_n + a_k$. The main obstruction appears to be the one shown in Figure~\ref{figu}: the scenario where elements of the sequence arise in groups that are clumped together followed by a huge gap to the next element. It is not clear to us how to exclude this scenario.

\begin{figure}[h!]
\begin{tikzpicture}
\draw [ultra thick] (0,0) -- (8,0);
\draw [ultra thick] (4, -0.1) -- (4,0.1);
\draw [ultra thick] (4.2, -0.1) -- (4.2,0.1);
\draw [ultra thick] (3.9, -0.1) -- (3.9,0.1);
\draw [ultra thick] (4.15, -0.1) -- (4.15,0.1);
\draw [ultra thick] (4.8, -0.1) -- (4.8,0.1);
\draw [ultra thick] (4.82, -0.1) -- (4.82,0.1);
\draw [ultra thick] (4.93, -0.1) -- (4.93,0.1);
\draw [ultra thick] (5.04, -0.1) -- (5.04,0.1);
\draw [ultra thick] (7.1, -0.1) -- (7.1,0.1);
\draw [ultra thick] (7.23, -0.1) -- (7.23,0.1);
\draw [ultra thick] (7.15, -0.1) -- (7.15,0.1);
\draw [ultra thick] (1.4, -0.1) -- (1.4,0.1);
\draw [ultra thick] (1.45, -0.1) -- (1.45,0.1);
\draw [ultra thick] (1.6, -0.1) -- (1.6,0.1);
\end{tikzpicture}
\caption{An obstacle: ``clumps'' followed by a big jump.}\label{figu}
\end{figure}

\section*{Declaration of interests}

The authors do not work for, advise, own shares in, or receive funds from any organization that could benefit from this article, and have declared no affiliations other than their research organizations.

\printbibliography

\end{document}