# Subset sums, completeness and colorings

David Conlon Department of Mathematics, California Institute of Technology,
Pasadena, CA 91125. Email<EMAIL_ADDRESS>Research supported by NSF
Award DMS-2054452. Jacob Fox Department of Mathematics, Stanford University,
Stanford, CA 94305. Email<EMAIL_ADDRESS>Research supported by a
Packard Fellowship and by NSF Award DMS-1855635. Huy Tuan Pham Department of
Mathematics, Stanford University, Stanford, CA 94305. Email:
<EMAIL_ADDRESS>
###### Abstract

We develop novel techniques which allow us to prove a diverse range of results
relating to subset sums and complete sequences of positive integers, including
solutions to several longstanding open problems. These include: solutions to
the three problems of Burr and Erdős on Ramsey complete sequences, for which
Erdős later offered a combined total of $350; analogous results for the new
notion of density complete sequences; the solution to a conjecture of Alon and
Erdős on the minimum number of colors needed to color the positive integers
less than $n$ so that $n$ cannot be written as a monochromatic sum; the exact
determination of an extremal function introduced by Erdős and Graham on sets
of integers avoiding a given subset sum; and, answering a question reiterated
by several authors, a homogeneous strengthening of a seminal result of
Szemerédi and Vu on long arithmetic progressions in subset sums.

##  1 Introduction

Many of the most famous problems and results in mathematics concern the
representation of positive integers as the sum of elements from a sparse
sequence. For example, the long open Goldbach conjecture states that every
even integer at least four is the sum of two primes, while Vinogradov’s
theorem states that every sufficiently large odd integer is the sum of three
primes (and was recently extended by Helfgott [28] to cover all odd integers
at least seven). Some other notable results of this type include Lagrange’s
four-square theorem that every positive integer is the sum of four squares,
Gauss’ Eureka theorem that every positive integer is the sum of three
triangular numbers and the Hilbert–Waring theorem.

While these problems concern the representation of integers as the sum of a
bounded number of terms from a particular sequence, there are many results and
open problems which do not stipulate a bound on the number of terms. A
prominent example of such a result is a theorem of Szemerédi and Vu [40],
confirming an old conjecture of Erdős [14], which says that there is a
constant $C$ such that if $A=(a_{n})_{n=1}^{\infty}$ is an infinite increasing
sequence of integers with $|A\cap[n]|\geq C\sqrt{n}$ for all sufficiently
large $n$ which intersects every infinite arithmetic progression of integers,
then we can represent any sufficiently large integer as a sum of distinct
terms from the sequence. In this paper, we develop general methods which solve
many open problems of precisely this type.

To be more precise, given a set or a sequence $A$ of integers, we define the
set of subset sums $\Sigma(A)$ to be the set of all integers representable as
a sum of distinct elements from $A$. That is,

$\Sigma(A)=\left\\{\sum_{s\in S}s:S\subseteq A\right\\}.$

Our contribution then is to solve several open problems on conditions which
guarantee that $\Sigma(A)$ contains either a particular integer or all
sufficiently large integers. In particular, we answer several old questions of
Burr and Erdős [9] on the density of so-called Ramsey complete sequences, for
whose solution Erdős [19] later offered $350. We also solve a conjecture of
Alon and Erdős [2] on the minimum number of colors needed to color the
positive integers less than $n$ so that $n$ cannot be written as a
monochromatic sum and determine exactly the answer to an extremal question
first studied by Alon, Erdős and Graham [1, 18] on the maximum size of a set
avoiding a particular subset sum. Finally, answering a question reiterated by
several groups of authors, including Erdős and Sárközy [22], Sárközy [36] and
Tran, Vu, and Wood [42], we prove a homogeneous strengthening of another
result of Szemerédi and Vu [40] from which the Erdős conjecture mentioned
above was derived.

What unites these seemingly disparate topics is a common proof framework that
allows us to show the existence of a long interval in the set of subset sums
of an integer set $S$. This framework has several steps:

  1. 1.

We partition $S$ into $\ell$ parts $S_{1},\ldots,S_{\ell}$ of roughly equal
size for an appropriate choice of $\ell$.

  2. 2.

We further partition each part $S_{i}$ into two parts $S_{i}^{\prime}$ and
$S_{i}^{\prime\prime}$ of appropriate size and show that, for any $s\in
S_{i}^{\prime\prime}$, the set of subset sums of $S_{i}^{\prime}$ modulo $s$
is large.

  3. 3.

Using step (ii), we show that $\Sigma(S_{i})=\Sigma(S_{i}^{\prime}\cup
S_{i}^{\prime\prime})$ is dense in some long interval.

  4. 4.

Using step (iii), we show that $\Sigma(S)=\Sigma(S_{1}\cup\dots\cup S_{\ell})$
contains a long interval.

Step (ii) is the heart of the method and must be appropriately tailored to
each application, drawing variously on the probabilistic method, on structural
results from additive number theory and on estimates from analytic number
theory. We will say more about our methods in Section 2. For now, we will
focus on describing our main results, along with several extensions,
variations and applications, in more detail.

###  1.1 Ramsey completeness and density completeness

We say that a sequence of positive integers $A$ is _complete_ if every
sufficiently large positive integer is in $\Sigma(A)$ and _entirely complete_
if every positive integer is in $\Sigma(A)$. For example, the powers of two
are entirely complete, while the powers of three are incomplete. A far less
simple example, due to Birch [6], is that the sequence $\\{p^{i}q^{j}:i,j\geq
0\\}$ is complete whenever $p,q\geq 2$ are coprime integers. For more on the
rich history of complete sequences (and some open problems), we refer the
interested reader to [10, 21].

Our starting point here is with the observation that the completeness property
can be surprisingly fragile. Indeed, removing any element from the powers of
two turns an entirely complete sequence into an incomplete one. For this
reason, Burr and Erdős [8, 9] began the study of more robust notions of
completeness. We will be concerned with two such notions here, namely,
robustness under partitioning, known as Ramsey completeness in the literature,
and robustness under taking subsets, a new concept which we refer to as
density completeness.

####  1.1.1 Ramsey completeness

Following Burr and Erdős [9], we say that a sequence of positive integers $A$
is _$r$ -Ramsey complete_ if, whenever the sequence is partitioned into $r$
classes $A_{1},A_{2},\dots,A_{r}$, every sufficiently large positive integer
is in $\bigcup_{i=1}^{r}\Sigma(A_{i})$ and _entirely $r$-Ramsey complete_ if
every positive integer is in $\bigcup_{i=1}^{r}\Sigma(A_{i})$. Equivalently,
$A$ is entirely $r$-Ramsey complete if, for any coloring of $A$ using $r$
colors, every positive integer can be written as a monochromatic subset sum.

In their paper introducing these concepts, Burr and Erdős [9] constructed an
entirely $2$-Ramsey complete sequence $A$ with the property that
$|A\cap[n]|\leq C\log^{3}n$ for all $n$, where $C$ is an absolute constant. In
the other direction, they were able to show that there is a constant $c>0$ for
which there is no $2$-Ramsey complete sequence with $|A\cap[n]|\leq
c\log^{2}n$ for all sufficiently large $n$. They also asked whether it might
be possible to narrow the gap between these two estimates and Erdős [19] later
offered $100 for such an improvement.

For $r\geq 3$, the results of Burr and Erdős clearly imply that there is no
$r$-Ramsey complete sequence with $|A\cap[n]|\leq c\log^{2}n$ for all
sufficiently large $n$. However, even for $r=3$, they were unable to construct
an $r$-Ramsey complete sequence with $|A\cap[n]|=n^{o(1)}$. Given the lack of
progress on this problem, Erdős [19] later offered $250 for any non-trivial
result. Our first theorem solves both this problem and that above at once, by
determining the growth rate of the sparsest possible $r$-Ramsey complete
sequence up to an absolute constant factor.

######  Theorem 1.1.

There is a constant $C$ such that, for every integer $r\geq 2$, there is an
$r$-Ramsey complete sequence $A$ with $|A\cap[n]|\leq Cr\log^{2}n$ for all
$n$. Furthermore, there is a constant $c>0$ such that no sequence $A$ with
$|A\cap[n]|\leq cr\log^{2}n$ for all sufficiently large $n$ is $r$-Ramsey
complete.

Note that the lower bound, that is, the statement that there is a constant
$c>0$ such that no sequence $A$ with $|A\cap[n]|\leq cr\log^{2}n$ for all
sufficiently large $n$ is $r$-Ramsey complete, already improves on Burr and
Erdős’ result, which had no dependency on $r$. We note also that a standard
compactness argument implies that if $A$ is an $r$-Ramsey complete sequence,
then there is $n(A)$ such that, for every $r$-coloring of $A$, every positive
integer at least $n(A)$ can be written as a sum of distinct monochromatic
elements. We may therefore enlarge the $r$-Ramsey complete sequence $A$
constructed in Theorem 1.1 to an entirely $r$-Ramsey complete sequence by
including all positive integers less than $n(A)$.

The key to proving Theorem 1.1 is a density-type result, Lemma 2.8, saying
that, with high probability, a random sequence of $C\epsilon^{-1}\log x$
elements chosen from those elements of the interval $[x,2x)$ with no small
prime factor has the property that any subset of size $C\log x$ contains a
particular long interval in its set of subset sums. This density statement
already improves a result of Spencer [37] from 1981 by showing that, for any
integers $r\geq 2$ and $n$ sufficiently large in terms of $r$, there is a set
of integers $S$ of size $Cr\log n$ with the property that any $r$-coloring of
$S$ contains a monochromatic subset whose elements add to $n$. More to the
point, by concatenating the sequences given by Lemma 2.8, one for each dyadic
interval $[x,2x)$, it is easy to construct the sparse $r$-Ramsey complete
sequence $A$ required by Theorem 1.1.

We also study Ramsey completeness for polynomial sequences. The study of
ordinary completeness for polynomial sequences has a long history, with
important contributions by Sprague [38], Roth and Szekeres [34] and Cassels
[11]. These efforts culminated in a result of Graham [26], who characterized
all real polynomial sequences which are complete (where the definition of
completeness extends to real-valued sequences without alteration). Graham
first observed the well-known fact that every real polynomial of degree $k$
can be written as $P(x)=\sum_{i=0}^{k}\alpha_{i}\binom{x}{i}$, where
$\binom{x}{i}$ is the polynomial $\frac{1}{i!}\prod_{j=0}^{i-1}(x-j)$ and
$\alpha_{i}\in\mathbb{R}$ with $\alpha_{k}\not=0$. He then showed that
$(P(m))_{m\geq 1}$ is complete if and only if the following three properties
hold:

  1. 1.

$\alpha_{k}>0$,

  2. 2.

$\alpha_{i}=p_{i}/q_{i}$ for each $i$, where $p_{i}$ and $q_{i}$ are
relatively prime integers, and

  3. 3.

$\gcd(p_{0},p_{1},\ldots,p_{k})=1$.

Given this body of work, it was a natural step for Burr and Erdős [9] to ask
which polynomial sequences are Ramsey complete. According to Erdős [19], Burr
subsequently proved that the sequence of $k^{\textrm{th}}$ powers is
$r$-Ramsey complete for all $r\geq 2$, though this result was never published.
Our next theorem subsumes this result, answering their question completely by
showing that all complete polynomial sequences are $r$-Ramsey complete for all
$r\geq 2$. In fact, it gives much more, extending the upper bound in Theorem
1.1, which corresponds to the case $P(x)=x$, by showing that every complete
polynomial sequence has a subsequence which is $r$-Ramsey complete and as
sparse as possible. Note again that in this context we are allowing the
sequence to be real-valued, rather than restricting to the integers. The
definitions of completeness and Ramsey completeness should then be adjusted to
facilitate this change.

######  Theorem 1.2.

For any positive integer $k$, there is a constant $C(k)$ such that, for every
polynomial $P$ of degree $k$ for which $(P(m))_{m\geq 1}$ is complete and
every $r\geq 2$, there is an $r$-Ramsey complete subsequence
$A\subset(P(m))_{m\geq 1}$ with $|A\cap[n]|\leq C(k)r\log^{2}n$ for all $n$.

####  1.1.2 Density completeness

We say that a sequence of positive integers $A$ is $\epsilon$-complete if
every subsequence $A^{\prime}$ of $A$ with the property that
$|A^{\prime}\cap[n]|\geq\epsilon|A\cap[n]|$ for all sufficiently large $n$ is
complete. This is the natural density analogue of Ramsey completeness, though
it is not at all obvious that such sequences actually exist. Indeed, since the
even integers are not complete, the set of all positive integers is not
$(\frac{1}{2}-\delta)$-complete for any $\delta>0$, an observation which might
suggest that no $\epsilon$-complete sequences exist when $\epsilon$ is small.
However, by using the result of Szemerédi and Vu [40], which we will discuss
in more detail in Section 1.3, that there is a constant $C$ such that any
subset of $[n]$ of size at least $C\sqrt{n}$ contains an arithmetic
progression of length $n$ in its set of subset sums, one can show that any
sequence of primes $A$ with $|A\cap[n]|\geq 2C\epsilon^{-1}\sqrt{n}$ for all
sufficiently large $n$ is $\epsilon$-complete. Thus, the correct takeaway is
that the property of being $\epsilon$-complete is not monotone. More
concretely, as in the example above where we looked at all positive integers,
an $\epsilon$-complete sequence cannot have an $\epsilon$-proportion of its
elements sharing a common divisor.

In keeping with our results about Ramsey completeness, our main result
regarding this new notion of $\epsilon$-completeness is a determination of how
sparse an $\epsilon$-complete sequence can be. To state this result, we need
some notation. Let $F=(f_{n})_{n\geq 1}$ be any sequence of positive integers
for which $f_{n}=\sum_{i\leq\epsilon n}f_{i}$ for all sufficiently large $n$.
It is easy to see that any two such sequences are comparable, growing within a
constant factor of each other which depends only on the initial terms. In
Appendix A.1, we will show that any such $F$ satisfies

$f_{n}=e^{\left(\frac{1}{2\log(1/\epsilon)}+o(1)\right)(\log n)^{2}}$

or, equivalently,

$|F\cap[n]|=e^{\sqrt{\left(2\log(1/\epsilon)+o(1)\right)\log n}}.$

The promised result now says that the fastest-growing $\epsilon$-complete
sequence grows on the same order as $F$.

######  Theorem 1.3.

Let $F=(f_{n})_{n\geq 1}$ be any sequence of positive integers for which
$f_{n}=\sum_{i\leq\epsilon n}f_{i}$ for all sufficiently large $n$. Then every
$\epsilon$-complete sequence $A=(a_{n})_{n\geq 1}$ must satisfy
$a_{n}=O(f_{n})$ and there is an $\epsilon$-complete sequence with
$a_{n}=\Theta(f_{n})$.

Like with Ramsey completeness, we may also prove a generalization regarding
$\epsilon$-complete subsequences of complete polynomial sequences, though in
this case we omit the details of the argument, only pointing to how ideas from
the proofs of Theorems 1.2 and 1.3 can be combined to give the required
conclusion.

######  Theorem 1.4.

Let $P$ be a polynomial for which the sequence $(P(m))_{m\geq 1}$ is complete.
Then there is a subsequence $A=(a_{n})_{n\geq 1}$ of $(P(m))_{m\geq 1}$ with
$a_{n}=\Theta(f_{n})$ which is $\epsilon$-complete. That is, any complete
polynomial sequence has an $\epsilon$-complete subsequence which is as sparse
as an $\epsilon$-complete sequence can be.

###  1.2 Ensuring a given subset sum

So far, we have discussed problems and results on notions of completeness,
where we require that all sufficiently large integers can be represented as
subset sums. We now address the natural problem of ensuring that a particular
integer is a subset sum, again looking at both a Ramsey variant and a density
variant.

####  1.2.1 Monochromatic subset sums

Given a positive integer $n$, let $f(n)$ be the minimum integer $r$ for which
there is an $r$-coloring of the positive integers less than $n$ with the
property that $n$ cannot be written as a monochromatic sum of distinct
integers. The problem of estimating $f(n)$ was raised by Erdős many times [15,
16, 17], culminating in a problem paper [20] where he stated that he could
show $f(n)=o(n^{1/3})$ and asked whether $f(n)=n^{1/3-o(1)}$. Solving this
problem, Alon and Erdős [2] showed that there are positive constants $c_{1}$
and $c_{2}$ such that

$\frac{c_{1}n^{1/3}}{\log^{4/3}n}\leq f(n)\leq\frac{c_{2}n^{1/3}(\log\log
n)^{1/3}}{(\log n)^{1/3}},$ (1)

adding that they suspect the upper bound is closer to the truth. Using his
result with Szemerédi [40] on long arithmetic progressions in subset sums, Vu
[43] later refined the lower bound, showing that
$f(n)\geq\frac{c_{1}n^{1/3}}{\log n}$ for some positive $c_{1}$.

We improve these results further, determining $f(n)$ up to an absolute
constant factor and thereby confirming Alon and Erdős’ conjecture that their
upper bound is close to the true order of magnitude. As is customary, we write
$\phi(n)$ for the Euler totient function, the number of positive integers less
than $n$ which are coprime to $n$.

######  Theorem 1.5.

For every positive integer $n$, the minimum number of colors $f(n)$ for which
it is possible to color the positive integers less than $n$ so that $n$ cannot
be written as a monochromatic sum of distinct integers satisfies

$f(n)=\Theta\left(\frac{n^{1/3}(n/\phi(n))}{(\log n)^{1/3}(\log\log
n)^{2/3}}\right).$

Standard estimates imply that $n/\phi(n)\in(1,2\log\log n)$ for $n$
sufficiently large, with $n/\phi(n)$ large if and only if $n$ is divisible by
many small primes. As a result, $f(n)$ is surprisingly far from being
monotone, exhibiting local multiplicative fluctuations on the order of
$\log\log n$. Moreover, though $f(n)$ is indeed close to the upper bound
proved by Alon and Erdős, differing by at most a $\log\log n$ factor, their
upper bound is only optimal up to a constant factor when $n$ is divisible by
many small primes.

To give some sense of where our improvement comes from, let us briefly
describe the coloring that Alon and Erdős use for their upper bound, using $r$
colors in total. First, they use $r/2$ colors to color all integers in $[n-1]$
larger than $2n/r$, with all integers in $[n/(j+1),n/j)$ getting color $j$.
Since any $j$ distinct integers of color $j$ have sum less than $n$ and any
$j+1$ distinct integers of color $j$ have sum larger than $n$, we see that $n$
is not a sum of distinct elements from any of these color classes. Second, for
each of the first $r/4$ primes $p$ that are coprime to $n$, they place all
remaining multiples of $p$ in a color class. Since each sum of multiples of
$p$ is itself a multiple of $p$ and each $p$ is coprime to $n$, we see that
$n$ is again not a sum of elements from any of these color classes. To
complete the construction, we group the few remaining uncolored integers into
color classes so that the sum of the elements in any given color class is less
than $n$. A careful analysis then shows that $r$ can be taken to be the upper
bound in (1).

As in the Alon–Erdős coloring, our coloring uses $r/2$ colors to color all
integers in $[n-1]$ larger than $2n/r$ and then $r/4$ colors to color the
multiples of each of the first $r/4$ primes which are coprime to $n$. However,
we then add an additional third step, which makes use of the non-uniform
distribution of the remaining elements in congruence classes modulo $d$ for an
appropriate choice of $d$. Indeed, let $d$ be as large as possible so that $d$
is coprime to $n$ and $\phi(d)<r/32$, noting that the prime factors of $d$
must be among the first $r/4$ primes coprime to $n$ and so the remaining
uncolored integers are all coprime to $d$. For each congruence class
$t\pmod{d}$ with $t$ coprime to $d$, let $x_{t}\in[d]$ be such that
$x_{t}\equiv t^{-1}n\pmod{d}$. If a sum of elements, each congruent to
$t\pmod{d}$, is equal to $n$, then the sum must involve either $x_{t}$ terms,
$d+x_{t}$ terms or more than $d+x_{t}$ terms. Therefore, arguing as for the
first $r/2$ colors, neither the set of integers congruent to $t\pmod{d}$ which
are at least $n/x_{t}$ nor the set of integers congruent to $t\pmod{d}$ which
are at least $n/(d+x_{t})$ and less than $n/x_{t}$ can contain a subset sum
equal to $n$. Hence, using at most $2\phi(d)<r/8$ additional colors, we may
color all integers in $[n-1]$ larger than $n/d$ in such a way that $n$ is not
a monochromatic sum of distinct elements. To complete the coloring, we again
group the remaining uncolored integers into color classes so that the sum of
the elements in any given color class is less than $n$. Worked out carefully,
this then returns the upper bound in Theorem 1.5. For a sketch of how we prove
the matching lower bound, which is the more difficult aspect of the proof, we
refer the reader to Section 2.3.

