\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{lineno}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\start}{\texttt{start}}
\newcommand{\final}{\texttt{end}}
\newcommand{\ulamset}{\texttt{ulam\_set}}
\newcommand{\onerepset}{\texttt{one\_rep\_set}}
\newcommand{\multrepset}{\texttt{mult\_rep\_set}}
\newcommand{\largestulam}{\texttt{largest\_ulam}}
\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}
\DeclareMathOperator{\eval}{eval}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{alg}{Algorithm}[section]
\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
The Ulam Sequence of Linear \\
\vskip .1in
Integer Polynomials}
\vskip 1cm
\large
Arseniy (Senia) Sheydvasser \\
Israel Institute of Technology \\
Department of Mathematics \\
Haifa 3200003 \\
Israel \\
\href{mailto:sheydvasser@campus.technion.ac.il}{\tt sheydvasser@campus.technion.ac.il}
\end{center}
\vskip .2 in
\begin{abstract}
The Ulam sequence $U(1,n)$ is defined as the sequence starting with integers $1,n$ such that $n > 1$, and such that every subsequent term is the smallest integer that can be written as the sum of distinct previous terms in exactly one way. This family of sequences is notable for being the subject of several remarkable rigidity conjectures. We introduce an analogous notion of an Ulam sequence inside the integer polynomial ring, and use it both to give new, constructive proofs of old results as well as to produce a new conjecture that implies many of the other existing conjectures.
\end{abstract}
\section{Introduction and main results}\label{section: introduction}
\begin{figure}
\centering
\includegraphics[width=0.7\textwidth]{U12_Histogram.pdf}
\caption{A histogram of the first billion terms of $U(1,2) \bmod \lambda_2$, re-scaled into the interval $[0,2\pi]$.}
\label{First Histogram}
\end{figure}
Given integers $1 \leq a < b$, define the \emph{Ulam sequence} $U(a,b)$ to be the sequence starting with $a,b$, and such that every subsequent term is the smallest integer that can be written as the sum of two distinct prior terms in exactly one way. The sequence
$$
U(1,2) = 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38\ldots,
$$
which is \seqnum{A002858} in the {\it On-Line Encyclopedia of Integer
Sequences} (OEIS),
was originally introduced in 1964 by Ulam \cite{ulam_1964}, who posed the question of determining the growth rate of this sequence, which remains opens to this day. It is conjectured that $U(1,2)$ grows linearly, and it has positive density of about $0.079$. The growth rate of certain other families of Ulam sequences was confirmed to be linear by proving the stronger result that they are eventually periodic---this was done for Ulam sequences $U(2,2n + 1)$ by Schmerl and Spiegel \cite{schmerl_spiegel_1994}, using previous work of Finch \cite{finch_1991,finch_1992_1,finch_1992_2} and Queneau \cite{queneau_1972}. Similarly, Cassaigne and Finch \cite{cassaigne_finch_1995} proved that sequences $U(4,n)$ are eventually periodic if $n \equiv \modd{1} {4}$, and Hinman, Kuca, Schlesinger, and Sheydvasser \cite{HKSS_2019_2} found a finite set of sequences $U(4,n)$ with $n \equiv \modd{3} {4}$ that are also eventually periodic. In contrast, none of the sequences of the form $U(1,n)$ seem to be eventually periodic, and virtually nothing was known about them until very recently, when Steinerberger \cite{steinerberger_2016} gave numerical evidence that there exists a real number $\lambda_2 \approx 2.44344296778$ with the curious property that $U(1,2) \bmod \lambda_2$ is concentrated in the middle third of the interval. To be more precise, we have the following conjecture, formulated by Gibbs \cite{Gibbs_2015}.
\begin{conjecture}\label{conj:gibbs}
There exists a real number $\lambda_2 \approx 2.44344296778$ such that for all $\epsilon > 0$, for $K$ sufficiently large,
\begin{align*}
U(1,2) \cap [K,\infty) \bmod \lambda_2 \subset \left(\frac{\lambda_2}{3} - \epsilon, \frac{2\lambda_2}{3} + \epsilon\right).
\end{align*}
\end{conjecture}
This conjecture has since been confirmed for the first trillion terms of $U(1,2)$ by Gibbs and McCranie \cite{Gibbs_Judson_2015}. Numerical evidence suggests that for Ulam sequences $U(a,b)$ that are not eventually periodic, similar behavior occurs---such ``magic numbers" for Ulam sequences are referred to as \emph{periods} in the literature. In particular, there is the following generalization of Gibbs' conjecture in the mathematical folklore, communicated to the author by Joshua Hinman, who did an extensive numerical study of the periods of various families of Ulam sequences.
\begin{conjecture}\label{conj:gibbslike}
For all $n \geq 2$, there exist real numbers $\lambda_n$, $K_n$ such that for all $\epsilon > 0$,
\begin{align*}
U(1,n) \cap [K_n,\infty) \bmod \lambda_n \subset \left(\frac{\lambda_n}{3} - \epsilon, \frac{2\lambda_n}{3} + \epsilon\right).
\end{align*}
Furthermore, for $n \geq 4$, we can take $\lambda_n = 3n + \lambda'$, where $\lambda' \approx 0.417031$.
\end{conjecture}
The observed empirical fact that for $n \geq 4$, the periods $\lambda_n$ grow linearly has been poorly understood up until now. Our goal is to show that this curious phenomenon is deeply tied to the following, seemingly unconnected, numerical observation of Hinman, Kuca, Schlesinger, and the present author \cite{HKSS_2019_1}. Specifically, we noted that for $n \geq 4$ runs of consecutive elements of $U(1,n)$ group into blocks whose endpoints grow linearly.
\begin{align*}
\begin{array}{rllllll}
U(1,4)= & \boxed{1}, & \boxed{4, 5, 6, 7, 8}, & \boxed{10}, & \boxed{16}, & \boxed{18, 19}, & \boxed{21} \ldots \\
U(1,5)= & \boxed{1}, & \boxed{5, 6, 7, 8, 9, 10}, & \boxed{12}, & \boxed{20}, & \boxed{22, 23, 24}, & \boxed{26} \ldots \\
U(1,6)= & \boxed{1}, & \boxed{6, 7, 8, 9, 10, 11, 12}, & \boxed{14}, & \boxed{24}, & \boxed{26, 27, 28, 29}, &\boxed{31} \ldots \\
U(1,n)= & \boxed{1}, & \boxed{n, n + 1, \ldots 2n}, & \boxed{2n + 2}, & \boxed{4n}, & \boxed{4n + 2 \ldots 5n - 1}, & \boxed{5n + 2} \ldots
\end{array}
\end{align*}
This observation was made precise by the following conjecture.
\begin{conjecture}\label{conj:rigidity}
There exist unique integer coefficients $a_i,b_i,c_i,d_i$ such that for all $n \geq 4$,
\begin{align*}
U(1,n) = \bigcup_{i = 0}^\infty \ [a_i n + b_i, c_i n + d_i],
\end{align*}
such that $a_{i + 1}n + b_{i + 1} > c_i n + d_i n + 1$ for all $i$.
\end{conjecture}
At present, this conjecture is still wide open, but there is a somewhat weaker result.
\begin{theorem}[\protect{\cite[Theorem 1.1]{HKSS_2019_1}}]\label{Weak Rigidity Theorem}
There exist integer coefficients $a_i, b_i, c_i, d_i$ such that for every $C > 0$, there exists a positive integer $N$ such that for all integers $n \geq N$,
\begin{align*}
U(1,n) \cap [1,Cn] = \left(\bigcup_{i = 0}^\infty\ [a_i n + b_i, c_i n + d_i] \right) \cap [1,Cn].
\end{align*}
\end{theorem}
\begin{table}
\renewcommand{\arraycolsep}{1.8pt}
\begin{align*}
\begin{array}{lllllllllll}
U(1,X) = \{1\} & \cup & [X, 2 X] & \cup & \{2 X+2\} & \cup & \{4 X\} \\
& \cup & [4 X+2, 5 X-1] & \cup & \{5 X+1\} & \cup & [7 X+3, 8 X+1] \\
& \cup & \{10 X+2\} & \cup & \{11 X+2\} & \cup & [13 X+4, 14 X+1] \\
& \cup & \{16 X+2\} & \cup & \{17 X+2\} & \cup & \{19 X+3\} \\
& \cup & \{20 X+2\} & \cup & \{22 X+3\} & \cup & \{23 X+4\} \\
& \cup & [25 X+4, 25 X+5] & \cup & \{26 X+3\} & \cup & \{28 X+4\} \\
& \cup & [31 X+5, 32 X+3] & \cup & \{34 X+5\} & \cup & \{38 X+6\} \\
& \cup & \{40 X+5\} & \cup & [40 X+8, 41 X+4] & \cup & [43 X+7, 44 X+4] \\
& \cup & \{44 X+6\} & \cup & \{46 X+7\} & \cup & [49 X+8, 50 X+6] \\
& \cup & [52 X+8, 53 X+7] & \cup & [55 X+9, 56 X+6] \ldots
\end{array}
\end{align*}
\caption{The first $30$ intervals of $U(1,X)$---equivalently, replacing $X$ with $n$, the first $56n + 6$ terms of $U(1,n)$ when $n \geq 4$.}
\label{tab:First 30 Intervals}
\end{table}
The original proof of this theorem was nonconstructive and in fact model-theoretic in nature, although we showed \cite{HKSS_2019_1} that assuming Theorem \ref{Weak Rigidity Theorem}, one can prove that there exists an algorithm that will both find the coefficients $a_i,b_i,c_i,d_i$ and the minimal integer $N_0$ that will satisfy the conditions of Theorem \ref{Weak Rigidity Theorem}, given $C > 0$. Our present goal is to give an alternate, constructive proof of Theorem \ref{Weak Rigidity Theorem} by considering a variant of the Ulam sequence that sits inside the polynomial ring $\ZZ[X]$. This ring can be given the structure of an ordered ring via the lexicographical ordering---that is, $p(X) > q(X)$ if and only if the leading term of $p(X) - q(X)$ has a positive coefficient. In Section \ref{section: new Ulam sequence}, we define a set
\begin{align*}
U(1,X) = \bigcup_{i = 0}^\infty\ [a_i X + b_i, c_i X + d_i] \subset \ZZ[X]
\end{align*}
which should be viewed as an analog of an Ulam sequence inside this ordered ring; specifically, in the additive subgroup of linear polynomials. Here $[x,y]$ has the usual meaning that it is the set of all elements $z \in \ZZ[X]$ such that $x \leq z \leq y$. We call the sequences $(a_i)_{i \in \NN}$, $(b_i)_{i \in \NN}$, $(c_i)_{i \in \NN}$, and $(d_i)_{i \in \NN}$ the \emph{coefficients} of $U(1,X)$---as we shall see, they are uniquely determined and, better yet, there is an algorithm to compute them.
\begin{theorem}\label{Main Theorem}
There exists a polynomial-time algorithm $\mathcal{A}_\text{Ulam}$ such that on an input of $k \in \NN$, it returns the first $k$ coefficients of $U(1,X)$---that is, $(a_i)_{i = 0}^k$, $(b_i)_{i = 0}^k$, $(c_i)_{i = 0}^k$, and $(d_i)_{i = 0}^k$---and an integer $N$ such that for all $n \geq N$,
\begin{align*}
U(1,n) \cap [1, c_k n + d_k + 1] = \bigcup_{i = 0}^k\ [a_i n + b_i, c_i n + d_i].
\end{align*}
\end{theorem}
Theorem \ref{Weak Rigidity Theorem} is an immediate corollary of Theorem \ref{Main Theorem}. We construct an explicit example of such an algorithm in Section \ref{section: algorithms} and show that there should be many other such algorithms, including ones that are likely much more efficient. Studying the output of such algorithms raises the possibility of proving that
\begin{align*}
U(1,n) = \bigcup_{i = 0}^\infty \ [a_i n + b_i, c_i n + d_i]
\end{align*}
for all $n \geq N$, for some natural number $N$. To the best of the author's knowledge, this is the first proposed method of attacking Conjecture \ref{conj:rigidity}. However, this is not the only benefit of introducing the set $U(1,X)$---it also makes it convenient to state a conjecture for which the author found ample numerical evidence, which is presented in Section \ref{section: numerical}.
\begin{conjecture}\label{conj:stat}
Let $a_i,b_i,c_i,d_i$ be the coefficients of $U(1,X)$. There exist real numbers $\lambda' \approx 0.417031, \sigma_1 \approx 1.86, \sigma_2 \approx -1.3$ such that for every $\epsilon > 0$, if $i$ is sufficiently large, then
\begin{align*}
a_iX + b_i, c_iX + d_i \bmod 3X + \lambda' \in &\left(X + \frac{\lambda'}{3} - \epsilon, X + \sigma_1 + \epsilon\right) \\ \cup &\left(2X + \sigma_2 - \epsilon, 2X + \frac{2\lambda'}{3} + \epsilon\right).
\end{align*}
\end{conjecture}
The precise definition of taking a modulus in $\ZZ[X]$ is given in Section \ref{section: numerical}, but the intuitive idea is as follows: the residues of the endpoints of the intervals defining $U(1,X)$ are
\begin{enumerate}
\item constrained (to $\epsilon$-neighborhoods of) the middle third of the interval $[0,3X + \lambda']$---that is, between $X + \lambda'/3$ and $2X + 2\lambda'/3$, and
\item there also seems to be a gap inside that middle third interval, namely $(X + \sigma_1, 2X + \sigma_2)$, where these residues also do not appear.
\end{enumerate}
This conjecture should be seen as an analog of Conjecture \ref{conj:gibbslike} for the ordered ring $\ZZ[X]$. In Section \ref{section: conjectures}, we also demonstrate that Conjecture \ref{conj:stat} has a number of remarkable consequences---for example, it implies that $b_i$ grows linearly with respect to $a_i$, and similarly $d_i$ grows linearly with respect to $c_i$; furthermore, we prove that Conjectures \ref{conj:stat} and \ref{conj:rigidity} together imply Conjecture \ref{conj:gibbslike}, for $n \geq 4$.
\begin{figure}
\begin{center}
\includegraphics[width=0.85\textwidth]{Ulam_Statistics.pdf}
\end{center}
\caption{A histogram of $U(1,X) \bmod \lambda(X)$ for the first 200000 intervals. The plot on the left represents elements in $(X + \frac{\lambda'}{3} - \epsilon, X + \sigma_1 + \epsilon)$. The plot on the right represents elements in $(2X + \sigma_2 - \epsilon, 2X + \frac{2\lambda'}{3} + \epsilon)$.}
\label{Ulam Statistics}
\end{figure}
\section{An Ulam-like sequence}\label{section: new Ulam sequence}
We begin by defining what we mean by Ulam sequences in $\langle 1,X \rangle$, the abelian group generated by $1,X$ in $\ZZ[X]$; equivalently, this is the set of linear integer polynomials. We always take this to be an ordered group via the lexicographical ordering---i.e., $aX + b > cX + d$ if and only if $a > c$ or $a = c$ and $b > d$.
\begin{definition}
Given $0 < a < b$ in $\langle 1,X \rangle$, an \emph{Ulam sequence} starting with $a,b$ is a set $U \subset \langle 1,X \rangle$ such that
\begin{enumerate}
\item $U \cap (-\infty,b] = \{a,b\}$,
\item for all $p < q \in \langle 1,X \rangle$, $U \cap [p,q]$ has both a minimum and a maximum, and
\item for every $p \in (b,\infty)$, $p \in U$ if and only if it is the smallest element in the set
\begin{align*}
\left\{q \in \langle 1,X \rangle\middle|q > U \cap (-\infty,p) \text{ and } \exists! x \neq y \in U, \ q = x + y\right\}.
\end{align*}
\end{enumerate}
\end{definition}
\begin{table}
\centering
\begin{align*}
X,&X+1,2 X+1,3 X+1,3 X+2,4 X+1,4 X+3,5 X+1,5 X+4,6 X+1, \\
&6 X+3,6 X+5,7 X+1,7 X+6,8 X+1,8 X+3,8 X+5,8 X+7,9 X+1, \\
&9 X+8,10 X+1,10 X+3,10 X+5,10 X+7,10 X+9,11 X+1,11 X+10,\\
&12 X+1,12 X+3,12 X+5,12 X+7,12 X+9,12 X+11,13 X+1,13 X+12, \\
&14 X+1,14 X+3,14 X+5,14 X+7,14 X+9,14 X+11,14 X+13,15 X+1,\\
&15 X+14,16 X+1,16 X+3,16 X+5,16 X+7,16 X+9,16 X+11,16 X+13,\\
&16 X+15,17 X+1,17 X+16,18 X+1,18 X+3,18 X+5,18 X+7,18 X+9,\\
&18 X+11,18 X+13,18 X+15,18 X+17,19 X+1,19 X+18,20 X+1,20 X+3,\\
&20 X+5,20 X+7,20 X+9,20 X+11,20 X+13,20 X+15,20 X+17,20 X+19,\\
&21 X+1,21 X+20,22 X+1,22 X+3,22 X+5,22 X+7,22 X+9,22 X+11,\\
&22 X+13,22 X+15,22 X+17,22 X+19,22 X+21,23 X+1,23 X+22,\\
&24 X+1,24 X+3,24 X+5,24 X+7,24 X+9,24 X+11,24 X+13,\\
&24 X+15,24 X+17,24 X+19, \ldots
\end{align*}
\caption{The first 100 terms of the unique Ulam sequence starting with $X,X+1$.}
\label{tab:weird ulam sequence}
\end{table}
\begin{remark}
The idea of extending Ulam sequences to other ordered abelian groups than the integers is not new---Kravitz and Steinerberger \cite{kravitz_steinerberger_2017} previously showed that one can define the notion of an Ulam subset of $\RR^n$.
\end{remark}
Why do we say that it is \emph{an} Ulam sequence, rather than \emph{the} Ulam sequence? This is because, in general, it is not unique! For example, it follows from earlier model-theoretic results \cite{HKSS_2019_1} that there exist Ulam sequences $U,U'$ starting with $2,X$ such that
\begin{align*}
U \cap [2,2X + 1] &= \{2\} \cup \{X + 2k|k \in \NN\} \cup \{2X - 2k|k \in \NN\} \\
U' \cap [2,2X + 1] &= \{2\} \cup \{X + 2k|k \in \NN\} \cup \{2X - 2k + 1|k \in \NN\}.
\end{align*}
Nevertheless, there are some specific cases where such an Ulam sequence is unique---in particular, we show that there is a unique Ulam sequence starting with $1,X$, which we denote by $U(1,X)$. This set is very special in that it is a disjoint union of intervals with an important finiteness property.
\begin{definition}
We say a set $S \subset \langle 1, X \rangle$ is a \emph{union of intervals with finite intersections} if it is a disjoint union of intervals $[a,b] \subset \langle 1,X \rangle$ such that for every $a, b \in \langle 1,X\rangle$, there are only finitely many of these intervals between $a$ and $b$.
\end{definition}
\begin{remark}
The core idea is that while $S$ might contain infinitely many intervals, every intersection with an interval $[a,b]$ can only contain finitely many.
\end{remark}
It is easy to see that for every union of intervals with finite intersections $S$, there exist integer sequences $a_i,b_i,c_i,d_i$ and $N \in \ZZ_{>0} \cup \{\infty\}$ such that
\begin{align*}
S = \bigcup_{i = 0}^N \ \left[a_i X + b_i, c_i X + d_i\right]
\end{align*}
and $c_i X + d_i + 1 < a_{i + 1} + b_{i + 1}$ for all $i < N$. This decomposition is clearly unique, which makes the following definition sensible.
\begin{definition}
Given a union of intervals with finite intersections $S$, we call the decomposition
\begin{align*}
S = \bigcup_{i = 0}^N \ \left[a_i X + b_i, c_i X + d_i\right]
\end{align*}
where $a_i,b_i,c_i,d_i$ are integer sequences and $N \in \ZZ_{>0} \cup \{\infty\}$ the \emph{standard form} of $S$. We call the sequences $a_i,b_i,c_i,d_i$ the \emph{coefficients} of $S$.
\end{definition}
To prove that there is a unique Ulam sequence starting with $1,X$, we start by showing that the beginning of its standard form is uniquely determined.
\begin{lemma}
Let $U$ be an Ulam sequence starting with $1,X$. Then $U \cap [1,2X + 1] = \{1\} \cup [X,2X]$.
\end{lemma}
\begin{proof}
Obviously, $U$ contains both $1$ and $X$, and hence it contains $X + 1$. By induction, it must also contain $X + k$ for all $k \in \NN$. It follows that it must contain elements $2X - k$ with $k$ arbitrarily large, since otherwise $U \cap [1,2X - k]$ would fail to have a maximum for some $k \in \NN$. But $2X-k$ must be the sum of two prior elements $u < v$, and if $u,v \geq X$, then it would have to be at least $2X + 1 = X + (X + 1)$. Therefore, $u = 1$ and $v = 2X - k - 1$, which is to say that $[X,2X] \subset U$. Finally, since $2X + 1$ can be written as the sum of distinct elements in $U$ in two different ways, $2X + 1 \notin U$.
\end{proof}
\begin{theorem}\label{unique linear polynomial Ulam sequence}
There exists a unique Ulam sequence $U(1,X)$ starting with $1,X$. Furthermore, $U(1,X)$ is a union of intervals with finite intersections.
\end{theorem}
\begin{proof}
We prove by induction that for all $k \in \NN$, there exists $l_k \in \ZZ$ and a unique set $U \subset [1,kX + l_k]$ such that
\begin{enumerate}
\item $U \cap [1,X] = \{1,X\}$,
\item $U$ is a finite union of intervals, and
\item for every $u \in [1,kX + l_k]$, $u \in U$ if and only if there exists a unique pair $p < q \in U$ such that $u = p + q$.
\end{enumerate}
We already know that this is true for $k = 0,1$. So, assume that it is true for $k - 1$; we prove it for $k$. Start with a set $U \subset [1,(k - 1)X + l_{k - 1}]$ which has the desired properties. By induction, there is a unique extension $U' \subset [1,(k - 1)X + l]$ for all $l \in \NN$ such that
\begin{enumerate}
\item $U' \cap [1,X] = \{1,X\}$ and
\item for every $u \in [1,(k - 1)X + l]$, $u \in U'$ if and only if there exists a unique pair $p < q \in U'$ such that $u = p + q$.
\end{enumerate}
Moreover, our claim is that if $l$ is sufficiently large, then either $U' \cap [(k - 1)X + l,(k - 1)X + l'] = [(k - 1)X + l,(k - 1)X + l']$ for all larger $l'$, or $U' \cap [(k - 1)X + l,(k - 1)X + l'] = \emptyset$. This is because if $u \in U'$, then $u + 1 \in U'$ unless there exist $X \leq p < q$ such that $u + 1 = p + q$. But it must be that $p < q < (k - 2)X + l$ for some $l \in \ZZ$ since otherwise $p + q$ would be too big. Therefore, $p,q$ both belong to one of the intervals of $U$---there are only finitely many of these, hence
\begin{align*}
[1,kX] \backslash \left\{p + q\middle|1 < p < q \in U\right\}
\end{align*}
is a finite union of intervals. Therefore, if $l$ is sufficiently large, the intersection of this set with $[(k - 1)X + l, kX - l]$ is either all of $[(k - 1)X + l, kX - l]$ or empty. In the first case, $U' \cap [(k - 1)X + l,(k - 1)X + l'] = \emptyset$; in the second case, either $U' \cap [(k - 1)X + l,(k - 1)X + l'] = \emptyset$ or $U' \cap [(k - 1)X + l,(k - 1)X + l'] = [(k - 1)X + l,(k - 1)X + l']$, depending on whether $(k - 1)X + l \in U'$.
If there exists $l \in \NN$ such that $U' \cap [(k - 1)X + l,(k - 1)X + l'] = [(k - 1)X + l,(k - 1)X + l']$ for all larger $l'$, then there exists some $l'' \in \ZZ$ such that
\begin{align*}
\left([1,kX] \backslash \left\{p + q\middle|1 < p < q \in U\right\}\right) \cap [(k - 1)X + l, kX - l''] = \emptyset.
\end{align*}
Therefore, if we define $l_k = l''$, $U'' = U \cup [(k - 1)X + l, kX + l'']$, then
\begin{enumerate}
\item $U'' \cap [1,X] = \{1,X\}$,
\item $U''$ is a finite union of intervals, and
\item for every $u \in [1,kX + l_k]$, $u \in U''$ if and only if there exists a unique pair $p < q \in U''$ such that $u = p + q$.
\end{enumerate}
Moreover, this is the only possible extension of $U'$ to $[1,kX + l_k]$, since the requirement that $U'' \cap [1,kX + l_k]$ have a maximum requires that there must be some element $kX + l''' \in U''$---but this forces $kX + l''' - 1, kX + l'''-2,\ldots \in U''$ and $kX + l''' + 1, kX + l''' + 2,\ldots, kX + l_k \in U$.
Otherwise, $U' \cap [(k - 1)X + l,kX - l] = \emptyset$ for sufficiently large $l$. We can choose $l$ large enough such that for all $p \in [(k - 1)X + l, kX - l]$, either there exists more than one pair $X \leq u,v < kX - l$ such that $p = u + v$, or there are no such pairs. Then if we define $l_k = -l$, then $U'$ is a subset of $[1,kX + l_k]$ such that
\begin{enumerate}
\item $U' \cap [1,X] = \{1,X\}$,
\item $U'$ is a finite union of intervals, and
\item for every $u \in [1,kX + l_k]$, $u \in U'$ if and only if there exists a unique pair $p < q \in U'$ such that $u = p + q$.
\end{enumerate}
Moreover, this is the only possible way to extend $U'$ to $[1,kX + l_k]$---if we were to add any element $kX + l$, it would require that $kX + l - 1, kX + l - 2, \ldots \in U'$, which would contradict the requirement that $U' \cap [(k - 1)X + l,kX + l_k]$ has a minimum.
Thus, we have shown that there is a unique $U \subset [1,kX + l_k]$ for all $k$. But this gives a unique $U \subset \langle 1,X\rangle$ which is just a union of all these sets---it is easy to see that this $U$ is the unique Ulam sequence starting with $1,X$, and that it is a union of intervals with finite intersections.
\end{proof}
\section{Numerical results}\label{section: numerical}
In light of Theorem \ref{unique linear polynomial Ulam sequence}, we know that $U(1,X)$ is uniquely defined; we now discuss some of the numerical data gathered about this set. In Section \ref{section: algorithms}, we produce an algorithm $\mathcal{A}_{\text{Ulam}}$ such that on an input of $k \in \NN$, it returns the first $k$ coefficients of $U(1,X)$ and an integer $N$ such that for all $n \geq N$,
\begin{align*}
\eval_{X \rightarrow n}\left(U(1,X) \cap [1,c_k X + d_k]\right) = U(1,n) \cap [1,c_k n + d_k],
\end{align*}
where $\eval_{X \rightarrow n}:\ZZ[X] \rightarrow \ZZ$ is the evaluation map sending $X$ to $n$. This algorithm has in fact been implemented in Python by the author; unfortunately, in practice $\mathcal{A}_\text{Ulam}$ is not very efficient, as we shall discuss.
An easier approach toward computing the coefficients $a_i,b_i,c_i,d_i$ is to assume that Conjecture \ref{conj:rigidity} is true and that Ulam sequences grow linearly, and then to compute $U(1,4)$ and $U(1,5)$ up to a suitably large number of terms, from which one can compute the coefficients $a_i,b_i,c_i,d_i$. The results of this method can be proven correct by using Theorem 3.1 from a paper of Hinman, Kuca, Schlesinger, and the present author \cite{HKSS_2019_2}; one need only verify that there exists a $B \approx 0.13901$ such that
\begin{enumerate}
\item $\left|b_i - B a_i\right|,\left|d_i - B c_i\right| < 2.5$ for all $i$, and
\item for $n = 4,5,\ldots 14$,
\begin{align*}
U(1,n) \cap \left[1, c_k n + d_k\right] = \bigcup_{i = 0}^k \ \left[a_i n + b_i, c_i n + d_i\right].
\end{align*}
\end{enumerate}
It is immediate from these calculations that the computed coefficients $a_i,b_i,c_i,d_i$ are actually the coefficients of $U(1,X)$ since we know that
\begin{align*}
\eval_{X \rightarrow n}\left(U(1,X) \cap [1,c_k X + d_k + 1]\right) = U(1,n) \cap [1,c_k n + d_k + 1],
\end{align*}
for sufficiently large $n$ and that the standard form of $U(1,X)$ is uniquely determined.
In this way, using a basic $\Theta(k^2)$ algorithm for computing Ulam sequences $U(1,n)$, the author was able to compute coefficients $a_i,b_i,c_i,d_i$ such that for all $n \geq 4$,
\begin{align*}
U(1,n) \cap \left[1, c_{217529} n + d_{217529}\right] = \bigcup_{i = 0}^{217529}\ \left[a_i n + b_i, c_i n + d_i\right].
\end{align*}
As $(a_{217529},b_{217529},c_{217529},d_{217529}) = (966409, 134342, 966410, 134340)$, this is the full list of coefficients $a_i,b_i,c_i,d_i$ such that $c_i n + d_i \leq 966410 n + 134340$. This data gives further numerical evidence for Conjecture \ref{conj:gibbslike}; specifically, defining $\lambda_n = 3n + 0.417031$, we consider the sets $U(1,n) \bmod \lambda_n$. We find that $99.9\%$ of the terms smaller than $10^7 n$ lie in the interval $[\lambda_n/3,2\lambda_n/3]$---this is shown in Figures \ref{Middle Third Statistics} and \ref{Middle Third Diagram}.
\begin{figure}
\begin{center}
\begin{tabular}{cccc}
$n$ & $\#$ of exceptions & $\#$ elements of $U(1,n)$ computed & Percent of exceptions \\ \hline
4 & 411 & 635045 & 0.0647198\% \\
5 & 416 & 814686 & 0.0510626\% \\
6 & 423 & 994573 & 0.0425308\% \\
7 & 426 & 1174402 & 0.0362738\% \\
8 & 427 & 1354386 & 0.0315272\% \\
9 & 430 & 1534323 & 0.0280254\% \\
10 & 430 & 1714404 & 0.0250816\% \\
11 & 432 & 1894463 & 0.0228033\% \\
12 & 433 & 2074581 & 0.0208717\% \\
13 & 436 & 2254856 & 0.019336\% \\
14 & 436 & 2435164 & 0.0179043\%
\end{tabular}
\end{center}
\caption{Computations of the number of elements $u \in U(1,n)$ such that $u \bmod \lambda_n$ is not between $\lambda_n/3$ and $2\lambda_n/3$.}
\label{Middle Third Statistics}
\end{figure}
\begin{figure}
\centering
\begin{tabular}{cc}
\includegraphics[width=0.4\textwidth]{Ulam4_Period.pdf} & \includegraphics[width=0.4\textwidth]{Ulam5_Period.pdf} \\
\includegraphics[width=0.4\textwidth]{Ulam6_Period.pdf} & \includegraphics[width=0.4\textwidth]{Ulam7_Period.pdf} \\
\includegraphics[width=0.4\textwidth]{Ulam8_Period.pdf} & \includegraphics[width=0.4\textwidth]{Ulam9_Period.pdf}
\end{tabular}
\caption{From left to right, and top to bottom, histograms of $U(1,n) \bmod \lambda_n$ for $n = 4,5,6,7,8,9$. The dashed lines split the interval into thirds.}
\label{Middle Third Diagram}
\end{figure}
With this motivation, it is natural to investigate whether there might be some ``magic polynomial" $\lambda(X)$ and a way to define $U(1,X) \bmod \lambda(X)$ such that the resulting distribution has interesting properties. Not only is this possible, but the results are startling. First, we give a couple of definitions.
\begin{definition}
Given elements $p,q \in \RR[X]$, define their \emph{remainder set} to be
\begin{align*}
\mathcal{R}_{p,q} := \left\{p - sq\middle|s \in \ZZ[X], \ p - sq \geq 0\right\}.
\end{align*}
If $\mathcal{R}_{p,q}$ has a smallest element, we define $p \bmod q = \min \mathcal{R}_{p,q}$.
\end{definition}
Notice in particular that if we define $\lambda(X) = 3X + .417031$, then $U(1,X) \bmod \lambda(X)$ is a well-defined subset of $\left\{a X + b\middle|a \in \{0,1,2\}, \ b \in \QQ\right\} \subset \QQ[X]$.
\begin{definition}
We say that an interval $[p,q] \subset \QQ[X]$ is $\emph{long}$ if $\deg(q - p) > 0$. Otherwise, we say that the interval is \emph{short}.
\end{definition}
Remarkably, long intervals in $U(1,X)$ seem to occur almost exactly four times as often as short ones---for the first $217530$ intervals, we find that $79.98\%$ are long, and $20.02\%$ are short. These two interval types seem to exhibit slightly different statistical behaviors modulo $\lambda(X)$, so we split into two cases accordingly.
\begin{description}
\item[Long Intervals:]
Let $\mathcal{U}_L$ be the subset of $U(1,X)$ consisting of all long intervals, and let $a_i',b_i',c_i',d_i'$ be the coefficients of $\mathcal{U}_L$. For all $i$ such that $c_i' X + d_i' \leq 966410 X + 134340$, we find that $a_i' \equiv \modd{1} {3}$ and $c_i' \equiv \modd{2} {3}$, hence $a_i'X + b_i' \bmod \lambda(X) = X + \sigma_{i,1}$ and $c_i'X + d_i' \bmod \lambda(X) = 2X + \sigma_{i,2}$. Furthermore, we find that $|\sigma_{i,1}|, |\sigma_{i,2}| < 3$ for all $i$. The statistical distributions of $\sigma_{i,1}$ and $\sigma_{i,2}$ are given in Figure \ref{Coefficient Distributions Long}.
\begin{figure}
\centering
\begin{tabular}{cc}
\includegraphics[width=0.4\textwidth]{Ulam_Long_First_Coeff.pdf} & \includegraphics[width=0.4\textwidth]{Ulam_Long_Second_Coeff.pdf}
\end{tabular}
\caption{The histograms of $\sigma_{i,1}$ (left) and $\sigma_{i,2}$ (right), together with black lines at $x = \lambda'/3$ (left) and $x = 2\lambda'/3$ (right), and blue lines at $x = 1.86$ (left) and $x = -1.3$ (right).}
\label{Coefficient Distributions Long}
\end{figure}
\item[Short Intervals:]
Let $\mathcal{U}_S$ be the subset of $U(1,X)$ consisting of all short intervals, and let $a_i',b_i',c_i',d_i'$ be the coefficients of $\mathcal{U}_S$. For all $i$ such that $c_i' X + d_i' \leq 966410 X + 134340$, we find that $b_i' = d_i'$ with just a single exception, namely the interval $[25X + 4, 25X + 5]$. Furthermore, we find that $a_i' \equiv \modd{0} {3}$ if and only if $(a_i',b_i',c_i',d_i') = (0,1,0,1)$, $a_i' \equiv \modd{1} {3}$ is true for $\approx 43.7\%$ of indices $i$, and $a_i' \equiv \modd{2} {3}$ is true for $\approx 56.3\%$ of indices $i$. Therefore, $a_i'X + b_i' \bmod \lambda(X) = X + \sigma_{i,3}$ or $a_i'X + b_i' \bmod \lambda(X) = 2X + \sigma_{i,4}$, and we find that $|\sigma_{i,3}|,|\sigma_{i,4}| \leq 2$ for all $i$. The statistical distributions of $\sigma_{i,3}$ and $\sigma_{i,4}$ are given in Figure \ref{Coefficient Distributions Short}.
\begin{figure}
\centering
\begin{tabular}{cc}
\includegraphics[width=0.4\textwidth]{Ulam_Short_Mod1.pdf} & \includegraphics[width=0.4\textwidth]{Ulam_Short_Mod2.pdf}
\end{tabular}
\caption{The histograms of $\sigma_{i,3}$ (left) and $\sigma_{i,4}$ (right), together with black lines at $x = \lambda'/3$ (left) and $x = 2\lambda'/3$ (right), and blue lines at $x = 0.86$ (left) and $x = -0.34$ (right).}
\label{Coefficient Distributions Short}
\end{figure}
\end{description}
One final, but important, numerical observation is that the bulk of of the $\sigma_{i,j}$ appear to be bounded---specifically, $\sigma_{i,1},\sigma_{i,3} \geq \lambda'/3$ and $\sigma_{i,2},\sigma_{i,4} \leq 2\lambda'/3$ for almost all $i$. Additionally, $\sigma_{i,1} \leq 1.86$, $\sigma_{i,3} \leq 0.86$, $\sigma_{i,2} \geq -1.3$, and $\sigma_{i,4} \geq -0.34$ for almost all $i$. Taking all of this information together, we precisely come up with Conjecture \ref{conj:stat}. Note additionally that $1.86 \approx 2 - \lambda'/3$ and $-1.3 \approx -1 - 2\lambda'/3$; unfortunately, the numerical evidence is insufficient to conjecture this with any strong degree of certainty.
\section{Relations between conjectures}\label{section: conjectures}
The importance of Conjecture \ref{conj:stat} is that, if true, then it sheds light on other open questions about Ulam sequences. We give a few examples.
\begin{theorem}
If Conjecture \ref{conj:stat} is true, then taking $B = \lambda'/3$, for all $\epsilon > 0$, if $i$ is sufficiently large,
\begin{align*}
\left|b_i - B a_i\right|,\left|d_i - B c_i\right| < \min\left(\sigma_1 -\frac{\lambda'}{3} + \epsilon, \frac{2\lambda'}{3} - \sigma_2 + \epsilon\right).
\end{align*}
\end{theorem}
\begin{proof}
Note that if $i > 0$, then
\begin{align*}
a_iX + b_i \bmod 3X + \lambda' &= a_iX + b_i - (3X + \lambda')\lfloor a_i/3\rfloor \\
&= \left(a_i - 3\lfloor a_i/3\rfloor\right)X + b_i + \frac{\lambda'}{3}\left(a_i - \lfloor a_i/3\rfloor\right) - \frac{\lambda' a_i}{3} \\
&= \begin{cases} X + b_i + \frac{\lambda'}{3} - \frac{\lambda' a_i}{3}, & \text{if } a_i \equiv \modd{1} {3}; \\
2X + b_i + \frac{2\lambda'}{3} - \frac{\lambda' a_i}{3}, & \text{if } a_i \equiv \modd{2} {3}. \end{cases}
\end{align*}
Therefore, for sufficiently large $i$, either
\begin{align*}
b_i + \frac{\lambda'}{3} - \frac{\lambda' a_i}{3} &\in \left(\frac{\lambda'}{3} - \epsilon, \sigma_1 + \epsilon\right) \\
b_i - \frac{\lambda' a_i}{3} &\in \left(-\epsilon, \sigma_1 -\frac{\lambda'}{3} + \epsilon\right) \\
\left|b_i - \frac{\lambda' a_i}{3}\right| &< \sigma_1 -\frac{\lambda'}{3} + \epsilon
\end{align*}
or
\begin{align*}
b_i + \frac{2\lambda'}{3} - \frac{\lambda' a_i}{3} &\in \left(\sigma_2 - \epsilon, \frac{2\lambda'}{3} + \epsilon\right) \\
b_i - \frac{\lambda' a_i}{3} &\in \left(\sigma_2 - \frac{2\lambda'}{3} - \epsilon, \epsilon\right) \\
\left|b_i - \frac{\lambda' a_i}{3}\right| &< \frac{2\lambda'}{3} - \sigma_2 + \epsilon.
\end{align*}
The argument for $c_i X + d_i$ is identical.
\end{proof}
\begin{theorem}
If Conjecture \ref{conj:rigidity} and Conjecture \ref{conj:stat} are true, then Conjecture \ref{conj:gibbslike} is true for $n \geq 4$.
\end{theorem}
\begin{proof}
Fix an $n \geq 4$ and define $\lambda_n = 3n + \lambda'$. Choose an $\epsilon > 0$. By Conjecture \ref{conj:stat}, we get that if $i$ is sufficiently large, then
\begin{align*}
a_in + b_i - \lambda_n \left\lfloor \frac{a_i}{3}\right\rfloor &= \left(a_i - 3\left\lfloor \frac{a_i}{3}\right\rfloor\right)n + \left(b_i - \lambda'\left\lfloor \frac{a_i}{3}\right\rfloor\right) \\
&\in \left(n + \frac{\lambda'}{3} - \epsilon, n + \sigma_1 + \epsilon\right) \cup \left(2n + \sigma_2 - \epsilon, 2n + \frac{2\lambda'}{3} + \epsilon\right) \\
&\subset \left(\frac{\lambda_n}{3} - \epsilon, \frac{2\lambda_n}{3} + \epsilon\right).
\end{align*}
Since this gives a real number between $0$ and $\lambda_n$, we conclude that for $i$ sufficiently large,
\begin{align*}
a_in + b_i \bmod \lambda_n \in &\left(\frac{\lambda_n}{3} - \epsilon, \frac{2\lambda_n}{3} + \epsilon\right),
\end{align*}
and similarly for $c_in + d_i$---thus, by Conjecture \ref{conj:rigidity}, it suffices to prove that for all $a_i n + b_i < u < c_i n + d_i$,
\begin{align*}
u \bmod \lambda_n \in &\left(\frac{\lambda_n}{3} - \epsilon, \frac{2\lambda_n}{3} + \epsilon\right).
\end{align*}
If $a_i = b_i$, then $u = a_i n + r$, where $b_i < r < d_i$. Therefore,
\begin{align*}
u - \lambda_n \left\lfloor \frac{u}{3}\right\rfloor &= \left(a_i - 3\left\lfloor \frac{a_i}{3}\right\rfloor\right)n + \left(r - \lambda'\left\lfloor \frac{a_i}{3}\right\rfloor\right) \\
&\in \left(\frac{\lambda_n}{3} - \epsilon, \frac{2\lambda_n}{3} + \epsilon\right),
\end{align*}
hence we have the desired conclusion. If $a_i \neq b_i$, then $b_i = a_i + 1$, and therefore $(a_i,b_i) \bmod 3 = (1,2)$. In that case, we know that
\begin{align*}
a_i n + b_i \bmod \lambda_n &\in \left(n + \frac{\lambda'}{3} - \epsilon, n + \sigma_1 + \epsilon\right).
\end{align*}
Since $u - (a_i n + b_i) < n$ and $2n + \sigma_1 + \epsilon < \lambda_n$ if $\epsilon$ is small enough, we conclude that
\begin{align*}
u \bmod \lambda_n = \left(a_i n + b_i \bmod \lambda_n\right) + u - a_i n + b_i,
\end{align*}
whence
\begin{align*}
u \bmod \lambda_n \in &\left(\frac{\lambda_n}{3} - \epsilon, \frac{2\lambda_n}{3} + \epsilon\right).
\end{align*}
\end{proof}
\section{Algorithms}\label{section: algorithms}
We close by giving the technical details behind Theorem \ref{Main Theorem} and the promised algorithm $\mathcal{A}_\text{Ulam}$. Before we present this, we will need four intermediate subroutines.
\begin{alg}\label{Sum Algorithm}
On an input of two intervals $I_1 = [p_1,q_1]$, $I_2 = [p_2,q_2]$ such that $p_2 + 1 < q_1$, this algorithm returns a pair of unions of intervals with finite intersections $S_1, S_2$ such that $S_1$ consists of all elements that can be written as the sum of an element of $I_1$ and an element of $I_2$ in exactly one way, and $S_2$ consists of all elements that can be written as the sum of an element of $I_1$ and an element of $I_2$ in more than one way.
\begin{algorithm}[H]
\begin{algorithmic}[1]
\Procedure{SumDistinct}{$I_1$,$I_2$}
\State $\start \gets p_1 + p_2$
\State $\final \gets q_1 + q_2$
\If{$\# I_1 = 1$ or $\# I_2 = 1$}
\State $S_1 \gets [\start, \final]$
\State $S_2 \gets \{\}$
\Else
\State $S_1 \gets \{\start\} \cup \{\final\}$
\State $S_2 \gets [\start + 1, \final - 1]$
\EndIf
\State \textbf{return} $S_1, S_2$
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{alg}
\begin{proof}[Proof of Correctness]
Clearly, $I_1 + I_2 = [\start, \final]$, so it is solely a question of how this set is partitioned between $S_1$ and $S_2$. If $\# I_1 = 1$ or $\# I_2 = 1$, then it is easy to see that $S_2$ is empty and $S_1 = [\start, \final]$. Otherwise, $\start, \final \in S_1$, but for every $x \in [\start + 1, \final - 1]$ we can write $x = u + v = (u - 1) + (v + 1)$ for some $u,(u - 1) \in I_1$, $v, (v + 1) \in I_2$.
\end{proof}
\begin{alg}\label{Sum Algorithm Redux}
On an input of an interval $I = [p,q]$, this algorithm returns a pair of unions of intervals with finite intersections $S_1, S_2$ such that $S_1$ consists of all elements that can be written as the sum of two distinct elements of $I$ in exactly one way, and $S_2$ consists of all elements that can be written as the sum of two distinct elements of $I$ in more than one way.
\begin{algorithm}[H]
\begin{algorithmic}[1]
\Procedure{SumWithItself}{$I$}
\If{$\# I = 1$}
\State $S_1 \gets \{\}$
\State $S_2 \gets \{\}$
\ElsIf{$\# I = 2$}
\State $S_1 \gets \{p + q\}$
\State $S_2 \gets \{\}$
\ElsIf{$\# I = 3$}
\State $S_1 \gets [2p + 1, 2p + 3]$
\State $S_2 \gets \{\}$
\Else
\State $S_1 \gets [2p + 1, 2p + 2] \cup [2q - 2, 2q - 1]$
\State $S_2 \gets [2p + 3, 2q - 3]$
\EndIf
\State \textbf{return} $S_1, S_2$
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{alg}
\begin{proof}[Proof of Correctness]
It is clear that the subset of $\langle 1,X \rangle$ representable by pairwise sums of distinct elements of $I$ is $[2p + 1, 2q - 1]$. It is easy to see that $2p + 1, 2p + 2, 2q - 2, 2q - 1 \in S_1$ if they are in this subset, while the remainder must be in $S_2$.
\end{proof}
\begin{alg}\label{UnionAlgorithm}
On an input of four unions of intervals with finite intersections $S_1,T_1,S_2,T_2$ such that $S_1 \cap T_1 = S_2 \cap T_2 = \emptyset$, this algorithm returns the unique pair $(S,T)$ of unions of intervals with finite intersections such that $S \cap T = \emptyset$, $S \cup T = S_1 \cup S_2 \cup T_1 \cup T_2$, and $S$ consists of all elements $x \in (S_1 \backslash T_2) \cup (S_2 \backslash T_1)$ such that $x \notin (S_1 \backslash T_2) \cap (S_2 \backslash T_1)$.
\begin{algorithm}[H]
\begin{algorithmic}[1]
\Procedure{Amalgam}{$S_1,T_1,S_2,T_2$}
\State $S_3 \gets S_1 \backslash T_2$
\State $S_4 \gets S_2 \backslash T_1$
\State $S \gets S_3 \triangle S_4$ \Comment{By $\triangle$ we mean the symmetric difference}
\State $T \gets S_1 \cup S_2 \cup T_1 \cup T_2$
\State $T \gets T \backslash S$
\State \textbf{return} $S,T$
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{alg}
\begin{proof}[Proof of Correctness]
It is clear that the defined pair of sets is unique and it is simple to verify that the given operations produce it. Although we have not shown explicitly how to do it here, both intersections and unions are easy to implement on the standard form of unions of intersections with finite intersection, using either a loop or recursion. Since the set of unions of intervals with finite intersection is closed under finite unions and intersections, the result of these operations is guaranteed to be a union of intervals with finite intersection.
\end{proof}
\begin{remark}\label{comment: explanation of union algorithm}
While it is clear what this algorithm does, it might not be clear why we need it. The idea is that $S_1,S_2$ will represent sets of elements $x$ for which only one representation $x = u + v$ with $u \neq v \in U(1,X)$ has been found, and $T_1,T_2$ will represent sets of elements for which multiple representations have been found. The new sets $S,T$ are what is needed to combine this information: $S$ contains everything in $S_1$ and $S_2$ except those elements that are now confirmed to have multiple representations, which get moved to $T$ along with everything else. An element is confirmed to have multiple representations if: 1) it is in either $T_1$ or $T_2$, or 2) it is not in $T_1$ or $T_2$ but is in both $S_1$ and $S_2$.
\end{remark}
\begin{alg}\label{BoundAlgorithm}
Let $\onerepset$ and $\multrepset$ be unions of intervals with finite intersection such that there exists $u \in \langle 1,X \rangle \backslash U(1,X)$ so that
\begin{enumerate}
\item $\onerepset$ consists of all elements greater than $u$ that can be written as the sum of two distinct elements in $U(1,X) \cap [1,u]$ in exactly one way, and
\item $\multrepset$ consists of all elements greater than $u$ that can be written as the sum of two distinct elements in $U(1,X) \cap [1,u]$ in more than one way.
\end{enumerate}
On an input of two such sets $\onerepset,\multrepset$, this algorithm returns the unique interval $[a,b]$ such that if we define $U' = \left(U(1,X) \cap [1,u]\right) \cup [a,b]$, then $U' = U(1,X) \cap [1,b+1]$.
\begin{algorithm}[H]
\begin{algorithmic}[1]
\Procedure{NextInterval}{$\onerepset,\multrepset$}
\State $[p,q] \gets$ smallest interval in $\onerepset$
\If{$p = q$}
\State $b \gets p + X$
\State $b' \gets \min\left(\onerepset \cap [p+1,\infty) \right)$
\State $b'' \gets \min\left(\multrepset \cap [p+1,\infty) \right)$
\State $b \gets \min\left(b,b',b''\right)$
\State \textbf{return} $[p,b - 1]$
\Else
\State \textbf{return} $[p,p]$
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{alg}
\begin{proof}[Proof of Correctness]
Let $p$ be the smallest element in $U(1,X) \cap [u,\infty)$. It must be the sum of two unique elements $u,v \in U(1,X)$, and it is not hard to see that actually $u,v \in U(1,X) \cap [1,u]$, hence $p \in \onerepset$---specifically, $p$ is the starting point of the smallest interval $[p,q]$ in $\onerepset$. If $p \neq q$, we are done: the next interval of $U(1,X)$ is $[p,p]$. This is because $p + 1$ can already be written as the sum of two prior Ulam elements in two different ways: on the one hand, there is the representation coming from $\onerepset$; on the other hand, $1,p \in U(1,X)$.
If $p = q$, then things are more complicated, and we need to find the largest $b$ such that $[p,b - 1] \subset U(1,X)$. Note that if $u \in U(1,X)$ then so is $u + 1$ unless there exist some other $v,w \in U(1,X)$ such that $u + 1 = v + w$. This condition can occur in one of three ways: first, if $u + 1 = p + X$; second, if $u + 1 \in \onerepset$; third, if $u + 1 \in \multrepset$. Therefore, $b$ is the minimum of $p + X$, $\onerepset \cap [p + 1,\infty)$, and $\multrepset \cap [p + 1,\infty)$.
\end{proof}
We are ready to give an algorithm for computing the coefficients of $U(1,X)$.
\begin{alg}\label{Naive Algorithm}
On an input of a natural number $k$, this algorithm returns the first $k + 1$ coefficients $a_i,b_i,c_i,d_i$ of $U(1,X)$.
\begin{algorithm}[H]
\begin{algorithmic}[1]
\Procedure{UlamCoefficients}{$k$}
\State $\ulamset \gets \{1\} \cup [X,2X]$
\State $\onerepset \gets \{\}$
\State $\multrepset \gets \{2X + 1\}$
\State $\largestulam \gets \max\left(\ulamset\right)$
\For{$1 < i \leq k$}
\State $\texttt{last} \gets$ last interval in $\ulamset$
\For{$\texttt{interval} \in \ulamset$}
\If{$\texttt{interval} = \texttt{last}$}
\State $(S, T) \gets \text{SumWithItself}(\texttt{last})$
\Else
\State $(S, T) \gets \text{SumDistinct}(\texttt{interval},\texttt{last})$
\EndIf
\State $S \gets S \cap [\largestulam + 2, \infty)$
\State $T \gets T \cap [\largestulam + 2, \infty)$
\State $(\onerepset,\multrepset) \gets \text{Amalgam}(\onerepset,\multrepset,S,T)$
\EndFor
\State $I \gets \text{NewInterval}(\onerepset,\multrepset)$
\State $\ulamset \gets \ulamset \cup I$
\State $\largestulam \gets \max\left(\ulamset\right)$
\State $\onerepset \gets \onerepset \cap [\largestulam + 2, \infty)$
\State $\multrepset \gets \multrepset \cap [\largestulam + 2, \infty)$
\EndFor
\State \textbf{return} coefficients of $\ulamset$
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{alg}
\begin{remark}
The basic idea behind this algorithm is that it keeps track of three unions of intervals with finite intersections.
\begin{enumerate}
\item $\ulamset$ maintains the subset of $U(1,X)$ computed thus far.
\item $\onerepset$ maintains a subset of $\langle 1,X \rangle$ such that every element of $\onerepset$ is larger than every element of $\ulamset$, and each element of $\onerepset$ can be written as a sum of distinct elements in $\ulamset$ in exactly one way.
\item $\multrepset$ maintains a subset of $\langle 1,X \rangle$ such that every element of $\multrepset$ is larger than every element of $\ulamset$, and each element of $\multrepset$ can be written as a sum of distinct elements in $\ulamset$ in more than one way.
\end{enumerate}
\end{remark}
\begin{proof}[Proof of Correctness]
For $l \in \NN$, let $\mathcal{U}_l$ consist of the first $l + 1$ intervals of $U(1,X)$. We show that at the end of each cycle of the outer for-loop indexed over $i$, $\ulamset = \mathcal{U}_i$; $\largestulam = \max \mathcal{U}_i$; $\onerepset$ consists of all elements of $\mathcal{U}_{i - 1} + \mathcal{U}_{i - 1}$ larger than $\largestulam + 1$ that can be written as a sum of two distinct elements in $\mathcal{U}_{i - 1}$ in exactly one way; and $\multrepset$ consists of all elements of $\mathcal{U}_{i - 1} + \mathcal{U}_{i - 1}$ larger than $\largestulam + 1$ that can be written as a sum of two distinct elements in $\mathcal{U}_{i - 1}$ in more than one way. We prove this claim by induction on $i$.
The base case $i = 1$ is obvious---this is just the initialization of $\ulamset$, $\largestulam$, $\onerepset$, and $\multrepset$ prior to the for-loop. For all subsequent $i$, note that to find all elements $\mathcal{U}_{i - 1} + \mathcal{U}_{i - 1}$ that need to be added to $\onerepset$ and $\multrepset$, it suffices to consider the sums of the intervals in $\mathcal{U}_{i - 2}$ with the last interval of $\mathcal{U}_{i - 1}$, since all other sums have already been handled in prior steps. Thus, for each interval $I$ of $\ulamset$, we add it to the last interval, producing a pair of sets $S,T$, where $S$ consists of all elements that can be written down as a sum in just one way, and $T$ consists of all elements that can be written down as a sum in multiple ways---this is established in the proofs of correctness of Algorithms \ref{Sum Algorithm} and \ref{Sum Algorithm Redux}. We remove anything smaller than $\largestulam + 2$ from both of these sets. We then use Algorithm \ref{UnionAlgorithm} to merge $S$ and $T$ into $\onerepset$ and $\multrepset$, as described in Comment \ref{comment: explanation of union algorithm}. Thus, by the end of the inner for-loop, we have constructed the desired sets $\onerepset$ and $\multrepset$. Algorithm \ref{BoundAlgorithm} then uses these two sets to compute the next interval $I$ of $U(1,X)$ such that $\mathcal{U}_i = \mathcal{U}_{i - 1} \cup I$. We use this to then update $\ulamset$, $\largestulam$, $\onerepset$, and $\multrepset$ as needed.
\end{proof}
What relation does this algorithm have to Theorem \ref{Main Theorem}? To explain, it is helpful to first reformulate the result we wish to prove slightly. For each $n \in \ZZ$, let $\eval_{X \rightarrow n}: \ZZ[X] \rightarrow \ZZ$ be the evaluation homomorphism defined by $X \mapsto n$. Conjecture \ref{conj:rigidity} can be stated as
\begin{align*}
\eval_{X \rightarrow n}\left(U(1,X)\right) = U(1,n)
\end{align*}
for all $n \geq 4$. Similarly, Theorem \ref{Main Theorem} states that there exists an algorithm $\mathcal{A}_\text{Ulam}$ such that on an input of $k > \NN$, it computes the coefficients $a_i,b_i,c_i,d_i$ of $U(1,X)$ and an $N \in \NN$ such that for all $n \geq N$,
\begin{align*}
\eval_{X \rightarrow n}\left(U(1,X) \cap [1,c_k n + d_k + 1]\right) = U(1,n) \cap [1,c_k n + d_k + 1].
\end{align*}
We can now show how this follows from Algorithm \ref{Naive Algorithm}.
\begin{proof}[Proof of Theorem \ref{Main Theorem}]
Modify Algorithm \ref{Naive Algorithm} as follows: each time a comparison $p(X) < q(X)$, $p(X) \leq q(X)$, $p(X) > q(X)$, $p(X) \geq q(X)$, or $p(X) = q(X)$ is made, compute the smallest natural number $M$ such that for all $m \geq M$, replacing $X$ with $m$ does not change the truth value of the comparison. It is not hard to see that such an $M$ must exist by considering the behavior of these polynomials as $M \rightarrow \infty$. At the end of the computation, along with the coefficients $a_i,b_i,c_i,d_i$, return the maximum $N$ of all of the aforementioned $M$. Call this new algorithm $\mathcal{A}_\text{Ulam}$.
Now, take any $n \geq N$ and consider modifying $\mathcal{A}_\text{Ulam}$ by replacing every set $S \subset \ZZ[X]$ used with $\eval_{X \rightarrow n}(S)$. It is easy enough to see that this will be an algorithm that computes the coefficients of $U(1,n)$. But since $N$ is chosen such that all comparisons of elements yield the same result as before, the output of this algorithm is the same as that of $\mathcal{A}_\text{Ulam}$, which proves that
\begin{align*}
\eval_{X \rightarrow n}\left(U(1,X) \cap [1,c_k n + d_k + 1]\right) = U(1,n) \cap [1,c_k n + d_k + 1].
\end{align*}
Thus, $\mathcal{A}_\text{Ulam}$ has the desired properties.
\end{proof}
Unfortunately, the particular algorithm $\mathcal{A}_\text{Ulam}$ defined in the proof of this theorem is not an efficient method of computing the coefficients $a_i,b_i,c_i,d_i$ of $U(1,X)$---a naive implementation puts it in the $\Theta(k^3\log_2(k))$ complexity class, due to the two nested for-loops and the need to perform binary search for the set operations. However, the ideas of the construction of the algorithm $\mathcal{A}_\text{Ulam}$ can be generalized---there are in fact families of algorithms with its essential properties. The importance of this is that it might be possible to construct a more efficient algorithm using, for example, ideas of Gibbs and Judson \cite{Gibbs_2015,Gibbs_Judson_2015}. Before we show what this family of algorithms is, we need some definitions.
\begin{definition}
Let $S$ be a computable ordered ring. We say that a formula is $S$-\emph{expressible} if it is
\begin{enumerate}
\item a variable $x$,
\item a constant $c \in S \cup \{\top, \bot\}$,
\item an empty list $[]$,
\end{enumerate}
or if it can be constructed recursively from other $S$-expressible formulas according to the following rules:
\begin{enumerate}
\item If $\mathcal{E}_1, \mathcal{E}_2$ are $S$-expressible, then $\mathcal{E}_1 = \mathcal{E}_2$ is $S$-expressible.
\item If $\mathcal{E}_1,\mathcal{E}_2$ are $S$-expressible, then $\mathcal{E}_1 + \mathcal{E}_2, \mathcal{E}_1 - \mathcal{E}_2, \mathcal{E}_1 \cdot \mathcal{E}_2, \mathcal{E}_1 / \mathcal{E}_2$ are $S$-expressible if defined.
\item If $\mathcal{E}_1,\mathcal{E}_2$ are $S$-expressible, then $\mathcal{E}_1 < \mathcal{E}_2, \mathcal{E}_1 \leq \mathcal{E}_2, \mathcal{E}_1 > \mathcal{E}_2, \mathcal{E}_1 \geq \mathcal{E}_2$ are $S$-expressible if defined. (We call such formulas \emph{comparisons}.)
\item If $\mathcal{E}_1,\mathcal{E}_2$ are $S$-expressible, then $\neg \mathcal{E}_1, \mathcal{E}_1 \lor \mathcal{E}_2, \mathcal{E}_1 \land \mathcal{E}_2, \mathcal{E}_1 \Rightarrow \mathcal{E}_2$ are $S$-expressible if defined.
\item If $\mathcal{E}_1,\mathcal{E}_2,\ldots, \mathcal{E}_n$ are $S$-expressible, then $\left[\mathcal{E}_1,\mathcal{E}_2,\ldots, \mathcal{E}_n\right]$ is $S$-expressible.
\end{enumerate}
We say that an algorithm $\mathcal{A}$ \emph{has basic steps over} $S$ if it is composed of the following basic steps:
\begin{enumerate}
\item Initializing $x \leftarrow \mathcal{E}$, where $x$ is a variable and $\mathcal{E}$ is $S$-expressible.
\item Retrieving the $i$-th index of a list $l$.
\item Checking an if-statement $\textbf{if}(\mathcal{E})$, where $\mathcal{E}$ is $S$-expressible, and branching accordingly.
\item Running a while-loop $\textbf{while}(\mathcal{E})$, where $\mathcal{E}$ is $S$-expressible.
\item Returning an $S$-expressible formula $\mathcal{E}$.
\end{enumerate}
\end{definition}
For $\ZZ[X]$ and $\QQ[X]$, specifically, we also need a way to extend the evaluation homomorphism $\eval_{X \rightarrow n}$ to expressible formulas.
\begin{definition}
Let $\mathcal{E}$ be an $\QQ[X]$-expressible formula. We define $\eval_{X \rightarrow n}(\mathcal{E})$ to be the formula produced by replacing each instance of a constant $c$ in $\mathcal{E}$ with $\eval_{X \rightarrow n}(c)$.
\end{definition}
With these definitions, we can state the following result.
\begin{theorem}\label{Replacement Theorem}
Define $\mathcal{C}_\text{Ulam}$ to be the set of all algorithms $\mathcal{A}$ with basic steps over $\QQ[X]$ such that on an input of $k \in \NN$, $\mathcal{A}$ returns the first $k$ coefficients of $U(1,X)$ and a proof of correctness. There exists an algorithm $\mathcal{P}$ such that, on an input of an algorithm $\mathcal{A} \in \mathcal{C}_\text{Ulam}$, it returns an algorithm $\mathcal{P}(\mathcal{A})$ which on an input of $k \in \NN$ returns an $N \in \NN$ such that for all $n \geq N$,
\begin{align*}
\eval_{X \rightarrow n}\left(U(1,X) \cap [1,c_k n + d_k + 1]\right) = U(1,n) \cap [1,c_k n + d_k + 1].
\end{align*}
\end{theorem}
\begin{proof}
The algorithm runs as follows: on an input of $k \in \NN$, run $\mathcal{A}(k)$, but each time a comparison $\mathcal{E}$ comes up in the computation, compute the smallest integer $M$ such that for all $m \geq M$, $\mathcal{E} = \eval_{X \rightarrow m}(\mathcal{E})$. Then return the maximum $N$ of all of these $M$---there will only be finitely many comparisons for a given input $k$.
Why does $N$ have the claimed properties? For each $n \geq N$, define an algorithm $\mathcal{A}_n$ produced by replacing each $\QQ[X]$-expressible formula $\mathcal{E}$ in $\mathcal{A}$ with $\eval_{X \rightarrow n}(\mathcal{E})$. Since the truth value of comparisons is preserved and $\mathcal{A}$ has basic steps over $\QQ[X]$, $\mathcal{A}_n$ produces the same coefficients $a_i,b_i,c_i,d_i$ as $\mathcal{A}$, and verifies that if we define a subset
\begin{align*}
\mathcal{U}_n = \bigcup_{i = 0}^k\ \left[a_i n + b_i, c_i n + d_i\right],
\end{align*}
then
\begin{enumerate}
\item $a_0 n + b_0 = c_0 n + d_0 = 1$ and $a_1 n + b_1 = n$,
\item $a_{i + 1} n + b_{i + 1} > c_i n + d_i + 1$ for all $i \in \NN$, and
\item for every $x \in \mathcal{U}_n$, $x$ is the smallest element of $\ZZ$ with the property that there exists exactly one way such that $x$ can be written as the sum of two distinct elements $y,z \in \mathcal{U}_n$.
\end{enumerate}
In other words, $\mathcal{U}_n = U(1,n) \cap [1,c_k n + d_k + 1] = \eval_{X \rightarrow n}(U(1,X) \cap [1,c_k X + d_k + 1])$. Ergo, we have the desired result.
\end{proof}
\section{Acknowledgments}
The author is exceptionally grateful to Oleg Sheydvasser, for lending his expertise in implementing efficient versions of the algorithms discussed in this paper, and for lending his processor time to run them. The author would also like to thank Stefan Steinerberger for providing helpful discussion and feedback, and Camp Minnetonka for the atmosphere in which this paper was finished.
\begin{thebibliography}{10}
\bibitem{cassaigne_finch_1995}
J.~Cassaigne and S.~R. Finch, A class of 1-additive sequences and quadratic
recurrences, {\em Exp. Math.} {\bf 4} (1995), 49--60.
\bibitem{finch_1991}
S.~R. Finch, Conjectures about $s$-additive sequences, {\em Fibonacci Quart.}
{\bf 29} (1991), 209--214.
\bibitem{finch_1992_2}
S.~R. Finch, On the regularity of certain 1-additive sequences, {\em J. Combin.
Theory Ser. A} {\bf 60} (1992), 123--130.
\bibitem{finch_1992_1}
S.~R. Finch, Patterns in 1-additive sequences, {\em Exp. Math.} {\bf 1} (1992),
57--63.
\bibitem{Gibbs_2015}
P.~Gibbs, An efficient method for computing {Ulam} numbers.
\newblock Available at \url{http://vixra.org/abs/1711.0134}, 2015.
\bibitem{Gibbs_Judson_2015}
P.~Gibbs and J.~McCranie, The {Ulam} numbers up to one trillion.
\newblock Available at \url{http://vixra.org/abs/1508.0085}, 2017.
\bibitem{HKSS_2019_2}
J.~Hinman, B.~Kuca, A.~Schlesinger, and A.~Sheydvasser, Rigidity of {Ulam} sets
and sequences, {\em Involve} {\bf 12} (2019), 521--539.
\bibitem{HKSS_2019_1}
J.~Hinman, B.~Kuca, A.~Schlesinger, and A.~Sheydvasser, The unreasonable
rigidity of {Ulam} sequences, {\em J. Number Theory} {\bf 194} (2019),
409--425.
\bibitem{kravitz_steinerberger_2017}
N.~Kravitz and S.~Steinerberger, {Ulam} sequences and {Ulam} sets, {\em
Integers} {\bf 18} (2018), A80.
\bibitem{queneau_1972}
R.~Queneau, Sur les suites $s$-additives,
{\em J. Combin. Theory Ser. A} {\bf 12} (1972), 31--71.
\bibitem{schmerl_spiegel_1994}
J.~Schmerl and E.~Spiegel, The regularity of some 1-additive sequences, {\em J.
Combin. Theory Ser. A} {\bf 66} (1994), 172--175.
\bibitem{steinerberger_2016}
S.~Steinerberger, A hidden signal in the {Ulam} sequence, {\em Exp. Math.} {\bf
26} (2017), 460--467.
\bibitem{ulam_1964}
S.~Ulam, Combinatorial analysis in infinite sets and some physical theories,
{\em SIAM Rev.} {\bf 6} (1964), 343--355.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11Y55; Secondary 11B83, 11U10.
\noindent \emph{Keywords:} additive number theory, Ulam sequence, computational number theory.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A002858}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received July 11 2021;
revised version received November 30 2021.
Published in {\it Journal of Integer Sequences},
December 27 2021.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}