In practice, since our methods allow it, we will prove a more general result.
For the statement, we need some notation. For positive integers $\rho$ and
$m$, writing $p_{i}$ for the $i^{\textrm{th}}$ prime, we let
$W(\rho)=\prod_{i=1}^{\rho}p_{i}$ and
$\tau(\rho,m)=\phi(W(\rho)m)/(W(\rho)m)$. For $m\in[n,\binom{n}{2}]$, we then
let $\rho(n,m)$ be the smallest positive integer $\rho$ such that
$\rho/\tau(\rho,m)\geq n^{2}/\phi(m)$. Our generalization of Theorem 1.5 is
now as follows.

######  Theorem 1.6.

For every positive integer $n$ and any $m\in[n,\binom{n}{2}]$, the minimum
number of colors $f(n,m)$ for which it is possible to color the positive
integers less than $n$ so that $m$ cannot be written as a monochromatic sum of
distinct integers satisfies

$f(n,m)=\Theta\left(\min\left(\frac{m^{1/3}(m/\phi(m))}{(\log
n)^{1/3}(\log\log n)^{2/3}},\rho(n,m)\right)\right).$

####  1.2.2 The largest set avoiding a given subset sum

What is the maximum size $g(n,m)$ of a subset of $[n]$ which has no subset sum
equal to $m$? Variants of this natural extremal problem, interesting for any
positive integers $n<m\leq\binom{n+1}{2}$, were originally raised by Erdős and
Graham (see, for instance, [21, Page 59] and [18]), although, in the exact
form mentioned here, the problem was first studied in detail by Alon [1].

If we let $\textrm{snd}(m)$ be the smallest positive integer that does not
divide $m$, an easy lower bound for $g(n,m)$ is
$\lfloor\frac{n}{\textrm{snd}(m)}\rfloor$, since the set of all multiples of
$\textrm{snd}(m)$ below $n$ does not have $n$ as a subset sum. This simple
observation of Alon [1] was later refined by Alon and Freiman [3], who
observed that $g(n,m)\geq
s(n,m):=\lfloor\frac{n}{\textrm{snd}(m)}\rfloor+\textrm{snd}(m)-2$ by
augmenting the example above with $\textrm{snd}(m)-2$ additional elements,
each congruent to either $1$ or $-1$ modulo $\textrm{snd}(m)$. Another simple
lower bound, better than that above when $m$ is close to $\binom{n+1}{2}$, is
$g(n,m)\geq\lfloor\sqrt{2m}-1/2\rfloor$, following from the fact that the sum
of the first $\lfloor\sqrt{2m}-1/2\rfloor$ positive integers is less than $m$.

For the upper bound, Alon [1] first showed that if $n^{1+\epsilon}\leq m\leq
n^{2}/(\log n)^{2}$, then $g(n,m)=O(s(n,m))$, where the implicit constant
depends on $\epsilon$. He also conjectured that $g(n,m)=(1+o(1))s(n,m)$ in
roughly the same range. For $Cn(\log n)^{6}\leq m\leq n^{1.5-o(1)}$, this
conjecture was proved soon after by Lipkin [31]. Remarkably, around the same
time, Alon and Freiman [3] determined the function exactly for
$n^{5/3+o(1)}\leq m<\frac{n^{2}}{20(\log n)^{2}}$, establishing that
$g(n,m)=s(n,m)$ in this range. More than twenty years then elapsed before
Tran, Vu and Wood [42] proved Alon’s conjecture in full generality by showing
that $g(n,m)=(1+o(1))s(n,m)$ for $n(\log n)^{1+o(1)}\leq
m\leq\frac{n^{2}}{9(\log n)^{2}}$. We improve these results, determining the
function exactly for all $Cn\log n\leq m\leq\frac{n^{2}}{(8+o(1))(\log
n)^{2}}$ and asymptotically for all $Cn\log n\leq m\leq\binom{n+1}{2}$.

######  Theorem 1.7.

There is a constant $C$ such that if $n$ and $m$ are positive integers and
$g(n,m)$ is the maximum size of a subset of $[n]$ with no subset sum equal to
$m$, then

$g(n,m)=s(n,m)=\left\lfloor\frac{n}{\textrm{snd}(m)}\right\rfloor+\textrm{snd}(m)-2$

for $m\in\left[Cn\log n,\frac{n^{2}}{12(\log n)^{2}}\right]$ and

$g(n,m)=\max\left(s(n,m),(1+o(1))\sqrt{2m}\right)$

for $m\in\left[\frac{n^{2}}{12(\log n)^{2}},\binom{n+1}{2}\right]$.

Since $\textrm{snd}(m)\leq(1+o(1))\log m\leq(2+o(1))\log n$, the theorem in
fact implies that $g(n,m)=\max\left(s(n,m),(1+o(1))\sqrt{2m}\right)=s(n,m)$
for $Cn\log n\leq m\leq\frac{n^{2}}{(8+o(1))(\log n)^{2}}$, as promised above.
On the other hand, once $m<cn\log n$ for $c$ sufficiently small, we do not
generally have the bound $g(n,m)=(1+o(1))s(n,m)$. Indeed, for $8n<m<n(\log
n)/8$, we can show that there is a subset of $[n]$ of size $h=\lfloor
n^{2}/(2m)\rfloor$ with no subset sum equal to $m$, so if
$\textrm{snd}(m)\geq(\log n)/2$, then $g(n,m)\geq h>(2-o(1))s(n,m)$. To show
the existence of the required subset of size $h$, choose an integer
$n^{\prime}\in(h+3n/4,n]$ such that
$m\in[n^{\prime}n/(2h),n^{\prime}n/(2h)+n/4]$. Note that
$n^{\prime}\in(h+3n/4,n]$ as $n^{\prime}\leq 2mh/n\leq n$ and, since
$n^{2}/(2m)\geq h\geq n^{2}/(2m)-1$, we can verify that, for $m\in(8n,n(\log
n)/8)$ and $n$ sufficiently large, $n^{\prime}\geq\frac{2h(m-n/4)}{n}>h+3n/4$.
Observe now that the set of subset sums of the interval
$[n^{\prime}-h,n^{\prime}]$ does not contain any element from the interval
$[n^{\prime}n/(2h),n^{\prime}n/(2h)+n/4]$, since any sum of at most $n/(2h)$
elements from the interval is strictly smaller than $n^{\prime}n/(2h)$, while
any sum of at least $n/(2h)+1$ elements from the interval is strictly larger
than
$(n^{\prime}-h)(n/(2h)+1)=n^{\prime}n/(2h)+n^{\prime}-h-n/2>n^{\prime}n/(2h)+n/4$.
Therefore, the interval $[n^{\prime}-h,n^{\prime}]$ has size at least $h$ and
does not contain $m$ as a subset sum, as required.

To say more about how we prove Theorem 1.7, we must first discuss the main
tool used in our proof, a strengthening of the subset sums result of Szemerédi
and Vu [40] which is itself of independent interest.

###  1.3 Long homogeneous progressions in subset sums

We opened this paper by mentioning Szemerédi and Vu’s proof [40] of a
longstanding conjecture of Erdős [14]. As shown by Folkman [24], this is
itself a corollary of the statement that there is a constant $C$ such that if
$A=(a_{n})_{n=1}^{\infty}$ is an infinite increasing sequence of integers with
$|A\cap[n]|\geq C\sqrt{n}$ for all sufficiently large $n$, then $\Sigma(A)$
contains an infinite arithmetic progression. In proving this latter statement,
Szemerédi and Vu first proved the following finite analogue, which we have
already mentioned several times. Note that this result is clearly best
possible, as may be seen by considering the set of all positive integers up to
$\lfloor\sqrt{2n}-1/2\rfloor$.

######  Theorem 1.8 (Szemerédi–Vu [40]).

There is a constant $C$ such that if $A\subset[n]$ with $|A|\geq C\sqrt{n}$,
then $\Sigma(A)$ contains an arithmetic progression of length $n$.

This theorem improved on an earlier result obtained independently by Freiman
[25] and Sárközy [35], who showed that there is a constant $C$ such that if
$|A|\geq C\sqrt{n\log n}$, then $\Sigma(A)$ contains an arithmetic progression
of length at least $n$. However, it also loses something, because the
Freiman–Sárközy result gives not only an arithmetic progression, but a
homogeneous progression, an arithmetic progression $a,a+d,\dots,a+kd$ where
the common difference $d$ divides $a$ and, hence, every other term in the
progression. The natural question then, reiterated by several groups of
authors, including Erdős and Sárközy [22], Sárközy [36] and Tran, Vu, and Wood
[42], is whether there is a common strengthening of the Szemerédi–Vu and
Freiman–Sárközy theorems. We answer this question in the affirmative.

######  Theorem 1.9.

There is a constant $C$ such that if $A\subset[n]$ with $|A|\geq C\sqrt{n}$,
then $\Sigma(A)$ contains a homogeneous progression of length $n$.

For the proof of Theorem 1.7, we need a slightly stronger version of Theorem
1.9. This result, Theorem 6.1, states that if $A\subset[n]$ with $|A|\geq
C\sqrt{n}$, then there exists $d$ (which is typically just $1$) such that most
elements in $A$ are divisible by $d$ and the set of subset sums formed from
adding at most $2^{50}n/|A|$ elements of $A$ which are divisible by $d$
contains a homogeneous progression with length $n$ and common difference $d$.

To prove Theorem 1.7, suppose now that $A$ is a subset of $[n]$ with
$s(n,m)+1$ elements and we wish to show that $m\in\Sigma(A)$. Using Theorem
6.1, we may conclude that $\Sigma(A)$ contains a homogeneous progression with
length $n$ and common difference $d$, where $d$ divides most elements of $A$.
Moreover, if $d|m$, this progression will contain $m$, so we may assume that
$d\geq\textrm{snd}(m)$. A simple counting argument then implies that $d$ must
in fact equal $\textrm{snd}(m)$, as otherwise there will not be enough
elements in $A$. Since
$s(n,m)+1=\lfloor\frac{n}{\textrm{snd}(m)}\rfloor+\textrm{snd}(m)-1$, there
must also be at least $\textrm{snd}(m)-1$ elements in $A$ which are not
divisible by $\textrm{snd}(m)$. We complete the proof by using these
additional elements to show that $m\in\Sigma(A)$, as required.

As another corollary of Theorem 1.9, we also obtain an improved bound on an
old question of Straus [39] (see also [23]) regarding the maximum size of a
non-averaging subset of $[n]$, where a subset $A$ of $[n]$ is said to be non-
averaging if no $a\in A$ is the average of two or more other elements of $A$.
If we write $h(n)$ for the maximum size of a non-averaging subset of $[n]$, an
elegant construction of Bosznay [7] shows that $h(n)=\Omega(n^{1/4})$. On the
other hand, if we write $H(n)$ for the maximum integer for which there are two
subsets of $[n]$ of size $H(n)$ whose sets of subset sums have no non-zero
common element, then a result of Straus [39] says that $h(n)\leq 2H(n)+2$.
Using the Freiman–Sárközy result on homogeneous progressions, Erdős and
Sárközy [22] were able to show that $H(n)=O(\sqrt{n\log n})$, which, by
Straus’ observation, also yields a similar upper bound on $h(n)$. By following
their method, but using Theorem 1.9 instead of the Freiman–Sárközy result, we
improve their bound to $H(n)=O(\sqrt{n})$, which is tight up to the constant
factor, as may be seen by considering the sets $[1,c\sqrt{n}]$ and
$[n-c\sqrt{n},n]$ for any $c<\sqrt{2}$. By Straus’ inequality, it also
provides an improved upper bound $h(n)=O(\sqrt{n})$ for the size of the
largest non-averaging subset of $[n]$.

######  Corollary 1.10.

There is a constant $C$ such that $H(n)\leq C\sqrt{n}$, where $H(n)$ is the
largest integer for which there are two subsets of $[n]$ of size $H(n)$ whose
sets of subset sums have no non-zero common element, and $h(n)\leq C\sqrt{n}$,
where $h(n)$ is the size of the largest non-averaging subset of $[n]$.

### Organization of the paper

In the next section, we will elaborate on our methods by giving rough outlines
of the proofs of some of our main results. We then proceed to the formal
proofs, proving Theorems 1.1 and 1.2 on Ramsey completeness in Section 3,
Theorem 1.3 on density completeness in Section 4 and Theorem 1.6 on
monochromatic subset sums in Section 5. We turn to the proof of Theorem 1.9,
our homogeneous strengthening of the Szemerédi–Vu theorem, and its consequence
Corollary 1.10 in Section 6 and conclude in Section 7 by proving Theorem 1.7
on the largest set avoiding a particular subset sum. Several supplementary
results are consigned to the appendices.

### Notation

For the sake of clarity of presentation, we omit floor and ceiling signs
whenever they are not essential. We also maintain the convention that all
logarithms are natural logarithms unless otherwise specified.

##  2 Overview of the proofs of the main results

The techniques used to prove Theorems 1.1, 1.2, 1.6 and 1.9 all share some
similarities. In each case, we reduce a problem over $\mathbb{Z}$ to the
corresponding problem over $\mathbb{Z}_{m}$. In the cyclic setting,
considering the structure of the “almost periods”, i.e., those elements whose
inclusion does not significantly expand the subset sum, allows us to transform
our questions about subset sums into problems about iterated sumsets. The
literature on iterated sumsets is extensive, allowing us to reach our desired
conclusions by combining existing results on these sumsets with novel
arguments from probabilistic combinatorics. In this section, we say more about
the specific ideas that go into the proofs of each of our main theorems. The
detailed proofs of these theorems and the other results described in the
introduction are then in subsequent sections.

###  2.1 Some useful tools

We will repeatedly use the following simple lemma, allowing us to extend
intervals in the set of subset sums by adding new elements. It is essentially
Lemma 1 of Graham [26].

######  Lemma 2.1 (Graham [26]).

Let $A$ be a set such that $\Sigma(A)$ contains all integers in the interval
$[x,x+y)$.

  1. 1.

If $a$ is a positive integer with $a\leq y$ and $a\notin A$, then
$\Sigma(A\cup\\{a\\})$ contains all integers in the interval $[x,x+y+a)$.

  2. 2.

If $a_{1},\ldots,a_{s}$ are positive integers such that $a_{i}\leq
y+\sum_{j<i}a_{j}$ and $a_{i}\notin A$ for $i=1,\ldots,s$, then
$\Sigma(A\cup\\{a_{1},a_{2},\dots,a_{s}\\})$ contains all integers in the
interval $[x,x+y+\sum_{i=1}^{s}a_{i})$.

###### Proof.

For the proof of the first part, note that if $u\in[x,x+y)$, then
$u\in\Sigma(A)\subset\Sigma(A\cup\\{a\\})$. If $u\in[x+y,x+y+a)$, then
$u-a\in[x,x+y)\subset\Sigma(A)$, so $u=(u-a)+a\in\Sigma(A\cup\\{a\\})$. The
second part follows from the first part by induction on $s$. ∎

We will also make repeated use of the following result of Lev [30]. The
importance of this result is that it allows us to find long intervals in a set
of subset sums by first finding several dense subsets of long intervals and
then summing these sets. Several weaker versions of this result appeared
earlier in the literature, many of which would also suffice for our purposes.

######  Lemma 2.2 (Lev [30]).

Suppose $\ell,q\geq 1$ and $n\geq 3$ are integers with $\ell\geq
2\lceil(q-1)/(n-2)\rceil$. If $S_{1},\dots,S_{\ell}$ are integer sets each
having at least $n$ elements, each a subset of an interval of at most $q+1$
integers and none a subset of an arithmetic progression of common difference
greater than one, then $S_{1}+\cdots+S_{\ell}$ contains an interval of length
at least $\ell(n-1)+1$.

In working with general cyclic groups, the following analogue of the
Cauchy–Davenport theorem, a consequence of Theorem 1.1 from [12], will also be
useful to us. Given subsets $A$ and $B$ of an abelian group $G$, we define
$A+B=\\{a+b:\,a\in A,b\in B\\}$ and $A-B=\\{a-b:\,a\in A,b\in B\\}$. For
$k\in\mathbb{N}$, we define the $k$-fold sumset
$kA=\underbrace{A+A+\cdots+A}_{k\textrm{ times}}$.

######  Lemma 2.3 (Cochrane, Ostergaard and Spencer [12]).

If $A$ is a subset of an abelian group $G$ which is not contained in a coset
of a proper subgroup of $G$ and $r,s$ are non-negative integers which are not
both zero, then

$|rA-sA|\geq\min\left\\{|G|,\frac{(r+s+1)|A|}{2}\right\\}.$

We will also make use of the following result of Deshouillers and Freiman
[13]. The following corrected statement of the result appears in [4], where it
is also shown that the hypothesis $|A+A|\leq 2.04|A|$ can be weakened to
$|A+A|\leq 2.1|A|$.

######  Lemma 2.4 (Deshouillers and Freiman [13]).

There exists a positive constant $\xi$ such that if $A$ is a subset of
$\mathbb{Z}_{m}$ of size at most $\xi m$ with $|A+A|\leq 2.04|A|$, then there
exists a proper subgroup $H\subseteq\mathbb{Z}_{m}$ such that either

  1. 1.

$A$ is a subset of an arithmetic progression of $H$-cosets of length $\ell$
with $(\ell-1)|H|\leq|A+A|-|A|$,

  2. 2.

$A$ meets exactly three $H$-cosets and these three $H$-cosets are terms of an
arithmetic progression of $H$-cosets of length $\ell$ with
$(\min(\ell,4)-1)|H|\leq|A+A|-|A|$ or

  3. 3.

$A$ is a subset of an $H$-coset and $|A|\geq\xi|H|$.

Here an arithmetic progression of $H$-cosets of length $\ell$ is a set of the
form $\bigcup_{i\in[\ell]}(x+id+H)$, where $x,d\in\mathbb{Z}_{m}$ and $d\notin
H$.

The following simple lemma is crucial in the proofs of most of our main
results.

######  Lemma 2.5.

Let $m$ be an integer. Let $A$ be a set of integers such that $m\notin A$ and
the size of $\Sigma(A)$ considered modulo $m$ is at least $h$, then
$|\Sigma(A\cup\\{m\\})|\geq|\Sigma(A)|+h$.

###### Proof.

The lemma follows since each modulo $m$ class containing an element of
$\Sigma(A)$ contributes at least one new element to
$(\Sigma(A)+\\{m\\})\setminus\Sigma(A)$. ∎

In showing that there are many subset sums over cyclic groups, we use the
following lemma, which shows that the set of new elements whose inclusion do
not expand the set of subset sums is small.

######  Lemma 2.6.

Suppose $A\subset\mathbb{Z}_{m}$ with $d<|A|<m$ and let $G_{d}$ be the set of
$x\in\mathbb{Z}_{m}$ such that $|(A+x)\cup A|\leq|A|+d$. Then
$|G_{d}|\leq\frac{|A|^{2}}{|A|-d}$.

###### Proof.

For each $x\in\mathbb{Z}_{m}$, $|(A+x)\cap(\mathbb{Z}_{m}\setminus
A)|\leq|A+x|=|A|$, while if $x\in G_{d}$, $|(A+x)\cap(\mathbb{Z}_{m}\setminus
A)|\leq d$ by definition. Furthermore,

$\sum_{x\in\mathbb{Z}_{m}}|(A+x)\cap(\mathbb{Z}_{m}\setminus A)|=\sum_{a\in
A}|\\{x\in\mathbb{Z}_{m}:a+x\in\mathbb{Z}_{m}\setminus A\\}|=\sum_{a\in
A}(m-|A|)=|A|(m-|A|),$

where the second equality follows since, for each $a\in A$, $a+x$ is an
element of $\mathbb{Z}_{m}\setminus A$ for exactly $|\mathbb{Z}_{m}\setminus
A|=m-|A|$ values of $x$. Thus,

$|A|(m-|A|)\leq|G_{d}|\cdot d+(m-|G_{d}|)|A|,$

from which we get the desired inequality by rearranging. ∎

We will often use the lemma above in combination with the following simple
result.

######  Lemma 2.7.

If $A\subset\mathbb{Z}_{m}$ and $x_{1},\dots,x_{k}\in\mathbb{Z}_{m}$ satisfy
$|(A+x_{i})\cup A|\leq|A|+d$ for all $i\in[k]$, then
$|(A+x_{1}+\cdots+x_{k})\cup A|\leq|A|+kd$.

###### Proof.

We will show, by induction on $i$, that $|(A+x_{1}+\cdots+x_{i})\cup
A|\leq|A|+id$ for $1\leq i\leq k$. This is clearly true for $i=1$. For the
induction step, assume that $|(A+x_{1}+\cdots+x_{i-1})\cup A|\leq|A|+(i-1)d$.
Then

$\displaystyle|(A+x_{1}+\cdots+x_{i})\cup A|-|A|$
$\displaystyle=|(A+x_{1}+\cdots+x_{i})\setminus A|$
$\displaystyle\leq|(A+x_{1}+\cdots+x_{i})\setminus(A+x_{i})|+|(A+x_{i})\setminus
A|$ $\displaystyle=|(A+x_{1}+\cdots+x_{i-1})\setminus A|+|(A+x_{i})\setminus
A|$ $\displaystyle\leq(i-1)d+d=id.$

Thus, $|(A+x_{1}+\cdots+x_{i})\cup A|\leq|A|+id$ for $1\leq i\leq k$. ∎

###  2.2 Outline of the proof of the upper bounds in Theorems 1.1 and 1.2

The upper bound in Theorem 1.1 states that there exists a constant $C$ such
that, for every $r\geq 2$, there is an $r$-Ramsey complete sequence $A$ with
$|A\cap[n]|\leq Cr\log^{2}n$ for all $n$. The following density-type result is
the key to the proof of this statement.

######  Lemma 2.8.

Let $C=3840$ and $\epsilon\in(0,1/2]$. Let $x$ be a positive integer. Let $X$
be the set of integers in $[x,2x)$ with no prime divisor at most $(\log x)/2$.
If a sequence $S$ of $C\epsilon^{-1}\log x$ elements in $X$ is chosen
independently and uniformly at random, then, with high probability (as
$x\to\infty$), $S$ has distinct terms and, for any subsequence $S^{\prime}$ of
$S$ of size $\epsilon|S|=C\log x$, the set $\Sigma(S^{\prime})$ contains all
integers in the interval $[\frac{Cx\log x}{4},\frac{7Cx\log x}{8}]$.

The upper bound in Theorem 1.1 can be easily deduced from Lemma 2.8 as
follows.

Proof of the upper bound in Theorem 1.1. Let $\epsilon=1/r$ and let $x_{0}$ be
large enough that the conclusion of Lemma 2.8 holds with positive probability
for this choice of $\epsilon$ and $x\geq x_{0}$. Let $x_{i}=2^{i}x_{0}$ and
$y_{i}=Cx_{i}\log x_{i}$. By Lemma 2.8, for each dyadic interval
$[x_{i},x_{i+1})$ with $i\geq 0$ we can pick a sequence $S_{i}$ of $Cr\log
x_{i}$ distinct elements in this interval such that the set of subset sums of
any subset of $S_{i}$ of size at least $|S_{i}|/r$ contains the integers in
$I_{i}:=[y_{i}/4,7y_{i}/8]$. Note that every $r$-coloring of $S_{i}$ has a
color class of size at least $|S_{i}|/r$ and so the set of monochromatic
subset sums of $S_{i}$ contains the integers in $I_{i}$. We pick the sequence
$A$ to be the concatenation of the sequences $S_{i}$ for $i\geq 0$. Observe
that, for all $n$, we have $A(n)\leq\sum_{i:n\leq x_{i+1}}|S_{i}|\leq Cr(\log
n)^{2}$. Moreover, since $y_{i+1}/4<7y_{i}/8$, the intervals $I_{i}$ cover all
integers at least $y_{0}/4$. Thus, for every $r$-coloring of $A$, every
sufficiently large integer can be represented as a monochromatic subset sum.
That is, the sequence $A$ is $r$-Ramsey complete. ∎

We now give an informal sketch of the proof of Lemma 2.8, showing how it
follows from an appropriate combination of the results of Section 2.1 with
some further ideas. To begin, we observe that for any fixed set $I$ of $C\log
x$ indices in $[C\epsilon^{-1}\log x]$, the elements of the subsequence
$(s_{i}:i\in I)$ of $S$ of size $\epsilon|S|$ are independently and uniformly
distributed in $X$. By taking a union bound, it will therefore suffice to show
that if $S^{\prime}$ is a sequence of $C\log x$ elements chosen independently
and uniformly from $X$, then the probability that $\Sigma(S^{\prime})$ does
not contain all integers in the interval $[\frac{Cx\log x}{4},\frac{7Cx\log
x}{8}]$ is sufficiently small.

For this, for some fixed $\ell$, we take $\ell$ disjoint random subsets
$S^{\prime\prime}_{1},\dots,S^{\prime\prime}_{\ell}$ of $S^{\prime}$, each of
size $|S^{\prime}|/(8\ell)$, with the aim being to show that, with
appropriately high probability, the set of subset sums
$\Sigma(S_{j}^{\prime\prime})$ is a dense subset of a long interval and is not
contained in an arithmetic progression with common difference larger than $1$.
Lemma 2.2 then allows us to conclude that
$S^{\prime\prime}=S^{\prime\prime}_{1}\cup\dots\cup S^{\prime\prime}_{\ell}$
is such that
$\Sigma(S^{\prime\prime})=\Sigma(S^{\prime\prime}_{1})+\dots+\Sigma(S^{\prime\prime}_{\ell})$
contains a long interval. Note, moreover, that $S^{\prime\prime}$ only has
size $|S^{\prime}|/8$, so there are at least $7|S^{\prime}|/8$ elements still
remaining in $S^{\prime}$. Using Graham’s lemma, Lemma 2.1, we can use these
elements to extend the long interval in $\Sigma(S^{\prime\prime})$ to a
significantly longer interval containing all of the required elements.

It only remains to show that $\Sigma(S_{j}^{\prime\prime})$ is a dense subset
of a long interval with appropriately high probability (showing that it is
also not contained in an arithmetic progression with common difference larger
than $1$ is reasonably straightforward). For this, we split
$S^{\prime\prime}_{j}$ randomly into two disjoint pieces $P_{1}$ and $P_{2}$.
The key remaining component is to show that for every $m\in X$, the set of
integers in $[x,2x)$ with no prime factor at most $(\log x)/2$, the mod $m$
set of subset sums $\Sigma_{m}(P_{1})$ is large with very high probability.
Very roughly, this follows by exposing the elements of $P_{1}$ one at a time
and showing that most elements expand the mod $m$ set of subset sums
significantly. Though we will not give a more detailed description here, we
note that this key step again relies on several results from the previous
section, including the Cauchy–Davenport-type statement, Lemma 2.3, as well as
Lemma 2.6, which bounds the number of almost periods, those $x$ for which
$(A+x)\setminus A$ is small. Finally, once we know that $|\Sigma_{m}(P_{1})|$
is, with high probability, large for each $m\in X$, we can apply Lemma 2.5
repeatedly to conclude that $|\Sigma(S^{\prime\prime}_{j})|\geq\sum_{m\in
P_{2}}|\Sigma_{m}(P_{1})|$, which yields the required lower bound for
$|\Sigma(S^{\prime\prime}_{j})|$.

The proof of Theorem 1.2 follows a similar scheme. Let $P$ be a complete
polynomial. By the characterization due to Graham [26] discussed in the
introduction, we can write $P(x)=\sum_{i=0}^{k}\alpha_{i}\binom{x}{i}$ with
$\alpha_{k}>0$ and $\alpha_{i}=\frac{p_{i}}{q_{i}}$, where $p_{i}$ and $q_{i}$
are relatively prime integers, $q_{i}>0$ and $\gcd(p_{0},\dots,p_{k})=1$. If
$L=\textrm{lcm}(q_{0},\dots,q_{k})$, then the polynomial $L\cdot P$ has
integer coefficients in its binomial representation and satisfies Graham’s
condition, so it is also complete. Furthermore, if $((L\cdot
P)(a_{n}))_{n=1}^{\infty}$ is $r$-Ramsey complete, then
$(P(a_{n}))_{n=1}^{\infty}$ is $r$-Ramsey complete, so it suffices to work
with complete polynomials which have integer coefficients in their binomial
representations. From now on, we will assume that $P$ is such a polynomial.

To prove Theorem 1.2, we prove the following polynomial analogue of Lemma 2.8.
For a polynomial $P$ and a sequence $T$ of integers, let $P(T)$ be the
sequence where we replace each term $t$ in $T$ by $P(t)$.

######  Lemma 2.9.

Let $P$ be a complete polynomial of degree $k$ with integer coefficients in
its binomial representation and let $C(k)=k2^{k+15}$. Let
$\epsilon\in(0,1/2]$. Let $x$ be a positive integer. Let $X$ be the set of
elements $y$ in $[x,(1+1/k)x)$ such that $P(y)$ has no prime divisor at most
$(\log x)^{1/2}$. If a sequence $S$ of $C(k)\epsilon^{-1}\log x$ elements in
$X$ is chosen independently and uniformly at random, then, with high
probability (as $x\to\infty$), $S$ has distinct terms and, for any subsequence
$S^{\prime}$ of $S$ of size $\epsilon|S|$, the set $\Sigma(P(S^{\prime}))$
contains all integers in the interval
$[\frac{e}{9}P(x)|S^{\prime}|,\frac{8}{9}P(x)|S^{\prime}|]$.

We now show how Theorem 1.2 follows from Lemma 2.9, just as the upper bound in
Theorem 1.1 follows from Lemma 2.8.

Proof of Theorem 1.2. Let $\epsilon=1/r$. For each positive integer $i$, let
$x_{i}=(1+1/k)^{i}$, $y_{i}=C(k)P(x_{i})\log x_{i}$ and
$I_{i}=[ey_{i}/9,8y_{i}/9]$. For $i$ sufficiently large in terms of $P$ and
$r$, Lemma 2.9 implies that we can pick a subsequence $S_{i}$ of $C(k)r\log
x_{i}$ distinct terms in $[x_{i},(1+1/k)x_{i})$ such that any subsequence
$S^{\prime}$ of $S_{i}$ with $|S_{i}|/r$ terms has the property that
$\Sigma(P(S^{\prime}))$ contains all integers in the interval $I_{i}$.
Therefore, since every $r$-coloring of $S_{i}$ has a color class of size at
least $|S_{i}|/r$, the set of monochromatic subset sums of $P(S_{i})$ contains
the integers in $I_{i}$. We pick the sequence $A$ to be the concatenation of
the sequences $P(S_{i})$ with $i$ sufficiently large. Then, for all $n$, we
have $A(n)\leq\sum_{i:P(x_{i})\leq n}|S_{i}|=O_{k}\left((\log n)^{2}\right)$.
Moreover, as $x_{i}$ is sufficiently large, $P(x)$ is increasing for $x\geq
x_{i}$ and $P(x_{i+1})=P((1+1/k)x_{i})\leq eP(x_{i})$. It follows that, for
$i$ sufficiently large, $ey_{i+1}/9\leq 8y_{i}/9$ and the intervals $I_{i}$
and $I_{i+1}$ are overlapping. Hence, the intervals $I_{i}$ cover all
sufficiently large integers. Thus, for every $r$-coloring of $A$, every
sufficiently large integer can be represented as a monochromatic subset sum.
That is, the sequence $A$ is $r$-Ramsey complete. ∎

The proof of Lemma 2.9 itself follows along broadly similar lines to the proof
of Lemma 2.8. The key additional input, arising in the analogue of the step
where we showed that $|\Sigma_{m}(P_{1})|$ is large with high probability for
each $m\in X$, is the following result on iterated sumsets of a set of
polynomial values, proved through a form of PET induction (see, for example,
[5]). For further details, we refer the reader to Section 3, where the proofs
of Lemmas 2.8 and 2.9 are given in full.

######  Lemma 2.10.

There exists a constant $C_{k}$, depending only on $k$, such that if $P$ is a
complete polynomial of degree $k$ with integer coefficients in its binomial
representation, $x$ is sufficiently large depending on $P$, $m$ is an integer
in $[x,2x)$, $(\log x)^{-1}<\alpha<1/2$ and $T$ is a subset of $[x,2x)$ of
size at least $\alpha x$, then the iterated sumset $2^{k-1}P(T)-2^{k-1}P(T)$
contains more than $\alpha^{C_{k}}P(m)$ residue classes modulo $P(m)$.

###  2.3 Outline of the proof of the lower bound in Theorems 1.5 and 1.6

Recall that, for any $n\leq m\leq{n\choose 2}$, $f(n,m)$ is defined as the
minimum $r$ for which there is an $r$-coloring of $[n-1]$ such that $m$ cannot
be written as a sum of distinct monochromatic elements. In this section, we
sketch the main ideas behind the lower bound in Theorem 1.6, which
asymptotically determines the value of $f(n,m)$. For simplicity, we will focus
on the case $m=n$ corresponding to Theorem 1.5, where we wish to show that
$f(n)=f(n,n)=\Theta\left(\frac{n^{1/3}(n/\phi(n))}{(\log n)^{1/3}(\log\log
n)^{2/3}}\right)$. Theorem 1.6 follows from an appropriate elaboration of
these ideas.

We begin by sketching Vu’s argument [43] (itself building on an argument used
by Alon and Erdős [2]), which yields the bound $f(n)\geq
c_{1}\frac{n^{1/3}}{\log n}$ for some positive constant $c_{1}$. To this end,
consider an arbitrary $r$-coloring of $[n]$ for some
$r<c_{1}\frac{n^{1/3}}{\log n}$. We restrict our attention to the interval
$[n^{2/3},2n^{2/3})$ and focus on the color class containing the largest
number of primes from this interval. Let $Q$ be the set of primes in this
color class, noting that $r<c_{1}\frac{n^{1/3}}{\log n}$ implies that $|Q|\geq
Cn^{1/3}$ for a positive constant $C$ (which can be made arbitrarily large by
taking $c_{1}$ to be sufficiently small). Partition $Q$ into three subsets
$Q_{1}$, $Q_{2}$ and $Q_{3}$ of roughly equal size. Since
$|Q_{1}|\geq\frac{C}{3}n^{1/3}$, we can apply the Szemerédi–Vu theorem,
Theorem 1.8, to $Q_{1}$ to obtain an arithmetic progression of length at least
$2n^{2/3}$ in $\Sigma(Q_{1})$. We can then complete this arithmetic
progression of common difference $d$, say, to a long interval by building a
complete modulo $d$ class using $Q_{2}$. Provided the parameters have been
chosen appropriately, this interval will have length at least $2n^{2/3}$ and
the minimum number in the interval will be smaller than $n$. Therefore, by
Lemma 2.1, adding each element of $Q_{3}$ in turn will expand the interval
and, since adding all elements in $Q_{3}$ would exceed $n$, the resulting
interval in $\Sigma(Q_{1}\cup Q_{2}\cup Q_{3})$ must contain $n$.

To go further, we make two observations about this argument. First, note that
we passed immediately to a subset of the primes. This was in order to avoid
the situation where a color class consists entirely of numbers with a given
divisor, as, otherwise, it would be impossible to write any $n$ which is not a
multiple of this divisor as a sum of elements from the color class. Second,
the key tool in the proof, Theorem 1.8, is tight up to the constant, since the
set of subset sums of the set consisting of the first
$\lfloor\sqrt{2n}-1/2\rfloor$ positive integers has size less than $n$.
However, this naive application of Theorem 1.8 makes no use of the fact that
our set consists entirely of primes. It is here that we are able to gain.

To illustrate the main ideas in our argument, we first restrict to the case
where $n$ is prime. Suppose then that there is an $r$-coloring of $[n-1]$,
where $r$ satisfies $n=\lambda r^{3}(\log r)(\log\log r)^{2}$ for a
sufficiently large constant $\lambda$. If we let $y=\Theta(r^{2}(\log
r)(\log\log r))$, the number of primes in the interval $[y,2y)$ is
$\Theta(r^{2}\log\log r)$, so, by the pigeonhole principle, there is a
monochromatic subset $Q$ of the primes in $[y,2y)$ with $|Q|=\Omega(r\log\log
r)$. As in Vu’s argument, the plan from this point is to use a subset $V$ of
$Q$ of size $O(r\log\log r)$ to build a large interval and then to apply Lemma
2.1 to expand this interval using the remaining elements. To show that
$\Sigma(V)$ contains the required interval, we partition $V$ into a bounded
number of sets $V_{1},V_{2},\dots,V_{\ell}$ of roughly equal size and show
that, for each $i$, $\Sigma(V_{i})$ contains a dense subset of an interval.
Given this crucial input, Lemma 2.2 then implies that $\Sigma(V)$ contains a
long interval.

Quantitatively, for this argument to go through, we need $\Sigma(V)$ to
contain an interval of length $\Omega(r^{2}(\log r)(\log\log r))$. For this to
follow from Lemma 2.2, we need to have $|\Sigma(V_{i})|=\Omega(r^{2}(\log
r)(\log\log r))$ for each $V_{i}$, themselves satisfying $|V_{i}|=O(r\log\log
r)$. Thus, we need to show that $|\Sigma(V_{i})|/|V_{i}|\geq r\log r$, say.
For this, we prove an inverse result, that if $|\Sigma(V_{i})|/|V_{i}|<r\log
r$, then a large subset of $V_{i}$ must be additively structured, in the sense
that this subset is contained in a set of size $O(|V_{i}|(\log r)/(\log\log
r))$ which can be written as a union of long arithmetic progressions. We then
use the Selberg sieve to show that, since $V_{i}$ consists of primes, it is
impossible for a large subset of $V_{i}$ to have this structure.

In practice, as in the proofs of Theorems 1.1 and 1.2, we do much of our work
over cyclic groups. Indeed, to show that $\Sigma(V_{i})$ is large, we
partition $V_{i}$ into two sets $A_{i,1}$ and $A_{i,2}$ and show that, for
each $a_{2}\in A_{i,2}$, $|\Sigma(A_{i,1})\pmod{a_{2}}|$ is large. Lemma 2.5
then allows us to conclude that $\Sigma(V_{i})=\Sigma(A_{i,1}\cup A_{i,2})$ is
large.

To show that $|\Sigma(A_{i,1})\pmod{a_{2}}|$ is large, we consider an
iterative building process which grows the set of subset sums modulo $a_{2}$
by picking elements in $A_{i,1}$ one at a time. We begin with $T_{0}=A_{i,1}$
and $\Sigma(0)=\\{0\\}\subseteq\mathbb{Z}_{a_{2}}$. In step $j\geq 1$, we
choose an element $x_{j}$ from $T_{j-1}$ which maximizes
$|(\Sigma(j-1)+x_{j})\setminus\Sigma(j-1)|$, where the set $\Sigma(j-1)$ is
viewed as a subset of $\mathbb{Z}_{a_{2}}$, and then set
$\Sigma(j)=(\Sigma(j-1)+x_{j})\cup\Sigma(j-1)$ and
$T_{j}=T_{j-1}\setminus\\{x_{j}\\}$. If, for each $j\leq|A_{i,1}|/2$, there is
a choice of $x_{j}$ such that $|(\Sigma(j-1)+x_{j})\setminus\Sigma(j-1)|$ is
large, then $|\Sigma(A_{i,1})\pmod{a_{2}}|$ will be large, as required. If,
instead, there is a step $j$ such that $|(\Sigma(j-1)+x)\setminus\Sigma(j-1)|$
is small for all $x\in T_{j-1}$, then, using Lemma 2.4 (or, rather, its
corollary, Lemma 5.7), we can show that $T_{j-1}$ is additively structured, in
the sense that it is contained in a small set which is a union of long
arithmetic progressions. By a version of the Selberg sieve, $T_{j-1}$ cannot
then contain too many primes, contradicting the fact that, as a subset of $Q$,
$T_{j-1}$ consists entirely of primes.

Several additional ideas are needed to handle the case where $n$ is not prime.
For instance, in the prime case, we could build the required sum $n$ using
only primes, but now we must use integers of the form $qu$, where $u$ is a
small divisor of $n$ and $q$ is coprime to the first $r$ primes. As before,
our first step is to pass to a large monochromatic subset $Q_{0}$ of this set,
the goal being to show that $n$ is contained in the set of subset sums of
$Q_{0}$. In the prime case, we took a subset $V$ of $Q=Q_{0}$, partitioned it
into sets $V_{i}$ and then partitioned each $V_{i}$ into sets $A_{i,1}$ and
$A_{i,2}$, before showing that $|\Sigma(A_{i,1})\pmod{a_{2}}|$ is large for
each $a_{2}\in A_{i,2}$. However, this argument may not go through in the
general case, because, when $a_{2}$ is not prime, we could have that
$A_{i,1}$, and hence $\Sigma(A_{i,1})$, is contained in a small proper
subgroup of $\mathbb{Z}_{a_{2}}$.

To overcome this issue, we first apply a preprocessing step to the set
$Q_{0}$, our aim being to find a closely related set $Q$ which is _$k$
-diverse_, by which we mean that, for any $d\geq 2$, there are at least $k$
elements of $Q$ which are not divisible by $d$. We obtain such a set through a
simple iteration. Indeed, if we have a set which is not $k$-diverse, then
there is some $d$ dividing all but $k$ elements of the set, so we can remove
these elements from the set and divide the remaining elements by $d$ to form a
new set. Repeating this procedure with an appropriate value of $k$, we
eventually arrive at a large $k$-diverse set $Q$ such that $\\{vx:x\in
Q\\}\subseteq Q_{0}$ for some $v|n$. Thus, in order to conclude that $n$ is a
sum of elements in $Q_{0}$, we only need to show that $n/v$ is a sum of
elements in $Q$.

A crucial property of diverse sets is that random subsets of a diverse set are
themselves diverse with high probability. Thus, by taking a random subset $V$
of $Q$, randomly partitioning $V$ into parts $V_{i}$ and then randomly
partitioning each $V_{i}$ into $A_{i,1}$ and $A_{i,2}$, we have that, with
high probability, all of the sets $A_{i,1}$ are diverse. We can also show that
any common divisor of a large subset of $A_{i,1}$ must be a small divisor of
$n$. Proceeding now along the same lines as the prime case, this reduces our
task to showing that $|\Sigma(A_{i,1})\pmod{a_{2}}|$ is large for any diverse
subset $A_{i,1}$ of $A$ with the additional property that any common divisor
of a large subset of $A_{i,1}$ is small.

To show that $|\Sigma(A_{i,1})\pmod{a_{2}}|$ is large, we consider a more
refined version of the iterative building process used in the prime case. The
details of this key step are contained in Lemma 5.6. We again begin with
$T_{0}=A_{i,1}$ and $\Sigma(0)=\\{0\\}\subseteq\mathbb{Z}_{a_{2}}$ and, in
step $j\geq 1$, we again choose an element $x_{j}$ from $T_{j-1}$ and set
$\Sigma(j)=(\Sigma(j-1)+x_{j})\cup\Sigma(j-1)$ and
$T_{j}=T_{j-1}\setminus\\{x_{j}\\}$, but the process for choosing $x_{j}$ is
more complex. To describe it, we let $d_{j}$ be the greatest common divisor of
the elements in $T_{j-1}$. The choice of $x_{j}$ depends on the sets
$S_{u}=\Sigma(j-1)\cap(u+d_{j}\mathbb{Z}_{a_{2}})$ with
$u\in\mathbb{Z}_{a_{2}}/d_{j}\mathbb{Z}_{a_{2}}$. We refer to step $j$ as a
growth phase, an unsaturated phase or a saturated phase, depending on whether
there exists $u$ such that $S_{u}$ is non-empty and small, no non-empty
$S_{u}$ is small and at least one is of intermediate size or all non-empty
$S_{u}$ are large, respectively. If $j$ is a growth phase, we choose $x_{j}$
from $T_{j-1}$ so as to maximize $|\Sigma(d_{j},j)|-|\Sigma(d_{j},j-1)|$,
where $\Sigma(d_{j},t)=\\{\sum_{h\in
H}x_{h}\pmod{a_{2}}:H\subseteq[t]\cap\\{h:d_{j}|x_{h}\\}\\}$. If $j$ is an
unsaturated or saturated phase, we choose $x_{j}$ from $T_{j-1}$ so as to
maximize $|(\Sigma(j-1)+x_{j})\setminus\Sigma(j-1)|$.

If now there is a saturated phase $j$ among the first $|A_{i,1}|/2$ steps, we
can show that $|\Sigma(A_{i,1})\pmod{a_{2}}|\geq|\Sigma(j-1)|$ is large, as
required. On the other hand, we can also show that there are only a small
number of growth phases among the first $|A_{i,1}|/2$ steps. Hence, we can
assume that there are many unsaturated phases. Our aim now is to show that
$|\Sigma(j)|-|\Sigma(j-1)|$ is large for any unsaturated phase, since,
together with the fact that there are many unsaturated phases, this will imply
that $|\Sigma(A_{i,1})\pmod{a_{2}}|$ is large, as required. As in the prime
case, this final step proceeds by first showing that if
$|\Sigma(j)|-|\Sigma(j-1)|$ is not large, then $T_{j-1}$ must be additively
structured, again that it is contained in a small set which is a union of long
arithmetic progressions, and then using the Selberg sieve to derive a
contradiction, in this case that $T_{j-1}$ cannot contain many elements of the
form $qu$, where $u$ is a small divisor of $n$ and $q$ is coprime to the first
$r$ primes.

###  2.4 Outline of the proof of Theorem 1.9

To prove Theorem 1.9, that there exists a constant $C$ such that any
$A\subset[n]$ with $|A|\geq C\sqrt{n}$ has a homogeneous progression of length
$n$ in $\Sigma(A)$, we use a variant of the ideas discussed in Subsection 2.3.
As in that subsection, we apply a preprocessing step to the set $A$ to find a
set $A^{\prime}$ of size comparable to $A$ which is $k$-diverse for an
appropriate $k$ and for which there exists an integer $d$ such that
$\\{dx:x\in A^{\prime}\\}\subseteq A$. We also maintain a further property,
that $A^{\prime}$ intersects each dyadic interval in either the empty set or a
large set. Having obtained the required set $A^{\prime}$, we replace $A$ with
this set and consider a random partition of the set into parts
$X_{1},Y_{1},\dots,X_{\ell},Y_{\ell}$.

The key step in the proof is Lemma 6.2, which roughly says that if $X_{i}$
satisfies an appropriate diversity condition, then $|\Sigma(X_{i})\pmod{b}|$
is large for all $b\in Y_{i}$. But since $X_{i}$ is part of a random partition
of the diverse set $A$, we can, with high probability, guarantee that $X_{i}$
is also diverse and, therefore, by Lemma 6.2, that $|\Sigma(X_{i})\pmod{b}|$
is large for all $b\in Y_{i}$. Then, as in the previous outlines, we apply
Lemma 2.5, in this case together with what we know about the distribution of
$A$ in dyadic intervals, to show that $\Sigma(X_{i}\cup Y_{i})$ is large,
followed by Lemma 2.2 to conclude that $\Sigma(A)$ contains a long interval.
Unwinding the preprocessing step, we see that this interval corresponds to a
long homogeneous arithmetic progression in the set of subset sums of the
original set, as required.

At first glance, Lemma 6.2 seems to bear close resemblance to one of the key
steps in the proofs of Theorems 1.5 and 1.6 described in the previous
subsection (and formally encapsulated in Lemma 5.6). In both cases, we wish to
show that if $X$ is a sufficiently diverse set, then $|\Sigma(X)\pmod{b}|$ is
large for all $b$ in a certain set $Y$. The difference lies in the fact that
the sets $X$ considered in Theorems 1.5 and 1.6 are carefully chosen so that
we can hope for a stronger guarantee on the size of $\Sigma(X)\pmod{b}$ than
in the typical case, whereas here we are concerned precisely with that typical
case. The proof of Lemma 6.2 follows from a similar iterative building process
to that used in the proof of Lemma 5.6, as described at the end of the last
subsection.

Because we need it for the proof of Theorem 1.7, our result on the largest
subset of $[n]$ avoiding a particular subset sum, we will actually prove a
strengthening of Theorem 1.9, saying that we can build the required
homogeneous progression using short sums, that is, sums with only a small
number of terms. This strengthening requires a somewhat more careful analysis
than that described above. In particular, we must start with $T_{0}$ equal to
a large random subset of $X_{i}$ and $\Sigma(0)=X_{i}\setminus T_{0}\pmod{b}$.

##  3 Ramsey completeness

###  3.1 Proof of the upper bound in Theorem 1.1

The goal of this section is to prove the upper bound in Theorem 1.1, that
there exists a constant $C$ such that, for every $r\geq 2$, there is an
$r$-Ramsey complete sequence $A$ with $|A\cap[n]|\leq Cr\log^{2}n$ for all
$n$. As shown in Section 2.2, this theorem follows from another statement,
Lemma 2.8, whose proof will occupy us in this subsection.

The next lemma, a mod $m$ analogue of Lemma 2.8, is the key step in proving
that lemma. Let $\Sigma_{m}(S)$ be the set of subset sums of $S$ taken modulo
$m$.

######  Lemma 3.1.

Fix $c\geq 6$ and assume that $x$ is sufficiently large. Let $w=(\log x)/2$
and let $X$ be the set of integers in $[x,2x)$ with no prime divisor at most
$w$. Let $m\in X$. If a sequence $S$ of $c\log x$ integers is chosen uniformly
and independently at random from $X$ and viewed as a sequence of elements in
$\mathbb{Z}_{m}$, then $|\Sigma_{m}(S)|<\frac{x}{4}$ with probability less
than $\left(\log x\right)^{-(c-5)\log x}$.

###### Proof.

Let $W=\prod_{p\leq w}p$, where the product is taken over primes, and
$\tau=\phi(W)/W$. The prime number theorem implies that
$W=e^{(1+o(1))w}=x^{1/2+o(1)}$. In any interval of length $W$, there are
exactly $\tau W$ integers with no prime divisor at most $w$. By Merten’s third
theorem, $\tau=\left(e^{-\gamma}+o(1)\right)/\log w$, where $\gamma$ is the
Euler–Mascheroni constant. It follows that

$|X|\geq\tau(x-W)\geq\frac{x}{2\log\log x}.$

Let $q=c\log x$. Let $S=(s_{1},s_{2},\dots,s_{q})$ be a sequence of $q$ random
elements of $X$. Let $S_{i}=(s_{1},\ldots,s_{i})$ denote the sequence
consisting of the first $i$ elements of $S$. Let $\delta=\log\log x/\log x$.
Call $i\in[2,q]$ bad if

  * •

$|\Sigma_{m}(S_{i})|\leq\frac{3}{2}|\Sigma_{m}(S_{i-1})|$ and
$|\Sigma_{m}(S_{i-1})|\leq x/\log x$ or

  * •

$|\Sigma_{m}(S_{i})|\leq(1+\delta)|\Sigma_{m}(S_{i-1})|$ and $x/\log
x<|\Sigma_{m}(S_{i-1})|<x/4$.

The following two claims allow us to quickly complete the proof.

Claim 1. The probability that $i$ is bad conditioned on the choice of
$S_{i-1}$ is at most $p:=\frac{4(\log\log x)^{2}}{\log x}$.

Claim 2. If $|\Sigma_{m}(S)|<x/4$, then the number of integers in $[2,q]$
which are not bad is less than $4\log x$.

Assuming Claim 1, for any $B\subset[2,q]$, the probability that all elements
in $B$ are bad is at most $p^{|B|}$. From Claim 2, if $|\Sigma_{m}(S)|<x/4$,
then there is a set $B$ of $q-4\log x$ integers $i\in[2,q]$ which are bad.
Taking a union bound over all such choices of $B$, the probability that
$|\Sigma_{m}(S)|<x/4$ is at most

${q\choose q-4\log x}p^{|B|}={q\choose 4\log x}p^{|B|}<c^{4\log
x}\left(\frac{4(\log\log x)^{2}}{\log x}\right)^{(c-4)\log x}<(\log
x)^{-(c-5)\log x}.\qed$

To complete the proof, it remains to verify Claims 1 and 2.

Proof of Claim 1. Fix $S_{i-1}=(s_{1},\ldots,s_{i-1})$. Conditioned on this
choice of $S_{i-1}$, we bound the probability that $i$ is bad. If
$|\Sigma_{m}(S_{i-1})|\geq x/4$, then $i$ cannot be bad (so the event that $i$
is bad has probability zero). We may therefore restrict attention to the two
cases $|\Sigma_{m}(S_{i-1})|\leq x/\log x$ and $x/\log
x<|\Sigma_{m}(S_{i-1})|<x/4$.

For the first case, note, by Lemma 2.6, that the number of $s$ with
$|\Sigma_{m}(S_{i-1}\cup\\{s\\})|\leq\frac{3}{2}|\Sigma_{m}(S_{i-1})|$ is at
most
$\frac{|\Sigma_{m}(S_{i-1})|^{2}}{|\Sigma_{m}(S_{i-1})|/2}=2|\Sigma_{m}(S_{i-1})|$.
Therefore, if $|\Sigma_{m}(S_{i-1})|\leq x/\log x$, the probability that $i$
is bad conditioned on $S_{i-1}$ is at most
$\frac{2|\Sigma_{m}(S_{i-1})|}{|X|}\leq\frac{2x}{|X|\log x}\leq\frac{4\log\log
x}{\log x}<p$.

Suppose now that $x/\log x<|\Sigma_{m}(S_{i-1})|<x/4$. For a positive integer
$D$, let $G_{D}$ be the set of $s$ such that
$|\Sigma_{m}(S_{i-1}\cup\\{s\\})|\leq|\Sigma_{m}(S_{i-1})|+D$. Let
$d=\lfloor\delta|\Sigma_{m}(S_{i-1})|\rfloor$, so $i$ is bad in this case if
and only if $s_{i}\in G_{d}$. Let $k=\lfloor\frac{1}{2\delta}\rfloor$, so
$kd\leq|\Sigma_{m}(S_{i-1})|/2$. By Lemma 2.7, $kG_{d}\subseteq G_{kd}$, so
$\left|kG_{d}\right|\leq|G_{kd}|\leq 2|\Sigma_{m}(S_{i-1})|<\frac{x}{2}$,
where the middle inequality is again by the consequence of Lemma 2.6 noted
above.

If $|G_{d}|\leq\frac{m}{w}$, then $|G_{d}|\leq\frac{m}{w}\leq\frac{2x}{(\log
x)/2}<2\delta x$. Otherwise, $|G_{d}|>\frac{m}{w}$. In this case, since $m$
has no prime divisor at most $w$, no subgroup of $\mathbb{Z}_{m}$ has size
larger than $\frac{m}{w}$. Thus, $G_{d}$ cannot be contained in a coset of a
non-trivial subgroup. By Lemma 2.3, since
$\left|kG_{d}\right|\leq\frac{x}{2}<m$, we must have
$\left|kG_{d}\right|\geq(k+1)|G_{d}|/2\geq|G_{d}|/(4\delta)$. Hence,
$|G_{d}|\leq 4\delta|kG_{d}|\leq 4\delta x/2=2\delta x$. Thus, in either case,
conditioned on the choice of $S_{i-1}$, the probability that $i$ is bad, which
is the same as the probability that $s_{i}\in G_{d}$, is at most
$\frac{|G_{d}|}{|X|}\leq\frac{2\delta x}{|X|}\leq 4\delta\log\log x=p$. ∎

Proof of Claim 2. As $S_{i-1}\subset S_{i}$ for $i\in[2,q]$,
$\Sigma_{m}(S_{i-1})\subset\Sigma_{m}(S_{i})$ and, hence,
$1\leq|\Sigma_{m}(S_{1})|\leq\cdots\leq|\Sigma_{m}(S_{q})|=|\Sigma_{m}(S)|<\frac{x}{4}$.
Therefore, the number of $i$ which are not bad with $|\Sigma_{m}(S_{i-1})|\leq
x/\log x$ and $|\Sigma_{m}(S_{i})|\geq\frac{3}{2}|\Sigma_{m}(S_{i-1})|$ is at
most $\log_{3/2}x$, as we get a factor of $3/2$ for each such $i$. Moreover,
since $(1+\delta)^{\delta^{-1}\log_{2}\log x}\geq 2^{\log_{2}\log x}=\log x$,
the number of elements $i$ which are not bad with
$x/4>|\Sigma_{m}(S_{i-1})|>x/\log x$ and
$|\Sigma_{m}(S_{i})|\geq(1+\delta)|\Sigma_{m}(S_{i-1})|$ is at most
$\delta^{-1}\log_{2}\log x=\log_{2}x$, as we get a factor of $1+\delta$ for
each such $i$. Therefore, the number of $i\in[2,q]$ which are not bad is at
most $\log_{3/2}x+\log_{2}x<4\log x$. ∎

We next prove Lemma 2.8 using Lemma 3.1. Let $C=3840$, $\epsilon\in(0,1/2]$
and $X$ be the set of integers in $[x,2x)$ with no prime divisor at most
$(\log x)/2$, as in Lemma 3.1. We wish to show that if a sequence $S$ of
$C\epsilon^{-1}\log x$ elements in $X$ is chosen independently and uniformly
at random, then, with high probability, $S$ has distinct terms and, for any
subsequence $S^{\prime}$ of $S$ of size $\epsilon|S|=C\log x$, the set
$\Sigma(S^{\prime})$ contains all integers in the interval $[\frac{Cx\log
x}{4},\frac{7Cx\log x}{8}]$.

###### Proof of Lemma 2.8.

By the birthday paradox, as $|S|=o(\sqrt{|X|})$, $S$ has distinct terms with
high probability. Fix a choice of subset $I^{\prime}$ of $[C\epsilon^{-1}\log
x]$ of size $C\log x$ and consider the subsequence $S^{\prime}$ of $S$ given
by $(s_{i})_{i\in I^{\prime}}$. Let $I^{\prime\prime}$ be the smallest
$|S^{\prime}|/8$ elements in $I^{\prime}$ and let $S^{\prime\prime}$ be given
by $(s_{i})_{i\in I^{\prime\prime}}$. Let $\ell=40$. Arrange
$I^{\prime\prime}$ in increasing order and partition $I^{\prime\prime}$ into
$\ell$ sets $I^{\prime\prime}_{1},\dots,I^{\prime\prime}_{\ell}$ of
consecutive terms so that each set $I^{\prime\prime}_{j}$ for $j\in[\ell]$ has
size $|I^{\prime\prime}|/\ell$. This gives a partition of $S^{\prime\prime}$
into $\ell$ subsequences $S^{\prime\prime}_{1},\dots,S^{\prime\prime}_{\ell}$,
where $S^{\prime\prime}_{j}=(s_{i})_{i\in I^{\prime\prime}_{j}}$. Note that
$|S_{j}^{\prime\prime}|=\frac{C\log x}{8\ell}$ and
$\Sigma(S^{\prime\prime}_{j})\subseteq[0,2x\frac{C\log x}{8\ell}]$. We shall
prove below that, with high probability, the sequence $S$ has the property
that, for all possible choices of $I^{\prime}$ and $j$,
$|\Sigma(S^{\prime\prime}_{j})|\geq Cx\log x/64\ell$. Assuming this, we can
show that $\Sigma(S_{j}^{\prime\prime})$ is not contained in an arithmetic
progression with common difference larger than $1$. Indeed, if
$\Sigma(S_{j}^{\prime\prime})$ is contained in an arithmetic progression with
common difference $d>1$, then $d\leq\frac{(2Cx\log x)/(8\ell)}{(Cx\log
x)/(64\ell)-1}\leq 17$. Moreover, if $\Sigma(S_{j}^{\prime\prime})$ is
contained in an arithmetic progression with common difference $d>1$, then all
elements in $\Sigma(S_{j}^{\prime\prime})$ are congruent modulo $d$, from
which it follows that all elements of $S_{j}^{\prime\prime}$ are divisible by
$d$. This contradicts the fact that no element of $S_{j}^{\prime\prime}$ has a
prime factor at most $(\log x)/2>17$. Hence, for each $j$,
$\Sigma(S_{j}^{\prime\prime})$ is not contained in an arithmetic progression
with common difference larger than $1$. Therefore, by Lemma 2.2, as
$\Sigma(S^{\prime\prime})=\Sigma(S^{\prime\prime}_{1})+\cdots+\Sigma(S^{\prime\prime}_{\ell})$,
the set $\Sigma(S^{\prime\prime})$ contains the integers in an interval of
length at least $\ell\left(\frac{Cx\log x}{64\ell}-1\right)+1>2x$. Finally, by
Lemma 2.1, $\Sigma(S^{\prime})=\Sigma(S^{\prime\prime}\cup(S^{\prime}\setminus
S^{\prime\prime}))$ contains all integers in the interval $[\frac{Cx\log
x}{4},\frac{7Cx\log x}{8}]$, where we used that all elements of $S^{\prime}$
are at most $2x$, the elements of $\Sigma(S^{\prime\prime})$ are at most
$2x|S^{\prime\prime}|=\frac{Cx\log x}{4}$ and the sum of the elements in
$S^{\prime}\setminus S^{\prime\prime}$ is at least
$\frac{7}{8}|S^{\prime}|x=\frac{7Cx\log x}{8}$.

It remains to show that, with high probability, the sequence $S$ has the
property that, for all possible choices of $I^{\prime}$ and $j$,
$|\Sigma(S^{\prime\prime}_{j})|\geq Cx\log x/64\ell$. Fix an index $1\leq
j\leq\ell$ and partition the index set $I^{\prime\prime}_{j}$ of
$S^{\prime\prime}_{j}$ into two consecutive blocks $J_{1}$ and $J_{2}$ of
equal size. Let $P_{1}=(s_{i})_{i\in J_{1}}$ and $P_{2}=(s_{i})_{i\in J_{2}}$,
so $|P_{1}|=|P_{2}|=\frac{|S_{j}^{\prime\prime}|}{2}=\frac{C\log x}{640}=c\log
x$ for $c=\frac{C}{640}=6$. Recall that $X$ is the set of integers in $[x,2x)$
with no prime divisor at most $(\log x)/2$. Consider $m\in X$. We note that
when we fix the subset of indices $I^{\prime}$ of $[C\epsilon^{-1}\log x]$ of
size $C\log x$ and the index $j$, then $J_{1}$ is determined as a particular
subsequence of $I^{\prime}$. Moreover, each element in $P_{1}$ is uniformly
and independently distributed in $X$. Taking a union bound over all
$x\ell\binom{C\epsilon^{-1}\log x}{C\log x}$ choices of $I^{\prime}$,
$j\in[\ell]$ and $m\in X$, Lemma 3.1 implies that the probability
$|\Sigma_{m}(P_{1})|<\frac{x}{4}$ for some $I^{\prime}$, $j\in[\ell]$ and
$m\in X$ is at most

$x\ell\binom{C\epsilon^{-1}\log x}{C\log x}\cdot\left(\frac{1}{\log
x}\right)^{(c-5)(\log x)}\leq 50x(e/\epsilon)^{3840\log
x}\cdot\left(\frac{1}{\log x}\right)^{\log x}=o_{x}(1),$

where $o_{x}(1)$ tends to $0$ as $x$ tends to infinity. Thus, with high
probability, the sequence $S$ is such that
$|\Sigma_{m}(P_{1})|\geq\frac{x}{4}$ for all choices of $I^{\prime}$,
$j\in[\ell]$ and $m\in X$. In this case, by repeated application of Lemma 2.5,
for all $j\in[\ell]$,

$|\Sigma(S_{j}^{\prime\prime})|\geq\sum_{m\in
P_{2}}\frac{x}{4}=\frac{x}{4}\cdot\frac{|S_{j}^{\prime\prime}|}{2}=\frac{Cx\log
x}{64\ell}.$

Therefore, with high probability, the sequence $S$ is such that
$|\Sigma(S^{\prime\prime}_{j})|\geq Cx\log x/64\ell$ for all possible choices
of $I^{\prime}$ and $j$, as required. ∎

###  3.2 Proof of Theorem 1.2

Our aim in this section is to prove Theorem 1.2, our main result on the Ramsey
completeness of complete polynomial sequences $(P(m))_{m\geq 1}$, saying that
there exists a constant $C$, depending only on the degree of $P$, such that,
for every $r\geq 2$, there is an $r$-Ramsey complete sequence
$A\subset(P(m))_{m\geq 1}$ with $|A\cap[n]|\leq Cr\log^{2}n$ for all $n$. As
remarked in Section 2.2, we can and will assume that $P$ is a complete
polynomial which has integer coefficients in its binomial representation. That
is, we can write $P(x)=\sum_{i=0}^{k}\alpha_{i}\binom{x}{i}$, with
$\alpha_{k}>0$, each $\alpha_{i}$ an integer and
$\gcd(\alpha_{0},\dots,\alpha_{k})=1$.

Our first goal will be to prove Lemma 2.10. To recall the statement, suppose
that $P$ is a complete polynomial of degree $k$ with integer coefficients in
its binomial representation, $m$ is an integer in $[x,2x)$, $(\log
x)^{-1}<\alpha<1/2$ and $T$ is a subset of $[x,2x)$ of size at least $\alpha
x$. Then Lemma 2.10 asserts that there is a constant $C_{k}$ depending only on
$k$ such that, for $x$ sufficiently large, the iterated sumset
$2^{k-1}P(T)-2^{k-1}P(T)$ contains more than $\alpha^{C_{k}}P(m)$ residue
classes modulo $P(m)$. Once this lemma is in place, we will follow a scheme
similar to that of the previous subsection to complete the proof.

###### Proof of Lemma 2.10.

Let $T=\\{x_{0},x_{1},\dots,x_{\ell-1}\\}$, where $x\leq
x_{0}<x_{1}<\dots<x_{\ell-1}<2x$ and $\ell\geq\alpha x$. Let $x_{0,i}=x_{i}$
and $\ell_{0}=\ell$. Let $\ell_{j}=\ell_{j-1}(\ell_{j-1}-1)/4x$ for
$j=1,\dots,k$. For each $j\in[k]$, we recursively construct a subsequence
$x_{j,0}<x_{j,1}<\dots<x_{j,\ell_{j}-1}$ of $T$ with $\ell_{j}$ terms, as
follows. For each $j\in[k]$, note that at least $\left(\ell_{j-1}-1\right)/2$
of the indices $0\leq i\leq\ell_{j-1}-2$ satisfy $x_{j-1,i+1}-x_{j-1,i}\leq
2x/\ell_{j-1}$. Thus, by the pigeonhole principle, there is
$y_{j}\in[2x/\ell_{j-1}]$ such that at least
$\left((\ell_{j-1}-1)/2)\right/\left(2x/\ell_{j-1}\right)=\ell_{j}$ indices
$0\leq i\leq\ell_{j-1}-2$ satisfy $x_{j-1,i+1}-x_{j-1,i}=y_{j}$. Let
$x_{j,i}=x_{j-1,t_{i}}$ for $\ell_{j}$ increasing indices
$t_{0},t_{1},\dots,t_{\ell_{j}-1}$ such that
$x_{j-1,t_{i}+1}-x_{j-1,t_{i}}=y_{j}$. As
$x/\left(\ell_{j}+1\right)\leq\left(2x/\left(\ell_{j-1}+1\right)\right)^{2}$,
by iterating we get

$\frac{x}{\ell_{j}+1}\leq\left(\frac{x}{\ell_{0}+1}\right)^{2^{j}}2^{2(1+2+\dots+2^{j-1})}\leq\alpha^{-2^{j}}2^{2^{j+1}}.$
(2)

In particular, by (2) and the assumption $\alpha\geq(\log x)^{-1}$, we obtain
that, for $1\leq j\leq k$, $y_{j}$ is bounded above by a polynomial function
of $\log x$ depending on $k$.

Let $P_{0}=P$ and recursively define

$P_{j}(x)=P_{j-1}(x+y_{j})-P_{j-1}(x),$

which is a polynomial in $x$ of degree $k-j$ whose coefficients are
polynomials in $y_{1},\dots,y_{j}$. Let $z_{j}:=\prod_{i=1}^{j}y_{i}$. Then
$z_{j}$ and the coefficients of $P_{j}$ are bounded in absolute value by a
polynomial function of $\log x$ which depends on $k$ and the coefficients of
$P$. This observation brings the following simple claim into play.

Claim. Let $Q(x)=\sum_{i=0}^{k}\beta_{i}x^{i}$ and
$\tilde{Q}(x)=\sum_{i=0}^{k}\tilde{\beta}_{i}x^{i}$, where $\beta_{i}$ and
$\tilde{\beta}_{i}$ are allowed to depend on $x$. If the $\beta_{i}$ and
$\tilde{\beta}_{i}$ are at most a fixed polynomial function of $\log x$ in
absolute value and $\beta_{k}=\tilde{\beta}_{k}$ is bounded below in absolute
value by some positive constant depending only on $k$, then
$\lim_{x\to\infty}\frac{Q(x)}{\tilde{Q}(x)}=1$.

Recall that $P$ is a complete polynomial with integer coefficients in its
binomial representation $P(x)=\sum_{i=0}^{k}\alpha_{i}{x\choose i}$ and the
leading coefficient $\alpha_{k}$ is a positive integer. The coefficient of
$x^{k-j}$ in $P_{j}(x)$ is the same as that in $\alpha_{k}z_{j}{x\choose
k-j}$. To see this, note, by induction, that the coefficient of $x^{k-j}$ in
$P_{j}(x)=P_{j-1}(x+y_{j})-P_{j-1}(x)$ is the same as the coefficient of
$x^{k-j}$ in $\alpha_{k}z_{j-1}\left({x+y_{j}\choose k-j+1}-{x\choose
k-j+1}\right)$ and, hence, of $\alpha_{k}z_{j-1}y_{j}{x\choose
k-j}=\alpha_{k}z_{j}{x\choose k-j}$. It follows from the claim that the
polynomial $P_{j}(x)$ is asymptotically equal to $\alpha_{k}z_{j}{x\choose
k-j}$.

Let $c=1/(k2^{k+2})$ and $w_{k-1}=1$. For $0\leq j\leq k-2$, let
$w_{j}=2^{k-j}y_{j+1}$. We choose (not necessarily disjoint) sets
$I_{0},I_{1},\dots,I_{k-1}$ of indices such that $I_{j}\subseteq[\ell_{j}]$
and any two distinct indices in $I_{j}$ differ by at least $w_{j}$. By
partitioning $[x,2x)$ into $1/c$ intervals of length $cx$ each, we can further
guarantee that $\\{x_{0,i_{0}}:i_{0}\in I_{0}\\}$ is a subset of an interval
$[x^{\prime},x^{\prime}+cx)$ of length $cx$ that is a subinterval of $[x,2x)$.
By greedily picking the elements, we can guarantee that $|I_{0}|\geq
c\ell_{0}/w_{0}$ and $|I_{j}|\geq\ell_{j}/w_{j}$ for $j>0$.

For a $k$-tuple $t=(i_{0},\dots,i_{k-1})\in I_{0}\times\cdots\times I_{k-1}$,
let

$F(t)=\sum_{j=0}^{k-1}P_{j}(x_{j,i_{j}}).$

We claim that these numbers are distinct modulo $P(m)$. This follows from
showing that (as integers) these numbers lie in an interval of length less
than $P(m)$ and that they are ordered lexicographically. That is, if
$t=(i_{j})$ and $t^{\prime}=(i^{\prime}_{j})$ are distinct $k$-tuples, $j_{0}$
is the smallest index such that $i_{j_{0}}\neq i^{\prime}_{j_{0}}$ and
$i_{j_{0}}>i^{\prime}_{j_{0}}$, then $F(t)>F(t^{\prime})$.

We first show that the numbers $F(t)$ with $t\in I_{0}\times\cdots\times
I_{k-1}$ lie in an interval of length less than $P(m)$. As $x$ is sufficiently
large, each $P_{j}$ is positive and increasing in $[x,2x)$. It follows that

$P(x^{\prime})+\sum_{1\leq j\leq k-1}P_{j}(x)\leq F(t)\leq
P(x^{\prime}+cx)+\sum_{1\leq j\leq k-1}P_{j}(2x).$ (3)

We have that

$\displaystyle P(x^{\prime}+cx)-P(x^{\prime})$
$\displaystyle\leq\alpha_{k}\left(\binom{x^{\prime}+cx}{k}-\binom{x^{\prime}}{k}\right)+\sum_{j<k}|\alpha_{j}|(x^{\prime}+cx)^{j}$
$\displaystyle\leq\alpha_{k}\left(\binom{2x}{k}-\binom{2x-cx}{k}\right)+\sum_{j<k}|\alpha_{j}|(2x)^{j}$
$\displaystyle=(2^{k}-(2-c)^{k})P(x)+R(x),$

where $R$ is a polynomial with degree at most $k-1$ depending only on $P$.
Thus, the difference between the upper and lower bounds for $F(t)$ in (3) is,
for $x$ sufficiently large, at most

$\displaystyle P(x^{\prime}+cx)-P(x^{\prime})+\sum_{1\leq j\leq k-1}P_{j}(2x)$
$\displaystyle\leq(2^{k}-(2-c)^{k})P(x)+R(x)+\sum_{1\leq j\leq k-1}P_{j}(2x)$
$\displaystyle\leq ck2^{k-1}P(x)\leq\frac{1}{2}P(x)\leq\frac{1}{2}P(m),$

where, in the second inequality, we used that $2^{k}-(2-c)^{k}<ck2^{k-1}$, as
well as the claim and the fact that $R(x)+\sum_{1\leq j\leq k-1}P_{j}(2x)$ is
a polynomial of degree at most $k-1$ in $x$ whose coefficients are polynomials
(depending only on $P$) in $y_{1},\dots,y_{k-1}$, where $y_{1},\dots,y_{k-1}$
are themselves bounded in absolute value by a polynomial function of $\log x$.
Hence, the integers $F(t)$ all lie in an interval of length at most
$P(m)/2<P(m)$, as desired.

We next show that the integers $F(t)$ with $t\in I_{0}\times\cdots\times
I_{k-1}$ are lexicographically ordered. Indeed, suppose $t=(i_{j})$ and
$t^{\prime}=(i^{\prime}_{j})$ are distinct $k$-tuples, $j_{0}$ is the smallest
index such that $i_{j_{0}}\neq i^{\prime}_{j_{0}}$ and
$i_{j_{0}}>i^{\prime}_{j_{0}}$. Then

$F(t)-F(t^{\prime})=\sum_{j=j_{0}}^{k-1}P_{j}(x_{j,i_{j}})-P_{j}(x_{j,i^{\prime}_{j}}).$
(4)

Since $x_{j,i_{j}}-x_{j,i^{\prime}_{j}}\geq i_{j}-i^{\prime}_{j}\geq w_{j}$,
the first summand in (4), when $j=j_{0}$, is asymptotically at least
$\alpha_{k}z_{j_{0}}w_{j_{0}}{x\choose k-j_{0}-1}$. If $j_{0}=k-1$, the rest
of the sum is $0$. Otherwise, $j_{0}\leq k-2$ and, since $x\leq
x_{j,i_{j}},x^{\prime}_{j,i^{\prime}_{j}}<2x$ and $P_{j}(x)$ is increasing for
$x$ sufficiently large, the rest of the sum in (4) is at least

$\sum_{j=j_{0}+1}^{k-1}P_{j}(x)-P_{j}(2x).$

By the claim, this sum is asymptotic to its first summand (when $j=j_{0}+1$).
Therefore, this sum is asymptotically
$-\alpha_{k}z_{j_{0}+1}(2^{k-j_{0}-1}-1){x\choose k-j_{0}-1}$. As
$z_{j_{0}+1}=y_{j_{0}+1}z_{j_{0}}$, we have
$z_{j_{0}}w_{j_{0}}>2z_{j_{0}+1}(2^{k-j_{0}-1}-1)$. Hence, as $x$ is
sufficiently large, the first term in the sum in (4) is more than the absolute
value of the sum of the other terms, so we conclude that $F(t)>F(t^{\prime})$,
as desired.

As the integers $F(t)$ with $t\in I_{0}\times\cdots\times I_{k-1}$ are
distinct modulo $P(m)$, the number of distinct residue classes
$F(t)\pmod{P(m)}$ is at least

$\prod_{j=0}^{k-1}|I_{j}|\geq c\prod_{j=0}^{k-1}\ell_{j}/w_{j}\geq
c_{k}x^{k}\prod_{j=0}^{k-1}\alpha^{2^{j+1}}\geq c_{k}\alpha^{2^{k+1}}x^{k},$

where $c_{k}>0$ depends only on $k$. Here we used $y_{j}\leq 2x/\ell_{j-1}$,
$w_{j}=2^{k-j}y_{j+1}$ by the definition of $w_{j}$ and the bound (2) on
$\ell_{j}$.

Note now that $P_{0}(x_{0,i})=P(x_{i})\in P(T)$. We will show, inductively,
that for $j\geq 1$ we have $P_{j}(x_{j,i})\in 2^{j-1}P(T)-2^{j-1}P(T)$ for all
$0\leq i\leq\ell_{j}-1$. Indeed,

$P_{j}(x_{j,i})=P_{j-1}(x_{j,i}+y_{j})-P_{j-1}(x_{j,i})=P_{j-1}(x_{j-1,t_{i}+1})-P_{j-1}(x_{j-1,t_{i}})\in
2^{j-1}P(T)-2^{j-1}P(T),$

recalling that there exist indices $t_{i}$ such that $x_{j,i}=x_{j-1,t_{i}}$
and $x_{j,i}+y_{j}=x_{j-1,t_{i}+1}$. As each $F(t)$ is the sum of $k$ terms in
which the $j^{\textrm{th}}$ term is of the form $P_{j}(x_{j,i})$, we have that
each $F(t)$ is in the set
$P(T)+\sum_{j=1}^{k-1}(2^{j-1}P(T)-2^{j-1}P(T))=2^{k-1}P(T)-(2^{k-1}-1)P(T)$.
The set $2^{k-1}P(T)-2^{k-1}P(T)=-P(T)+2^{k-1}P(T)-(2^{k-1}-1)P(T)$ is the
union of $|-P(T)|$ translates of $2^{k-1}P(T)-(2^{k-1}-1)P(T)$. Hence,

$\left|2^{k-1}P(T)-2^{k-1}P(T)\right|\geq
c_{k}\alpha^{2^{k+1}}x^{k}>\alpha^{C_{k}}P(m)$

for an appropriate constant $C_{k}$ depending only on $k$, completing the
proof. ∎

Remark. A Hilbert cube of dimension $k$ (or simply a $k$-cube) is a set
$H(a_{0},e_{1},\dots,e_{k})$ of the form $\\{a_{0}+\sum_{i\in
I}e_{i}:I\subseteq[k]\\}$ with $a_{0}$ an integer and $e_{1},\ldots,e_{k}$
positive integers (see [27] for more on the long history of these objects).
The first step in the proof of Lemma 2.10 was to iteratively build many
Hilbert cubes of dimension $k$ consisting of elements of $T$, all with
$e_{j}=y_{j}$ and where we can take $a_{0}$ to be any $x_{k,i}$. An
alternative approach to this step is to build many $k$-cubes in $T$ with small
$e_{1},\dots,e_{k}$ and then to use the pigeonhole principle to show that one
can pick out many such $k$-cubes with the same $e_{1},\dots,e_{k}$.

As in the previous subsection, we will deduce Lemma 2.9 from a modular
analogue, which we now state. Recall that $\Sigma_{m}(S)$ is the set of subset
sums modulo $m$.

######  Lemma 3.2.

Let $P$ be a complete polynomial of degree $k$ with integer coefficients in
its binomial representation. Fix $c\geq k2^{k+4}$ and assume $x$ is
sufficiently large (depending on $P$). Let $w=(\log x)^{1/2}$ and let $X$ be
the set of $y\in[x,(1+1/k)x)$ such that $P(y)$ has no prime divisor at most
$w$. Let $m\in X$. If $S=(s_{1},\dots,s_{q})$ is a sequence of $q=c\log x$
elements chosen uniformly and independently at random from $X$ and the
sequence $P(S)=(P(s_{1}),\dots,P(s_{q}))$ is viewed as a sequence of elements
in $\mathbb{Z}_{P(m)}$, then $|\Sigma_{P(m)}(P(S))|<P(m)/4$ with probability
at most $\left(\log x\right)^{-(c-k2^{k+3})(\log x)/(8C_{k})}$, where $C_{k}$
is the constant defined in Lemma 2.10.

We will need the following estimate for the proof of Lemma 3.2.

######  Lemma 3.3.

For each positive integer $k$, there is $c_{k}>0$ such that the following
holds. Suppose $P$ is a complete polynomial of degree $k$ with integer
coefficients in its binomial representation. If $x$ is sufficiently large and
$1<w<(\log x)/2$ is an integer, then the set $X$ of $y\in[x,(1+1/k)x)$ such
that $P(y)$ has no prime divisor at most $w$ satisfies $|X|\geq c_{k}(\log
w)^{-k}x$.

###### Proof.

For each prime $q\leq k$, let $v_{q}$ be the largest integer $v$ such that
$q^{v}\mid k!$. For $i\leq k$, we have
$\prod_{j=0}^{i-1}(q^{2v_{q}}+(x-j))=\prod_{j=0}^{i-1}(x-j)+q^{2v_{q}}z$ for
some integer $z$, so

$\binom{x+q^{2v_{q}}}{i}-\binom{x}{i}=\frac{1}{i!}\prod_{j=0}^{i-1}(q^{2v_{q}}+(x-j))-\frac{1}{i!}\prod_{j=0}^{i-1}(x-j)=\frac{q^{2v_{q}}z}{i!}.$

Letting $v_{q,i}$ and $r_{i}$ be integers such that $i!=q^{v_{q,i}}r_{i}$ and
$\gcd(r_{i},q)=1$, we have, since $\binom{x+q^{2v_{q}}}{i}-\binom{x}{i}$ is an
integer, that $r_{i}\mid z$. Moreover, $v_{q,i}\leq v_{q}$, since $i!\mid k!$.
Hence,

$\binom{x+q^{2v_{q}}}{i}-\binom{x}{i}=\frac{q^{2v_{q}}z}{i!}=q^{v_{q}}\cdot
q^{v_{q}-v_{q,i}}\frac{z}{r_{i}}\equiv 0\pmod{q^{v_{q}}}.$

That is, $\binom{x}{i}\pmod{q^{v_{q}}}$ is periodic every $q^{2v_{q}}$ and,
therefore, $P(x)\pmod{q}$ is periodic every $q^{2v_{q}}$. Since $P$ is
complete, for each prime $q\leq k$, there exists an integer
$x\in[1,q^{2v_{q}}]$ such that $P(x)$ is coprime to $q$. Using that
$\prod_{q\leq k,\textrm{ $q$ prime}}q^{2v_{q}}=k!^{2}$, we have, by the
Chinese Remainder Theorem, that there exists an integer $y\in[1,k!^{2}]$ such
that $P(y)$ is coprime to all primes $q\leq k$. We also have that
$P(x)\pmod{q}$ is periodic every $k!^{2}$ for all primes $q\leq k$. Moreover,
for each prime $q>k\geq i$, $\binom{x}{i}\pmod{q}$ is periodic every $q$.
Therefore, letting $R_{k,w}=k!^{2}\prod_{k<q\leq w,\,q\textrm{ prime}}q$, we
have that $P(x)\pmod{\prod_{q\leq w,\,q\textrm{ prime}}q}$ is periodic every
$R_{k,w}$.

Let $W$ be the set of positive integers $y$ at most $R_{k,w}$ such that $P(y)$
is coprime to all primes at most $w$. Let $m_{P,q}$ be the number of roots of
$P(x)\pmod{q}$, which is at most $k$ for each prime $q$, where we used that
$P$ has degree $k$ and is nonzero modulo $q$ by completeness. By the Chinese
Remainder Theorem, the fraction of $y\in[\prod_{k<q\leq w,\,q\textrm{
prime}}q]$ such that $P(y)$ is coprime to $\prod_{k<q\leq w,\,q\textrm{
prime}}q$ is then

$\prod_{k<q\leq w,\,q\textrm{ prime}}\left(1-\frac{m_{P,q}}{q}\right)\geq
c^{\prime}_{k}(\log w)^{-k}$

for some constant $c^{\prime}_{k}>0$, where we used the bound
$1-\varepsilon>e^{-\varepsilon-\varepsilon^{2}}$ for $0<\varepsilon<1/2$ and
Merten’s second theorem, which implies that $\sum_{q\leq w,\,q\textrm{
prime}}1/q=\log\log w+O(1)$. Furthermore, as shown above, there exists
$y\in[k!^{2}]$ such that $P(y)$ is coprime to $\prod_{q\leq k,\,q\textrm{
prime}}q$. Since $P(y)\pmod{\prod_{q\leq k,\,q\textrm{ prime}}q}$ is periodic
every $k!^{2}$ and $\gcd(k!^{2},\prod_{k<q\leq w,\,q\textrm{ prime}}q)=1$, the
Chinese Remainder Theorem implies that the fraction of $y\in[R_{k,w}]$ such
that $P(y)$ is coprime to $R_{k,w}$ is at least $(c^{\prime}_{k}/k!^{2})(\log
w)^{-k}$. Hence, $|W|\geq(c^{\prime}_{k}/k!^{2})(\log w)^{-k}R_{k,w}$. Since
the integers $y$ for which $P(y)$ has no prime factor at most $w$ are periodic
every $R_{k,w}$ and $R_{k,w}\leq x^{1/2+o(1)}$ by the assumption $w\leq(\log
x)/2$, we have that $|X|\geq(|W|/R_{k,w})(x/k)-|W|\geq c_{k}(\log w)^{-k}x$
for an appropriate $c_{k}>0$ depending only on $k$, as required. ∎

The proof of Lemma 3.2 now proceeds along broadly similar lines to the proof
of Lemma 3.1.

###### Proof of Lemma 3.2.

Let $S_{i}=(s_{1},\ldots,s_{i})$ denote the sequence consisting of the first
$i$ terms of $S$ and let $T_{i}=(P(s_{1}),P(s_{2}),\dots,P(s_{i}))$. We also
write $T$ as a shorthand for $T_{q}=P(S)$. Call $i\in[2,q]$ bad if

  * •

$|\Sigma_{P(m)}(T_{i})|\leq(1+2^{-k-1})|\Sigma_{P(m)}(T_{i-1})|$ and
$|\Sigma_{P(m)}(T_{i-1})|<\frac{P(m)}{2w}$ or

  * •

$|\Sigma_{P(m)}(T_{i})|\leq\left(1+\frac{1}{2^{k+1}w}\right)|\Sigma_{P(m)}(T_{i-1})|$
and $\frac{P(m)}{2w}\leq|\Sigma_{P(m)}(T_{i-1})|<\frac{P(m)}{4}$.

The following claims are the key components in the proof. Here $C_{k}$ is the
constant from Lemma 2.10.

Claim 1. The probability that $i$ is bad conditioned on the choice of
$S_{i-1}$ is at most $p:=(\log x)^{-1/(4C_{k})}$.

Claim 2. If $|\Sigma_{P(m)}(T)|<P(m)/4$, then the number of integers in
$[2,q]$ which are not bad is less than $k2^{k+3}\log x$.

By Claim 1, for any $B\subset[2,q]$, the probability that all elements in $B$
are bad is at most $p^{|B|}$. By Claim 2, if $|\Sigma_{P(m)}(T)|<P(m)/4$, then
there is a set $B$ of $q-k2^{k+3}\log x=(c-k2^{k+3})\log x$ integers
$i\in[2,q]$ which are bad. Taking a union bound over all choices of $B$, the
probability that $|\Sigma_{P(m)}(T)|<P(m)/4$ is at most

$\displaystyle\binom{q}{q-k2^{k+3}\log x}p^{|B|}$
$\displaystyle=\binom{q}{k2^{k+3}\log x}p^{|B|}$
$\displaystyle\leq(ec)^{k2^{k+3}\log x}(\log x)^{-(c-k2^{k+3})(\log
x)/(4C_{k})}$ $\displaystyle<(\log x)^{-(c-k2^{k+3})(\log x)/(8C_{k})}.\qed$

Therefore, in order to complete the proof of the lemma, it suffices to prove
Claims 1 and 2. It is here, in the proof of Claim 1, that Lemma 2.10 comes
into play.

Proof of Claim 1. Fix $S_{i-1}=(s_{1},\dots,s_{i-1})$. Conditioned on this
choice of $S_{i-1}$, we bound the probability that $i$ is bad. If
$|\Sigma_{P(m)}(T_{i-1})|\geq P(m)/4$, then $i$ cannot be bad (so the
probability that $i$ is bad is zero). The proof now splits into two cases,
when $|\Sigma_{P(m)}(T_{i-1})|<\frac{P(m)}{2w}$ and when
$\frac{P(m)}{2w}\leq|\Sigma_{P(m)}(T_{i-1})|<P(m)/4$.

Case 1. $|\Sigma_{P(m)}(T_{i-1})|<\frac{P(m)}{2w}$.

Let

$V=\left\\{t\in[x,(1+1/k)x):\,|\Sigma_{P(m)}(T_{i-1}\cup\\{P(t)\\})|\leq\left(1+\frac{1}{2^{k+1}}\right)|\Sigma_{P(m)}(T_{i-1})|\right\\}.$

Observe that $i$ is bad conditioned on $S_{i-1}$ if and only if $s_{i}\in V$.
We will show that $|V|\leq\alpha x$, where $\alpha=w^{-1/C_{k}}$ and $C_{k}$
is again the constant from Lemma 2.10.

Suppose, for the sake of contradiction, that $|V|>\alpha x$. Lemma 2.10 then
implies that

$|2^{k-1}P(V)-2^{k-1}P(V)|>\alpha^{C_{k}}P(m)=P(m)/w,$

where $P(V)=\\{P(v):v\in V\\}$. Note now that if $U\subseteq\mathbb{Z}_{P(m)}$
and $u\in\mathbb{Z}_{P(m)}$, then
$|\Sigma_{P(m)}(U\cup\\{u\\})|=|\Sigma_{P(m)}(U\cup\\{-u\\})|$. Thus, for each
$z\in P(V)\cup(-P(V))$, we have

$|\Sigma_{P(m)}(T_{i-1}\cup\\{z\\})|\leq\left(1+\frac{1}{2^{k+1}}\right)|\Sigma_{P(m)}(T_{i-1})|$

and Lemma 2.7 implies that, for each $y\in 2^{k-1}P(V)-2^{k-1}P(V)$,

$|\Sigma_{P(m)}(T_{i-1}\cup\\{y\\})|\leq\left(1+\frac{2^{k}}{2^{k+1}}\right)|\Sigma_{P(m)}(T_{i-1})|=\frac{3}{2}|\Sigma_{P(m)}(T_{i-1})|.$
(5)

However, by Lemma 2.6, the number of $y\in\mathbb{Z}_{P(m)}$ satisfying (5) is
at most $2|\Sigma_{P(m)}(T_{i-1})|<P(m)/w$. But this contradicts the bound
$|2^{k-1}P(V)-2^{k-1}P(V)|>P(m)/w$, so we must indeed have that $|V|\leq\alpha
x$.

Case 2. $P(m)/2w\leq|\Sigma_{P(m)}(T_{i-1})|<P(m)/4$.

Let

$V=\left\\{t\in[x,(1+1/k)x):|\Sigma_{P(m)}(T_{i-1}\cup\\{P(t)\\})|\leq\left(1+\frac{1}{2^{k+1}w}\right)|\Sigma_{P(m)}(T_{i-1})|\right\\}.$

Observe again that $i$ is bad conditioned on $S_{i-1}$ if and only if
$s_{i}\in V$. As in Case 1, we will show that $|V|\leq\alpha x$. Indeed,
suppose, for the sake of contradiction, that $|V|>\alpha x$. Then, by Lemma
2.10, we again have that $|2^{k-1}P(V)-2^{k-1}P(V)|>P(m)/w$. By our assumption
that $P(m)$ has no prime divisor at most $w$, $2^{k-1}P(V)-2^{k-1}P(V)$ cannot
be contained in a coset of a proper subgroup of $\mathbb{Z}_{P(m)}$. Hence, by
Lemma 2.3,

$|2^{k-1}wP(V)-2^{k-1}wP(V)|>P(m)/2.$

However, again using Lemma 2.7, for all elements $y\in
2^{k-1}wP(V)-2^{k-1}wP(V)$, we have

$|\Sigma_{P(m)}(T_{i-1}\cup\\{y\\})|\leq\left(1+\frac{2^{k}w}{2^{k+1}w}\right)|\Sigma_{P(m)}(T_{i-1})|=\frac{3}{2}|\Sigma_{P(m)}(T_{i-1})|.$

But, by Lemma 2.6, the number of such elements is at most
$2|\Sigma_{P(m)}(T_{i-1})|<P(m)/2$, a contradiction.

Therefore, in either case, the set $V$ of bad choices satisfies $|V|\leq\alpha
x$. By using Lemma 3.3, which says that $|X|\geq c_{k}(\log w)^{-k}x$ for an
appropriate $c_{k}>0$, this implies that the probability $i$ is bad
conditioned on the choice of $S_{i-1}$ is at most

$|V|/|X|\leq\alpha x/\left(c_{k}(\log w)^{-k}x\right)=\alpha c_{k}^{-1}(\log
w)^{k}=c_{k}^{-1}(\log x)^{-1/(2C_{k})}\left(\frac{1}{2}\log\log
x\right)^{k}<(\log x)^{-1/(4C_{k})}=p,$

as required. ∎

Proof of Claim 2. As $S_{i-1}\subset S_{i}$ for $i\in[2,q]$,
$\Sigma_{P(m)}(T_{i-1})\subseteq\Sigma_{P(m)}(T_{i})$ and, hence,
$1\leq|\Sigma_{P(m)}(T_{1})|\leq\cdots\leq|\Sigma_{P(m)}(T_{q})|=|\Sigma_{P(m)}(T)|<P(m)/4$.
Therefore, the number of $i$ which are not bad with
$|\Sigma_{P(m)}(T_{i-1})|<P(m)/2w$ and
$|\Sigma_{P(m)}(T_{i})|\geq(1+2^{-k-1})|\Sigma_{P(m)}(T_{i-1})|$ is at most
$\frac{\log(P(2x)/2w)}{\log(1+2^{-k-1})}\leq k2^{k+2}\log x$. Moreover, the
number of $i$ which are not bad with
$P(m)/2w\leq|\Sigma_{P(m)}(T_{i-1})|<P(m)/4$ and
$|\Sigma_{P(m)}(T_{i})|\geq\left(1+\frac{1}{2^{k+1}w}\right)|\Sigma_{P(m)}(T_{i-1})|$
is at most $\frac{\log(2w)}{\log(1+2^{-k-1}w^{-1})}\leq\log x$, where we used
that $w=(\log x)^{1/2}$. Therefore, the number of $i\in[2,q]$ which are not
bad is at most $k2^{k+2}\log x+\log x<k2^{k+3}\log x$. ∎

We conclude this subsection and the proof of Theorem 1.2 by using Lemma 3.2 to
prove Lemma 2.9. To this end, suppose that $P$ is a complete polynomial of
degree $k$ with integer coefficients in its binomial representation,
$C(k)=k2^{k+15}$, $\epsilon\in(0,1/2]$ and $X$ is the set of
$y\in[x,(1+1/k)x)$ such that $P(y)$ has no prime divisor at most $(\log
x)^{1/2}$. Our aim is to show that if a sequence $S$ of $C(k)\epsilon^{-1}\log
x$ elements in $X$ is chosen independently and uniformly at random, then, with
high probability, $S$ has distinct terms and, for any subsequence $S^{\prime}$
of $S$ of size $\epsilon|S|$, the set $\Sigma(P(S^{\prime}))$ contains all
integers in the interval
$[\frac{e}{9}P(x)|S^{\prime}|,\frac{8}{9}P(x)|S^{\prime}|]$.

###### Proof of Lemma 2.9.

As $P$ is a complete polynomial, its leading coefficient is positive. Hence,
for $x$ sufficiently large, $P$ will be positive and strictly increasing on
the interval $[x,(1+1/k)x]$. We may therefore assume that $P$ is injective on
the interval $[x,(1+1/k)x)$ and, for any $y$ in this interval,
$P(y)\in[P(x),P((1+1/k)x))\subset[P(x),eP(x))$.

By the birthday paradox, as $|S|=o(\sqrt{|X|})$, $P(S)$ has distinct terms
with high probability. Fix a choice of subset $I^{\prime}$ of
$[C(k)\epsilon^{-1}\log x]$ of size $C(k)\log x$ and consider the subsequence
$S^{\prime}$ of $S$ given by $(s_{i})_{i\in I^{\prime}}$. Let
$I^{\prime\prime}$ be the smallest $|S^{\prime}|/9$ elements in $I^{\prime}$
and let $S^{\prime\prime}$ be given by $(s_{i})_{i\in I^{\prime\prime}}$. Let
$\ell=64$. Arrange $I^{\prime\prime}$ in increasing order and partition
$I^{\prime\prime}$ into $\ell$ sets
$I^{\prime\prime}_{1},\dots,I^{\prime\prime}_{\ell}$ of consecutive terms so
that each set $I^{\prime\prime}_{j}$ for $j\in[\ell]$ has size
$|I^{\prime\prime}|/\ell$. This gives a partition of $S^{\prime\prime}$ into
$\ell$ subsequences $S^{\prime\prime}_{1},\dots,S^{\prime\prime}_{\ell}$,
where $S^{\prime\prime}_{j}=(s_{i})_{i\in I^{\prime\prime}_{j}}$. Note that
each element of $\Sigma(P(S^{\prime\prime}_{j}))$ is nonnegative and at most
$P((1+1/k)x)|S^{\prime\prime}_{j}|<eP(x)|S^{\prime\prime}_{j}|$. We shall
prove below that, with high probability, the sequence $S$ has the property
that, for all possible choices of $I^{\prime}$ and $j$,
$|\Sigma(P(S^{\prime\prime}_{j}))|\geq P(x)|S^{\prime\prime}_{j}|/8$. Assuming
this, we can show that $\Sigma(P(S_{j}^{\prime\prime}))$ is not contained in
an arithmetic progression with common difference larger than $1$. Indeed, if
$\Sigma(P(S_{j}^{\prime\prime}))$ is contained in an arithmetic progression
with common difference $d>1$, then
$d\leq\frac{P((1+1/k)x)|S^{\prime\prime}_{j}|}{P(x)|S^{\prime\prime}_{j}|/8-1}\leq
9e$. Moreover, if $\Sigma(P(S_{j}^{\prime\prime}))$ is contained in an
arithmetic progression with common difference $d>1$, then all elements in
$\Sigma(P(S_{j}^{\prime\prime}))$ are congruent modulo $d$, from which it
follows that all elements of $P(S_{j}^{\prime\prime})$ are divisible by $d$.
This contradicts the fact that no element of $P(S_{j}^{\prime\prime})$ has a
prime factor at most $(\log x)^{1/2}$. Hence, for each $j$,
$\Sigma(P(S_{j}^{\prime\prime}))$ is not contained in an arithmetic
progression with common difference larger than $1$. Therefore, by Lemma 2.2,
as
$\Sigma(S^{\prime\prime})=\Sigma(S^{\prime\prime}_{1})+\cdots+\Sigma(S^{\prime\prime}_{\ell})$,
the set $\Sigma(S^{\prime\prime})$ contains the integers in an interval of
length at least
$\ell\left(P(x)|S^{\prime\prime}_{j}|/8-1\right)+1>P((1+1/k)x)$. Finally, by
Lemma 2.1, $\Sigma(P(S^{\prime\prime})\cup P(S^{\prime}\setminus
S^{\prime\prime}))$ contains all integers in the interval
$[eP(x)|S^{\prime}|/9,8P(x)|S^{\prime}|/9]$, where we used that all elements
of $S^{\prime}$ are at most $P((1+1/k)x)$, the elements of
$\Sigma(S^{\prime\prime})$ are at most
$P((1+1/k)x)|S^{\prime\prime}|=P((1+1/k)x)|S^{\prime}|/9<eP(x)|S^{\prime}|/9$
and the sum of the elements in $S^{\prime}$ is at least
$P(x)|S^{\prime}\setminus S^{\prime\prime}|=8P(x)|S^{\prime}|/9$.

It remains to show that, with high probability, the sequence $S$ has the
property that, for all possible choices of $I^{\prime}$ and $j$,
$|\Sigma(P(S^{\prime\prime}_{j}))|\geq P(x)|S^{\prime\prime}_{j}|/8$. Fix an
index $1\leq j\leq\ell$ and partition the index set $I^{\prime\prime}_{j}$ of
$S^{\prime\prime}_{j}$ into two consecutive blocks $J_{1}$ and $J_{2}$ of
equal size. Let $Q_{1}=(s_{i})_{i\in J_{1}}$ and $Q_{2}=(s_{i})_{i\in J_{2}}$,
so $|Q_{1}|=|Q_{2}|=\frac{|S_{j}^{\prime\prime}|}{2}=\frac{C(k)\log
x}{18\ell}>k2^{k+4}\log x$. Recall that $X$ is the set of integers in
$[x,(1+1/k)x)$ such that $P(x)$ has no prime divisor at most $(\log x)^{1/2}$.
Consider $m\in X$. We note that when we fix the subset of indices $I^{\prime}$
of $[C(k)\epsilon^{-1}\log x]$ of size $C(k)\log x$ and the index $j$, then
$J_{1}$ is determined as a particular subsequence of $I^{\prime}$. Moreover,
each element in $Q_{1}$ is uniformly and independently distributed in $X$.
Taking a union bound over all $x\ell\binom{C(k)\epsilon^{-1}\log x}{C(k)\log
x}$ choices of $I^{\prime}$, $j\in[\ell]$ and $m\in X$, Lemma 3.2 implies that
the probability $|\Sigma_{P(m)}(P(Q_{1}))|<\frac{P(m)}{4}$ for some choice of
$I^{\prime}$, $j\in[\ell]$ and $m\in X$ is at most

$\displaystyle x\ell\binom{C(k)\epsilon^{-1}\log x}{C(k)\log x}\cdot\left(\log
x\right)^{-k2^{k}C_{k}^{-1}\log x}$ $\displaystyle\leq
x\ell(e/\epsilon)^{C(k)\log x}\cdot\left(\log x\right)^{-k2^{k}C_{k}^{-1}\log
x}=o_{x}(1),$

where $o_{x}(1)$ tends to $0$ as $x$ tends to infinity. Thus, with high
probability, the sequence $S$ is such that
$|\Sigma_{P(m)}(P(Q_{1}))|\geq\frac{P(m)}{4}$ for all possible choices of
$I^{\prime}$, $j\in[\ell]$ and $m\in X$. In this case, by repeated application
of Lemma 2.5, for all $j\in[\ell]$,

$|\Sigma(P(S_{j}^{\prime\prime}))|\geq\sum_{m\in
Q_{2}}P(m)/4=|Q_{2}|P(m)/4=|S^{\prime\prime}_{j}|P(m)/8\geq
P(x)|S^{\prime\prime}_{j}|/8.$

Therefore, with high probability, the sequence $S$ is such that
$|\Sigma(P(S^{\prime\prime}_{j}))|\geq P(x)|S^{\prime\prime}_{j}|/8$ for all
possible choices of $I^{\prime}$ and $j$, as required. ∎

###  3.3 Proof of the lower bound in Theorem 1.1

We first prove a useful lemma.

######  Lemma 3.4.

Let $S$ be a sequence of positive integers and $m$ and $q$ be positive
integers. Then

$\left|\Sigma(S)\cap[m]\right|\leq 2^{m/q}\prod_{a\in
S\cap[m]}\left(1+2^{-a/q}\right)\leq 2^{m/q}\exp\left(\sum_{a\in
S\cap[m]}2^{-a/q}\right).$

###### Proof.

Let $r_{S}(s)$ denote the number of ways of representing $s$ as a sum of
distinct elements from $S$. So if $s\in\Sigma(S)$, then $r_{S}(s)\geq 1$,
while $r_{S}(s)=0$ otherwise. For each $s\in\Sigma(S)\cap[m]$, we get a
contribution of one to the leftmost expression. For the middle expression, by
expanding the product, for each $s\in\Sigma(S)\cap[m]$ we get a contribution
of $r_{S}(s)\cdot 2^{m/q}\cdot 2^{-s/q}\geq 1$, proving the desired
inequality. We then get the last inequality by using $1+z\leq e^{z}$ for
$z\geq 0$. ∎

Using the above lemma, we prove the following theorem, giving the lower bound
in Theorem 1.1.

######  Theorem 3.5.

Let $r\geq 2$ be an integer. If a sequence of positive integers $A$ satisfies
$A(n)\leq\frac{r-1}{140}(\log_{2}n)^{2}$ for all sufficently large $n$, then
$A$ is not $r$-Ramsey complete.

###### Proof.

By replacing $r$ by $r-1$ if $r$ is odd, it suffices to prove that, for $r\geq
2$ even, a sequence of positive integers $A$ with
$A(n)\leq\frac{r}{70}(\log_{2}n)^{2}$ for all sufficiently large $n$ is not
$r$-Ramsey complete.

By reordering, we may suppose that $A=(a_{i})_{i=1}^{\infty}$ is in increasing
order $a_{1}\leq a_{2}\leq\cdots$. Define an $r/2$-coloring of $A$, which we
call the hue coloring, by assigning $a_{\ell}$ hue $h\in\mathbb{Z}_{r/2}$ if
$\ell\equiv h\pmod{r/2}$. For a positive integer $j$, define a red/blue-
coloring $C_{j}$ of $A$ where $C_{j}(a)$ is red if $a\leq 2^{j}$ and blue
otherwise. Let $c_{j}$ be the product coloring formed from the hue coloring
and the red/blue-coloring $C_{j}$. That is, $c_{j}$ is an $r$-coloring of $A$
given by the hue and whether or not the term is at most $2^{j}$.

The largest positive integer that can be written as a sum of red elements of
the same hue in coloring $c_{j}$ is at most

$2^{j}+\frac{2}{r}\sum_{a\in A\cap[2^{j}]}a.$ (6)

This follows since, for any two hues $h$ and $h^{\prime}$, the elements of
$A\cap[2^{j}]$ with hue $h$ and those with hue $h^{\prime}$ interlace and are
bounded by $2^{j}$, so the sum of elements of hue $h$ is at most $2^{j}$ more
than the sum of elements of hue $h^{\prime}$ and, therefore, at most $2^{j}$
more than the average sum of elements taken over all hues.

Let the _cost_ of $a\in A\cap[2^{j}]$ for the coloring $c_{j}$ be $a/2^{j}j$.
Over all colorings $c_{j}$ with $j\geq 1$, the total cost of $a>2$ is
$\sum_{j\geq\log_{2}a}a/2^{j}j\leq 2/\log_{2}a$, while the cost of each
$a\in\\{1,2\\}$ over all such $c_{j}$ is at most $2$. If any number larger
than $2^{j-1}(j+2)$ can be written as a sum of monochromatic red elements in
coloring $c_{j}$ (so they are also of the same hue), then, by (6), we have

$2^{j}+\frac{2}{r}\sum_{a\in A\cap[2^{j}]}a>2^{j-1}(j+2),$

or, equivalently, $\sum_{a\in A\cap[2^{j}]}a>r2^{j-2}j$, so the total cost of
all elements in $A\cap[2^{j}]$ for the coloring $c_{j}$ is at least $r/4$.

Let $i$ be a sufficiently large positive integer. The total cost of the
elements $a\in A\cap[2^{i}]$ for the colorings $c_{1},\ldots,c_{i}$ is at most

$O(1)+\sum_{a\in A\cap(2,2^{i}]}\frac{2}{\log_{2}a}<\frac{ri}{32},$ (7)

where the $O(1)$ term comes from considering the cost of the terms
$a\in\\{1,2\\}$. To prove inequality (7), we use Abel’s summation formula

$\sum_{x_{0}<n\leq
x}t_{n}f(n)=T(x)f(x)-T(x_{0})f(x_{0})-\int_{x_{0}}^{x}T(y)f^{\prime}(y)dy,$

where $f$ is a continuously differentiable function on $[x_{0},x]$ and
$T(y)=\sum_{n\leq y}t_{n}$. Using Abel’s summation formula with $t_{n}=1$ if
$n\in A\cap(2^{i_{0}},2^{i}]$ and $t_{n}=0$ otherwise, where $i_{0}$ is chosen
so that $A(n)\leq\frac{r}{140}(\log_{2}n)^{2}$ for all $n\geq 2^{i_{0}}$, and
$f(x)=\frac{1}{\log_{2}x}$, we obtain

$\displaystyle\sum_{a\in A\cap(2,2^{i}]}\frac{1}{\log_{2}a}$
$\displaystyle=O(1)+\frac{A(2^{i})}{i}-\frac{A(2^{i_{0}})}{i_{0}}+\int_{2^{i_{0}}}^{2^{i}}\frac{A(x)\log
2}{x(\log x)^{2}}dx$ $\displaystyle\leq
O(1)+\frac{ri^{2}}{140i}+\int_{2^{i_{0}}}^{2^{i}}\frac{r(\log_{2}x)^{2}\log
2}{140x(\log x)^{2}}dx$ $\displaystyle\leq
O(1)+\frac{2ri}{140}<\frac{ri}{65},$

where we assume in the last inequality that $i$ is sufficiently large.

Thus, fewer than $(ri/32)/(r/4)=i/8$ of the $i$ colorings $c_{j}$ with $1\leq
j\leq i$ have the property that there is a number greater than $2^{j-1}(j+2)$
that can be expressed as a sum of elements which are red of the same hue. We
call $j$ red-strong if there is a number greater than $2^{j-1}(j+2)$ that can
be expressed as a sum of elements which are red of the same hue in the
coloring $c_{j}$.

For a non-negative integer $j$, define

$g(j)=\sum_{a\in A,2^{j}<a\leq 2^{j}j}2^{-a/2^{j+4}}.$

For each $a\in A$, the contribution of $a$ to the various $g(j)$ is

$\sum_{j:2^{j}<a\leq 2^{j}j}2^{-a/2^{j+4}}\leq\sum_{h\geq 0}2^{-2^{h-4}}<5,$

where we used the change of variables $h=\lfloor\log_{2}a\rfloor-j$. Hence,

$\sum_{j=1}^{i}g(j)<\sum_{a\in A\cap[2^{i}i]}5=5A(i2^{i}).$

For $s\in\mathbb{Z}_{r/2}$, let $A_{s}$ be the subset of $A$ consisting of
elements of hue $s$. Let $A_{s,>t}=\\{a\in A_{s}:a>t\\}$. Let $b(j)$ denote
the number of elements of $[2^{j}j]$ which can be written as a sum of blue
elements in coloring $c_{j}$ of the same hue, so
$b(j)=|\bigcup_{s=1}^{r/2}\Sigma(A_{s,>2^{j}})\cap[2^{j}j]|\leq\sum_{s=1}^{r/2}|\Sigma(A_{s,>2^{j}})\cap[2^{j}j]|$.
Applying Lemma 3.4 with $S=A_{s,>2^{j}}$, $m=2^{j}j$ and $q=2^{j+4}$, we have

$\left|\Sigma(A_{s,>2^{j}})\cap[2^{j}j]\right|\leq
2^{j/16}\exp\left(\sum_{a\in
A_{s,>2^{j}}\cap[2^{j}j]}2^{-a/2^{j+4}}\right)\leq
2^{j/16}\exp\left(1+\frac{2}{r}g(j)\right),$

where we have again used the fact that, for any two hues $h$ and $h^{\prime}$,
the blue elements with hue $h$ interlace the blue elements of hue $h^{\prime}$
together with the observation that the function $x\mapsto 2^{-2^{x-4}}$ is
monotone and bounded above by $1$. We thus have
$b(j)\leq\frac{r}{2}2^{j/16}\exp\left(1+\frac{2}{r}g(j)\right)$. Hence, for
$i$ sufficiently large,

$\prod_{j=1}^{i}b(j)\leq\prod_{j=1}^{i}\frac{r}{2}2^{j/16}\textrm{exp}\left(1+\frac{2}{r}g(j)\right)\leq
r^{i}2^{i^{2}/31}\exp\left(\frac{2}{r}\sum_{j=1}^{i}g(j)\right)\leq
r^{i}2^{i^{2}/31}\exp\left(\frac{10}{r}A(i2^{i})\right)<2^{i^{2}/4}.$ (8)

If at least $3i/4$ of the $i$ colorings $c_{j}$ for $j=1,\ldots,i$ have the
property that at least $2^{j}$ positive integers at most $2^{j}j$ can be
written as a sum of blue elements of the same hue, then the left hand side of
(8) is at least $\prod_{j=1}^{3i/4}2^{j}=2^{\binom{3i/4+1}{2}}>2^{i^{2}/4}$,
contradicting (8). Hence, for at least $i/4$ of the colorings $c_{j}$ with
$j=1,\ldots,i$, we have that there are at most $2^{j}$ positive integers at
most $2^{j}j$ which can be written as a sum of blue elements of the same hue
in $A$. Call $j$ blue-strong if in coloring $c_{j}$ at least $2^{j}$ positive
integers at most $2^{j}j$ can be written as a sum of blue elements of the same
hue in $A$. Call $j$ weak if it is neither blue-strong nor red-strong. Hence,
for $i$ sufficiently large, there are at least $i-i/8-3i/4=i/8$ elements
$j\in[i]$ which are weak. Thus, there are infinitely many weak $j$ and we let
$J=\\{j_{h}\\}_{h\geq 1}$ be an infinite sequence of weak $j$ so that
$j_{h}\geq 2^{rj_{h-1}^{2}}$.

We next define an $r$-coloring $c$ of $A$ for which there are infinitely many
integers which cannot be written as a sum of monochromatic elements from $A$.
The coloring $c$ is a product coloring of the hue coloring (which uses $r/2$
colors) and a red/blue-coloring of $A$. We color an integer in $A$ blue if it
is in one of the intervals $(2^{j},2^{j}j]$ with $j\in J$ and red otherwise.
We will prove that at least half the elements in $(2^{j-1}(j+2),2^{j}j]$,
where $j\in J$ is sufficiently large, cannot be written as a monochromatic sum
in the coloring $c$.

Suppose now that $N\in(2^{j-1}(j+2),2^{j}j]$ is a sum of red elements of the
same hue. Since there are no red elements in $(2^{j},2^{j}j]$ in the coloring
$c$, $N$ can also be written as a sum of red elements of the same hue in
$c_{j}$, contradicting the assumption that $j$ is weak. Hence, no element in
$(2^{j-1}(j+2),2^{j}j]$ is a sum of red elements of the same hue in the
coloring $c$.

As $j=j_{h}$ is weak, there are at most $2^{j}$ elements at most $2^{j}j$ that
can be written as a monochromatic sum of blue elements of the same hue in
$(2^{j},2^{j}j]$. The number of remaining blue elements in $[2^{j}j]$ is at
most

$A(2^{j_{h-1}}j_{h-1})\leq\frac{r}{140}(\log_{2}(2^{j_{h-1}}j_{h-1}))^{2}\leq\frac{rj_{h-1}^{2}}{2}\leq\frac{\log_{2}j}{2}.$

Thus, the number of positive integers at most $2^{j}j$ which can be written as
a monochromatic sum of blue elements in the coloring $c$ is at most
$2^{(\log_{2}j)/2}2^{j}<2^{j}j/8$. Hence, as
$2^{j}j/8\leq\frac{1}{2}\left(2^{j}j-2^{j-1}(j+2)\right)$, at least half the
elements in $(2^{j-1}(j+2),2^{j}j]$ cannot be written as a sum of blue
elements of the same hue in the coloring $c$. As there are infinitely many
such $j$, there are infinitely many positive integers which are not the
monochromatic sum of elements in the coloring $c$. This completes the proof. ∎

Remark. In the proof above, for $j=1,\ldots,i$, we made use of colorings
$C_{j}$ which color the positive integers up to $2^{j}$ red and all larger
integers blue. Alternatively, we could have picked a random coloring
$\phi_{x}$ which colors all positive integers up to $x$ red and all larger
integers blue, where $x\in[N]$ is chosen with probability $\frac{1}{xH(N)}$
with $H(N)=\sum_{x=1}^{N}\frac{1}{x}$. One can then do a similar analysis
using elementary probability to get a better constant factor in Theorem 3.5.

##  4 Density completeness

In this section, we discuss Theorems 1.3 and 1.4, our results on density
completeness. Since reordering a sequence does not change whether or not it is
$\epsilon$-complete, it will suffice to consider monotonically increasing
sequences. We will begin with the following simple result, from which the
first part of Theorem 1.3 follows.

######  Theorem 4.1.

Let $\epsilon>0$. If $A=(a_{n})_{n\geq 1}$ is a monotonically increasing
sequence of positive integers which is $\epsilon$-complete, then there is $C$
such that

$a_{n}\leq\sum_{i\leq\epsilon n+C}a_{i}$

holds for all positive integers $n$.

###### Proof.

Suppose that there is no such $C$. Then there is a function
$g:\mathbb{N}\rightarrow\mathbb{N}$ with $\lim_{n\to\infty}g(n)=\infty$ such
that $a_{n}>\sum_{i\leq\epsilon n+g(n)}a_{i}$ holds for infinitely many $n$.
Thus, we can pick an infinite sequence of positive integers
$n_{1},n_{2},\dots$ such that, for all $j$, we have
$a_{n_{j}}>\sum_{i\leq\epsilon n_{j}+g(n_{j})}a_{i}$ and $g(n_{j})>n_{j-1}$.
Pick a subsequence $A^{\prime}$ of $A$ by deleting all elements $a_{i}$ of $A$
whose subscript $i$ satisfies $\epsilon n_{j}+g(n_{j})<i\leq n_{j}$ for some
positive integer $j$.

We first show that $A^{\prime}(x)\geq\epsilon A(x)$ holds for all $x$. It
suffices to check this when $x=a_{n_{j}}$ for some positive integer $j$.
However, we have $A^{\prime}(a_{n_{j}})\geq\epsilon
n_{j}+g(n_{j})-n_{j-1}>\epsilon n_{j}=\epsilon A(a_{n_{j}})$, as required.

To see that $A^{\prime}$ is not complete, we show that each integer
$a_{n_{j}}$ is not the sum of elements from $A^{\prime}$. Indeed, such
elements must be at most $a_{n_{j}}$ and hence at most $a_{\epsilon
n_{j}+g(n_{j})}$. However, $\sum_{i\leq\epsilon
n_{j}+g(n_{j})}a_{i}<a_{n_{j}}$, so $a_{n_{j}}$ is not in $\Sigma(A^{\prime})$
and $A^{\prime}$ is not complete. ∎

This gives a necessary growth condition for a sequence to be
$\epsilon$-complete. Recall that it is also necessary for an
$\epsilon$-complete sequence to satisfy the divisibility condition that no
prime is a factor of more than an $\epsilon$-proportion of the elements in the
sequence. In the proof of Theorem 4.3 below, we show that, apart from some
mild additional assumptions, a random sequence satisfying both the growth
condition from Theorem 4.1 and a suitable variant of this divisibility
condition is likely to be $\epsilon$-complete.

Recall that, for a sequence $B=(b_{n})_{n\geq 1}$, the discrete derivative is
defined by $\Delta b_{n}:=b_{n+1}-b_{n}$. Fix $0<\epsilon<1$. A sequence
$B=(b_{n})_{n\geq 1}$ is called _$\epsilon$ -friendly_ (or _friendly_) if it
satisfies the following five growth conditions:

  1. 1.

For some constant $C$ and all $n$,

$b_{n}\leq\sum_{i\leq\epsilon n+C}b_{i}.$

  2. 2.

$\lim_{n\to\infty}\Delta b_{n}=\infty$.

  3. 3.

$\lim_{i\to\infty}\frac{B(2^{i+1})-B(2^{i})}{i}=\infty$.

  4. 4.

There exists $0<c<1$ such that $c\Delta b_{i}\leq\Delta b_{j}$ for all $i<j$.
Moreover, if $b_{j}<2b_{i}$, then $\Delta b_{j}\leq\frac{1}{c}\Delta b_{i}$.

  5. 5.

$B$ is strictly increasing.

By Theorem 4.1, condition (i) is necessary for an increasing sequence of
positive integers to be $\epsilon$-complete. The other growth conditions are
mild assumptions that will be helpful in proving the existence of an
$\epsilon$-complete sequence $A=(a_{n})_{n\geq 1}$ which interlaces $B$, that
is, for which $b_{n}\leq a_{n}\leq b_{n+1}$ for all $n$.

Let $b_{1},b_{2},\ldots,b_{t}$ be any finite strictly increasing sequence of
positive integers. Let $\\{x\\}=x-\lfloor x\rfloor$ denote the fractional part
of $x$. If we define $B=(b_{n})_{n\geq 1}$ recursively by

$b_{n}=\lfloor\\{\epsilon n\\}b_{\lceil\epsilon
n\rceil}\rfloor+\sum_{i\leq\epsilon n}b_{i}$

for $n>t$, then it is easy to check that such a sequence is friendly and
satisfies $b_{n}=\Theta(f_{n})$, where, following the introduction,
$F=(f_{n})_{n\geq 1}$ is any sequence of positive integers for which
$f_{n}=\sum_{i\leq\epsilon n}f_{i}$ for all sufficiently large $n$. We note
that the term $\lfloor\\{\epsilon n\\}b_{\lceil\epsilon n\rceil}\rfloor$ is
added as a “discrete interpolation” factor to guarantee conditions (ii) and
(iv) of friendly sequences.

######  Claim 4.2.

If $B=(b_{n})_{n\geq 1}$ is a friendly sequence and $n$ is a sufficiently
large positive integer, then $b_{2n/c+1}\geq 2b_{n+1}$, where $c$ is the
constant in condition (iv) of friendly sequences.

###### Proof.

We have

$b_{n+1}=b_{1}+\sum_{i=1}^{n}\Delta b_{i}\leq b_{1}+n\max_{i\leq n}\Delta
b_{i}$ (9)

and

$\displaystyle b_{2n/c+1}$ $\displaystyle=$ $\displaystyle
b_{n+1}+\sum_{i=n+1}^{2n/c}\Delta b_{i}$ $\displaystyle\geq$ $\displaystyle
b_{n+1}+(2n/c-n)\min_{j\geq n}\Delta b_{j}$ $\displaystyle\geq$ $\displaystyle
b_{n+1}+(n/c)\cdot c\max_{i\leq n}\Delta b_{i}+(n/c-n)\min_{j\geq n}\Delta
b_{j}$ $\displaystyle\geq$ $\displaystyle b_{n+1}+(n/c)\cdot c\max_{i\leq
n}\Delta b_{i}+b_{1}$ $\displaystyle\geq$ $\displaystyle 2b_{n+1}.$

Here we used condition (iv) of friendly sequences to deduce the second
inequality, the third inequality follows from $(n/c-n)\min_{j\geq n}\Delta
b_{j}>b_{1}$ for $n$ sufficiently large and the last inequality is by (9). ∎

The next theorem is our main result on $\epsilon$-complete sequences and
completes the proof of Theorem 1.3. We remark that since condition (i) of
friendly sequences only gives an upper bound on $b_{n}$, this result also
allows us to find sequences that are considerably denser than $(f_{n})_{n\geq
1}$ that are $\epsilon$-complete.

######  Theorem 4.3.

Let $0<\epsilon<1$ and $B=(b_{n})_{n\geq 1}$ be a friendly sequence as defined
above. Then there is a sequence $A=(a_{n})_{n\geq 1}$ of positive integers
that interlaces $B$, i.e., $b_{n}\leq a_{n}<b_{n+1}$ for all $n$, which is
$\epsilon$-complete.

###### Proof.

Let $\epsilon_{0}>0$ be sufficiently small. We pick the sequence $A$ by
taking, for $j$ sufficiently large, $a_{j}$ to be a uniform random integer in
$[b_{j},b_{j+1})$ which has no prime factor at most
$(\max(1/\epsilon,1/\epsilon_{0}))^{4000}$. For small $j$ this might not be
possible, as the interval $[b_{j},b_{j+1})$ might not contain any integer with
no prime factor at most $(\max(1/\epsilon,1/\epsilon_{0}))^{4000}$, so we let
$a_{j}$ be any integer in $[b_{j},b_{j+1})$ in this case. This guarantees that
$A$ interlaces $B$.

For a positive integer $i$, let $h(i)$ be the smallest integer for which
$b_{h(i)}\geq 2^{i}$. Note that $b_{h(i+1)-1}$ is the largest element of $B$
which is less than $2^{i+1}$. Let $A_{i}:=A\cap[b_{h(i)},b_{h(i+1)-1})$, so
$A_{i}$ consists of all but at most two elements of $A\cap[2^{i},2^{i+1})$. By
condition (iii) of friendly sequences, for any $C$ and for $i$ sufficiently
large depending on $C$, $|A_{i}|\geq C\max(1/\epsilon,1/\epsilon_{0})i$. The
following lemma is a close relative of Lemma 2.8. The proof of the lemma,
which is an appropriate modification of the proof of Lemma 2.8, is deferred to
Appendix A.2.

######  Lemma 4.4.

There exist positive constants $\epsilon_{0}$, $C_{1}$ and $C_{2}$ such that
the following holds. For $i$ sufficiently large, with positive probability,
the set $A_{i}$ has the property that, for any subset $A^{\prime}_{i}\subset
A_{i}$ with $|A^{\prime}_{i}|\geq(\min(\epsilon,\epsilon_{0})/4)|A_{i}|$,
$A^{\prime}_{i}$ contains a subset $A^{\prime\prime}_{i}$ with
$|A^{\prime\prime}_{i}|\leq C_{1}i$ such that $\Sigma(A^{\prime\prime}_{i})$
contains every integer in the interval $[y,2y]$, where $y=C_{2}2^{i}i$.

Since the choices of $A_{i}$ for different $i$ are mutually independent, we
can guarantee and will assume that $A_{i}$ satisfies the conclusion of Lemma
4.4 for _each_ sufficiently large $i$.

Our goal now is to show that if $A^{\prime}$ is any subsequence of $A$ with
$|A^{\prime}(n)|\geq\epsilon|A(n)|$ for all sufficiently large $n$, then
$A^{\prime}$ is complete. We first show that for each $n_{0}$ there is $n\geq
n_{0}$ such that $A^{\prime}$ is complete or $A^{\prime}$ contains only
roughly $\epsilon n$ elements among the first $n$ elements of $A$. We then go
through a very similar argument using this additional structure to conclude
that $A^{\prime}$ is complete.

Let $i_{0}$ be a sufficiently large positive integer and $m=A(2^{i_{0}})$. The
number of elements in $A$ which are at most $2^{i_{0}}$ and not in any $A_{i}$
is at most $2i_{0}\leq\frac{\epsilon}{4}m$. Let $A^{\prime}_{i}=A_{i}\cap
A^{\prime}$. So the set $\bigcup_{i\leq i_{0}}A^{\prime}_{i}$ of elements in
$A^{\prime}$ which are at most $2^{i_{0}}$ and in some $A_{i}$ has size at
least $\epsilon A(2^{i_{0}})-\frac{\epsilon}{4}m\geq\frac{3\epsilon}{4}m$. Let
$i_{1}\leq i_{0}$ be the largest positive integer for which
$|A^{\prime}_{i_{1}}|\geq\frac{\epsilon}{4}|A_{i_{1}}|$, which exists by the
observation just made. The set $\bigcup_{i_{1}<i\leq i_{0}}A^{\prime}_{i}$ has
cardinality at most $\frac{\epsilon}{4}|\bigcup_{i_{1}<i\leq
i_{0}}A_{i}|\leq\frac{\epsilon}{4}m$, so there are at least
$\frac{3\epsilon}{4}m-\frac{\epsilon}{4}m=\frac{\epsilon}{2}m$ elements in
$\bigcup_{i\leq i_{1}}A^{\prime}_{i}$. In particular, $A(2^{i_{1}+1})\geq
A^{\prime}(2^{i_{1}+1})\geq\frac{\epsilon}{2}m$.

Since $A_{i_{1}}$ satisfies the conclusion of Lemma 4.4 and
$|A^{\prime}_{i_{1}}|\geq(\epsilon/4)|A_{i_{1}}|\geq(\min(\epsilon,\epsilon_{0})/4)|A_{i_{1}}|$,
there is $A^{\prime\prime}_{i_{1}}\subset A^{\prime}_{i_{1}}$ with
$|A^{\prime\prime}_{i_{1}}|\leq C_{1}i_{1}$ such that
$\Sigma(A^{\prime\prime}_{i_{1}})$ contains every integer in the interval
$[y,2y]$ where $y=C_{2}2^{i_{1}}i_{1}$. Label the elements in
$A^{\prime}\setminus A^{\prime\prime}_{i_{1}}$ in increasing order as
$a^{\prime}_{1},a^{\prime}_{2},\ldots$.

By Lemma 2.1, if, for each $j$, we have $a^{\prime}_{j}\leq
2y-y+a^{\prime}_{1}+\cdots+a^{\prime}_{j-1}$, then $\Sigma(A^{\prime}\setminus
A^{\prime\prime}_{i_{1}})+[y,2y)$ contains all integers at least $y$ and, as
$\Sigma(A^{\prime})$ is a superset of $\Sigma(A^{\prime}\setminus
A^{\prime\prime}_{i_{1}})+[y,2y)$, $A^{\prime}$ would be complete. So we may
assume that there is some $j$ for which

$a^{\prime}_{j}>y+a^{\prime}_{1}+\cdots+a^{\prime}_{j-1}.$ (10)

In particular, $a^{\prime}_{j}\geq 2^{i_{1}+1}\geq
a_{\frac{\epsilon}{2}m}\geq\frac{\epsilon}{2}m$, so that $j$ can be made
sufficiently large by taking $i_{0}$ and, hence, $m$ sufficiently large.

As $a^{\prime}_{j}\in A^{\prime}\setminus A^{\prime\prime}_{i_{1}}\subset A$,
there is a positive integer $n$ for which $a^{\prime}_{j}=a_{n}$, where,
again, $n$ can be made sufficiently large by taking $i_{0}$ sufficiently
large. We have

$\sum_{i\leq
j-1}a^{\prime}_{i}<a_{n}<b_{n+1}\leq\sum_{i\leq\epsilon(n+1)+C}b_{i}\leq\sum_{i\leq\epsilon(n+1)+C}a_{i},$

where the first inequality follows from (10), the second and fourth
inequalities are by the fact that $A$ interlaces $B$ and the third inequality
follows from condition (i) of friendly sequences. This implies that
$j-1\leq\epsilon(n+1)+C$, so

$A^{\prime}(a_{n}-1)\leq|A^{\prime\prime}_{i_{1}}|+j-1\leq
C_{1}i_{1}+\epsilon(n+1)+C<C_{1}i_{0}+\epsilon n+C+1.$ (11)

That is, the number of elements of $A^{\prime}$ amongst the first $n$ elements
of $A$ is roughly $\epsilon n$.

We next give a similar argument, but using the extra information that there
are many elements $a_{s}\in A\setminus A^{\prime}$ with $s\leq n$ in order to
conclude that $A^{\prime}$ is complete. Let $N=8(n+1)/(\epsilon^{2}c)$. Let
$i_{2}$ be the least positive integer such that $2^{i_{2}}\geq a_{N}$ and let
$m^{\prime}=A(2^{i_{2}})$, so $m^{\prime}\geq N$. As $a_{2N/c+1}\geq
b_{2N/c+1}\geq 2b_{N+1}>2a_{N}$, where the middle inequality follows from
Claim 4.2, there is a perfect power of two which is at least $a_{N}$ and less
than $a_{2N/c+1}$, so $m^{\prime}=A(2^{i_{2}})\leq 2N/c$. Furthermore, since
$a_{n}=a_{j}^{\prime}\geq a_{\frac{\epsilon}{2}m}$, we have that
$n\geq\frac{\epsilon}{2}m$. Thus, $N=8(n+1)/(\epsilon^{2}c)>m$, so
$A(2^{i_{2}})\geq N>m=A(2^{i_{0}})$. In particular, we obtain that $i_{2}\geq
i_{0}$. Hence, $N$, $i_{2}$ and $m^{\prime}$ may be made sufficiently large by
taking $i_{0}$ and, hence, $n$ sufficiently large.

We also have $A^{\prime}(2^{i_{2}})\geq\epsilon A(2^{i_{2}})=\epsilon
m^{\prime}$, so $A^{\prime}$ contains at least $\epsilon m^{\prime}$ elements
$a_{s}\leq 2^{i_{2}}$. Let $i_{3}\leq i_{2}$ be the largest positive integer
such that $|A^{\prime}_{i_{3}}|\geq\frac{\epsilon}{4}|A_{i_{3}}|$. Recall
that, for each positive integer $i$, the number of elements of $A$ in
$[2^{i},2^{i+1})\setminus[b_{h(i)},b_{h(i+1)-1})$ is at most two. It follows
that
$A^{\prime}\cap[2^{i_{2}}]\setminus\bigcup_{i<i_{2}}[b_{h(i)},b_{h(i+1)-1})$
has cardinality at most $2i_{2}\leq\frac{\epsilon m^{\prime}}{4}$, where the
last inequality follows from condition (iii) of friendly sequences and the
fact that $i_{2}$ is sufficiently large. Hence, at least a fraction
$\epsilon-\frac{\epsilon}{4}-\frac{\epsilon}{4}=\frac{\epsilon}{2}$ of the
elements of $A$ up to $2^{i_{2}}$ are greater than $a_{\epsilon N/4}$ and in
$A^{\prime}\cap\bigcup_{i<i_{2}}[b_{h(i)},b_{h(i+1)-1})$ and, therefore,
$i_{3}$ satisfies $2^{i_{3}+1}>a_{\epsilon N/4}$.

Since $A_{i_{3}}$ satisfies the conclusion of Lemma 4.4 and
$|A^{\prime}_{i_{3}}|\geq(\min(\epsilon,\epsilon_{0})/4)|A_{i_{3}}|$, there is
$A_{i_{3}}^{\prime\prime}\subset A^{\prime}_{i_{3}}$ with
$|A_{i_{3}}^{\prime\prime}|\leq C_{1}i_{3}$ such that
$\Sigma(A_{i_{3}}^{\prime\prime})$ contains every integer in the interval
$[y^{\prime},2y^{\prime}]$ where $y^{\prime}=C_{2}2^{i_{3}}i_{3}$. Label the
elements in $A^{\prime}\setminus A_{i_{3}}^{\prime\prime}$ in increasing order
as $a^{\prime}_{1},a^{\prime}_{2},\ldots$, noting that we have relabeled most
of the elements in $A^{\prime}$.

Again, by Lemma 2.1, if, for each $j$, we have $a^{\prime}_{j}\leq
2y^{\prime}-y^{\prime}+a^{\prime}_{1}+\cdots+a^{\prime}_{j-1}$, then
$\Sigma(A^{\prime}\setminus
A_{i_{3}}^{\prime\prime})+[y^{\prime},2y^{\prime})$ contains all integers at
least $y^{\prime}$ and, as $\Sigma(A^{\prime})$ is a superset of
$\Sigma(A^{\prime}\setminus
A_{i_{3}}^{\prime\prime})+[y^{\prime},2y^{\prime})$, $A^{\prime}$ would be
complete. So we may assume that there is some $j^{\prime}$ for which

$a^{\prime}_{j^{\prime}}>y^{\prime}+a^{\prime}_{1}+\cdots+a^{\prime}_{j^{\prime}-1}.$

Note in particular that $a^{\prime}_{j^{\prime}}\geq y^{\prime}\geq
2^{i_{3}+1}\geq a_{\epsilon N/4}$. Let $n^{\prime}$ be such that
$a_{n^{\prime}}=a^{\prime}_{j^{\prime}}$, so

$n^{\prime}\geq\epsilon N/4.$ (12)

By condition (i) of friendly sequences, we have

$a^{\prime}_{j^{\prime}}=a_{n^{\prime}}<b_{n^{\prime}+1}\leq\sum_{i\leq\epsilon(n^{\prime}+1)+C}b_{i}\leq\sum_{i\leq\epsilon(n^{\prime}+1)+C}a_{i}.$

Note also that, for $i\geq\epsilon n^{\prime}$, we have

$a_{i}\geq a_{\epsilon n^{\prime}}\geq b_{\epsilon n^{\prime}}\geq
2b_{c\epsilon n^{\prime}/2}>2a_{c\epsilon n^{\prime}/2-1}\geq
2a_{c\epsilon^{2}N/8-1}\geq 2a_{n}.$ (13)

Here the first inequality follows from $A$ being increasing, the second and
fourth inequalities follow from the fact that $A$ interlaces $B$, the third
inequality follows from Claim 4.2, the fifth inequality follows from (12) and
the last inequality follows from the choice of $N$ and the fact that $A$ is
increasing.

Since $A^{\prime}$ has at least $\epsilon n^{\prime}$ elements up to
$a_{n^{\prime}}$, we have $j^{\prime}\geq\epsilon
n^{\prime}-|A^{\prime\prime}_{i_{3}}|$. It follows that

$\displaystyle\sum_{k<j^{\prime}}a^{\prime}_{k}$ $\displaystyle\geq$
$\displaystyle-\sum_{a\in[a_{n}]\cap(A\setminus
A^{\prime})}a+\sum_{k\leq\epsilon
n^{\prime}-|A_{i_{3}}^{\prime\prime}|-1+n-A^{\prime}(a_{n})}a_{k}$
$\displaystyle\geq$ $\displaystyle-
a_{n}(n-A^{\prime}(a_{n}))+\sum_{k\leq\epsilon
n^{\prime}-|A_{i_{3}}^{\prime\prime}|-1+n-A^{\prime}(a_{n})}a_{k}$
$\displaystyle\geq$ $\displaystyle-\frac{1}{2}a_{\epsilon
n^{\prime}}(n-A^{\prime}(a_{n}))+\sum_{k\leq\epsilon
n^{\prime}-|A_{i_{3}}^{\prime\prime}|-1+n-A^{\prime}(a_{n})}a_{k}$
$\displaystyle\geq$ $\displaystyle\sum_{k\leq\epsilon
n^{\prime}-|A_{i_{3}}^{\prime\prime}|-1+\frac{1}{2}\left(n-A^{\prime}(a_{n})\right)}a_{k},$

where the first inequality uses that $A$ is an increasing sequence and
$\sum_{k<j^{\prime}}a^{\prime}_{k}+\sum_{a\in[a_{n}]\cap(A\setminus