A^{\prime})}a$ is a sum of at least $\epsilon
n^{\prime}-|A^{\prime\prime}_{i_{3}}|-1+n-A^{\prime}(a_{n})$ distinct terms of
$A$, which is at least the sum of the first $\epsilon
n^{\prime}-|A^{\prime\prime}_{i_{3}}|-1+n-A^{\prime}(a_{n})$ terms in $A$. The
second inequality follows from $A$ being increasing, the third inequality
follows from using (13) and the last inequality follows from $A$ being
increasing and the following estimate showing that
$\frac{1}{2}(n-A^{\prime}(a_{n}))-|A^{\prime\prime}_{i_{3}}|-1>0$. We have

$-|A_{i_{3}}^{\prime\prime}|-1+\frac{1}{2}\left(n-A^{\prime}(a_{n})\right)\geq-
C_{1}i_{3}-1+\frac{1}{2}\left(n-\left(C_{1}i_{0}+\epsilon
n+C+2\right)\right)\geq-2C_{1}i_{2}+\frac{1}{2}(1-\epsilon)n-\frac{C+2}{2}>C+1,$

where the first inequality is by (11), the second inequality uses
$i_{0},i_{3}\leq i_{2}$ and $i_{2}$ is sufficiently large, while the last
inequality uses $n\geq\epsilon^{2}cN/10$, $N\geq cm^{\prime}/2$, condition (i)
of friendly sequences, the fact that $A$ interlaces $B$,
$m^{\prime}=A(2^{i_{2}})$, $i_{2}$ is sufficiently large and $m^{\prime}\geq
2^{\sqrt{\left(2\log_{2}(1/\epsilon)+o(1)\right)i_{2}}}$ from Appendix A.1,
from all of which it follows that $i_{2}\ll n$. However, this implies that

$b_{n^{\prime}+1}>a_{n^{\prime}}=a^{\prime}_{j^{\prime}}>\sum_{k<j^{\prime}}a^{\prime}_{k}>\sum_{k\leq\epsilon
n^{\prime}+C+1}a_{k}\geq\sum_{k\leq\epsilon
n^{\prime}+C+1}b_{k}\geq\sum_{k\leq\epsilon(n^{\prime}+1)+C}b_{k},$

contradicting condition (i) of friendly sequences. ∎

Theorem 1.4 is obtained similarly, by replacing Lemma 4.4 in the above proof
by an appropriate analogue of Lemma 2.9. As indicated in the introduction, we
omit the details.

##  5 Monochromatic subset sums

###  5.1 Proof of the lower bound in Theorem 1.6

Throughout this section, we use the convention that products and sums indexed
by $p$ run over primes. Recall that $p_{i}$ is the $i^{\textrm{th}}$ prime,
$W(\rho)=\prod_{i=1}^{\rho}p_{i}$ and
$\tau(\rho,m)=\phi(W(\rho)m)/(W(\rho)m)=\prod_{p|W(\rho)m}(1-1/p)$. We recall
from the introduction that, for positive integers $n$ and $m$ with
$m\in[n,\binom{n}{2}]$, we define $\rho(n,m)$ to be the smallest positive
integer $\rho$ such that $\rho/\tau(\rho,m)\geq n^{2}/\phi(m)$. Let
$\psi(n,m)=\frac{m^{1/3}(m/\phi(m))}{(\log n)^{1/3}(\log\log n)^{2/3}}$ and
${\cal R}(n,m)=\min\left(\psi(n,m),\rho(n,m)\right)$. By Claim B.3 in Appendix
B.2, we note that ${\cal R}(n,m)=\Theta\left(\psi(n,m)\right)$ when
$m=O\left(\frac{n^{3/2}(\log\log n)^{1/2}}{(\log n)^{1/2}}\right)$ and ${\cal
R}(m,n)=\Theta(\rho(n,m))$ otherwise.

We aim to prove that $f(n,m)$, the minimum $r$ such that there exists an
$r$-coloring of $[n-1]$ where $m$ cannot be written as a sum of distinct
monochromatic elements, is bounded below by ${\cal R}(n,m)$ up to a constant
factor, giving the lower bound in Theorem 1.6. The main result of this
subsection is the following lemma, from which the required lower bound easily
follows.

######  Lemma 5.1.

There exist positive constants $c$ and $C$ such that the following holds. Let
$n$ be sufficiently large and $m\in[n,\binom{n}{2}]$ be such that $r=c{\cal
R}(n,m)$ is at least $C$. Let $y<n/2$ be such that

$m\in\left[\frac{y^{2}(m/\phi(m))\tau(r,m)}{25r},\frac{y^{2}(m/\phi(m))\tau(r,m)}{15r}\right]$

and let $Y$ be the set of integers in $[y,2y)$ of the form $qu$, where $u|m$,
$u\leq y^{1/16}$ and $q$ is coprime to $W(r)m$. Then, in any $r$-coloring of
$Y$, there exists a monochromatic subset sum which equals $m$.

By Claim B.4 in Appendix B.2, for any $m\in[n,\binom{n}{2}]$, there exists a
choice of $y\in[\max(r^{2},n^{3/5}),n/2)$ satisfying the required condition.
We may therefore apply the lemma to conclude that if ${\cal R}(n,m)\geq C/c$,
then $f(n,m)\geq c{\cal R}(n,m)$. That is, the lower bound in Theorem 1.6
holds in this case. On the other hand, if ${\cal R}(n,m)<C/c$, we have the
trivial bound $f(n,m)\geq 1\geq C^{-1}c{\cal R}(n,m)$, so the lower bound in
Theorem 1.6 also holds in this case. For the same reason, we can and will
assume throughout that $r$ is sufficiently large.

We will build towards the proof of Lemma 5.1 through a series of reductions
and intermediate results. For convenience, we will often use objects and
notation in the lemma statements without repeating their definitions from
earlier. We begin with the following number-theoretic estimate, whose proof
may be found in Appendix B.1.

######  Lemma 5.2.

Let $r$, $n$ and $m$ be positive integers such that $m\in[n,\binom{n}{2}]$,
$r\leq n$ and $r$ is sufficiently large. For any interval $I=[x,2x)$ with
$x\geq n^{1/4}$, there are at most $8(m/\phi(m))\tau(r,m)x$ integers in $I$ of
the form $qu$, where $u|m$, $u\leq x^{1/16}$ and $q$ is coprime to $W(r)m$. If
also $x\geq r^{2}$, then there are at least $\frac{1}{8}(m/\phi(m))\tau(r,m)x$
integers in $I$ of this form.

By Lemma 5.2, the set $Y$ defined in Lemma 5.1 satisfies

$|Y|\geq\frac{1}{8}(m/\phi(m))\tau(r,m)y.$

By the pigeonhole principle, in any $r$-coloring of $Y$, there is one color
class whose size is at least $\frac{1}{8}(m/\phi(m))\tau(r,m)\frac{y}{r}$. Let
$Q_{0}$ be the elements of $Y$ in this color class. We will prove that
$m\in\Sigma(Q_{0})$.

Call a set $X$ of integers $k$-diverse if, for each $v\geq 2$, there are at
least $k$ elements of $X$ which are not divisible by $v$. If $Q_{0}$ is not
$y^{1/4}$-diverse, there exists $v_{0}\geq 2$ such that at most $y^{1/4}$
elements of $Q_{0}$ are not divisible by $v_{0}$. We replace $Q_{0}$ by
$Q_{1}=\\{a/v_{0}:a\in Q_{0},v_{0}|a\\}\subseteq[y/v_{0},2y/v_{0})$. We then
iterate this process. For $i\geq 1$, if $Q_{i}$ is not $y^{1/4}$-diverse, we
can remove at most $y^{1/4}$ elements of $Q_{i}$ so that the remaining
elements are divisible by some $v_{i}\geq 2$. We then let
$Q_{i+1}=\\{x/v_{i}:x\in Q_{i},v_{i}|x\\}$. We stop the process once we reach
a set $Q_{s}$ which is $y^{1/4}$-diverse. Note that there can be at most
$\log_{2}n$ iterations, so there must be at least
$\frac{1}{8}(m/\phi(m))\tau(r,m)\frac{y}{r}-y^{1/4}\log_{2}n$ elements in
$Q_{s}$.

By the process defining $Q_{s}$, there exists $v$ such that $Q_{s}=\\{x/v:x\in
Q_{0},v|x\\}$. Let $Q=Q_{s}$. Then $Q$ is a subset of $[y/v,2y/v)$ of size at
least $\frac{1}{8}(m/\phi(m))\tau(r,m)\frac{y}{r}-y^{1/4}\log_{2}n$ which is
$y^{1/4}$-diverse. Let
$z=\frac{1}{8}(m/\phi(m))\tau(r,m)\frac{y}{r}-y^{1/4}\log_{2}n$. Note that

$\frac{1}{8}(m/\phi(m))\tau(r,m)\frac{y}{r}\geq
z\geq\frac{1}{10}(m/\phi(m))\tau(r,m)\frac{y}{r}\geq\frac{1}{10}\tau(r,m)\sqrt{y}>y^{1/3},$
(14)

where we used that $y\geq\max(r^{2},n^{3/5})$, which is inequality (35) of
Claim B.4 in Appendix B.2, and $\tau(r,m)\geq 1/(8\log n\log\log n)$ by
inequality (33) in Appendix B.2. In particular, for $r$ sufficiently large,

$|Q|=z\geq\frac{1}{10}(m/\phi(m))\tau(r,m)\frac{y}{r}>64(m/\phi(m))\tau(r,m)\frac{y}{r\log
r}.$

The next lemma shows that $v|m$.

######  Lemma 5.3.

If there exist at least $64(m/\phi(m))\tau(r,m)\frac{y}{r\log r}$ elements in
$Y$ which are divisible by $v$, then $v|m$ and $v\leq y^{1/16}$. Furthermore,
all elements of $Y$ which are divisible by $v$ have the form $qvu$, where
$(vu)|m$, $vu\leq y^{1/16}$ and $\gcd(q,W(r)m)=1$.

###### Proof.

Note that if $\gcd(q,W(r)m)=1$ and $q\neq 1$, then any prime factor of $q$ is
at least $p_{r}>r\log r/8$ for sufficiently large $r$. Recall that elements of
$Y$ have the form $qu$, where $u|m$, $u\leq y^{1/16}$ and $\gcd(q,W(r)m)=1$.
Assume that there exists $v$ such that either $v\nmid m$ or $v>y^{1/16}$ and
at least $64(m/\phi(m))\tau(r,m)\frac{y}{r\log r}$ elements in $Y$ are
divisible by $v$. We claim that $v$ must have a prime factor $p$ which is
coprime to $W(r)m$. Indeed, if this were not the case, then $v$ only has prime
factors which are divisors of $W(r)m$, so $\gcd(v,q)=1$ for any $q$ coprime to
$W(r)m$. Thus, if an element of the form $qu$ with $u|m$, $u\leq y^{1/16}$ and
$\gcd(q,W(r)m)=1$ is divisible by $v$, then $v|u$, so $v|m$ and $v\leq
y^{1/16}$, contradicting our assumption. Thus, $v$ has a prime factor $p$
which is coprime to $W(r)m$. In particular, $p\geq p_{r}>r(\log r)/8$.

We have that at least $64(m/\phi(m))\tau(r,m)\frac{y}{r\log r}$ elements of
$Y$ are divisible by $p$. For each element $qu$ of $Y$ which is divisible by
$p$, since $p$ is coprime to $W(r)m$, we must have $p|q$, so $q=q^{\prime}p$
for $q^{\prime}$ coprime to $W(r)m$. Hence, elements of $Y$ which are
divisible by $p$ have the form $pq^{\prime}u$ where $u|m$, $u\leq y^{1/16}$
and $\gcd(q^{\prime},W(r)m)=1$. If $y/p\geq n^{1/4}$, Lemma 5.2 implies that
the number of such elements is at most
$8(m/\phi(m))\tau(r,m)\frac{y}{p}<64(m/\phi(m))\tau(r,m)\frac{y}{r\log r}$. If
$y/p<n^{1/4}$, then the number of such elements is at most
$y/p<n^{1/4}<64(m/\phi(m))\tau(r,m)\frac{y}{r\log r}$, where the second
inequality is verified as inequality (36) of Claim B.4 in Appendix B.2. In
either case, we have a contradiction, so we must have that $v|m$ and $v\leq
y^{1/16}$.

Since $v|m$, we have $\gcd(v,W(r)m)=v$, so each element of the form $qu$ where
$u|m$, $u\leq y^{1/16}$ and $\gcd(q,W(r)m)=1$ which is divisible by $v$ must
have $v|u$. Hence, $qu=qvu^{\prime}$ where $(vu^{\prime})|m$, $vu^{\prime}\leq
y^{1/16}$ and $\gcd(q,W(r)m)=1$, establishing the second claim in the lemma. ∎

Since $|Q|>64(m/\phi(m))\tau(r,m)\frac{y}{r\log r}$ and $\\{vx:x\in Q\\}$ is a
subset of $Y$, Lemma 5.3 implies that each element of $Q$ can be written in
the form $qu$, where $(vu)|m$, $vu\leq y^{1/16}$ and $\gcd(q,W(r)m)=1$. Let

$Y_{v}=\\{t\in[y/v,2y/v):t=qu,u|(m/v),u\leq y^{1/16}/v,\gcd(q,W(r)m)=1\\}.$

We have that $vt\in Y$ for all $t\in Y_{v}$ and $Q\subseteq Y_{v}$.

Let $V$ be a random subset of $Q$ of size $z/8$. The next lemma implies that
$V$ is $y^{1/4}/16$-diverse with probability at least $1/2$. From now, we fix
$V$ to be a subset of $Q$ of size $z/8$ which is $y^{1/4}/16$-diverse.

######  Lemma 5.4.

Let $k$ and $h$ be positive integers with $h\neq 1$ and $N=\exp(k/16h)$. Let
$A$ be a set of $t$ integers in $[N]$ which is $k$-diverse. Let $B$ be a
uniformly random subset of $A$ of size $t/h$. Then $B$ is $k/(2h)$-diverse
with probability at least $1-1/N$.

###### Proof.

For each $d\in[N]$ with $d>1$, let $X_{d}$ be the set of elements in $A$ which
are not divisible by $d$. By our assumption, $|X_{d}|\geq k$ for each $d$. The
number of elements in $B\cap X_{d}$ follows a hypergeometric distribution. As
the hypergeometric distribution is at least as concentrated as the
corresponding binomial distribution (for a proof, see Section 6 of [29]), we
can apply the Chernoff bound to obtain that the probability that $|B\cap
X_{d}|<|X_{d}|/(2h)$ is at most $\exp(-|X_{d}|/8h)\leq\exp(-k/8h)=N^{-2}$. By
taking a union bound over all $d\in[N]$ with $d>1$, we conclude that the
probability $B$ is not $k/(2h)$-diverse is at most $N\cdot N^{-2}=N^{-1}$. ∎

The following lemma is the key to proving Lemma 5.1.

######  Lemma 5.5.

Let $\ell=\lceil 32/\xi\rceil$, where $\xi$ is the constant in Lemma 2.4. Let
$A$ be a subset of $Y_{v}$ of size $z/(8\ell)$ which is
$y^{1/4}/(32\ell)$-diverse. Then $|\Sigma(A)|\geq yz/(\ell^{2}v)$ and
$\Sigma(A)$ is not a subset of an arithmetic progression with common
difference greater than $1$.

Before moving on to the proof of Lemma 5.5, we show how Lemma 5.1 follows from
it.

###### Proof of Lemma 5.1 assuming Lemma 5.5.

Recall that we have fixed a subset $V$ of $Q$ of size $z/8$ which is
$y^{1/4}/16$-diverse. We will prove that $\Sigma(V)$ contains an interval
$J=[a,b]$ of length at least $2y/v$. To see why this suffices, first note that

$vb\leq v\cdot\max\Sigma(V)<2y\cdot\frac{z}{8}\leq
2y\cdot\frac{(m/\phi(m))\tau(r,m)y}{8\cdot 8r}<m,$

where the third inequality follows from (14) and the last inequality follows
since $y^{2}\leq\frac{25rm}{(m/\phi(m))\tau(r,m)}$ by the choice of $y$. If
now we can find the required interval $J$, Lemma 5.1 follows since each
element of $Q$ is at most $2y/v$ and, hence, by Lemma 2.1,
$\Sigma(Q)=\Sigma(V\cup(Q\setminus V))$ contains an interval whose smallest
element is $a<m/v$ by the inequality above and whose largest element is

$b+\sum_{i\in Q\setminus V}i>\frac{y}{v}\cdot
z(1-1/8)\geq\frac{y}{v}\cdot\frac{7(m/\phi(m))\tau(r,m)y}{8\cdot
10r}>\frac{m}{v},$

where the last inequality follows since
$y^{2}\geq\frac{15rm}{(m/\phi(m))\tau(r,m)}$ by the choice of $y$. Hence,
$\Sigma(Q_{0})$ contains the progression $\\{va,v(a+1),\dots,v(m/v)\\}$, which
contains $m$.

We partition $V$ randomly into $\ell$ sets $V_{1},V_{2},\dots,V_{\ell}$ of
size $z/(8\ell)$. By Lemma 5.4 and the union bound, the probability that
$V_{i}$ is $y^{1/4}/(32\ell)$-diverse for all $i\in[\ell]$ is at least $1/2$.
Hence, we can fix a partition of $V$ into $\ell$ sets
$V_{1},V_{2},\dots,V_{\ell}$ of size $z/(8\ell)$, where $V_{i}$ is
$y^{1/4}/(32\ell)$-diverse for each $i\in[\ell]$.

For each $i\in[\ell]$, $\Sigma(V_{i})$ is a subset of the interval
$[0,z/(8\ell)\cdot 2y/v]=[0,yz/(4\ell v)]$. By Lemma 5.5, $|\Sigma(V_{i})|\geq
yz/(\ell^{2}v)$ and $\Sigma(V_{i})$ is not a subset of an arithmetic
progression with common difference greater than $1$. Therefore, by Lemma 2.2,
$\Sigma(V_{1})+\cdots+\Sigma(V_{\ell})$ contains an interval of length at
least $yz/(2\ell v)>2y/v$ for $n$ sufficiently large, as required. ∎

We have therefore reduced the task of proving the lower bound in Theorem 1.6
to Lemma 5.5. The strategy for proving Lemma 5.5 is now as follows. We
partition $A$ into two subsets $A_{1}$ and $A_{2}$ of size $z/(16\ell)$,
observing that we can choose $A_{1}$ and $A_{2}$ to be
$y^{1/4}/(128\ell)$-diverse by Lemma 5.4. We then show that $\Sigma(A_{1})$
contains elements in many different congruence classes modulo $t$ for all $t$
in $A_{2}$, allowing us to apply Lemma 2.5 repeatedly (as in the proofs of our
results on completeness) to conclude that each element of $A_{2}$ introduces
many new elements to the set of subset sums.

The next lemma is the main step in the proof of Lemma 5.5. Recall that

$\Sigma_{t}(A)=\left\\{\sum_{x\in S}x\bmod{t}:S\subseteq A\right\\}$

and $\xi$ is the absolute constant defined in Lemma 2.4.

######  Lemma 5.6.

Let $t\in[y/v,2y/v)$. Let $A$ be a subset of $Y_{v}$ of size $z/(16\ell)$
which is $y^{1/4}/(128\ell)$-diverse. Then
$|\Sigma_{t}(A)|\geq\min(\xi,32/\ell)t$.

To show that the set of mod $t$ subset sums is large, we prove the following
structural lemma, stating that the set of elements whose inclusion does not
expand the set of mod $t$ subset sums must either be small or additively
structured. We will then use this additive structure to show that the
corresponding set in $\mathbb{Z}$ must contain a small number of integers of
the form $qu$, which we will see is impossible.

######  Lemma 5.7.

Let $t$ be an integer. Let $A\subseteq\mathbb{Z}_{t}$ be such that $8d<|A|<\xi
t$. Let $G_{d}\subseteq\mathbb{Z}_{t}$ be the set of $x$ such that $|(A+x)\cup
A|\leq|A|+d$. Then either $G_{d}$ is contained in a proper subgroup of
$\mathbb{Z}_{t}$, $|G_{d}|\leq\frac{20|A|}{(|A|/2d)^{1.02}}$ or there is a
subgroup $H$ of $\mathbb{Z}_{t}$ such that $G_{d}$ is contained in a set of
size at most $128d$ which is an arithmetic progression of $H$-cosets.

###### Proof.

By Lemma 2.7, $kG_{d}\subseteq G_{kd}$, where
$kG_{d}=\\{x_{1}+x_{2}+\cdots+x_{k}:x_{1},x_{2},\dots,x_{k}\in G_{d}\\}$. Let
$i=\lfloor\log_{2}(|A|/2d)\rfloor$ and let $k=2^{i}$, noting that
$kd\leq|A|/2$. Therefore, applying Lemma 2.6 to $G_{kd}$, we get

$|kG_{d}|\leq|G_{kd}|\leq\frac{|A|^{2}}{|A|-kd}\leq 2|A|.$ (15)

Assume that $G_{d}$ is not contained in a proper subgroup of $\mathbb{Z}_{t}$.
Let $j$ be such that $0\leq j<i$. Since $0\in G_{d}$ by definition, we have
$G_{d}\subset 2^{j}G_{d}$, so $0\in 2^{j}G_{d}$ and $2^{j}G_{d}$ is not
contained in a proper subgroup of $\mathbb{Z}_{t}$. Thus, $2^{j}G_{d}$ is not
contained in a coset of a proper subgroup of $\mathbb{Z}_{t}$. By Lemma 2.3,
$|2^{i}G_{d}|\geq\min\\{t,2^{i-j-1}|2^{j}G_{d}|\\}=2^{i-j-1}|2^{j}G_{d}|$,
where we used that $|2^{i}G_{d}|\leq 2|A|<2\xi t<t$ from (15). Thus,

$|2^{j}G_{d}|\leq 2^{1-i+j}|2^{i}G_{d}|<2\xi t.$ (16)

Assume now that $|2^{j+1}G_{d}|=|2^{j}G_{d}+2^{j}G_{d}|\leq 2.04|2^{j}G_{d}|$
for some $2\leq j<i$. By Lemma 2.4, there exists a proper subgroup $H$ of
$\mathbb{Z}_{t}$ such that one of the following holds:

  1. 1.

$2^{j}G_{d}$ is contained in a set of size at most $\frac{\ell}{\ell-1}\cdot
1.04|2^{j}G_{d}|$ which is an arithmetic progression of $H$-cosets of length
$\ell\geq 2$,

  2. 2.

$2^{j}G_{d}$ meets exactly three $H$-cosets which are terms of an arithmetic
progression of $H$-cosets of length $\ell$ and $(\min(\ell,4)-1)|H|\leq
1.04|2^{j}G_{d}|$ or

  3. 3.

$2^{j}G_{d}$ is contained in one $H$-coset.

We have already seen that the third case cannot happen, that is, that
$2^{j}G_{d}$ is not contained in a coset of a proper subgroup of
$\mathbb{Z}_{t}$.

Suppose that we are in the second case. Then $2^{j}G_{d}$ is contained in a
union of three $H$-cosets, so $4G_{d}$ is contained in a union of three
$H$-cosets. Since $0\in G_{d}$ and $G_{d}$ is not contained in an $H$-coset,
the image of $G_{d}$ in $\mathbb{Z}_{t}/H$ is a subset $S$ of
$\mathbb{Z}_{t}/H$ of size at least $2$ such that $0\in S$ and $4S$ has size
at most $3$. This can only happen if $S$ is contained in a subgroup of
$\mathbb{Z}_{t}/H$ of size at most $3$. In this case, $G_{d}$ is contained in
a subgroup of $\mathbb{Z}_{t}$ of size at most $3|H|$. Since
$|H|\leq(\min(\ell,4)-1)|H|\leq 1.04|2^{j}G_{d}|$, we have $3|H|\leq
3.12|2^{j}G_{d}|<6.24\xi t<t$, so $G_{d}$ is contained in a proper subgroup of
$\mathbb{Z}_{t}$, a contradiction. Thus, the second case cannot happen.

We now consider the first case, where $2^{j}G_{d}$ is contained in a set of
size at most $\frac{\ell}{\ell-1}\cdot 1.04|2^{j}G_{d}|\leq 2.08|2^{j}G_{d}|$
which is an arithmetic progression of $H$-cosets of length $\ell$. As $0\in
G_{d}$, this progression of $H$-cosets contains $0$. Let $m$ be such that
$H=\\{x\in\mathbb{Z}_{t}:m|x\\}$. Then the $H$-cosets can be identified with
elements of $\mathbb{Z}_{m}$. The common difference of the progression of
$H$-cosets must be coprime to $m$, as otherwise $2^{j}G_{d}$ would be
contained in a proper subgroup of $\mathbb{Z}_{t}$. Thus, by rescaling if
necessary, we may assume that the common difference of the progression of
$H$-cosets is $1$. Let $P_{j}$ be the interval in $\mathbb{Z}_{m}$ which
corresponds to the $H$-cosets in the progression containing $2^{j}G_{d}$. Note
that $0\in G_{d}$, so that $2^{h-1}G_{d}\subseteq 2^{h}G_{d}$ for all $h$.
Hence, for each $h\leq j$, we can choose intervals $P_{h}$ around $0$ in
$\mathbb{Z}_{m}$ such that $2^{h}(G_{d}/H)\subseteq P_{h}$, $P_{h}\subseteq
P_{j}$ and $2^{j-h}P_{h}\subseteq P_{j}$. The length $\ell$ of $P_{j}$ is at
most $m/2$, since otherwise $|2^{j}G_{d}|\geq\frac{t/2}{2.08}$, contradicting
(16). We can thus deduce that, for all $h\leq j$, $P_{h}$ is an interval of
length at most $1+2^{h-j}(|P_{j}|-1)$ around $0$ in $\mathbb{Z}_{m}$, since,
for two intervals $I$, $I^{\prime}$ around 0 of length
$|I|\leq|I^{\prime}|\leq m/2$ with $2I\subseteq I^{\prime}$, we have
$|I|\leq(|I^{\prime}|+1)/2$. Hence, $G_{d}/H$ is a subset of an interval of
length at most $1+(|P_{j}|-1)/2^{j}$. Since $G_{d}$ is not contained in a
proper subgroup of $\mathbb{Z}_{t}$, $(|P_{j}|-1)/2^{j}\geq 1$. Thus, we have
$1+(|P_{j}|-1)/2^{j}\leq|P_{j}|/2^{j-1}$. Therefore, $G_{d}$ is contained in a
union of $H$-cosets of size at most

$|H||P_{j}|/2^{j-1}\leq\frac{\ell}{\ell-1}\cdot 1.04|2^{j}G_{d}|\cdot
2^{1-j}\leq\frac{\ell}{\ell-1}\cdot 1.04\cdot 2^{3-i}|A|\leq 128d,$

where, in the second inequality, we used (15) and (16) and, in the final
inequality, we used that $i=\lfloor\log_{2}(|A|/2d)\rfloor$ and $\ell\geq 2$.

If there does not exist $j\in[2,i)$ such that $|2^{j+1}G_{d}|\leq
2.04|2^{j}G_{d}|$, then

$|2^{i}G_{d}|\geq 2.04^{i-2}|G_{d}|\geq(|A|/2d)^{1.02}|G_{d}|/10.$

Combining this with (15), we deduce that
$|G_{d}|\leq\frac{20|A|}{(|A|/2d)^{1.02}}$. ∎

Besides Lemma 5.7, we need several other ingredients for the proof of Lemma
5.6. We begin with the following result, which will also be useful to us in
subsequent sections. For this section, the key corollary is that if $A$ is
$k$-diverse for $k\geq d-1$, then $\Sigma_{d}(A)=\mathbb{Z}_{d}$.

######  Lemma 5.8.

Let $d$ be a positive integer. Let $A$ be a set of integers such that, for
each $d^{\prime}|d$, at least $d^{\prime}-1$ elements of $A$ are not divisible
by $d^{\prime}$. Then $\Sigma_{d}(A)=\mathbb{Z}_{d}$. Furthermore, if $A$
contains at least $d-1$ elements which are not divisible by $d$, then
$\Sigma_{d}(A)$ contains a non-zero subgroup of $\mathbb{Z}_{d}$.

###### Proof.

We will use the following simple claim.

Claim. If $S$ is a subset of $\mathbb{Z}_{t}$ and $X\subseteq\mathbb{Z}_{t}$
is such that $|(S+x)\cup S|=|S|$ for all $x\in X$, then $S$ is a union of
cosets of the subgroup of $\mathbb{Z}_{t}$ spanned by $X$.

Proof. If $|(S+x)\cup S|=|S|$, then $S+x=S$. Thus, by induction, we have that
$S+x_{1}+\dots+x_{k}=S$ for all $k\in\mathbb{N}$ and $x_{1},\dots,x_{k}\in X$.
In particular, we have $S+\langle X\rangle=S$, where $\langle X\rangle$ is the
subgroup of $\mathbb{Z}_{t}$ spanned by $X$. Since $S+\langle X\rangle$ is a
union of cosets of $\langle X\rangle$, we obtain the desired conclusion. ∎

Note that $\Sigma_{t}(S\cup\\{x\\})=\Sigma_{t}(S)\cup(\Sigma_{t}(S)+x)$. From
the claim, if $S$ is a multiset in $\mathbb{Z}_{t}$ and $x\in\mathbb{Z}_{t}$
is coprime to $t$, then we have
$|\Sigma_{t}(S\cup\\{x\\})|\geq\min(|\Sigma_{t}(S)|+1,t)$, as either
$|\Sigma_{t}(S\cup\\{x\\})|\geq|\Sigma_{t}(S)|+1$ or $\Sigma_{t}(S)$ is a
union of cosets of $x\mathbb{Z}_{t}=\mathbb{Z}_{t}$, so
$\Sigma_{t}(S)=\mathbb{Z}_{t}$. Thus, if $B=\\{b_{1},\dots,b_{t-1}\\}$ is a
multiset of size $t-1$ consisting of elements in $\mathbb{Z}_{t}$ coprime to
$t$, then $\Sigma_{t}(B)=\mathbb{Z}_{t}$. Indeed, this follows easily from the
fact that $\Sigma_{t}(\emptyset)=\\{0\\}$ and, for each $i\geq 1$,
$|\Sigma_{t}(\\{b_{1},\dots,b_{i}\\})|\geq\min(|\Sigma_{t}(\\{b_{1},\dots,b_{i-1}\\})|+1,t)$.

Suppose now that $A$ is a set of integers such that, for each $d^{\prime}|d$,
at least $d^{\prime}-1$ elements of $A$ are not divisible by $d^{\prime}$. We
will prove that $\Sigma_{d^{\prime}}(A)=\mathbb{Z}_{d^{\prime}}$ for all
$d^{\prime}|d$ by induction on the number of prime factors (counted with
repeats) of $d^{\prime}$. When $d^{\prime}$ is a prime, the conclusion follows
from the observation above. Assume now that the conclusion holds whenever
$d^{\prime}$ has at most $j$ prime factors, for some $j\geq 1$.

Let $d^{\prime}$ be a divisor of $d$ with $j+1$ prime factors. Let $A_{0}$ be
the multiset of elements in $A$ not divisible by $d^{\prime}$, considered
modulo $d^{\prime}$. By our assumption, $A_{0}$ has size at least
$d^{\prime}-1$. Observe that
$\Sigma_{d^{\prime}}(A)=\Sigma_{d^{\prime}}(A_{0})$. Assume that
$|\Sigma_{d^{\prime}}(A_{0})|<d^{\prime}$. Let
$\Sigma_{d^{\prime}}(0)=\\{0\\}$. We consider the following iterative process.
At step $i\geq 1$, we choose $a_{i}\in A_{i-1}$ so that
$|(\Sigma_{d^{\prime}}(i-1)+a_{i})\setminus\Sigma_{d^{\prime}}(i-1)|$ is
maximized and let
$\Sigma_{d^{\prime}}(i)=\Sigma_{d^{\prime}}(i-1)\cup(\Sigma_{d^{\prime}}(i-1)+a_{i})$
and $A_{i}=A_{i-1}\setminus\\{a_{i}\\}$. Note that we consider the $A_{i}$ as
a multiset of elements of $\mathbb{Z}_{d^{\prime}}$ and the
$\Sigma_{d^{\prime}}(i)$ as subsets of $\mathbb{Z}_{d^{\prime}}$.

Let $i\leq|A_{0}|$ be the first step where
$|\Sigma_{d^{\prime}}(i)|\leq|\Sigma_{d^{\prime}}(i-1)|$. Note that $i$ must
exist since, otherwise,
$|\Sigma_{d^{\prime}}(|A_{0}|)|\geq|\Sigma_{d^{\prime}}(0)|+|A_{0}|=1+|A_{0}|\geq
d^{\prime}$, contradicting our assumption that
$|\Sigma_{d^{\prime}}(|A_{0}|)|=|\Sigma_{d^{\prime}}(A_{0})|<d^{\prime}$.
Since $i$ is the first step with
$|\Sigma_{d^{\prime}}(i)|\leq|\Sigma_{d^{\prime}}(i-1)|$, we must have that
$|\Sigma_{d^{\prime}}(j)|\geq|\Sigma_{d^{\prime}}(j-1)|+1$ for all $j<i$.
Thus, $|\Sigma_{d^{\prime}}(i)|\geq 1+i-1=i$. In step $i$, we have
$|(\Sigma_{d^{\prime}}(i-1)+a)\cup\Sigma_{d^{\prime}}(i-1)|=|\Sigma_{d^{\prime}}(i-1)|$
for all $a\in A_{i-1}$, so, by the claim, $\Sigma_{d^{\prime}}(i-1)$ is a
union of cosets of the subgroup of $\mathbb{Z}_{d^{\prime}}$ spanned by
$A_{i-1}$. Let $d^{\prime\prime}$ be the largest divisor of $d^{\prime}$ which
divides all elements in $A_{i-1}$. Then the subgroup of
$\mathbb{Z}_{d^{\prime}}$ spanned by $A_{i-1}$ is
$d^{\prime\prime}\mathbb{Z}_{d^{\prime}}$ and we have that
$\Sigma_{d^{\prime}}(i-1)$ is a union of
$d^{\prime\prime}\mathbb{Z}_{d^{\prime}}$-cosets. Note that
$d^{\prime\prime}\neq d^{\prime}$, since the elements of $A_{0}$ are not
divisible by $d^{\prime}$ and $A_{i-1}$ contains at least one element in
$A_{0}$. Thus, $d^{\prime\prime}<d^{\prime}$ and, hence, $d^{\prime\prime}$
has at most $j$ prime factors. By the induction hypothesis,
$\Sigma_{d^{\prime\prime}}(A_{0})=\mathbb{Z}_{d^{\prime\prime}}$. Note that
$\Sigma_{d^{\prime\prime}}(A_{0})=\Sigma_{d^{\prime\prime}}(\\{a_{1},\dots,a_{i-1}\\})$,
since all remaining elements of $A_{0}$ are divisible by $d^{\prime\prime}$.
Thus, $\Sigma_{d^{\prime}}(i-1)$ contains an element in each
$d^{\prime\prime}\mathbb{Z}_{d^{\prime}}$-coset of $\mathbb{Z}_{d^{\prime}}$.
Since $\Sigma_{d^{\prime}}(i-1)$ is a union of
$d^{\prime\prime}\mathbb{Z}_{d^{\prime}}$-cosets and contains an element in
each $d^{\prime\prime}\mathbb{Z}_{d^{\prime}}$-coset of
$\mathbb{Z}_{d^{\prime}}$, $\Sigma_{d^{\prime}}(i-1)$ contains all elements of
$\mathbb{Z}_{d^{\prime}}$. Thus,
$\Sigma_{d^{\prime}}(A)=\Sigma_{d^{\prime}}(i-1)=\mathbb{Z}_{d^{\prime}}$,
completing the induction.

For the second statement, observe, by the claim, that if
$|\Sigma_{d}(S\cup\\{x\\})|=|\Sigma_{d}(S)|$, then $\Sigma_{d}(S)$ is a union
of cosets of $x\mathbb{Z}_{d}$ and, as $0\in\Sigma_{d}(S)$, we have that
$\Sigma_{d}(S)$ contains the subgroup $x\mathbb{Z}_{d}$ of $\mathbb{Z}_{d}$.
Thus, if $A$ contains at least $d-1$ integers $a_{1},\dots,a_{d-1}$ not
divisible by $d$ and $\Sigma_{d}(A)$ does not contain a non-zero subgroup of
$\mathbb{Z}_{d}$, then we must have
$|\Sigma_{d}(\\{a_{1},\dots,a_{i}\\})|\geq|\Sigma_{d}(\\{a_{1},\dots,a_{i-1}\\})|+1$
for all $i\geq 1$. But then $|\Sigma_{d}(A)|\geq 1+(d-1)=d$, which means that
$\Sigma_{d}(A)$ equals $\mathbb{Z}_{d}$. ∎

We remark that the condition in the above lemma is tight, since if $d$ is
prime and $A$ consists of $d-2$ elements congruent to $1$ modulo $d$, then
$\Sigma_{d}(A)$ does not contain any non-zero subgroup of $\mathbb{Z}_{d}$.

The next lemma gives an upper bound on the number of integers coprime to
$W(r)/\gcd(W(r),m)$ in an arithmetic progression. Note that all integers of
the form $qu$ where $u|m$ and $\gcd(q,W(r)m)=1$ are coprime to
$W(r)/\gcd(W(r),m)$. The proof of this lemma uses the Selberg sieve and may be
found in Appendix B.1.

######  Lemma 5.9.

Let $r$ and $n$ be sufficiently large positive integers and
$m\in[n,\binom{n}{2}]$. Let $X$ be an arithmetic progression of size $|X|\geq
r^{1/16}$ with common difference $b\leq n$. Then the number of elements of $X$
which are coprime to $W(r)/\gcd(W(r),m)$ is at most

$\frac{256|X|\log\log n}{\log r}.$

Furthermore, when $b=1$, the number of elements of $X$ which are coprime to
$W(r)/\gcd(W(r),m)$ is at most

$256|X|\prod_{p|W(r),p\nmid m}(1-1/p).$

Given a cyclic group $\mathbb{Z}_{t}$ and an interval of integers $[x,x+t)$,
we have a natural identification $\psi_{t}:\mathbb{Z}_{t}\to[x,x+t)$, where
$\psi_{t}(u)$ is the unique integer in $[x,x+t)$ which is congruent to $u$
modulo $t$. The next lemma shows that under this identification, for a
subgroup $H$ of $\mathbb{Z}_{t}$, a progression of $H$-cosets is identified
with a large subset of a union of long arithmetic progressions of integers. A
variant of this lemma goes back at least to the proof of Roth’s Theorem [33].

######  Lemma 5.10.

Let $H$ be a subgroup of $\mathbb{Z}_{t}$ and let $R$ be an arithmetic
progression of $H$-cosets. Consider the image $\psi_{t}(R)$ of $R$ under the
identification $\psi_{t}:\mathbb{Z}_{t}\to[x,x+t)$. Then $\psi_{t}(R)$ is
contained in a set of size at most $3|R|$ which is a union of arithmetic
progressions of integers, each of length at least $|R|^{1/3}$.

###### Proof.

First observe that the image under $\psi_{t}$ of each $H$-coset is an
arithmetic progression. Thus, if $|H|\geq|R|^{1/3}$, then $\psi_{t}(R)$ is a
union of arithmetic progressions, each of length at least $|R|^{1/3}$.

Assume now that $|H|<|R|^{1/3}$. Let $H=d\mathbb{Z}_{t}$ for some divisor $d$
of $t$. Let $\ell=|R|/|H|\geq|R|^{2/3}$. By definition, we can write
$R=\bigcup_{i\in[\ell]}(x+iy+H)$ for some $x,y\in\mathbb{Z}_{t}$ and $y\notin
H$. For each $H$-coset $x+iy+H$, we can choose a representative $z_{i}$ for
the coset in $[x,x+d)$. Let $P=(z_{1},z_{2},\dots,z_{\ell})$. We have that
$P\pmod{d}$ forms a progression of common difference $u$ in $\mathbb{Z}_{d}$.
We show that $P$ is contained in a set of size at most $3\ell$ which is a
union of progressions of integers, each of length at least
$\sqrt{\ell}=\sqrt{|R|/|H|}\geq|R|^{1/3}$. From this claim, the conclusion of
the lemma easily follows.

We claim that there exists $s\in[1,\lfloor\sqrt{\ell}\rfloor]$ such that $su$
is congruent to an integer in
$[-d/\lceil\sqrt{\ell}\rceil,d/\lceil\sqrt{\ell}\rceil]$ modulo $d$. Partition
$\mathbb{Z}_{d}$ into a union of intervals
$[kd/\lceil\sqrt{\ell}\rceil,(k+1)d/\lceil\sqrt{\ell}\rceil)$ for
$k=0,1,\dots,\lceil\sqrt{\ell}\rceil-1$. Suppose that there does not exist
$s\in[1,\lfloor\sqrt{\ell}\rfloor]$ such that
$su\pmod{d}\in[-d/\lceil\sqrt{\ell}\rceil,d/\lceil\sqrt{\ell}\rceil]$. Then
$u,2u,\dots,\lfloor\sqrt{\ell}\rfloor u\pmod{d}$ must be contained in the
intervals $[kd/\lceil\sqrt{\ell}\rceil,(k+1)d/\lceil\sqrt{\ell}\rceil)$ for
$k=1,\dots,\lceil\sqrt{\ell}\rceil-2$. Since
$\lfloor\sqrt{\ell}\rfloor\geq\lceil\sqrt{\ell}\rceil-1$, the pigeonhole
principle implies that there are $1\leq
s^{\prime}<s^{\prime\prime}\leq\lfloor\sqrt{\ell}\rfloor$ such that
$s^{\prime}u\pmod{d}$ and $s^{\prime\prime}u\pmod{d}$ are in the same interval
$[kd/\lceil\sqrt{\ell}\rceil,(k+1)d/\lceil\sqrt{\ell}\rceil)$. Then
$s^{\prime\prime}-s^{\prime}\in[1,\lfloor\sqrt{\ell}\rfloor]$ and
$(s^{\prime\prime}-s^{\prime})u$ is congruent to an integer $v$ in
$[-d/\lceil\sqrt{\ell}\rceil,d/\lceil\sqrt{\ell}\rceil]$ modulo $d$,
contradicting our assumption.

Suppose now that $s\in[1,\lfloor\sqrt{\ell}\rfloor]$ is such that $su$ is
congruent to an integer in
$[-d/\lceil\sqrt{\ell}\rceil,d/\lceil\sqrt{\ell}\rceil]$ modulo $d$. Since
$P\pmod{d}$ forms a progression of common difference $u$ in $\mathbb{Z}_{d}$,
we can partition $P$ into $s$ subsets $P_{1},P_{2},\dots,P_{s}$ such that
$P_{i}\pmod{d}$ is a progression with common difference $su$ in
$\mathbb{Z}_{d}$. Each set $P_{i}$ can be greedily partitioned into
progressions of integers with common difference $v$ such that all of the
progressions in the partition, except the first and last ones, have length at
least $\lceil\sqrt{\ell}\rceil$. By extending arbitrarily the progressions
with length less than $\lceil\sqrt{\ell}\rceil$, we obtain that $P$ is
contained in a union of arithmetic progressions of integers, each of length at
least $\lceil\sqrt{\ell}\rceil$, where the size of the union is at most
$(\lceil\sqrt{\ell}\rceil-1)\cdot 2s+|P|\leq 3|P|$. This verifies the desired
claim. ∎

We will also need the following simple lemma in the proof of Lemma 5.6.

######  Lemma 5.11.

Let $A$ be a multiset of elements of $\mathbb{Z}_{t}$ and let $d$ be a divisor
of $t$. Then, for any $u\in\mathbb{Z}_{t}/d\mathbb{Z}_{t}$ such that
$\Sigma_{t}(A)\cap(u+d\mathbb{Z}_{t})\neq\emptyset$,

$|\Sigma_{t}(A)\cap(u+d\mathbb{Z}_{t})|\geq|\Sigma_{t}(A\cap
d\mathbb{Z}_{t})|.$

###### Proof.

Let $S_{u}=\Sigma_{t}(A)\cap(u+d\mathbb{Z}_{t})$. For all non-zero
$u\in\mathbb{Z}_{t}/d\mathbb{Z}_{t}$, if $S_{u}\neq\emptyset$, then we can
find an element $x$ in $S_{u}$ which is a sum of distinct elements of $A$
which are not in $d\mathbb{Z}_{t}$. Thus, each element of $x+\Sigma_{t}(A\cap
d\mathbb{Z}_{t})$ can be written a sum of distinct elements in $A$, so
$x+\Sigma_{t}(A\cap d\mathbb{Z}_{t})\subseteq\Sigma_{t}(A)$. It is also clear
that $x+\Sigma_{t}(A\cap d\mathbb{Z}_{t})\subseteq u+d\mathbb{Z}_{t}$, so
$x+\Sigma_{t}(A\cap d\mathbb{Z}_{t})\subseteq S_{u}$. If
$u=0\in\mathbb{Z}_{t}/d\mathbb{Z}_{t}$, then letting $x=0$, we have
$x+\Sigma_{t}(A\cap d\mathbb{Z}_{t})=\Sigma_{t}(A\cap
d\mathbb{Z}_{t})\subseteq S_{u}$. Thus, if $S_{u}$ is non-empty, then
$|S_{u}|\geq|\Sigma_{t}(A\cap d\mathbb{Z}_{t})|$. ∎

We can now prove Lemma 5.6. We recall the statement, that if $t\in[y/v,2y/v)$
and $A$ is a subset of $Y_{v}$ of size $z/(16\ell)$ which is
$y^{1/4}/(128\ell)$-diverse, then $|\Sigma_{t}(A)|\geq\min(\xi,32/\ell)t$.

###### Proof of Lemma 5.6.

We consider the following iterative process. Let $\Sigma_{t}(0)=\\{0\\}$ and
$A_{0}=A$. At each step $i\geq 1$, we pick an element $a_{i}$ in $A_{i-1}$ and
let $\Sigma_{t}(i)=\Sigma_{t}(i-1)\cup(\Sigma_{t}(i-1)+a_{i})$ and
$A_{i}=A_{i-1}\setminus\\{a_{i}\\}$. In particular,
$\Sigma_{t}(i)=\Sigma_{t}(\\{a_{1},\dots,a_{i}\\})\subseteq\Sigma_{t}(A)$ for
all $i\leq|A|$. Let $d_{i}=\gcd(A_{i-1})$. For $i\leq|A|/2$, $A_{i-1}$ is a
subset of $Y_{v}$ of size at least
$\frac{|A|}{2}\geq\frac{z}{32\ell}>64(m/\phi(m))\tau(r,m)\frac{y}{r\log r}$,
where we used (14) and assumed that $r$ is sufficiently large in terms of
$\ell$. Thus, $\\{vx:x\in A_{i-1}\\}$ is a subset of $Y$ of size larger than
$64(m/\phi(m))\tau(r,m)\frac{y}{r\log r}$ whose elements are divisible by
$vd_{i}$. By Lemma 5.3, we obtain $vd_{i}\leq y^{1/16}$ and all elements of
$A_{i-1}$ have the form $qu$ where $u\mid(m/v)$, $u\leq y^{1/16}/v\leq
y^{1/16}$, $d_{i}|u$ and $\gcd(q,W(r)m)=1$. We will run the above process for
at most $|A|/2$ steps, so we may assume that $i\leq|A|/2$ and these
conclusions hold throughout.

For each $i$, we say that step $i$ is either a growth phase, an unsaturated
phase or a saturated phase. Note that the cosets of $d_{i}\mathbb{Z}_{t}$ can
be indexed by elements of $\mathbb{Z}_{d_{i}}$. For each
$u\in\mathbb{Z}_{d_{i}}$, let
$S_{u}=\Sigma_{t}(i-1)\cap(u+d_{i}\mathbb{Z}_{t})$. We say that $i$ is a
growth phase if there exists $u\in\mathbb{Z}_{d_{i}}$ such that $S_{u}$ is
non-empty and has size at most $y^{3/4}$. We say that $i$ is an unsaturated
phase if it is not a growth phase and there exists $u\in\mathbb{Z}_{d_{i}}$
such that $y^{3/4}<|S_{u}|<\frac{\xi t}{d_{i}}$. Finally, if step $i$ is
neither a growth phase nor an unsaturated phase, then it is a saturated phase.

Next we describe how $a_{i}$ is chosen. Let $\Sigma(d,i-1)=\\{\sum_{j\in
S}a_{j}\pmod{t}:S\subseteq[i-1]\cap\\{j:d|a_{j}\\}\\}$. Then $\Sigma(d,i-1)$
is a subset of the subgroup $d\mathbb{Z}_{t}$ of $\mathbb{Z}_{t}$, which can
be identified with $\mathbb{Z}_{t/d}$. We identify $\Sigma(d,i-1)$ with a
subset of $\mathbb{Z}_{t/d}$. Similarly, we can identify $A_{i-1}$ with a
subset of $\mathbb{Z}_{t/d_{i}}$. If $i$ is a growth phase, we pick $a_{i}$
such that $|\Sigma(d_{i},i)|-|\Sigma(d_{i},i-1)|$ is maximized. Otherwise, if
$i$ is not a growth phase, we pick $a_{i}$ such that
$|\Sigma_{t}(i)|-|\Sigma_{t}(i-1)|$ is maximized.

The following claims capture the key steps in the proof.

Claim 1. The number of growth phases among the first $|A|/2$ steps is at most
$(256\ell y^{3/4}/z+\log_{3/2}t+2)(\log_{2}y^{1/16}+1)$.

Claim 2. If $i\leq|A|/2$ is an unsaturated phase, then
$|\Sigma_{t}(i)|-|\Sigma_{t}(i-1)|>2^{12}y/z$.

Claim 2 is the most important step in the proof and will take up most of our
time. However, before proving these claims, let us see how Lemma 5.6 follows
from combining them.

First, suppose that there exists $i\leq|A|/2$ such that $i$ is a saturated
phase. By Lemma 5.8, since $A$ is $y^{1/4}/(128\ell)$-diverse and
$d_{i}<y^{1/4}/(128\ell)$,
$\Sigma_{d_{i}}(\\{a_{1},\dots,a_{i-1}\\})=\Sigma_{d_{i}}(A)=\mathbb{Z}_{d_{i}}$.
Hence, $S_{u}$ is non-empty for all $u\in\mathbb{Z}_{d_{i}}$. Since $i$ is a
saturated phase, we have that $|S_{u}|\geq\frac{\xi t}{d_{i}}$ for all
$u\in\mathbb{Z}_{d_{i}}$, so
$|\Sigma_{t}(i-1)|=\sum_{u\in\mathbb{Z}_{d_{i}}}|S_{u}|\geq\xi t$. Therefore,
$|\Sigma_{t}(A)|\geq|\Sigma_{t}(i-1)|\geq\xi t$, as desired.

Next, suppose that no $i\leq|A|/2$ is a saturated phase. In this case, if
$i\leq|A|/2$ is not a growth phase, it must be an unsaturated phase and, by
Claim 2, we have $|\Sigma_{t}(i)|>|\Sigma_{t}(i-1)|+2^{12}y/z$. Since Claim 1
implies that there are at least $|A|/2-(256\ell
y^{3/4}/z+\log_{3/2}t+2)(\log_{2}y^{1/16}+1)$ unsaturated phases in the first
$|A|/2$ steps and $|A|=z/(16\ell)$, we have

$|\Sigma_{t}(A)|\geq|\Sigma_{t}(|A|/2)|\geq\frac{2^{12}y}{z}\cdot\left(\frac{z}{32\ell}-(256\ell
y^{3/4}/z+\log_{3/2}t+2)(\log_{2}y^{1/16}+1)\right)\geq\frac{2^{12}y}{64\ell}\geq\frac{32t}{\ell},$

as required. ∎

We next give the proofs of Claims 1 and 2, beginning with the simpler of the
two.

###### Proof of Claim 1.

First, we show that in each step $i\leq|A|/2$, if
$|\Sigma(d_{i},i-1)|<|A_{i-1}|/2$, then

$|\Sigma(d_{i},i)|-|\Sigma(d_{i},i-1)|\geq\max_{a\in
A_{i-1}}|(\Sigma(d_{i},i-1)+a)\setminus\Sigma(d_{i},i-1)|\geq|\Sigma(d_{i},i-1)|/2,$
(17)

while if $|A_{i-1}|/2\leq|\Sigma(d_{i},i-1)|\leq y^{3/4}$, then

$|\Sigma(d_{i},i)|-|\Sigma(d_{i},i-1)|\geq\max_{a\in
A_{i-1}}|(\Sigma(d_{i},i-1)+a)\setminus\Sigma(d_{i},i-1)|\geq|A_{i-1}|/8.$
(18)

The first bound (17) follows directly from Lemma 2.6, since the set of
elements $a\in\mathbb{Z}_{t/d_{i}}$ for which

$|(\Sigma(d_{i},i-1)+a)\setminus\Sigma(d_{i},i-1)|<|\Sigma(d_{i},i-1)|/2$

has size at most $2|\Sigma(d_{i},i-1)|<|A_{i-1}|$.

For the second bound (18), assume, for the sake of contradiction, that for
some step $i\leq|A|/2$ where $|A_{i-1}|/2\leq|\Sigma(d_{i},i-1)|\leq y^{3/4}$,
$|\Sigma(d_{i},i)|-|\Sigma(d_{i},i-1)|<|A_{i-1}|/8$. Then, for all $a\in
A_{i-1}$, we have
$|(\Sigma(d_{i},i-1)+a)\setminus\Sigma(d_{i},i-1)|<|A_{i-1}|/8$. Let
$k=\left\lfloor\frac{4|\Sigma(d_{i},i-1)|}{|A_{i-1}|}\right\rfloor$ and let

$T=\\{a\in\mathbb{Z}_{t/d_{i}}:|(\Sigma(d_{i},i-1)+a)\setminus\Sigma(d_{i},i-1)|<|A_{i-1}|/8\\}.$

We have $A_{i-1}\subseteq T$ and $0\in T$. By Lemma 2.7, for any $a\in kT$,

$|(\Sigma(d_{i},i-1)+a)\setminus\Sigma(d_{i},i-1)|<|\Sigma(d_{i},i-1)|/2.$

Hence, by Lemma 2.6, we have $|k(A_{i-1}\cup\\{0\\})|\leq|kT|\leq
2|\Sigma(d_{i},i-1)|$. Using that $vd_{i}\leq y^{1/16}$ and $t\geq y/v$, we
have $|\Sigma(d_{i},i-1)|\leq y^{3/4}<t/(2d_{i})$, so
$|k(A_{i-1}\cup\\{0\\})|<t/d_{i}$. Identified as a subset of
$\mathbb{Z}_{t/d_{i}}$, $A_{i-1}$ is not a subset of any proper subgroup of
$\mathbb{Z}_{t/d_{i}}$ by the definition of $d_{i}$, so $A_{i-1}\cup\\{0\\}$
is not contained in any coset of a proper subgroup of $\mathbb{Z}_{t/d_{i}}$.
Therefore, by Lemma 2.3, we have

$|A_{i-1}\cup\\{0\\}|\leq\frac{2}{k+1}|k(A_{i-1}\cup\\{0\\})|\leq\frac{4|\Sigma(d_{i},i-1)|}{k+1}<\frac{4|\Sigma(d_{i},i-1)|}{4|\Sigma(d_{i},i-1)|/|A_{i-1}|}=|A_{i-1}|,$

a contradiction.

Using (17) and (18), we may quickly complete the proof of Claim 1. Note that,
by Lemma 5.11, for any $u$ such that $S_{u}$ is non-empty,
$|S_{u}|\geq|\Sigma(d_{i},i-1)|$. Thus, if $i$ is a growth phase, then
$|\Sigma(d_{i},i-1)|\leq y^{3/4}$. Note that $d_{i}|d_{i+1}$, so either
$d_{i+1}=d_{i}$ or $d_{i+1}\geq 2d_{i}$. As $d_{i}\leq y^{1/16}$ for
$i\leq|A|/2$, $d_{i}$ can change at most $1+\log_{2}y^{1/16}$ times in the
first $|A|/2$ steps. By (17), if $|\Sigma(d_{i},i-1)|<|A_{i-1}|/2$, then
$|\Sigma(d_{i},i)|-|\Sigma(d_{i},i-1)|\geq|\Sigma(d_{i},i-1)|/2$. Thus, for
each period among the first $|A|/2$ steps where $d_{i}$ remains constant, the
number of steps where $|\Sigma(d_{i},i-1)|<|A_{i-1}|/2$ is at most
$1+\log_{3/2}t$, since, in each such step, $|\Sigma(d_{i},i-1)|$ grows by a
factor of at least $3/2$. For the remaining steps in this period, where
$|A_{i-1}|/2\leq|\Sigma(d_{i},i-1)|\leq y^{3/4}$, (18) implies that
$|\Sigma(d_{i},i)|-|\Sigma(d_{i},i-1)|\geq|A_{i-1}|/8\geq z/(256\ell)$ in each
step, so there are at most $1+256\ell y^{3/4}/z$ more growth phases where
$d_{i}$ stays constant. Thus, the number of growth phases among the first
$|A|/2$ steps in each period where $d_{i}$ stays constant is at most $256\ell
y^{3/4}/z+\log_{3/2}t+2$. Since $d_{i}$ can change at most
$1+\log_{2}y^{1/16}$ times in the first $|A|/2$ steps, there are at most
$(256\ell y^{3/4}/z+\log_{3/2}t+2)(\log_{2}y^{1/16}+1)$ growth phases in the
first $|A|/2$ steps. ∎

Finally, we give the proof of Claim 2, thereby completing the proof of Lemma
5.6.

###### Proof of Claim 2.

Let $i$ be an unsaturated phase with $i\leq|A|/2$. Assume, for the sake of
contradiction, that $|\Sigma_{t}(i)|-|\Sigma_{t}(i-1)|\leq 2^{12}y/z$. Since
$i$ is not a growth phase and not a saturated phase, there exists
$u\in\mathbb{Z}_{d_{i}}$ such that $y^{3/4}<|S_{u}|<\frac{\xi t}{d_{i}}$.

We now view $S_{u}$ and $A_{i-1}$ as subsets of $\mathbb{Z}_{t/d_{i}}$. Note
that, by the definition of $d_{i}$, $A_{i-1}$ is not a subset of any proper
subgroup of $\mathbb{Z}_{t/d_{i}}$. Let $B$ be the set of elements $a$ of
$\mathbb{Z}_{t/d_{i}}$ such that $|(S_{u}+a)\setminus S_{u}|\leq 2^{12}y/z$.
By our choice of $a_{i}$ and our assumption that
$|\Sigma_{t}(i)|-|\Sigma_{t}(i-1)|\leq 2^{12}y/z$, we have $A_{i-1}\subseteq
B$. Since $|S_{u}|<\frac{\xi t}{d_{i}}$ and $|S_{u}|>y^{3/4}>8\cdot 2^{12}y/z$
by (14), we can apply Lemma 5.7 to conclude that either the set $B$ is
contained in a proper subgroup of $\mathbb{Z}_{t/d_{i}}$, $B$ has size at most
$\frac{20(2^{13}y/z)^{1.02}}{|S_{u}|^{0.02}}$ or there is a subgroup $H$ of
$\mathbb{Z}_{t/d_{i}}$ such that $B$ is contained in a set of size at most
$2^{20}y/z$ which is an arithmetic progression of $H$-cosets. The first
possibility cannot hold, since $B$ contains $A_{i-1}$ which is not a subset of
any proper subgroup of $\mathbb{Z}_{t/d_{i}}$. The second possibility also
cannot hold, since

$\frac{20(2^{13}y/z)^{1.02}}{|S_{u}|^{0.02}}\leq\frac{2^{5+13\cdot
1.02}y^{1.005}}{z^{1.02}}<|A|/2\leq|A_{i-1}|\leq|B|,$

where we used the bound $|S_{u}|>y^{3/4}$. Therefore, there is a subgroup $H$
of $\mathbb{Z}_{t/d_{i}}$ such that $A_{i-1}$, identified as a subset of
$\mathbb{Z}_{t/d_{i}}$, is contained in a set $R$ of size at most $2^{20}y/z$
which is an arithmetic progression of $H$-cosets. We can identify the elements
of $\mathbb{Z}_{t/d_{i}}$ with elements in $[y/v,y/v+t)\supseteq[y/v,2y/v)$
which are divisible by $d_{i}$. Under this identification, $R$ is identified
with a set of integers which contains $A_{i-1}$.

By Lemma 5.10, under the above identification, the image of $R$ is contained
in a set of integers of size at most $3|R|$ which is a union of arithmetic
progressions $P_{s}$, $s\in\mathcal{S}$, of integers, each of length at least
$|R|^{1/3}$. We have $|R|\geq|A_{i-1}|\geq z/(32\ell)$. Thus, $A_{i-1}$ is
contained in a set of size at most $2^{22}y/z$ which is a union of arithmetic
progressions $P_{s}$ of integers, each of length at least
$(z/(32\ell))^{1/3}\geq r^{1/16}$, by (14) and (35) from Appendix B.2. Recall
that $A_{i-1}$ is a subset of $[y/v,2y/v)$ consisting of elements of the form
$qu$, where $u|m$, $u\leq y^{1/16}$, $d_{i}|u$ and $\gcd(q,W(r)m)=1$. Note
that each element of the form $qu$ where $u|m$ and $\gcd(q,W(r)m)=1$ is
coprime to $W(r)/\gcd(W(r),m)$. Since each arithmetic progression $P_{s}$ has
length at least $r^{1/16}$ and common difference at most $n$, Lemma 5.9
implies that the number of elements in $P_{s}$ of the form $qu$, where $u|m$,
$u\leq y^{1/16}$ and $\gcd(q,W(r)m)=1$, is at most

$256|P_{s}|\cdot\frac{\log\log n}{\log r}.$

Thus, the number of elements of $R$ (identified with a subset of
$[y/v,y/v+t)$) of the form $qu$, where $u|m$, $u\leq y^{1/16}$ and
$\gcd(q,W(r)m)=1$, is at most

$256(\sum_{s\in\mathcal{S}}|P_{s}|)\cdot\frac{\log\log n}{\log r}\leq
256\cdot\frac{2^{22}y}{z}\cdot\frac{\log\log n}{\log r}.$

We claim that

$256\cdot\frac{2^{22}y}{z}\cdot\frac{\log\log n}{\log r}<\frac{z}{32l}.$

This holds if $r\geq 10\log m/\log\log m$, since then, from (34) in Appendix
B.2, $\tau(r,m)\geq 1/(4\log r)$ and

$\displaystyle\frac{\ell y\log\log n}{z^{2}\log r}$
$\displaystyle\leq\frac{100\ell yr^{2}(\log\log n)}{(\log
r)(m/\phi(m))^{2}y^{2}\tau(r,m)^{2}}\leq\frac{100\ell r^{2}(\log\log n)}{(\log
r)\tau(r,m)^{2}(m/\phi(m))^{2}}\cdot\sqrt{\frac{\tau(r,m)(m/\phi(m))}{15mr}}$
$\displaystyle\leq 100\ell\sqrt{\frac{64r^{3}(\log r)(\log\log
n)^{2}}{m(m/\phi(m))^{3}}}\leq 100\ell\sqrt{64c^{3}}\leq 2^{-40},$

where we used (14) in the first inequality, the definition of $y$ in the
second inequality, the bound $\tau(r,m)\geq 1/(4\log r)$ in the third
inequality, the bound $r\leq c\psi(n,m)=c\frac{m^{1/3}(m/\phi(m))}{(\log
n)^{1/3}(\log\log n)^{2/3}}$ in the fourth inequality and, in the last
inequality, we assumed a sufficiently small choice of $c$ (depending on
$\ell$). Next, assume that $r<10\log m/\log\log m$. In this case, we have that
$r=c{\cal R}(n,m)=c\rho(n,m)$. Furthermore, $m\geq\frac{n^{2}}{(\log n)^{2}}$
as, for $\frac{n^{3/2}(\log\log n)^{1/2}}{(\log n)^{1/2}}\leq
m\leq\frac{n^{2}}{(\log n)^{2}}$,
$r=c\rho(n,m)=\Theta\left(\frac{n^{2}/\phi(m)}{\log(n^{2}/\phi(m))}\right)$ by
Claim B.3, so $r>10\log m/\log\log m$ for sufficiently large $n$,
contradicting our assumption. We also have that
$\tau(r,m)\geq(\phi(m)/m)/(2\log r)$ by (32) in Appendix B.2, so

$\displaystyle\frac{\ell y\log\log n}{z^{2}\log r}$
$\displaystyle\leq\frac{100\ell r^{2}(\log\log n)}{(\log
r)\tau(r,m)^{2}(m/\phi(m))^{2}}\cdot\sqrt{\frac{\tau(r,m)(m/\phi(m))}{15mr}}$
$\displaystyle\leq 100\ell\sqrt{\frac{8r^{3}(\log r)(\log\log n)^{2}}{m}}\leq
100\ell\sqrt{\frac{10^{5}(\log n)^{3}}{n^{2}/(\log n)^{2}}}\leq 2^{-40},$

assuming that $n$ is sufficiently large, where in the third inequality we used
$r<10\log m/\log\log m<20\log n/\log\log n$. Thus, in both cases,

$256\cdot\frac{2^{22}y}{z}\cdot\frac{\log\log n}{\log r}<\frac{z}{32\ell}.$

This is a contradiction since there are at least $\frac{z}{32\ell}$ integers
of the form $qu$ where $u|m,u\leq y^{1/16}$ and $\gcd(q,W(r)m)=1$ contained in
$R$. Hence, in each step $i\leq|A|/2$ which is an unsaturated phase,
$|\Sigma_{t}(i)|$ grows by at least $2^{12}y/z$. ∎

Using Lemma 5.6, we can now give the proof of Lemma 5.5, thus completing our
proof of the lower bound in Theorem 1.6. Again we recall the statement, that
if $\ell=\lceil 32/\xi\rceil$ and $A$ is a subset of $Y_{v}$ of size
$z/(8\ell)$ which is $y^{1/4}/(32\ell)$-diverse, then $|\Sigma(A)|\geq
3yz/(4\ell^{2}v)$ and $\Sigma(A)$ is not a subset of an arithmetic progression
with common difference greater than $1$.

###### Proof of Lemma 5.5.

Using Lemma 5.4, we can partition $A$ into two sets $A_{1},A_{2}$ such that
$|A_{1}|=|A_{2}|=z/(16\ell)$ and $A_{1}$ is $y^{1/4}/(128\ell)$-diverse. By
Lemma 5.6, for each $t$ in $A_{2}$,
$|\Sigma_{t}(A_{1})|\geq\min(\xi,32/\ell)t$. Recall that we chose $\ell=\lceil
32/\xi\rceil$, so $|\Sigma_{t}(A_{1})|\geq 32t/\ell$. Therefore, by repeated
applications of Lemma 2.5,

$|\Sigma(A)|=|\Sigma(A_{1}\cup A_{2})|\geq\sum_{t\in
A_{2}}\frac{32t}{\ell}\geq|A_{2}|\cdot\frac{32y}{\ell
v}>\frac{yz}{\ell^{2}v}.$

Finally, we prove that $\Sigma(A)$ is not contained in an arithmetic
progression with common difference $d$ larger than $1$. Indeed, if $\Sigma(A)$
were contained in an arithmetic progression with common difference $d$ larger
than $1$, then all elements of $\Sigma(A)$ would be in the same congruence
class modulo $d$, which in turn implies that all elements of $A$ would be
divisible by $d$. But this is impossible since $A$ is
$y^{1/4}/(32\ell)$-diverse. ∎

###  5.2 Proof of the upper bound in Theorem 1.6

In this section, we show how to improve on the construction of Alon and Erdős
[2] described in the introduction. We begin with the following simple claim.

######  Claim 5.12.

There exists a positive constant $\kappa$ such that the following holds. For
each positive integer $m$, let $d_{m}$ be the product of all the primes at
most $(\log m)/64$ which are not prime divisors of $m$, where $d_{m}=1$ if the
product is over an empty set. Then, for $m$ sufficiently large, $d_{m}\leq
m^{1/32}$, $\gcd(d_{m},m)=1$ and
$\frac{m}{\phi(m)}\cdot\frac{d_{m}}{\phi(d_{m})}\geq\kappa\log\log m$.

###### Proof.

It is easy to see that $d_{m}\leq m^{1/32}$. Furthermore,

$\displaystyle\frac{m}{\phi(m)}\cdot\frac{d_{m}}{\phi(d_{m})}$
$\displaystyle\geq\prod_{p\leq(\log
m)/64}\frac{p}{p-1}\geq\exp\left(\sum_{p\leq(\log m)/64}\frac{1}{p}\right)$
$\displaystyle\geq\exp(\log\log((\log
m)/64)-\kappa^{\prime})\geq\kappa\log\log m,$

for some absolute constants $\kappa^{\prime},\kappa$. ∎

We are now ready to prove the upper bound in Theorem 1.6. For the sake of easy
reference, we recall the statement, that, for all $n$ sufficiently large and
$m\in[n,\binom{n}{2}]$,

$f(n,m)=O\left({\cal R}(n,m)\right),$

where ${\cal R}(n,m)=\min\left(\psi(n,m),\rho(n,m)\right)$. Here
$\psi(n,m)=\frac{m^{1/3}(m/\phi(m))}{(\log n)^{1/3}(\log\log n)^{2/3}}$ and
$\rho(n,m)$ is the smallest positive integer $\rho$ such that
$\rho\prod_{p|W(\rho)m}(1-1/p)^{-1}\geq n^{2}/\phi(m)$, where $W(\rho)$ is the
product of the first $\rho$ primes. We also recall from the previous
subsection that when $m=O\left(\frac{n^{3/2}(\log\log n)^{1/2}}{(\log
n)^{1/2}}\right)$, we have ${\cal R}(n,m)=\Theta\left(\psi(n,m)\right)$ and
when $m=\Omega\left(\frac{n^{3/2}(\log\log n)^{1/2}}{(\log n)^{1/2}}\right)$,
we have ${\cal R}(m,n)=\Theta(\rho(n,m))$.

###### Proof of the upper bound in Theorem 1.6.

We first consider the case where $m\leq\frac{n^{3/2}(\log\log n)^{1/2}}{(\log
n)^{1/2}}$. Let $r=C\psi(n,m)=\frac{Cm^{1/3}(m/\phi(m))}{(\log
n)^{1/3}(\log\log n)^{2/3}}$ for a sufficiently large constant $C$. Note that
$r\geq\frac{n^{1/3}}{(\log n)^{2/3}}$. Our aim is to construct an $r$-coloring
of $[1,n-1]$ such that the set of subset sums of each color class does not
contain $m$. We will do this in four steps.

Step 1. For $k=2,3,\dots,\frac{r}{2}$, we form a color class
$S_{1}(k)=\\{\lceil\frac{m}{k+1}\rceil,\lceil\frac{m}{k+1}\rceil+1,\dots,\lfloor\frac{m}{k}\rfloor\\}\cap[n-1]$,
while, for $k=1$, we take
$S_{1}(1)=\\{\lceil\frac{m}{2}\rceil,\lceil\frac{m}{2}\rceil+1,\dots,m-1\\}\cap[n-1]$.
As defined, the color classes may overlap, but we can safely assign any
element in the overlap to any color class that includes it. Crucially, no
subset sum of $S_{1}(k)$ can contain $m$, since the sum of at most $k$
elements from $S_{1}(k)$ is less than $m$, while any sum of $k+1$ elements
from $S_{1}(k)$ is larger than $m$. Let $X_{1}=\bigcup_{k=1}^{r/2}S_{1}(k)$.

Step 2. For each of the first $r/4$ primes $p$ which are coprime to $m$, we
form a color class $S_{2}(p)=\\{kp:k\in\mathbb{N}\\}\cap[1,n-1]$, noting that
no subset sum of $S_{2}(p)$ can contain $m$, since each element of
$\Sigma(S_{2}(p))$ is a multiple of $p$. Let $X_{2}=\bigcup_{p\leq
p_{r/4},p\nmid m}S_{2}(p)$.

Step 3. Let $R=[1,n-1]\setminus(X_{1}\cup X_{2})$. The construction in [2]
also uses color classes like those defined in Steps 1 and 2. They then
arbitrarily partition the remaining elements $R$ so that the sum of the
elements in each of the classes is smaller than $m$. For our improvement, we
need to be more careful. Note that elements in the remainder set $R$ are
natural numbers $t\leq\frac{2m}{r}$ such that $t$ is coprime to
$W(r/4)/\gcd(W(r/4),m)$, that is, all prime divisors of $t$ which are at most
$p_{r/4}$ are also prime divisors of $m$. In particular, $t$ is coprime to the
integer $d_{m}$ given by Claim 5.12, since $d_{m}$ has only prime factors at
most $(\log m)/64<r/4$ which are not prime divisors of $m$.

With $\kappa$ also as in Claim 5.12, we next show that there exists a multiple
$d$ of $d_{m}$ such that

$\kappa(\phi(m)/m)r(\log\log n)/64\leq d\leq\kappa(\phi(m)/m)r(\log\log
n)/32,$ (19)

$\gcd(d,m)=1$ and the largest prime factor of $d$ is at most $p_{r/4}$. Let
$x=\frac{\kappa(\phi(m)/m)r\log\log n}{50d_{m}}$. Note that $x\geq\frac{\kappa
r}{100d_{m}\log\log n}>n^{1/4}$, since $r\geq n^{1/3}/(\log n)^{2/3}$ and
$d_{m}\leq m^{1/32}\leq n^{1/16}$. Since $m$ has at most $\log m\leq 2\log n$
distinct prime factors, there exists a prime $p<n^{1/100}$ such that $p$ does
not divide $m$. Let $k$ be the smallest positive integer such that
$x/p^{k}<n^{1/100}$. Then $x/p^{k-1}\in[n^{1/100},n^{2/100}]$ and, by the
prime number theorem, the interval $[(1-1/100)x/p^{k-1},(1+1/100)x/p^{k-1}]$
has at least $10^{-3}n^{1/100}/(\log n)$ primes for sufficiently large $n$.
Thus, there exists a prime $p^{\prime}$ in this interval which does not divide
$m$. Then $p^{\prime}p^{k-1}\in[(1-1/100)x,(1+1/100)x]$ and
$\gcd(p^{\prime}p^{k-1},m)=1$, since $p^{\prime}$ and $p$ are primes which do
not divide $m$. We can now verify that $d=p^{\prime}p^{k-1}d_{m}$ satisfies
(19), $\gcd(d,m)=1$ and the largest prime factor of $d$ is at most
$2n^{2/100}<p_{r/4}$ (noting that all prime factors of $d_{m}$ are at most
$(\log m)/64<2n^{2/100}$). Since $d_{m}|d$, we also have $d/\phi(d)\geq
d_{m}/\phi(d_{m})$. Furthermore, all elements of $R$ are coprime to $d$, since
any element in $R$ is coprime to $W(r/4)/\gcd(W(r/4),m)$, whereas $d$ is
coprime to $m$ and all prime factors of $d$ are at most $p_{r/4}$.

Fix $s\in\mathbb{Z}_{d}^{\times}$. Then there exist $k$ integers congruent to
$s\pmod{d}$ that sum to $m$ only if $sk\equiv m\pmod{d}$. Let $x_{s}$ be the
positive integer in $[d]$ that is congruent to $s^{-1}m\pmod{d}$. Consider now
the color classes

$S_{s,1}=\left\\{t:\,t\in R,t\equiv
s\,(\bmod\,d),t\geq\frac{m}{x_{s}}\right\\},$ $S_{s,2}=\left\\{t:\,t\in
R,t\equiv s\,(\bmod\,d),\frac{m}{d+x_{s}}\leq t<\frac{m}{x_{s}}\right\\}.$

If a sum of $k$ elements in $S_{s,1}$ is equal to $m\pmod{d}$, then $k\geq
x_{s}$. But then the sum of the $k$ elements is larger than $m$. Similarly, if
a sum of $k$ elements in $S_{s,2}$ is equal to $m\pmod{d}$, then $k=x_{s}$ or
$k\geq d+x_{s}$. But the sum of $k$ elements is less than $m$ if $k=x_{s}$ and
larger than $m$ if $k\geq d+x_{s}$. Thus,
$m\notin\Sigma(S_{s,1})\cup\Sigma(S_{s,2})$. Note that in this step we have in
total defined $2\phi(d)$ color classes of the form $S_{s,1}$ and $S_{s,2}$ for
$s\in\mathbb{Z}_{d}^{\times}$.

Step 4. Let
$R^{\prime}=R\setminus(\bigcup_{s\in\mathbb{Z}_{d}^{\times}}(S_{s,1}\cup
S_{s,2})).$ Then all elements of $R^{\prime}$ are less than $m/d$. Thus, if we
arbitrarily partition $R^{\prime}$ into sets of size at most $d$, then no set
contains a subset sum which is equal to $m$. Hence, we need at most
$|R^{\prime}|/d$ colors to color $R^{\prime}$ so that no color class contains
$m$ as a subset sum. Recall that any element in $R^{\prime}$ is coprime to
$W(r/4)/\gcd(W(r/4),m)$. By the second part of Lemma 5.9, applied to the
interval $[1,m/d]$, we have

$\displaystyle|R^{\prime}|$ $\displaystyle\leq 256(m/d)\prod_{p|W(r/4),p\nmid
m}(1-1/p)$ $\displaystyle\leq 256(m/d)\prod_{p|W(r/4)}(1-1/p)\prod_{p|m,p\leq
r/4}(1-1/p)^{-1}$ $\displaystyle<\frac{500m(m/\phi(m))}{d\log r},$

where we used that $r$ is sufficiently large, so that
$\prod_{p|W(r/4)}(1-1/p)\leq 1.1/\log r$, and $\prod_{p|m,p\leq
r/4}(1-1/p)^{-1}\leq m/\phi(m)$. Therefore, the number of color classes used
in Step 4 is at most

$\displaystyle\frac{500m(m/\phi(m))}{d^{2}\log r}$
$\displaystyle\leq\frac{64^{2}\cdot 500m(m/\phi(m))^{3}}{\kappa^{2}r^{2}(\log
r)(\log\log n)^{2}}$ $\displaystyle<\frac{r}{16},$

where the first inequality follows from (19) and in the second inequality we
have assumed that the constant $C$ is chosen sufficiently large.

Combining all four steps, the total number of colors we have used is at most

$\displaystyle\frac{r}{2}+\frac{r}{4}+2\phi(d)+\frac{r}{16}\leq\frac{13r}{16}+\frac{2md}{\kappa\phi(m)\log\log
n}\leq\frac{7r}{8},$

where we have used Claim 5.12, so that $d/\phi(d)\geq
d_{m}/\phi(d_{m})\geq\kappa(\log\log m)\phi(m)/m\geq\kappa(\log\log
n)\phi(m)/m$, and the bound (19). Thus, we can use at most $r$ colors to color
$[1,n-1]$ such that no monochromatic subset sum is equal to $m$, as required.

Next we consider the case $m\in\left[\frac{n^{3/2}(\log\log n)^{1/2}}{(\log
n)^{1/2}},\binom{n}{2}\right]$. Let $r=C\rho(n,m)$, where $C$ is a
sufficiently large absolute constant. We construct the coloring as follows.

Step 1. For each of the first $7r/8$ primes $p$ that do not divide $m$, we
construct a color class $S_{1}(p)=\\{kp:k\in\mathbb{N}\\}$. Let
$X_{1}=\bigcup_{p\leq p_{7r/8},p\nmid m}S_{1}(p)$.

Step 2. Let $R=[1,n-1]\setminus X_{1}$. The set $R$ consists of those integers
less than $n$ which are coprime to $W(7r/8)/\gcd(W(7r/8),m)$. By Lemma 5.9,
the number of elements of $R$ is at most

$\displaystyle 256n\prod_{p|W(7r/8),p\nmid m}(1-1/p)$ $\displaystyle\leq
256n\prod_{p|W(\rho(n,m))m}(1-1/p)\cdot\prod_{p|\gcd(m,W(\rho(n,m)))}(1-1/p)^{-1}$
$\displaystyle\leq 256n(m/\phi(m))\prod_{p|W(\rho(n,m))m}(1-1/p),$

where in the first inequality we used that $7r/8=7C\rho(n,m)/8>\rho(n,m)$,
which holds by choosing the constant $C$ to be sufficiently large, and in the
second inequality we used
$\prod_{p|\gcd(m,W(\rho(n,m)))}(1-1/p)^{-1}\leq\prod_{p|m}(1-1/p)^{-1}=m/\phi(m)$.

Since each element of $R$ is less than $n$, if a color class contains at most
$m/n$ elements, then no sum of elements from the color class can equal $m$.
Thus, we can use at most

$\frac{|R|}{m/n}\leq 256n^{2}/\phi(m)\cdot\prod_{p|W(\rho(n,m))m}(1-1/p)\leq
256\rho(n,m)$

colors to color the elements of $R$ so that no monochromatic subset sum equals
$m$. The second inequality follows from the definition of $\rho(n,m)$, which
is the smallest positive integer such that
$\rho(n,m)\prod_{p|W(\rho(n,m))m}(1-1/p)^{-1}\geq n^{2}/\phi(m)$. Hence, the
total number of colors we used is at most

$\frac{7r}{8}+256\rho(n,m)\leq r,$

assuming that $C$ is a sufficiently large absolute constant. ∎

##  6 Long homogeneous progressions in subset sums

In this section, we prove Theorem 1.9, strengthening Theorem 1.8, Szemerédi
and Vu’s result [40] on arithmetic progressions in subset sums, by showing
that the progression may be taken to be homogeneous. For our application to
the Erdős–Graham problem in Section 7, we will need a somewhat technical
strengthening of this result, for which it will be useful to have the notation

$\Sigma^{[h]}(A)=\left\\{\sum_{s\in S}s:S\subseteq A,|S|\leq h\right\\}.$

The main result of this section, which includes Theorem 1.9 as a special case,
is now as follows. To gain some intuition, we remark that for a typical set
$A$ which is not dominated by multiples of an integer at least $2$, we will
simply have $d=1$.

######  Theorem 6.1.

There exists an absolute constant $C>0$ such that the following holds. For any
subset $A$ of $[n]$ of size $m\geq C\sqrt{n}$, there exists $d\geq 1$ such
that, for $A^{\prime}=\\{x/d\,:\,x\in A,d|x\\}$ and $k=2^{50}n/m$,
$\Sigma^{[k]}(A^{\prime})$ contains an interval of length at least $n$.
Furthermore,

$|A|-|A^{\prime}|\leq 2^{30}(\log n)^{3}+\frac{2^{30}n}{m}.$

Theorem 1.9 immediately follows from Theorem 6.1 by noticing that $\Sigma(A)$
contains the set $\\{dy\,:\,y\in\Sigma^{[k]}(A^{\prime})\\}$, which is a
homogeneous arithmetic progression with common difference $d$.

As a crucial step in the proof of Theorem 6.1, we first show that subsets of
$\mathbb{Z}_{b}$ satisfying a diversity condition have a large set of subset
sums. We will need to use the mod $b$ analogue of $\Sigma^{[h]}(A)$, namely,

$\Sigma_{b}^{[h]}(A)=\left\\{\sum_{s\in S}s\bmod b:S\subseteq A,|S|\leq
h\right\\}.$

######  Lemma 6.2.

Let $b$ be a positive integer. Let $A$ be a subset of $\mathbb{Z}_{b}$ of size
$m\in(80(\log b)^{2},b]$ such that, for each $d|b$ with $d\in[2,4b/m]$, there
are at least $64(\log b)^{2}+8d$ elements in $A$ which are not divisible by
$d$. Let $k=1280b/m$. Then

$|\Sigma_{b}^{[k+1]}(A)|\geq\min(m^{2}/256,b/4).$

###### Proof.

Let $A^{\prime}$ be a uniformly random subset of $A$ of size $3m/4$ and
$A^{\prime\prime}=A\setminus A^{\prime}$. Let ${\cal E}_{1}$ be the event that
for some $d|b$ with $d\in[2,4b/m]$, there are at most $8(\log b)^{2}+d$
elements in $A^{\prime}$ which are not divisible by $d$. Recall that for each
$d|b$ and $d\in[2,4b/m]$, at least $64(\log b)^{2}+8d$ elements of $A$ are not
divisible by $d$. By the Chernoff bound for hypergeometric distributions, the
probability that there are at most $8(\log b)^{2}+d$ elements in $A^{\prime}$
which are not divisible by $d$ is at most $\exp(-64(\log b)^{2}/32)\leq
1/b^{2}$. By taking a union bound over all $d|b$, the probability that ${\cal
E}_{1}$ happens is then at most $1/b<1$. We may therefore fix a choice of
$A^{\prime}$ and $A^{\prime\prime}$ so that ${\cal E}_{1}$ does not hold.

We consider the following iterative process. Let
$\Sigma_{b}(0)=A^{\prime\prime}$ and let $A_{0}=A^{\prime}$. At each step
$i\geq 1$, we pick an element $a_{i}$ in $A_{i-1}$ and let
$A_{i}=A_{i-1}\setminus\\{a_{i}\\}$ and
$\Sigma_{b}(i)=\Sigma_{b}(i-1)\cup(\Sigma_{b}(i-1)+a_{i})$. Observe that the
elements in $\Sigma_{b}(i)$ can be written as the sum of one element in
$A^{\prime\prime}$ and a subset of $A^{\prime}$ of size at most $i$, so
$\Sigma_{b}(i)\subseteq\Sigma_{b}^{[i+1]}(A)$. Let $d_{i}|b$ be such that
$\langle A_{i-1}\rangle=d_{i}\mathbb{Z}_{b}\cong\mathbb{Z}_{b/d_{i}}$, where
$\langle X\rangle$ denotes the subgroup generated by $X$. Note that, by
definition, $d_{i}|d_{j}$ if $i\leq j$. Furthermore, $|A_{i-1}|\leq b/d_{i}$
and $|A_{i-1}|=3m/4-i+1\geq m/4$ for $i\leq m/2$, so $d_{i}\leq 4b/m$ for
$i\leq m/2$. We will run the above process for at most $m/2$ steps, so we only
consider $i\leq m/2$ throughout.

For each $i$, we say that step $i$ is either a growth phase, an unsaturated
phase or a saturated phase. For each
$u\in\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}\cong\mathbb{Z}_{d_{i}}$, let
$S_{u}=\Sigma_{b}(i-1)\cap(u+d_{i}\mathbb{Z}_{b})$. We then say that step $i$
is a growth phase if there exists
$u\in\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}\cong\mathbb{Z}_{d_{i}}$ such that
$S_{u}$ is non-empty and has size at most $|A_{i-1}|/4$. We say that step $i$
is an unsaturated phase if it is not a growth phase and there exists
$u\in\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}$ such that
$\frac{|A_{i-1}|}{4}<|S_{u}|<\frac{b}{4d_{i}}$. Finally, if step $i$ is
neither a growth phase nor an unsaturated phase, then it is a saturated phase.
We remark that if $d_{i}=d$ for all steps $i$ in an interval $[x,y]$, then the
interval can be partitioned into three (possibly empty) intervals such that
the steps in the first interval are all growth phases, the steps in the second
interval are all unsaturated phases and the steps in the third interval are
all saturated phases.

We next discuss how to pick $a_{i}$, which depends on the type of phase. For
$d|b$, let $\Sigma(d,i-1)=\Sigma_{b}(\\{a_{1},\dots,a_{i-1}\\}\cap
d\mathbb{Z}_{b})$. If step $i$ is a growth phase, we pick $a_{i}$ which
maximizes $|\Sigma(d_{i},i)|-|\Sigma(d_{i},i-1)|$. If step $i$ is an
unsaturated or saturated phase, we pick $a_{i}$ which maximizes
$|\Sigma_{b}(i)|-|\Sigma_{b}(i-1)|$.

The following claims record important properties of the process we have
defined.

Claim 1. The first $(\log b)^{2}$ steps are not growth phases.

Proof. Consider $i\leq(\log b)^{2}$. Note that $i\leq m/2$. Since, for each
$d|b$ with $d\in[2,4b/m]$, there are more than $8(\log b)^{2}$ elements in
$A^{\prime}$ which are not divisible by $d$, there must be at least $7(\log
b)^{2}$ elements in $A_{i-1}$ which are not divisible by $d$. Hence,
$d_{i}=1$. Thus, there is only one coset $u$ of $d_{i}\mathbb{Z}_{b}$ in
$\mathbb{Z}_{b}$ and $|S_{u}|\geq|\Sigma_{b}(0)|=m/4\geq|A_{i-1}|/4$, so $i$
is not a growth phase. ∎

Claim 2. There are at most $20(\log b)(\log(4b/m))$ growth phases among the
first $m/2$ steps.

Proof. Suppose that step $i$ is a growth phase. By Lemma 5.11, for
$u\in\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}$, if $S_{u}$ is non-empty, then
$|S_{u}|\geq|\Sigma(d_{i},i-1)|$. Since we are in a growth phase, there is
some $u$ such that $S_{u}$ is non-empty and $|S_{u}|\leq|A_{i-1}|/4$. This
implies that $|\Sigma(d_{i},i-1)|\leq|A_{i-1}|/4$. By Lemma 2.6, the set of
$a\in d_{i}\mathbb{Z}_{b}$ such that
$|(\Sigma(d_{i},i-1)+a)\setminus\Sigma(d_{i},i-1)|\leq\frac{1}{2}|\Sigma(d_{i},i-1)|$
has size at most $2|\Sigma(d_{i},i-1)|\leq|A_{i-1}|/2$. Thus, there exists
$a_{i}\in A_{i-1}$ such that
$|\Sigma(d_{i},i)|\geq\frac{3}{2}|\Sigma(d_{i},i-1)|$. As
$|\Sigma(d_{i},i)|\leq b$ for all $i$, there can be at most $1+\log_{3/2}b$
successive growth phases with $d_{i}=d$. Since $d_{1}\leq d_{2}\leq\dots\leq
d_{m/2}\leq 4b/m$ and $d_{i+1}\geq 2d_{i}$ if $d_{i+1}\neq d_{i}$, $d_{i}$ can
take at most $1+\log_{2}(4b/m)$ distinct values. This shows that there can be
at most $(1+\log_{3/2}b)(1+\log_{2}(4b/m))<20(\log b)(\log(4b/m))$ growth
phases among the first $m/2$ steps. ∎

Claim 3. Let $i$ be an unsaturated phase. Then
$|\Sigma_{b}(i)|-|\Sigma_{b}(i-1)|\geq\frac{|A_{i-1}|}{16}$.

Proof. Note that if $a\in A_{i-1}$, then $a\in d_{i}\mathbb{Z}_{b}$, since
$A_{i-1}\subseteq d_{i}\mathbb{Z}_{b}$. Thus, for each
$u\in\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}$ and $x\in\mathbb{Z}_{b}$, $x+a\in
u+d_{i}\mathbb{Z}_{b}$ if and only if $x\in u+d_{i}\mathbb{Z}_{b}$. Hence,
$(\Sigma_{b}(i-1)+a)\cap(u+d_{i}\mathbb{Z}_{b})=(\Sigma_{b}(i-1)\cap(u+d_{i}\mathbb{Z}_{b}))+a=S_{u}+a$
and
$((\Sigma_{b}(i-1)+a)\setminus\Sigma_{b}(i-1))\cap(u+d_{i}\mathbb{Z}_{b}))=(S_{u}+a)\setminus
S_{u}$. Let $u_{0}$ be such that
$|S_{u_{0}}|=\max_{u:|S_{u}|<b/4d_{i}}|S_{u}|$. We have

$\displaystyle|(\Sigma_{b}(i-1)+a)\setminus\Sigma_{b}(i-1)|$
$\displaystyle=\sum_{u\in\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}}|((\Sigma_{b}(i-1)+a)\setminus\Sigma_{b}(i-1))\cap(u+d_{i}\mathbb{Z}_{b})|$
$\displaystyle=\sum_{u\in\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}}|(S_{u}+a)\setminus
S_{u}|$ $\displaystyle\geq|(S_{u_{0}}+a)\setminus S_{u_{0}}|.$

Let
$k_{i}=1+\left\lfloor\frac{4|S_{u_{0}}|}{|A_{i-1}|}\right\rfloor\in\left[2,\frac{8|S_{u_{0}}|}{|A_{i-1}|}\right]$,
noting that $|S_{u_{0}}|>|A_{i-1}|/4$ since step $i$ is not a growth phase.
Let $P_{i-1}\subseteq d_{i}\mathbb{Z}_{b}$ be the set of elements $a\in
d_{i}\mathbb{Z}_{b}$ such that $|(S_{u_{0}}+a)\setminus
S_{u_{0}}|<\frac{1}{2k_{i}}|S_{u_{0}}|$. Note that $0\in P_{i-1}$ and, by
Lemma 2.7, for any $a\in k_{i}P_{i-1}$, $|(S_{u_{0}}+a)\setminus
S_{u_{0}}|<\frac{1}{2}|S_{u_{0}}|$. Therefore, by Lemma 2.6,
$|k_{i}P_{i-1}|\leq 2|S_{u_{0}}|$. Suppose now that $A_{i-1}\subseteq
P_{i-1}$. Since $d_{i}$ is defined so that $\langle
A_{i-1}\rangle=d_{i}\mathbb{Z}_{b}\cong\mathbb{Z}_{b/d_{i}}$, $A_{i-1}$ is not
a subset of a proper subgroup of $\mathbb{Z}_{b/d_{i}}$ and, since $0\in
P_{i-1}$, $P_{i-1}$ is not contained in a coset of a proper subgroup of
$\mathbb{Z}_{b/d_{i}}$. Thus, by Lemma 2.3 and the fact that
$|k_{i}P_{i-1}|\leq 2|S_{u_{0}}|<\frac{b}{2d_{i}}<|\mathbb{Z}_{b/d_{i}}|$,
$|P_{i-1}|\leq\frac{2|k_{i}P_{i-1}|}{k_{i}}\leq\frac{4}{k_{i}}|S_{u_{0}}|$.
However, by our choice of $k_{i}$, $|A_{i-1}|>\frac{4}{k_{i}}|S_{u_{0}}|$,
which is a contradiction. Therefore, $A_{i-1}\cap P_{i-1}^{c}\neq\emptyset$
and, since $a_{i}$ is chosen so that
$|\Sigma_{b}(i)|-|\Sigma_{b}(i-1)|=|(\Sigma_{b}(i-1)+a_{i})\setminus\Sigma_{b}(i-1)|$
is maximized,

$\displaystyle|(\Sigma_{b}(i-1)+a_{i})\cup\Sigma_{b}(i-1)|$
$\displaystyle\geq|\Sigma_{b}(i-1)|+\frac{1}{2k_{i}}|S_{u_{0}}|$
$\displaystyle\geq|\Sigma_{b}(i-1)|+\frac{|A_{i-1}|}{16|S_{u_{0}}|}|S_{u_{0}}|$
$\displaystyle=|\Sigma_{b}(i-1)|+\frac{|A_{i-1}|}{16}.$

Thus, over any unsaturated phase $i$,
$|\Sigma_{b}(i)|-|\Sigma_{b}(i-1)|\geq\frac{|A_{i-1}|}{16}$. ∎

Claim 4. For each step $i\leq m/2$,
$S_{u}=\Sigma_{b}(i-1)\cap(u+d_{i}\mathbb{Z}_{b})$ is non-empty for every
$u\in\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}$.

Proof. The claim holds trivially if $d_{i}=1$. Assume that $d_{i}>1$. Since
$i\leq m/2$, we have $d_{i}|b$ and $d_{i}\leq 4b/m$. For each $d|d_{i}$ with
$d>1$, we have $d|b$ and $d\in[2,4b/m]$, so $A^{\prime}$ contains at least
$d-1$ elements which are not divisible by $d$. By Lemma 5.8,

$\Sigma_{d_{i}}(\\{a_{1},\dots,a_{i-1}\\})=\Sigma_{d_{i}}(A^{\prime})=\mathbb{Z}_{d_{i}},$

where we used that the elements of
$A^{\prime}\setminus\\{a_{1},\dots,a_{i-1}\\}$ are all divisible by $d_{i}$.
The claim follows upon noting that we can identify
$\mathbb{Z}_{b}/d_{i}\mathbb{Z}_{b}$ with $\mathbb{Z}_{d_{i}}$ and, under this
identification, $S_{u}$ is non-empty if and only if
$u\in\Sigma_{d_{i}}(\\{a_{1},\dots,a_{i-1}\\})$. ∎

We now complete the proof of the lemma using these claims. First, assume that
there is no saturated phase $i$ with $i\leq\min(m/2,k)$. Then, among the first
$\min(m/2,k)$ steps, from Claims 1 and 2, at least $\max(\min(m/2,k)-20(\log
b)(\log(4b/m)),\min((\log b)^{2},k))$ steps are unsaturated phases. Note that
if $k=1280b/m\leq 80(\log b)^{2}$, then $(\log b)^{2}\geq k/80$ and

$\max(\min(m/2,k)-20(\log b)(\log(4b/m)),\min((\log b)^{2},k))\geq\min((\log
b)^{2},k)\geq k/80.$

If $k=1280b/m\geq 80(\log b)^{2}$, then $20(\log b)(\log(4b/m))\leq k/2$ and
$20(\log b)(\log(4b/m))\leq m/4$ by our assumption on $m$, so

$\displaystyle\max(\min(m/2,k)-20(\log b)(\log(4b/m)),\min((\log b)^{2},k))$
$\displaystyle\geq\min(m/2,k)-20(\log b)(\log(4b/m))$
$\displaystyle\geq\min(m/4,k/2).$

In either case, we have

$\max(\min(m/2,k)-20(\log b)(\log(4b/m)),\min((\log
b)^{2},k))\geq\min(m/4,k/80).$

For each step $i$ which is an unsaturated phase, we have, by Claim 3, that
$|\Sigma_{b}(i)|-|\Sigma_{b}(i-1)|\geq|A_{i-1}|/16\geq m/64$. Hence, recalling
that $k=1280b/m$, we get

$|\Sigma_{b}^{[k+1]}(A)|\geq|\Sigma_{b}(\min(m/2,k))|\geq\min\left(\frac{m}{4},\frac{k}{80}\right)\cdot\frac{m}{64}=\min\left(\frac{m^{2}}{256},\frac{b}{4}\right).$

If, instead, there is a saturated phase $i_{0}$ with $i_{0}\leq\min(m/2,k)$,
then, for each $u\in\mathbb{Z}_{b}/d_{i_{0}}\mathbb{Z}_{b}$ with
$S_{u}=\Sigma_{b}(i_{0}-1)\cap(u+d_{i_{0}}\mathbb{Z}_{b})$ non-empty,
$|S_{u}|\geq\frac{b}{4d_{i_{0}}}$. But Claim 4 implies that $S_{u}$ is non-
empty for all $u\in\mathbb{Z}_{b}/d_{i_{0}}\mathbb{Z}_{b}$, so that

$|\Sigma_{b}^{[k+1]}(A)|\geq|\Sigma_{b}(i_{0})|\geq\sum_{u\in\mathbb{Z}_{b}/d_{i_{0}}\mathbb{Z}_{b}}|S_{u}|\geq\frac{b}{4d_{i_{0}}}\cdot
d_{i_{0}}=\frac{b}{4}.$

Hence, the desired conclusion holds in both cases. ∎

Let $\ell=2^{15}$. We say that a subset $A$ of $[n]$ of size $m$ is _nice_ if
the following conditions hold:

  1. 1.

There is no $d\in[2,8\ell n/m]$ such that all but at most $512\ell(\log
n)^{2}+64\ell d$ elements of $A$ are divisible by $d$.

  2. 2.

For each dyadic interval $I_{j}=[2^{j-1},2^{j})\cap[n]$, either $|A\cap
I_{j}|=0$ or $|A\cap I_{j}|\geq 64\ell(\log n)$.

The next lemma says that any large subset of $[n]$ contains a multiple of a
large nice set.

######  Lemma 6.3.

There exists a constant $C>0$ such that the following holds. Let $A$ be a
subset of $[n]$ of size $m\geq Cn^{1/2}$. Then there is an integer $d$ and a
set $A^{\prime}$ of integers such that

  * •

$A^{\prime}$ is nice,

  * •

$\\{dx:x\in A^{\prime}\\}\subseteq A$ and

  * •

$|A|-|A^{\prime}|\leq 1000\ell(\log n)^{3}+\frac{256\ell n}{m}$.

###### Proof.

We consider the following iteration. Let $A_{0}=A$ and $n_{0}=n$. Note that
$A_{0}\subseteq[n_{0}]$. For each $i\geq 0$, if $|A_{i}|<m/2$, we stop. If
$A_{i}$ is nice, we let $A^{\prime}=A_{i}$ and stop. Otherwise,
$A_{i}\subseteq[n_{i}]$ is not nice and $|A_{i}|\geq m/2$. If (1) does not
hold, we let $A_{i+1}=\\{x/d_{i}:x\in A_{i},d_{i}|x\\}$, where
$d_{i}\in[2,8\ell n/|A_{i}|]$ is such that all but at most $512\ell(\log
n)^{2}+64\ell d_{i}$ elements of $A_{i}$ are divisible by $d_{i}$. Note that
$d_{i}\leq 8\ell n/|A_{i}|\leq 16\ell n/m$. Let $n_{i+1}=n_{i}/d_{i}$. Then

$|A_{i+1}|\geq|A_{i}|-512\ell(\log n)^{2}-64\ell d_{i}$

and $A_{i+1}\subseteq[n_{i+1}]$. If (1) holds and (2) does not hold, we remove
all elements in $A_{i}$ which are contained in dyadic intervals $I_{j}$ with
$|A\cap I_{j}|<64\ell(\log n)$ and let $A_{i+1}$ be the resulting set. Let
$n_{i+1}=n_{i}$, so $A_{i+1}\subseteq[n_{i+1}]$, and let $d_{i}=1$. In this
case, $|A_{i+1}|\geq|A_{i}|-64\ell(\log n)(1+\log_{2}n)$.

We show that we will always stop and output a nice set with the required
properties. Let $s$ be the step where we stop. Note that there can be at most
$\log_{2}n$ steps where (1) does not hold. Furthermore, the number of steps
where (2) does not hold is at most one more than the number of steps where (1)
does not hold. Thus, we have

$|A_{s}|\geq|A_{0}|-(1+\log_{2}n)(512\ell(\log n)^{2}+64\ell(\log
n)(1+\log_{2}n))-64\ell\sum_{i\leq s-1:d_{i}>1}d_{i}.$ (20)

Furthermore, $n_{s}=n/(\prod_{i\leq s-1}d_{i})$, so
$A_{s}\subseteq[n/(\prod_{i\leq s-1}d_{i})]$. We also have that

$\displaystyle|A_{s}|$ $\displaystyle\geq|A_{s-1}|-\max(64\ell(\log
n)(1+\log_{2}n),512\ell(\log n)^{2}+64\ell d_{s-1})$
$\displaystyle\geq|A_{s-1}|-512\ell(\log n)^{2}-1024\ell^{2}n/m$
$\displaystyle\geq m/4,$

where we used that $d_{s-1}\leq 16\ell n/m$, $|A_{s-1}|\geq m/2$, $m\geq
C\sqrt{n}$ for a sufficiently large constant $C$ and $n$ is sufficiently
large. Hence,

$\prod_{i\leq s-1}d_{i}\leq n/|A_{s}|\leq 4n/m.$

Since $d_{i}\geq 2$ for each $i\leq s-1$ with $d_{i}>1$, we have $\sum_{i\leq
s-1:d_{i}>1}d_{i}\leq\prod_{i\leq s-1}d_{i}\leq 4n/m$. Hence, combining with
(20),

$|A_{s}|\geq|A_{0}|-(1+\log_{2}n)(512\ell(\log n)^{2}+64\ell(\log
n)(1+\log_{2}n))-64\ell\cdot\frac{4n}{m}\geq m-1000\ell(\log
n)^{3}-\frac{256\ell n}{m}\geq\frac{m}{2},$

assuming that $m\geq C\sqrt{n}$ for $C$ sufficiently large and $n$ is
sufficiently large. This implies that the iteration stops at step $s$ because
$A_{s}$ is nice. The set $A^{\prime}=A_{s}$ then satisfies all of the required
properties. ∎

We are now in a position to prove the main result of this section, Theorem
6.1.

###### Proof of Theorem 6.1.

By Lemma 6.3, we can find a nice set $A^{\prime}$ and an integer $d$ such that
$\\{dx:x\in A^{\prime}\\}\subseteq A$ and

$\displaystyle|A|-|A^{\prime}|$ $\displaystyle\leq 1000\ell(\log
n)^{3}+\frac{256\ell n}{m}.$

In particular, $|A^{\prime}|\geq 5|A|/8$ for $n$ sufficiently large. Partition
$A^{\prime}$ into $\ell$ sets $A_{1}^{\prime},\dots,A_{\ell}^{\prime}$ as
follows. Let $A_{<}^{\prime}$ be the set consisting of the $7|A^{\prime}|/8$
smallest elements in $A^{\prime}$ and let $A^{\prime}_{>}$ be the remaining
elements. Partition $A^{\prime}_{<}$ into $\ell$ sets
$A_{<,1}^{\prime},\dots,A_{<,\ell}^{\prime}$, each of size
$|A^{\prime}_{<}|/\ell$, and partition $A^{\prime}_{>}$ into $\ell$ sets
$A_{>,1}^{\prime},\dots,A_{>,\ell}^{\prime}$, each of size
$|A^{\prime}_{>}|/\ell$, uniformly at random. Let
$A_{i}^{\prime}=A_{<,i}^{\prime}\cup A_{>,i}^{\prime}$.

Let $b_{i,1},b_{i,2},\dots,b_{i,|A^{\prime}_{>,i}|}$ be a uniformly random
enumeration of $A^{\prime}_{>,i}$ and we then define two sets
$B_{i,1}=\\{b_{i,1},b_{i,2},\dots,b_{i,|A^{\prime}_{>,i}|/2}\\}$ and
$B_{i,2}=\\{b_{i,|A^{\prime}_{>,i}|/2+1},\dots,b_{i,|A^{\prime}_{>,i}|}\\}$.
Let $k^{\prime}=2560\ell n/m+1$. Theorem 6.1 will follow easily from the next
two claims.

Claim 1. Suppose that $C$ and $n$ are sufficiently large. Then, with
probability at least $3/4$, for all $i\in[\ell]$ and all
$j\in[|A^{\prime}_{>,i}|/2+1,|A^{\prime}_{>,i}|]$,

$|\Sigma_{b_{i,j}}^{[k^{\prime}]}(A^{\prime}_{<,i}\cup
B_{i,1})|\geq\frac{b_{i,j}}{4}.$

Claim 2. Let $M(i)$ be the sum of the largest $k^{\prime}$ elements in
$B_{i,2}$, let $\overline{M}(i)$ be the sum of the largest $2k^{\prime}$
elements in $A^{\prime}_{i}$ and let $M$ be the sum of the largest $2\ell
k^{\prime}$ elements in $A^{\prime}$. Then, with probability at least $3/4$,
for all $i\in[\ell]$,

$M(i)\geq\frac{M}{8\ell}$

and

$\overline{M}(i)\leq\frac{4M}{\ell}.$

Before proving these claims, we show how to complete the proof of Theorem 6.1
assuming that their conclusions both hold, which happens with probability at
least $1/2$. For any subset $J$ of
$[|A^{\prime}_{>,i}|/2+1,|A^{\prime}_{>,i}|]$ of size $k^{\prime}$, let
$J=\\{j_{1},j_{2},\dots,j_{k^{\prime}}\\}$ for
$j_{1}<j_{2}<\dots<j_{k^{\prime}}$. A straightforward adaptation of Lemma 2.5
shows that for any set of integers $A$ and any integer $m\notin A$, we have
$|\Sigma^{[h+1]}(A\cup\\{m\\})|\geq|\Sigma^{[h]}(A)|+|\Sigma_{m}^{[h]}(A)|$.
For each $v\leq k^{\prime}$, apply this statement with $h=k^{\prime}+v-1$,
$m=b_{i,j_{v}}$ and $A=A^{\prime}_{<,i}\cup
B_{i,1}\cup\\{b_{i,j_{1}},\dots,b_{i,j_{v-1}}\\}$ to conclude that

$\displaystyle|\Sigma^{[k^{\prime}+v]}(A^{\prime}_{<,i}\cup
B_{i,1}\cup\\{b_{i,j_{1}},\dots,b_{i,j_{v}}\\})|$
$\displaystyle\geq|\Sigma^{[k^{\prime}+v-1]}(A^{\prime}_{<,i}\cup
B_{i,1}\cup\\{b_{i,j_{1}},\dots,b_{i,j_{v-1}}\\})|+|\Sigma_{b_{i,j_{v}}}^{[k^{\prime}+v-1]}(A^{\prime}_{<,i}\cup
B_{i,1}\cup\\{b_{i,j_{1}},\dots,b_{i,j_{v-1}}\\})|$
$\displaystyle\geq|\Sigma^{[k^{\prime}+v-1]}(A^{\prime}_{<,i}\cup
B_{i,1}\cup\\{b_{i,j_{1}},\dots,b_{i,j_{v-1}}\\})|+|\Sigma_{b_{i,j_{v}}}^{[k^{\prime}]}(A^{\prime}_{<,i}\cup
B_{i,1})|.$

Thus,

$|\Sigma^{[2k^{\prime}]}(A^{\prime}_{<,i}\cup
B_{i})|\geq|\Sigma^{[2k^{\prime}]}(A^{\prime}_{<,i}\cup
B_{i,1}\cup\\{b_{i,j_{1}},\dots,b_{i,j_{k^{\prime}}}\\})|\geq\sum_{v\leq
k^{\prime}}|\Sigma_{b_{i,j_{v}}}^{[k^{\prime}]}(A^{\prime}_{<,i}\cup
B_{i,1})|.$

By Claim 1, we have, for each $v\leq k^{\prime}$, that
$|\Sigma_{b_{i,j_{v}}}^{[k^{\prime}]}(A^{\prime}_{<,i}\cup B_{i,1})|\geq
b_{i,j_{v}}/4$. Thus,

$|\Sigma^{[2k^{\prime}]}(A^{\prime}_{<,i}\cup
B_{i})|\geq\frac{1}{4}\sum_{v\leq k^{\prime}}b_{i,j_{v}}=\frac{1}{4}\sum_{j\in
J}b_{i,j}.$

By choosing $J$ to be the set of indices of the $k^{\prime}$ largest elements
of $B_{i,2}$, we obtain that

$|\Sigma^{[2k^{\prime}]}(A^{\prime}_{i})|\geq\frac{1}{4}M(i).$

Therefore, by Claim 2, we have that, for all $i\in[\ell]$,

$|\Sigma^{[2k^{\prime}]}(A^{\prime}_{i})|\geq\frac{M}{32\ell}\geq\frac{1}{128}\frac{4M}{\ell}.$

Also by Claim 2,
$\Sigma^{[2k^{\prime}]}(A_{i}^{\prime})\subseteq[\overline{M}(i)]\subseteq[4M/\ell]$.
Therefore, by Lemma 2.2 with $q=4M/\ell$ and $n=q/128$,
$\Sigma^{[2k^{\prime}]}(A^{\prime}_{1})+\cdots+\Sigma^{[2k^{\prime}]}(A^{\prime}_{\ell})$
contains an interval of length at least

$\frac{1}{256}\cdot\frac{4M}{\ell}\cdot\ell=\frac{1}{64}M\geq\frac{1}{128}\ell
k^{\prime}m>n,$

where we used that $M$ is the sum of the largest $2\ell
k^{\prime}<|A^{\prime}|/2$ elements of $A^{\prime}$, so that $M\geq 2\ell
k^{\prime}|A^{\prime}|/2>\ell k^{\prime}m/2$, the bound
$k^{\prime}\geq\frac{2560\ell n}{m}$ and $\ell=2^{15}$. Thus, $\Sigma^{[2\ell
k^{\prime}]}(A^{\prime})$ contains an interval of length at least $n$. ∎

###### Proof of Claim 1.

Assume that, for some $i\in[\ell]$ and
$j\in[|A^{\prime}_{>,i}|/2+1,|A^{\prime}_{>,i}|]$,

$|\Sigma_{b_{i,j}}^{[k^{\prime}]}(A^{\prime}_{<,i}\cup
B_{i,1})|<\min\left(\frac{m^{2}}{1024\ell^{2}},\frac{b_{i,j}}{4}\right).$ (21)

Note that the size of the set $A^{\prime}_{<,i}\cup B_{i,1}$, considered as a
subset of $\mathbb{Z}_{b_{i,j}}$, is at least
$\frac{7|A^{\prime}|}{8\ell}>\frac{m}{2\ell}$ and at most
$\frac{|A^{\prime}|}{\ell}<\frac{m}{\ell}$, since all elements of
$A^{\prime}_{<,i}$ are smaller than $b_{i,j}$ and, hence, are distinct modulo
$b_{i,j}$. But then, since $\frac{m}{2\ell}>80(\log b_{i,j})^{2}$, Lemma 6.2
with $b=b_{i,j}$ and $A=A^{\prime}_{<,i}\cup B_{i,1}$ implies that if (21)
holds, there must be some $d\in[2,8\ell n/m]$ such that all but at most
$64(\log n)^{2}+8d$ elements of $A^{\prime}_{<,i}\cup B_{i,1}$ are divisible
by $d$.

Since $A^{\prime}$ is nice, for each $d\in[2,8\ell n/m]$, at least
$512\ell(\log n)^{2}+64\ell d$ elements of $A^{\prime}$ are not divisible by
$d$. By the pigeonhole principle, we obtain that, for each $d\in[2,8\ell
n/m]$, either $A^{\prime}_{>}$ or $A^{\prime}_{<}$ contains at least
$256\ell(\log n)^{2}+32\ell d$ elements not divisible by $d$.

Note that $A^{\prime}_{<,i}$ is distributed as a uniformly random subset of
$A^{\prime}_{<}$ of size $|A^{\prime}_{<}|/\ell$ and $B_{i,1}$ is distributed
as a uniformly random subset of $A^{\prime}_{>}$ of size
$|A^{\prime}_{>}|/(2\ell)$. Consider the event ${\cal E}(i)$ that, for some
$d\in[2,8\ell n/m]$, $A^{\prime}_{<,i}\cup B_{i,1}$ contains at most $64(\log
n)^{2}+8d$ elements which are not divisible by $d$. By the argument of Lemma
5.4 and a union bound over all $d\leq 8\ell n/m\leq n$, ${\cal E}(i)$ happens
with probability at most $n\exp(-256\ell(\log n)^{2}/(16\ell))<1/n$. Thus, by
a union bound over all $i\in[\ell]$, for sufficiently large $n$, the
probability of the event $\bigcup_{i\in[\ell]}{\cal E}(i)$ is at most $1/4$.

By our earlier observations, (21) cannot hold under the complement of the
event $\bigcup_{i\in[\ell]}{\cal E}(i)$, so, provided $m\geq C\sqrt{n}$ for
sufficiently large $C$,

$|\Sigma_{b_{i,j}}^{[k^{\prime}]}(A^{\prime}_{<,i}\cup
B_{i,1})|\geq\min\left(\frac{m^{2}}{1024\ell^{2}},\frac{b_{i,j}}{4}\right)=\frac{b_{i,j}}{4}$

holds for all $i\in[\ell]$ and all
$j\in[|A^{\prime}_{>,i}|/2+1,|A^{\prime}_{>,i}|]$ with probability at least
$3/4$. ∎

###### Proof of Claim 2.

Since $A^{\prime}$ is nice, for each dyadic interval $I_{j}$ in $[n]$, either
$A^{\prime}$ is disjoint from $I_{j}$ or $A^{\prime}$ intersects $I_{j}$ in at
least $64\ell(\log n)$ elements. Note that there exists $j_{0}$ such that the
dyadic intervals $I_{j}$ which intersect $A^{\prime}$ have at least
$64\ell(\log n)$ common elements with $A^{\prime}_{>}$ for $j>j_{0}$,
$|I_{j_{0}}\cap A^{\prime}_{>}|<64\ell(\log n)$ and $I_{j}\cap
A^{\prime}_{>}=\emptyset$ for $j<j_{0}$. As in the proof of Lemma 5.4,
Chernoff’s inequality for hypergeometric distributions implies that the
probability $|A^{\prime}_{>,i}\cap I_{j}|>2|A^{\prime}_{>}\cap I_{j}|/\ell$ is
at most $\exp(-|A^{\prime}_{>}\cap I_{j}|/(3\ell))\leq\exp(-2\log n)$.
Similarly, the probability that $|B_{i,2}\cap I_{j}|<|A^{\prime}_{>}\cap
I_{j}|/(4\ell)$ is at most $\exp(-|A^{\prime}_{>}\cap
I_{j}|/(32\ell))\leq\exp(-2\log n)$. Thus, by a union bound, with probability
at least $3/4$, for each $i\in[\ell]$ and $j>j_{0}$,

$|B_{i,2}\cap I_{j}|\geq\frac{1}{4\ell}|A^{\prime}_{>}\cap I_{j}|$ (22)

and

$|A^{\prime}_{>,i}\cap I_{j}|\leq\frac{2}{\ell}|A^{\prime}_{>}\cap I_{j}|.$
(23)

Assume now that (22) and (23) hold for all $i\in[\ell]$ and $j>j_{0}$. Note
that since $k^{\prime}=2560\ell n/m+1$ and $m\geq C\sqrt{n}$, we have
$|A^{\prime}_{>}|>2\ell k^{\prime}+64\ell(\log n)$. Let $X$ be the set
consisting of the largest $2\ell k^{\prime}$ elements of $A^{\prime}_{>}$,
which is the same as the set of the largest $2\ell k^{\prime}$ elements of
$A^{\prime}$. Observe that there is $j_{1}>j_{0}$ such that, for all
$j>j_{1}$, $X\supseteq A^{\prime}_{>}\cap I_{j}$ and, for all $j<j_{1}$,
$X\cap I_{j}=\emptyset$. Since, for each $j\geq j_{1}>j_{0}$ and $i\in[\ell]$,
$|B_{i,2}\cap I_{j}|\geq\frac{1}{4\ell}|A^{\prime}_{>}\cap
I_{j}|\geq\frac{1}{4\ell}|X\cap I_{j}|$, we have that $B_{i,2}$ contains a
subset with $\left\lceil\frac{1}{4\ell}|X\cap I_{j}|\right\rceil$ elements in
$I_{j}$ for each $j\geq j_{1}$. We next show that $\sum_{j\geq
j_{1}}\left\lceil\frac{1}{4\ell}|X\cap I_{j}|\right\rceil<k^{\prime}$. Indeed,
let $t$ be the number of indices $j\geq j_{1}$ such that $X\cap
I_{j}\neq\emptyset$. Note that $\sum_{j\geq j_{1}}|X\cap I_{j}|=|X|=2\ell
k^{\prime}>256\ell$ and, for each $j>j_{1}$ for which $X\cap I_{j}$ is non-
empty, $|X\cap I_{j}|=|A^{\prime}_{>}\cap I_{j}|\geq 64\ell(\log n)$. Thus,

$t\leq 1+\frac{|X|}{64\ell(\log n)}<\frac{k^{\prime}}{16}.$ (24)

Therefore,

$\sum_{j\geq j_{1}}\left\lceil\frac{1}{4\ell}|X\cap I_{j}|\right\rceil\leq
t+\sum_{j\geq j_{1}}\frac{1}{4\ell}|X\cap
I_{j}|<\frac{k^{\prime}}{16}+\frac{k^{\prime}}{2}<k^{\prime}.$

Since $B_{i,2}$ contains a subset of size less than $k^{\prime}$ with at least
$\left\lceil\frac{1}{4\ell}|X\cap I_{j}|\right\rceil$ elements in $I_{j}$ for
each $j\geq j_{1}$ and $M(i)$ is the sum of the $k^{\prime}$ largest elements
of $B_{i,2}$, one has

$M(i)\geq\sum_{j\geq j_{1}}2^{j-1}\cdot\frac{1}{4\ell}|X\cap
I_{j}|=\frac{1}{8\ell}\sum_{j\geq j_{1}}2^{j}\cdot|X\cap
I_{j}|\geq\frac{M}{8\ell}.$

We also have $|A^{\prime}_{>,i}\cap
I_{j}|\leq\frac{2}{\ell}|A^{\prime}_{>}\cap I_{j}|=\frac{2}{\ell}|X\cap
I_{j}|$ for all $j>j_{1}$. Moreover,

$\sum_{j\geq j_{1}}\left\lfloor\frac{2}{\ell}|X\cap
I_{j}|\right\rfloor\geq\sum_{j\geq j_{1}}\frac{2}{\ell}|X\cap I_{j}|-t\geq
4k^{\prime}-\frac{k^{\prime}}{16}>2k^{\prime},$

where we used the bound (24). Thus, there exists a set of size at least
$2k^{\prime}$ containing $\left\lfloor\frac{2}{\ell}|X\cap
I_{j}|\right\rfloor$ elements in $I_{j}$ for each $j\geq j_{1}$ such that the
elements of this set dominate the $2k^{\prime}$ largest elements of
$A^{\prime}_{>,i}$. Hence,

$\overline{M}(i)\leq\sum_{j\geq j_{1}}2^{j}\cdot\frac{2}{\ell}|X\cap
I_{j}|\leq\frac{4M}{\ell},$

completing the proof of Claim 2. ∎

Both Sárközy [35] and Szemerédi and Vu [41] also state results which apply to

$\Sigma^{(h)}(A)=\left\\{\sum_{s\in S}s:S\subseteq A,|S|=h\right\\},$

the set of subset sums formed by adding exactly $h$ distinct elements from
$A$. By a small modification of our proof, we can also derive the following
variant of Theorem 6.1 that applies in this context.

######  Theorem 6.4.

There exists an absolute constant $C>0$ such that the following holds. For any
subset $A$ of $[n]$ of size $m\geq C\sqrt{n}$, there exists $d\geq 1$ and
$r\in[0,d-1]$ such that, for $A^{\prime}=\\{(x-r)/d\,:\,x\in A,d|(x-r)\\}$ and
$k\geq Cn/m$, $\Sigma^{(k)}(A^{\prime})$ contains an interval of length at
least $n$. Furthermore,

$|A|-|A^{\prime}|\leq C((\log n)^{3}+n/m).$

That is, if $A\subset[n]$ has size $m\geq C\sqrt{n}$ and $k\geq Cn/m$, then
$\Sigma^{(k)}(A)$ contains an arithmetic progression of length at least $n$.
Since we do not need this variant and the proof is rather similar to that of
Theorem 6.1, we omit the details.

Instead, we conclude the section by proving Corollary 1.10, that there is a
constant $C$ such that $H(n)$ and $h(n)$ are both at most $C\sqrt{n}$, where
we recall that $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)$ is the size of the largest non-averaging subset of $[n]$.

###### Proof of Corollary 1.10.

For the bound on $H(n)$, we need to show that for any two subsets
$S_{1},S_{2}\subset[n]$, each of size $m\geq C\sqrt{n}$, there are non-empty
subsets $S_{1}^{\prime}\subset S_{1}$ and $S_{2}^{\prime}\subset S_{2}$ such
that $\sum_{s_{1}\in S^{\prime}_{1}}s_{1}=\sum_{s_{2}\in
S^{\prime}_{2}}s_{2}$. To this end, order the elements of $S_{1}\cup S_{2}$ in
increasing order and let $M$ be the median. Without loss of generality, we may
assume that the smallest $m/2$ elements from $S_{1}$ are each at most $M$ and
the largest $m/2$ elements from $S_{2}$ are each at least $M$. Let
$R_{1}\subset S_{1}$ consist of the smallest $m/2$ elements from $S_{1}$ and
$R_{2}\subset S_{2}$ consist of the largest $m/2$ elements of $S_{2}$.

Applying Theorem 6.1 to $R_{1}$, we see that, provided $C$ is sufficiently
large, $\Sigma^{[k]}(R_{1})$ with $k=2^{52}n/m$ contains a homogeneous
arithmetic progression $P$ of common difference $d\leq 4M/m$ and length at
least $2n$ whose minimum element is at most $kM$. Note now, by the pigeonhole
principle, that any $d$ element sequence contains a subsequence (consisting of
consecutive terms) whose sum is divisible by $d$. We may therefore partition
$R_{2}$ greedily into subsets $T_{1}\cup\cdots\cup T_{s}$, each of size at
most $d$, such that for each $i<s$ the sum of the elements in $T_{i}$ is a
multiple of $d$. Note that the sum of the elements in any $T_{i}$ is at most
$dn$, while the sum of all the elements in $R_{2}\setminus T_{s}$ is at least
$(m/2-d)M\geq kM$. It therefore follows that, for some $j$, the sum
$\sum_{i=1}^{j}\sum_{t\in T_{i}}t$, which is a sum of elements from $S_{2}$,
lies in the homogeneous arithmetic progression $P$.

For the bound on $h(n)$, we apply Straus’ inequality $h(n)\leq 2H(n)+2$ (see
[39]), whose proof we include for completeness. Indeed, suppose that we have a
subset of $[n]$ of size $p=2H(n)+3$, say $\\{a_{1},a_{2},\dots,a_{p}\\}$ with
$a_{1}<a_{2}<\dots<a_{p}$. Writing $q=H(n)+2$, we see that $a_{q}$ is the
median element and the sets $\\{a_{q}-a_{i}:1\leq i<q\\}$ and
$\\{a_{j}-a_{q}:q<j\leq p\\}$ are both subsets of $[n]$ of size $H(n)+1$.
Therefore, by the definition of $H(n)$, there must be sets $I\subset[q-1]$ and
$J\subset[q+1,p]$ such that $\sum_{i\in I}(a_{q}-a_{i})=\sum_{j\in
J}(a_{j}-a_{q})$. Rearranging, we see that $a_{q}=\frac{1}{|I|+|J|}\sum_{i\in
I\cup J}a_{i}$, so the set is not non-averaging. ∎

##  7 Subsets avoiding a given subset sum

Recall that $g(n,m)$ is the maximum size of a subset of $[n]$ with no subset
sum equal to $m$. Using the results of Section 6, we now prove Theorem 1.7,
giving the precise value of $g(n,m)$. Theorem 1.7 states that there is a
constant $C$ such that if $m\in\left[Cn(\log n),\frac{n^{2}}{12(\log
n)^{2}}\right]$, then

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

where $\textrm{snd}(m)$ is the smallest positive integer which is not a
divisor of $m$. Moreover, if $m\in\left[\frac{n^{2}}{12(\log
n)^{2}},\binom{n+1}{2}\right]$, then
$g(n,m)=\max\left(s(n,m),(1+o(1))\sqrt{2m}\right)$.

###### Proof of Theorem 1.7.

We consider the cases $m\leq\frac{n^{2}}{12(\log n)^{2}}$ and
$m>\frac{n^{2}}{12(\log n)^{2}}$ separately.

Case 1. $Cn(\log n)\leq m\leq\frac{n^{2}}{12(\log n)^{2}}$ for $C$
sufficiently large.

Let $A\subseteq[n]$ be such that $m\notin\Sigma(A)$. Assume that $|A|\geq
s(n,m)+1$. We claim that $\textrm{snd}(m)\leq 1.01\log m$ for $m$ sufficiently
large. Indeed, if $\textrm{snd}(m)>1.01\log m$, then
$m\geq\textrm{lcm}(1,2,\dots,1.01\log m)$. It is easy to see that
$\textrm{lcm}(1,2,\dots,1.01\log m)=\exp\left(\sum_{x\leq 1.01\log
m}\Lambda(x)\right)$, where $\Lambda$ is the von Mangoldt function given by
$\Lambda(x)=\log p$ if $x=p^{k}$ is a prime power and $\Lambda(x)=0$
otherwise. But, by the prime number theorem, $\sum_{x\leq 1.01\log
m}\Lambda(x)\geq 1.005\log m$ for $m$ sufficiently large, so that
$m\geq\textrm{lcm}(1,2,\dots,1.01\log m)\geq\exp(1.005\log m)$, a
contradiction. Thus, $\textrm{snd}(m)\leq 1.01\log m\leq 2.02\log n$ and, in
particular, $|A|\geq\frac{n}{2.02\log n}$.

Let $A^{*}$ be a random subset of $A$ where each element is chosen
independently with probability $1/10$. By Hoeffding’s inequality,
$|A|/9\geq|A^{*}|\geq|A|/11$ with high probability. Suppose that $2\leq d\leq
n$ is such that there are at least $(\log n)^{3}$ elements in $A$ which are
not divisible by $d$. Again by Hoeffding’s inequality, the probability that
the number of elements in $A$ which are not divisible by $d$ is more than $20$
times larger than the number of elements in $A^{*}$ which are not divisible by
$d$ is at most $\exp(-(\log n)^{3}/800)$. Thus, by the union bound, the
probability that there exists $d\in[2,n]$ such that there are at least $(\log
n)^{3}$ elements in $A$ which are not divisible by $d$ and the number of
elements in $A$ which are not divisible by $d$ is at least $20$ times larger
than the number of elements in $A^{*}$ which are not divisible by $d$ is at
most $n\exp(-(\log n)^{3}/800)<1/4$. Denote this latter event by ${\cal E}$
and assume from here on that $A^{*}$ has been chosen so that
$|A|/9\geq|A^{*}|\geq|A|/11$ and ${\cal E}$ does not hold.

By Theorem 6.1, there exists $d$ such that, for $A^{\prime}=\\{x/d:\,x\in
A^{*},d|x\\}$, we have $|A^{\prime}|\geq|A^{*}|-2^{30}(\log
n)^{3}-\frac{2^{30}n}{|A^{*}|}$ and $\Sigma^{[k]}(A^{\prime})$ contains an
interval $I$ of length at least $n$ for $k=2^{50}n/h$, where $h=|A^{*}|$. Note
that $|A^{\prime}|\geq|A^{*}|-2^{30}(\log
n)^{3}-\frac{2^{30}n}{|A^{*}|}\geq|A^{*}|-2^{40}(\log n)^{3}$, as
$|A^{*}|\geq\frac{|A|}{11}\geq\frac{n}{22.22\log n}$. Since ${\cal E}$ does
not hold, there are at most $2^{50}(\log n)^{3}$ elements in $A$ which are not
divisible by $d$.

Let $A^{\prime\prime}=\\{x/d:x\in A\setminus A^{*},d|x\\}$. Since
$|A^{*}|\leq|A|/9$ and there are at most $2^{50}(\log n)^{3}$ elements in $A$
which are not divisible by $d$, the size of $A^{\prime\prime}$ is at least
$|A|-|A^{*}|-2^{50}(\log n)^{3}\geq 8|A|/9-2^{50}(\log n)^{3}\geq 0.87|A|$.
Note that the smallest element of $I$ is at most $nk/d\leq
2^{50}\frac{n}{h}\cdot\frac{n}{d}$ and each element in $A^{\prime\prime}$ is
at most $n/d\leq n$. Therefore, by Lemma 2.1,
$\Sigma^{[k+|A^{\prime\prime}|]}(A^{\prime}\cup A^{\prime\prime})$ contains
the interval $[2^{50}\frac{n}{h}\cdot\frac{n}{d},\sum_{x\in
A^{\prime\prime}}x)$. We have

$\sum_{x\in
A^{\prime\prime}}x\geq\frac{|A^{\prime\prime}|^{2}}{2}\geq\frac{|A|^{2}}{2.7}\geq\frac{n^{2}}{12(\log
n)^{2}}$

and

$\frac{n}{h}\cdot n\leq 30n(\log n).$

Hence, $\Sigma(A)$ contains all multiples $z$ of $d$ with $2^{60}n(\log n)\leq
z\leq\frac{n^{2}d}{12(\log n)^{2}}$. In particular, if $m\notin\Sigma(A)$,
then $d\nmid m$. Thus, $d\geq\textrm{snd}(m)$. Recall that at most
$2^{50}(\log n)^{3}$ elements of $A$ are not divisible by $d$. Therefore, if
$d\geq\textrm{snd}(m)+1$, then

$|A|\leq 2^{50}(\log n)^{3}+\left\lfloor\frac{n}{d}\right\rfloor\leq
2^{50}(\log
n)^{3}+\frac{n}{\textrm{snd}(m)+1}<\frac{n}{\textrm{snd}(m)}-\frac{n}{4\textrm{snd}(m)^{2}}<s(n,m),$

a contradiction. Thus, $d=\textrm{snd}(m)$.

Since
$|A|\geq\left\lfloor\frac{n}{\textrm{snd}(m)}\right\rfloor+\textrm{snd}(m)-1$
and at most $\left\lfloor\frac{n}{\textrm{snd}(m)}\right\rfloor$ elements in
$A$ are divisible by $d$, there exist at least $d-1$ elements in $A$ which are
not divisible by $d$. Let $\bar{A}$ be a set of $d-1$ such elements. Note that
$\bar{A}$ is disjoint from $\\{dx:x\in A^{\prime}\cup A^{\prime\prime}\\}$. By
Lemma 5.8, $\Sigma_{d}(\bar{A})$ contains a non-zero subgroup
$d^{\prime}\mathbb{Z}_{d}$ of $\mathbb{Z}_{d}$. Since $d=\textrm{snd}(m)$,
$d^{\prime}|m$ for any $d^{\prime}|d$ and $d^{\prime}\neq d$. Thus, there
exists a subset of $\bar{A}$ whose sum $y$ is congruent to $m$ modulo $d$.
Furthermore, $y$ is at most $dn$ since $|\bar{A}|=d-1$ and all elements of
$\bar{A}$ are at most $n$. Noting that $d\leq 4\log n$, we have $m-y\geq
Cn(\log n)-nd\geq 2^{60}n(\log n)$ for sufficiently large $C$. We also have
$m-y\leq m\leq\frac{n^{2}}{12(\log n)^{2}}$. Hence, $m-y\in\Sigma(\\{dx:x\in
A^{\prime}\cup A^{\prime\prime}\\})$, so $m\in\Sigma(\\{dx:x\in A^{\prime}\cup
A^{\prime\prime}\\}\cup\bar{A})$. Thus, if $|A|\geq s(n,m)+1$, then
$m\in\Sigma(A)$. Hence, $g(n,m)\leq s(n,m)$. Since we already noted in the
introduction that $g(n,m)\geq s(n,m)$, this completes the proof in this case.

Case 2. $\frac{n^{2}}{12(\log n)^{2}}\leq m\leq\binom{n+1}{2}$.

Let $A\subseteq[n]$ be such that $m\notin\Sigma(A)$. Assume that

$|A|\geq 1+\max\left(s(n,m),\sqrt{2m}(1+2^{50}(\log n)^{2}/n^{1/3})\right).$

Let $A^{*}$ be a random subset of $A$ where each element is chosen
independently with probability $n^{-1/3}$. By Hoeffding’s inequality,
$0.9|A|/n^{1/3}\leq|A^{*}|\leq 1.1|A|/n^{1/3}$ with high probability. As in
the case above, we can again define an event ${\cal E}$, in this case that
there exists $d\in[2,n]$ such that there are at least $n^{1/3}(\log n)^{2}$
elements in $A$ which are not divisible by $d$ and the number of elements in
$A$ which are not divisible by $d$ is at least $2n^{1/3}$ times larger than
the number of elements in $A^{*}$ which are not divisible by $d$, and show
that it happens with probability at most $1/4$. We now fix $A^{*}$ with
$0.9|A|/n^{1/3}\leq|A^{*}|\leq 1.1|A|/n^{1/3}$ such that ${\cal E}$ does not
hold.

By Theorem 6.1, there exists $d$ such that, for $A^{\prime}=\\{x/d:\,x\in
A^{*},d|x\\}$, we have $|A^{\prime}|\geq|A^{*}|-2^{30}(\log
n)^{3}-\frac{2^{30}n}{|A^{*}|}$ and $\Sigma(A^{\prime})$ contains an interval
$I$ of length at least $n$. Note that $|A|>s(n,m)\geq\frac{n}{2.02\log n}$, so
$|A^{*}|\geq\frac{0.9|A|}{n^{1/3}}\geq\frac{0.4n^{2/3}}{\log n}$ and
$|A^{\prime}|\geq|A^{*}|-2^{30}(\log
n)^{3}-\frac{2^{30}n}{|A^{*}|}\geq|A^{*}|-2^{40}n^{1/3}(\log n)$. Since ${\cal
E}$ does not hold, there are at most $2^{41}n^{2/3}(\log n)$ elements of $A$
which are not divisible by $d$.

Since $|A|\geq s(n,m)+1$, we must again have $d\leq\textrm{snd}(m)$. If
$d=\textrm{snd}(m)$, then, as above, we can find at most $d-1$ elements of $A$
which are not divisible by $d$ and whose sum is congruent to $m$ modulo $d$.
If $d<\textrm{snd}(m)$, then $d|m$. In either case, there is a (possibly
empty) sum $y$ of at most $d-1$ elements of $A$ not divisible by $d$ such that
$d|(m-y)$. Therefore, to show that $m\in\Sigma(A)$, it suffices to show that
$(m-y)/d\in\Sigma(\\{x/d:x\in A,d|x\\})$.

Note that $\Sigma(A^{\prime})$ contains an interval $I$ where the largest
element of $I$ is at most $\sum_{x\in A^{\prime}}x\leq 1.1n^{5/3}/d$ and each
element in $\\{x/d:x\in A\setminus A^{*},d|x\\}$ is at most $n/d$. By Lemma
2.1, $\Sigma(\\{x/d:x\in A,d|x\\})$ contains the interval
$[1.1n^{5/3}/d,\sum_{z\in A\setminus A^{*},d|z}z/d]$. The number of elements
in $A\setminus A^{*}$ which are divisible by $d$ is at least
$|A|-|A^{*}|-2^{41}n^{2/3}(\log n)\geq|A|-1.1|A|/n^{1/3}-2^{41}n^{2/3}(\log
n)\geq|A|(1-2^{42}n^{-1/3}(\log n)^{2})>\sqrt{2m}$. Hence,

$\sum_{z\in A\setminus
A^{*},d|z}z/d\geq\sum_{i=1}^{\lceil\sqrt{2m}\rceil}i\geq m.$

Thus, $\Sigma(\\{x/d:x\in A,d|x\\})$ contains $(m-y)/d$, since
$(m-y)/d\geq(m-dn)/d>1.1n^{5/3}/d$ and $(m-y)/d<m$.

Hence,

$g(n,m)\leq\max\left(s(n,m),\sqrt{2m}(1+2^{50}(\log n)^{2}/n^{1/3})\right).$

Since $g(n,m)\geq s(n,m)$ and $g(n,m)\geq\lfloor\sqrt{2m}\rfloor$ as the
interval $[\lfloor\sqrt{2m}\rfloor-1]$ does not have a subset sum which equals
$m$, we have

$g(n,m)=\max\left(s(n,m),\sqrt{2m}(1+O((\log n)^{2}/n^{1/3}))\right),$

completing the proof. ∎

## References

  * [1] N. Alon, Subset sums, J. Number Theory 27 (1987), 196–205.
  * [2] N. Alon and P. Erdős, Sure monochromatic subset sums, Acta Arith. 74 (1996), 269–272.
  * [3] N. Alon and G. Freiman, On sums of subsets of a set of integers, Combinatorica 8 (1988), 297–306.
  * [4] R. Balasubramanian and P. P. Pandey, On a theorem of Deshouillers and Freiman, European J. Combin. 70 (2018), 284–296.
  * [5] V. Bergelson and A. Leibman, Polynomial extensions of van der Waerden’s and Szemerédi’s theorems, J. Amer. Math. Soc. 9 (1996), 725–753.
  * [6] B. J. Birch, Note on a problem of Erdős, Proc. Cambridge Philos. Soc. 55 (1959), 370–373.
  * [7] A. P. Bosznay, On the lower estimation of non-averaging sets, Acta Math. Hungar. 53 (1989), 155–157.
  * [8] S. A. Burr and P. Erdős, Completeness properties of perturbed sequences, J. Number Theory 13 (1981), 446–455.
  * [9] S. A. Burr and P. Erdős, A Ramsey-type property in additive number theory, Glasgow Math. J. 27 (1985), 5–10.
  * [10] S. A. Burr, P. Erdős, R. L. Graham and W. Li, Complete sequences of sets of integer powers, Acta Arith. 77 (1996), 133–138.
  * [11] J. W. S. Cassels, On the representation of integers as sums of distinct summands taken from a fixed set, Acta Sci. Math. (Szeged) 21 (1960), 111–124.
  * [12] T. Cochrane, M. Ostergaard and C. Spencer, Cauchy–Davenport theorem for abelian groups and diagonal congruences, Proc. Amer. Math. Soc. 147 (2019), 3339–3345.
  * [13] J. M. Deshouillers and G. Freiman, A step beyond Kneser’s theorem for abelian finite groups, Proc. London Math. Soc. 86 (2003), 1–28.
  * [14] P. Erdős, On the representation of large integers as sums of distinct summands taken from a fixed set, Acta. Arith. 7 (1962), 345–354.
  * [15] P. Erdős, Many old and on some new problems of mine in number theory, Congr. Numer. 30 (1981), 3–27.
  * [16] P. Erdős, Miscellaneous problems in number theory, Congr. Numer. 34 (1982), 25–45.
  * [17] P. Erdős, Some new problems and results in number theory, in Number theory (Mysore, 1981), 50–74, Lecture Notes in Math., 938, Springer, Berlin-New York, 1982.
  * [18] P. Erdős, Some problems and results on combinatorial number theory, in Graph theory and its applications: East and West (Jinan, 1986), 132–145, Ann. New York Acad. Sci., 576, New York Acad. Sci., New York, 1989.
  * [19] P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas 2 (1995), 165–186.
  * [20] P. Erdős, Some of my recent problems in combinatorial number theory, geometry and combinatorics, in Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), 335–349, Wiley-Intersci. Publ., Wiley, New York, 1995.
  * [21] P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L’Enseignement Mathématique, 28, Université de Genève, L’Enseignement Mathématique, Geneva, 1980.
  * [22] P. Erdős and A. Sárközy, On a problem of Straus, in Disorder in Physical Systems, 55–66, Oxford Univ. Press, New York, 1990.
  * [23] P. Erdős and E. G. Straus, Nonaveraging sets II, in Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), 405–411, North-Holland, Amsterdam, 1970.
  * [24] J. Folkman, On the representation of integers as sums of distinct terms from a fixed sequence, Canadian J. Math. 18 (1966), 643–655.
  * [25] G. A. Freiman, New analytical results in subset-sum problem, Discrete Math. 114 (1993), 205–218.
  * [26] R. L. Graham, Complete sequences of polynomial values, Duke Math. J. 31 (1964), 275–285.
  * [27] D. S. Gunderson and V. Rödl, Extremal problems for affine cubes of integers, Combin. Probab. Comput. 7 (1998), 65–79.
  * [28] H. A. Helfgott, The ternary Goldbach problem, to appear in Ann. of Math. Stud.
  * [29] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30.
  * [30] V. Lev, Consecutive integers in high-multiplicity sumsets, Acta Math. Hungar. 129 (2010), 245–253.
  * [31] E. Lipkin, On representation of $r$th powers by subset sums, Acta Arith. 52 (1989), 353–365.
  * [32] H. L. Montgomery and R. C. Vaughan, Multiplicative Number Theory I: Classical Theory, Cambridge Studies in Advanced Mathematics, 97, Cambridge University Press, Cambridge, 2007.
  * [33] K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109.
  * [34] K. F. Roth and G. Szekeres, Some asymptotic formulae in the theory of partitions, Quart. J. Math. 5 (1954), 241–259.
  * [35] A. Sárközy, Finite addition theorems II, J. Number Theory 48 (1994), 197–218.
  * [36] A. Sárközy, On finite addition theorems, Astérisque 258 (1999), 109–127.
  * [37] J. Spencer, Suresums, Combinatorica 1 (1981), 203–208.
  * [38] R. Sprague, Über Zerlegungen in $n$-te Potenzen mit lauter verschiedenen Grundzahlen, Math. Z. 51 (1948), 466–468.
  * [39] E. G. Straus, Nonaveraging sets, in Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), 215–222, Amer. Math. Soc., Providence, R.I., 1971.
  * [40] E. Szemerédi and V. H. Vu, Finite and infinite arithmetic progressions in sumsets, Ann. of Math. 163 (2006), 1–35.
  * [41] E. Szemerédi and V. H. Vu, Long arithmetic progressions in sumsets: Thresholds and bounds, J. Amer. Math. Soc. 19 (2006), 119–169.
  * [42] L. Tran, V. H. Vu and P. M. Wood, On a conjecture of Alon, J. Number Theory 129 (2009), 2801–2807.
  * [43] V. H. Vu, Some new results on subset sums, J. Number Theory 124 (2007), 229–233.

##  Appendix A Supplementary results for Section 4

###  A.1 The growth rate of $F$

In Section 4, we consider a sequence of positive integers $F=(f_{n})_{n\geq
1}$ which satisfies $f_{n}=\sum_{i\leq\epsilon n}f_{i}$ for all $n\geq n_{0}$.
Here we establish the asymptotic for $F$ claimed in the introduction.

######  Claim A.1.

Let $F=(f_{n})_{n\geq 1}$ be a sequence of positive integers which satisfies
$f_{n}=\sum_{i\leq\epsilon n}f_{i}$ for all $n\geq n_{0}$. Then
$f_{n}=\exp\left(\left(\frac{1}{2\log(1/\epsilon)}+o(1)\right)(\log
n)^{2}\right)$.

###### Proof.

We first show by induction that there is a constant $C$ for which
$f_{n}\leq\exp\left(\frac{1}{2\log(1/\epsilon)}((\log n)^{2}+C)\right)$ for
all positive integers $n$, which would imply the upper bound in the claim. We
can choose $C$ sufficiently large so that this holds for all
$n\leq\max(n_{0},10/\epsilon)$. Let $m>\max(n_{0},10/\epsilon)$. If
$f_{n}\leq\exp\left(\frac{(\log n)^{2}+C}{2\log(1/\epsilon)}\right)$ for all
$n\leq m-1$, then

$\displaystyle f_{m}$ $\displaystyle=\sum_{i\leq\epsilon m}f_{i}\leq\epsilon
m\cdot\exp\left(\frac{1}{2\log(1/\epsilon)}((\log(\epsilon m))^{2}+C)\right)$
$\displaystyle=\exp\left(\frac{1}{2\log(1/\epsilon)}((\log
m-\log(1/\epsilon))^{2}+C+2\log(1/\epsilon)\log(\epsilon m))\right)$
$\displaystyle\leq\exp\left(\frac{1}{2\log(1/\epsilon)}((\log
m)^{2}+C)\right),$

completing the induction proof of the desired upper bound on $f_{n}$.

We now turn to proving the desired lower bound on $f_{n}$ in the claim. Let
$C^{\prime}=100\log(1/\epsilon)$. Let $\tilde{g}(x)=\exp\left(\frac{(\log
x)^{2}-C^{\prime}\log x\log\log x}{2\log(1/\epsilon)}\right)$. Note that there
is $x_{0}>0$ depending only on $\epsilon$ such that $(\log
x)^{2}-C^{\prime}\log x\log\log x$ is increasing for all $x\geq x_{0}$. Let
$m(\epsilon)$ be the least positive integer such that, for all $m\geq
m(\epsilon)$,

$\epsilon\tilde{g}(m)\leq\tilde{g}(m-1/\epsilon)-\tilde{g}(x_{0}/\epsilon).$

It is easy to verify that such $m(\epsilon)$ exists. Let
$g(x)=\exp\left(\frac{(\log x)^{2}-C^{\prime}\log x\log\log
x-C}{2\log(1/\epsilon)}\right)$, where $C$ is a sufficiently large constant to
be chosen later. We next show by induction that, for an appropriate choice of
$C$, $f_{n}\geq g(n)$ for all $n\geq 2$. We choose $C$ sufficiently large that
the above claim holds for all $n\leq\max(n_{0},x_{0},m(\epsilon))$. Let
$m\geq\max(n_{0},x_{0},m(\epsilon))$. If $f_{n}\geq g(n)$ for all $n\leq m-1$,
then

$\displaystyle f_{m}$ $\displaystyle=\sum_{i\leq\epsilon
m}f_{i}\geq\sum_{i\leq\epsilon m}g(i)$
$\displaystyle\geq\int_{x_{0}}^{\epsilon
m-1}g(x)dx=\int_{x_{0}/\epsilon}^{m-1/\epsilon}\epsilon g(\epsilon y)dy,$

where in the last step we used the change of variable $y=x/\epsilon$. Note now
that

$\displaystyle g^{\prime}(y)$
$\displaystyle=\exp\left(\frac{1}{2\log(1/\epsilon)}((\log
y)^{2}-C^{\prime}\log y\log\log y-C)\right)\cdot\frac{2\log
y-C^{\prime}-C^{\prime}\log\log y}{2y\log(1/\epsilon)}$
$\displaystyle\leq\exp\left(\frac{1}{2\log(1/\epsilon)}\left[(\log
y)^{2}-C^{\prime}\log y\log\log y-C-2\log(1/\epsilon)\log
y+2\log(1/\epsilon)\log(\log y/\log(1/\epsilon))\right]\right).$

Thus,

$\displaystyle g^{\prime}(y)/g(\epsilon y)$
$\displaystyle\leq\exp\left(\frac{1}{2\log(1/\epsilon)}\left[(\log
y)^{2}-C^{\prime}\log y\log\log y-C-2\log(1/\epsilon)\log
y+2\log(1/\epsilon)\log(\log y/\log(1/\epsilon))\right]\right)$
$\displaystyle\qquad\qquad\cdot\exp\left(\frac{1}{2\log(1/\epsilon)}\left[-(\log(\epsilon
y))^{2}+C^{\prime}\log(\epsilon y)\log\log(\epsilon y)+C\right]\right)$
$\displaystyle\leq\exp\left(\frac{1}{2\log(1/\epsilon)}\left[2\log(1/\epsilon)\log(\log
y/\log(1/\epsilon))+C^{\prime}\log(\epsilon)\log\log y\right]\right)$
$\displaystyle\leq\exp(-C^{\prime}(\log\log y)/4)\leq\epsilon^{2},$

where in the last inequality we used the fact that
$C^{\prime}=100\log(1/\epsilon)$. Then

$f_{m}\geq\int_{x_{0}/\epsilon}^{m-1/\epsilon}\epsilon g(\epsilon
y)dy\geq\int_{x_{0}/\epsilon}^{m-1/\epsilon}\frac{g^{\prime}(y)}{\epsilon}dy\geq\frac{g(m-1/\epsilon)-g(x_{0}/\epsilon)}{\epsilon}\geq
g(m),$

where in the last inequality we used the definition of $m(\epsilon)$ and the
fact that $m\geq m(\epsilon)$. This completes the induction. ∎

###  A.2 Proof of Lemma 4.4

In this subsection, we give the proof of Lemma 4.4, which is a key component
in the proof of Theorem 4.3. First, we recall the setting and the statement of
the lemma. Let $\epsilon_{0}>0$ be a sufficiently small constant. Let
$B=(b_{n})_{n\geq 1}$ be an $\epsilon$-friendly sequence. For $j$ sufficiently
large, we choose $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}$
and let $A=(a_{j})_{j\geq 1}$. For small $j$, we choose $a_{j}$ to be an
arbitrary integer in $[b_{j},b_{j+1})$. We let $h(i)$ be the smallest integer
for which $b_{h(i)}\geq 2^{i}$ and $A_{i}=A\cap[b_{h(i)},b_{h(i+1)-1})$.

######  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$.

The proof of this lemma has been consigned to an appendix because of its
similarity to the proof of Lemma 2.8. Indeed, the difference between the two
proofs consists mainly of minor modifications to account for the non-
uniformity in the distribution of the elements of $A_{i}$. However, for
completeness, we give the proof in full, beginning with the following lemma,
which is the analogue of Lemma 3.1 in this context.

######  Lemma A.2.

For a sufficiently large positive constant $C_{0}$, the following holds.
Assume that $\epsilon>0$ is sufficiently small. Let $i$ be sufficiently large
and let $m$ be an integer in $[2^{i},2^{i+1})$ with no prime factor at most
$\epsilon^{-4000}$. If $S$ is a uniformly chosen random subsequence of $A_{i}$
of size $C_{0}i$, then $|\Sigma_{m}(S)|<2^{i-2}$ with probability less than
$\epsilon^{1000C_{0}i}$.

###### Proof.

Let $w=\epsilon^{-4000}$. Denote by $X$ the set of integers
$[b_{h(i)},b_{h(i+1)-1})$ with no prime divisor at most $w$. For each
$j\in[h(i),h(i+1)-1)$, let $X_{j}$ be the set of integers in $[b_{j},b_{j+1})$
with no prime divisor at most $w$. Let $t=h(i+1)-h(i)-1$, which is the number
of intervals $[b_{j},b_{j+1})$ in $[b_{h(i)},b_{h(i+1)-1})$. Note that for
each interval $I$ of integers of sufficient length, the number of elements in
the interval which are coprime to all the primes at most $w$ is
$(\tau+o(1))|I|$, where $\tau=\phi(W)/W$ with $W$ being the product of all
primes at most $w$. Since $B$ is a friendly sequence, we have
$b_{j+1}-b_{j}\leq(b_{j^{\prime}+1}-b_{j^{\prime}})/c$ for all
$j\in[h(i)-1,h(i+1)-1]$ and $j^{\prime}\in[h(i),h(i+1)-2]$. Thus,

$2^{i}\leq b_{h(i+1)}-b_{h(i)-1}\leq(1+2/(ct))(b_{h(i+1)-1}-b_{h(i)}).$

Since $t$ tends to infinity as $i$ tends to infinity, we have that
$b_{h(i+1)-1}-b_{h(i)}\geq\frac{7}{8}2^{i}$ for sufficiently large $i$. Hence,
for large $i$, we have that

$|X|\geq\frac{2^{i}\tau}{2}.$ (25)

Again by properties of friendly sequences, the length of the intervals
$[b_{j},b_{j+1})$ for $j\in[h(i),h(i+1)-1)$ are within a factor $1/c$ of each
other and the minimum length of an interval $[b_{j},b_{j+1})$ with
$j\in[h(i),h(i+1)-1)$ tends to infinity as $i$ tends to infinity. We thus
obtain that all $|X_{j}|$ with $j\in[h(i),h(i+1)-1)$ are within a factor $2/c$
of each other for $i$ sufficiently large. Hence,

$|X_{j}|\geq\frac{c|X|}{2t}.$ (26)

Let ${\cal D}$ be the distribution of a random integer in
$[b_{h(i)},b_{h(i+1)-1})$, where the probability that an element $a\in X_{j}$
is chosen is $\frac{1}{|X_{j}|t}$. Observe that the random sequence $S$ is a
sequence of $C_{0}i$ random integers with distribution ${\cal D}$, subject to
the condition that no two elements come from the same interval
$[b_{j},b_{j+1})$.

Let $q=C_{0}i$. Let $S=(s_{1},s_{2},\dots,s_{q})$. Let
$S_{j}=(s_{1},s_{2},\ldots,s_{j})$ denote the sequence consisting of the first
$j$ elements of $S$. Let $\delta=1/w$. Call $j\in[2,q]$ bad if

  * •

$|\Sigma_{m}(S_{j})|\leq\frac{3}{2}|\Sigma_{m}(S_{j-1})|$ and
$|\Sigma_{m}(S_{j-1})|\leq\frac{2^{i}}{w}$ or

  * •

$|\Sigma_{m}(S_{j})|\leq(1+\delta)|\Sigma_{m}(S_{j-1})|$ and
$\frac{2^{i}}{w}<|\Sigma_{m}(S_{j-1})|<2^{i-2}$.

The following two claims will allow us to complete the proof of the lemma.

Claim 1. The probability that $j$ is bad conditioned on the choice of
$S_{j-1}$ is at most $p:=\frac{16}{cw\tau}$.

Claim 2. If $|\Sigma_{m}(S)|<2^{i-2}$, then all but fewer than $2i$ integers
in $[2,q]$ are bad.

Assuming Claim 1, for any $B\subset[2,q]$, the probability that all elements
in $B$ are bad is at most $p^{|B|}$. By Merten’s third theorem, we have
$\tau=(e^{-\gamma}+o(1))/\log w\geq 1/(2\log w)$ for sufficiently small
$\epsilon$, so

$p\leq\frac{32\log w}{cw}.$ (27)

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

${q\choose q-2i}p^{|B|}={q\choose 2i}p^{|B|}<(eC_{0})^{2i}\left(\frac{32\log
w}{cw}\right)^{C_{0}i-2i}<\epsilon^{1000C_{0}i},$

where in the first inequality we used (27) and in the second inequality we
assume a sufficiently large choice of $C_{0}$ and note that
$w=\epsilon^{-4000}$ with $\epsilon$ sufficiently small. ∎

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

Proof of Claim 1. Fix $S_{j-1}=(s_{1},\ldots,s_{j-1})$. Conditioned on this
choice of $S_{j-1}$, we bound the probability that $j$ is bad. Let $T$ be the
set of $k$ such that $[b_{k},b_{k+1})$ contains at least one of
$s_{1},\ldots,s_{j-1}$. Observe that conditioned on $s_{1},\dots,s_{j-1}$, the
distribution of $s_{j}$ is supported on $\bigcup_{k\in[h(i),h(i+1)-1)\setminus
T}X_{k}$ and, for $x_{k}\in X_{k}$ with $k\in[h(i),h(i+1)-1)\setminus T$, the
conditional probability that $s_{j}$ is equal to $x_{k}$ is

$\frac{1}{|X_{k}|(t-|T|)}\leq\frac{2}{|X_{k}|t}\leq\frac{4}{c|X|},$

where we used (26).

If $|\Sigma_{m}(S_{j-1})|\geq 2^{i-2}$, then $j$ cannot be bad (so the event
that $j$ is bad has probability zero). We may therefore restrict attention to
the two cases $|\Sigma_{m}(S_{j-1})|\leq 2^{i}/w$ and
$2^{i}/w<|\Sigma_{m}(S_{j-1})|<2^{i-2}$.

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

$2|\Sigma_{m}(S_{j-1})|\cdot\frac{4}{c|X|}\leq\frac{16}{cw\tau}=p,$

where in the inequality we used (25).

Suppose now that $2^{i}/w<|\Sigma_{m}(S_{j-1})|<2^{i-2}$. For a positive
integer $D$, let $G_{D}$ be the set of $s$ such that
$|\Sigma_{m}(S_{j-1}\cup\\{s\\})|\leq|\Sigma_{m}(S_{j-1})|+D$. Let
$d=\lfloor\delta|\Sigma_{m}(S_{j-1})|\rfloor$, so $j$ is bad in this case if
and only if $s_{j}\in G_{d}$. Let $k=\lfloor\frac{1}{2\delta}\rfloor$, so
$kd\leq|\Sigma_{m}(S_{j-1})|/2$. By Lemma 2.7, $kG_{d}\subseteq G_{kd}$, so
$\left|kG_{d}\right|\leq|G_{kd}|\leq 2|\Sigma_{m}(S_{j-1})|<2^{i-1}$, 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{2^{i+1}}{w}=2\delta 2^{i}$. 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 2^{i-1}<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 2^{i-1}=2\delta 2^{i}$. Thus, in
either case, conditioned on the choice of $S_{j-1}$, the probability that $j$
is bad, which is the same as the probability that $s_{j}\in G_{d}$, is at most

$|G_{d}|\cdot\frac{4}{c|X|}\leq\frac{16\delta}{c\tau}=p,$

where we again used (25). ∎

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

We are now ready to prove Lemma 4.4.

###### Proof of Lemma 4.4.

By replacing $\epsilon$ with $\min(\epsilon,\epsilon_{0})$, we only need to
prove Lemma 4.4 for $\epsilon\leq\epsilon_{0}$. Thus, by choosing
$\epsilon_{0}$ sufficiently small, it suffices to prove that the following
holds for sufficiently small $\epsilon$. If $i$ is sufficiently large, then
any subset $A_{i}^{\prime}$ of $A_{i}$ with
$|A_{i}^{\prime}|\geq(\epsilon/4)|A_{i}|$ contains a subset
$A_{i}^{\prime\prime}$ with $|A_{i}^{\prime\prime}|\leq C_{1}i$ such that
$\Sigma(A_{i}^{\prime\prime})$ contains every integer in the interval
$[y,2y]$, where $y=C_{2}2^{i}i$.

For a given $C_{1}$ and $i$ sufficiently large, we have that $|A_{i}|\geq
400\epsilon^{-1}C_{1}i$. Consider a random partition of $A_{i}$ into subsets
of size $4\epsilon^{-1}C_{1}i$ and consider a uniform random ordering of each
subset as a sequence of integers. Let the obtained sequences be
$A_{i,1},\dots,A_{i,u}$.

We will show that for an appropriate choice of $C_{1}$, there exists a
positive constant $C_{2}$ such that, with positive probability, the following
event ${\cal E}$ holds. For all $k\leq u$ and all subsequences
$A^{\prime}_{i,k}$ of $A_{i,k}$ of size $(\epsilon/4)|A_{i,k}|$,
$\Sigma(A^{\prime}_{i,k})$ contains the interval $[y,2y]$ for $y=C_{2}2^{i}i$.

Fix $k\leq u$ and fix a subset $I^{\prime}$ of $[4\epsilon^{-1}C_{1}i]$ of
size $C_{1}i$. Let $A^{\prime}_{i,k}$ be the subsequence of $A_{i,k}$
consisting of elements with index in $I^{\prime}$. Let $\ell$ be a constant to
be chosen later. We partition $I^{\prime}$ into a subset $I^{\prime\prime}$ of
size $7C_{1}i/8$ and $\ell$ subsets
$I^{\prime\prime}_{k,1},\dots,I^{\prime\prime}_{k,\ell}$ of equal size such
that each subset in the partition consists of consecutive terms from
$I^{\prime}$. Let $A^{\prime\prime}_{i,k}$ be the elements with index in
$I^{\prime\prime}$ and, for each $j\in[\ell]$, let $S_{k,j}$ be the elements
with index in $I^{\prime\prime}_{k,j}$. Let $J^{\prime}_{k,j}$ be the first
$|I^{\prime\prime}_{k,j}|/2$ elements of $I^{\prime\prime}_{k,j}$ and let
$J^{\prime\prime}_{k,j}$ be the remaining elements. Let $S^{\prime}_{k,j}$ be
the elements with index in $J^{\prime}_{k,j}$ and let $S^{\prime\prime}_{k,j}$
be the elements with index in $J^{\prime\prime}_{k,j}$. Then
$S^{\prime}_{k,j}$ has the same distribution as a random subsequence of
$A_{i}$ of length $|S_{k,j}|/2$. We choose $C_{1}=16\ell C_{0}$, so that
$|S^{\prime}_{k,j}|=C_{0}i$, where $C_{0}$ is the constant defined in Lemma
A.2. By Lemma A.2 and a union bound, we have that
$|\Sigma_{m}(S^{\prime}_{k,j})|\geq 2^{i-2}$ for all $m\in[2^{i},2^{i+1})$
with no prime factor at most $\epsilon^{-4000}$ with probability at least
$1-2^{i}\epsilon^{1000C_{0}i}>1-\epsilon^{800C_{0}i}$, assuming that
$\epsilon$ is sufficiently small. Thus, by another union bound, with
probability at least $1-\ell\epsilon^{800C_{0}i}$,
$|\Sigma_{m}(S^{\prime}_{k,j})|\geq 2^{i-2}$ for all $j\leq\ell$ and all $m\in
S^{\prime\prime}_{k,j}$. By repeated application of Lemma 2.5, we have that

$|\Sigma(S_{k,j})|=|\Sigma(S^{\prime}_{k,j}\cup
S^{\prime\prime}_{k,j})|\geq|S^{\prime\prime}_{k,j}|2^{i-2}\geq\frac{1}{16}2^{i}|A^{\prime}_{i,k}|/(4\ell).$

We also have that $\Sigma(S_{k,j})$ is a subset of the interval
$[0,2^{i}|A^{\prime}_{i,k}|/(4\ell)]$. Furthermore, $\Sigma(S_{k,j})$ is not
contained in any arithmetic progression with common difference greater than
$1$, as otherwise there exists $1<d\leq 16$ such that all elements of
$S_{k,j}$ are divisible by $d$, contradicting the fact that elements of
$A_{i}$ do not have prime factors at most $\epsilon^{-4000}$. Thus, choosing
$\ell=33$, by Lemma 2.2, we have that $S_{k,1}+\ldots+S_{k,\ell}$ contains an
interval of length at least $2^{i}|A^{\prime}_{i,k}|/(4\ell)$. Hence,
$\Sigma(A^{\prime}_{i,k}\setminus A^{\prime\prime}_{i,k})$ contains an
interval $[a,b]$ of length at least $2^{i}|A^{\prime}_{i,k}|/(4\ell)>2^{i+1}$.
Note that $a<b\leq 2^{i-2}|A^{\prime}_{i,k}|$. By Lemma 2.1, we then have that
$\Sigma(A^{\prime}_{i,k})$ contains the interval $[a,b+\sum_{x\in
A^{\prime\prime}_{i,k}}x]\supset[y,2y]$ for
$y=\frac{1}{4}2^{i}|A^{\prime}_{i,k}|=\frac{C_{1}}{4}2^{i}i$. Let
$C_{2}=\frac{C_{1}}{4}$.

By taking a union bound over all possible choices of $I^{\prime}$, the
probability that there exists a subsequence $A^{\prime}_{i,k}$ of $A_{i,k}$ of
size $(\epsilon/4)|A_{i,k}|$ such that $\Sigma(A^{\prime}_{i,k})$ does not
contain the interval $[y,2y]$ for $y=C_{2}2^{i}i$ is at most
${|A_{i,k}|\choose(\epsilon/4)|A_{i,k}|}\ell\epsilon^{800C_{0}i}$. By a union
bound over all $k\leq u$, we then obtain that the event ${\cal E}$ holds with
probability at least

$1-u{|A_{i,k}|\choose(\epsilon/4)|A_{i,k}|}\ell\epsilon^{800C_{0}i}\geq
1-2^{i+7}(4e/\epsilon)^{C_{1}i}\epsilon^{800C_{0}i}\geq
1-\epsilon^{200C_{0}i}>0,$

where we used that $\epsilon$ is sufficiently small, $C_{1}=16\ell C_{0}$ with
$C_{0}$ sufficiently large, $\ell=33$ and $u\leq 2^{i+1}$.

Assume now that the event ${\cal E}$ holds. For any subset $A^{\prime}_{i}$ of
$A_{i}$ such that $|A^{\prime}_{i}|\geq(\epsilon/4)|A_{i}|$, there exists
$k\leq u$ such that $|A^{\prime}_{i}\cap A_{i,k}|\geq(\epsilon/4)|A_{i,k}|$.
Thus, defining $A^{\prime\prime}_{i}$ to be an arbitrary subset of
$A^{\prime}_{i}\cap A_{i,k}$ of size $(\epsilon/4)|A_{i,k}|=C_{1}i$, we have
that $\Sigma(A^{\prime\prime}_{i})$ contains the interval $[y,2y]$ for
$y=C_{2}2^{i}i$, as required. ∎

##  Appendix B Supplementary results for Section 5

###  B.1 Number-theoretic estimates

This short section contains the proofs of some number-theoretic estimates
which were used in Section 5. We will need the following simple lemma.

######  Lemma B.1.

One has

$\frac{m}{\zeta(2)\phi(m)}\leq\prod_{p|m}\left(1+\frac{1}{p}\right)\leq\sum_{u|m}\frac{1}{u}\leq\prod_{p|m}\left(1+\frac{1}{p-1}\right)=\frac{m}{\phi(m)}.$

###### Proof.

By considering the squarefree divisors of $m$, we have

$\sum_{u|m}\frac{1}{u}\geq\prod_{p|m}\left(1+\frac{1}{p}\right).$

On the other hand,

$\sum_{u|m}\frac{1}{u}\leq\prod_{p|m}\left(1+\frac{1}{p}+\frac{1}{p^{2}}+\cdots\right)=\prod_{p|m}\left(1+\frac{1}{p-1}\right).$

Furthermore,

$\prod_{p|m}\left(1+\frac{1}{p}\right)=\prod_{p|m}\left(1+\frac{1}{p-1}\right)\cdot\prod_{p|m}\left(1-\frac{1}{p^{2}}\right)=\frac{m}{\phi(m)}\prod_{p|m}\left(1-\frac{1}{p^{2}}\right)\geq\frac{m}{\zeta(2)\phi(m)}.\qed$

Our first aim is to prove Lemma 5.2, which gives upper and lower bounds on the
number of integers in an interval with certain number-theoretic properties.
The following lemma, of a similar flavor, is a key component in the proof.
Recall that $W(r)=\prod_{i=1}^{r}p_{i}$, where $p_{i}$ is the
$i^{\textrm{th}}$ prime, and
$\tau(r,m)=\phi(W(r)m)/(W(r)m)=\prod_{p|W(r)m}(1-1/p)$.

######  Lemma B.2.

Let $r$, $n$ and $m$ be positive integers such that $m\in[n,\binom{n}{2}]$,
$r\leq n$ and $r$ is sufficiently large. For any interval $I=[x,2x)$ with
$x\geq n^{1/6}$, the number of integers in $I$ which are coprime to $W(r)m$ is
at most $8\tau(r,m)x$. If also $x\geq r^{1.5}$, then the number of integers in
$I$ which are coprime to $W(r)m$ is at least $\frac{1}{4}\tau(r,m)x$.

###### Proof.

By [32, Theorem 7.11], for each interval $I=[x,2x)$ with $x\geq p_{r}/2$, the
number of integers in $I$ which are coprime to $W(r)$ is at most
$(1+o(1))\frac{x}{\log p_{r}}\leq 2\tau(r,1)x$, where we used that
$p_{r}=(1+o(1))r\log r$ and (31). For $x<p_{r}/2$, the number of integers in
$I$ which are coprime to $W(r)$ is $0<2\tau(r,1)x$. If also $x\geq
r^{1.5}>p_{r}$, then the number of integers in $I$ which are coprime to $W(r)$
is at least $\left(\frac{1}{2}-o(1)\right)\frac{x}{\log
p_{r}}\geq\frac{1}{2}\tau(r,1)x$, again using (31).

Consider the case $r\geq(\log m)/100$. Then $\tau(r,1)\leq 1/\log r\leq
4\tau(r,m)$ by (31) and (34), so the number of integers in $I$ which are
coprime to $W(r)m$ is at most $8\tau(r,m)x$. For $x\geq r^{1.5}$, we have seen
that there are at least $\frac{1}{2}\tau(r,1)x$ integers in $I$ which are
coprime to $W(r)$. For each prime factor $p$ of $m$ that is larger than
$p_{r}>r$, the number of integers in $I$ divisible by $p$ and coprime to
$W(r)$ is the same as the number of integers in $[x/p,2x/p)$ coprime to
$W(r)$, which is at most $2\tau(r,1)x/p$. Since there are at most $(\log
m)/(\log r)$ such prime factors, the number of integers in $I$ which are
coprime to $W(r)m$ is at least

$\displaystyle\frac{1}{2}\tau(r,1)x-\frac{\log m}{\log
r}\cdot\frac{2\tau(r,1)x}{r}$
$\displaystyle\geq\frac{1}{2}\tau(r,1)x-\frac{200r\tau(r,1)x}{r\log r}$
$\displaystyle>\tau(r,m)x/4,$

where, in the first inequality, we used the assumption $r\geq(\log m)/100$
and, in the second inequailty, we used that $r$ is sufficiently large and
$\tau(r,m)\leq\tau(r,1)$ by (30).

Next, consider the case $r<(\log m)/100$. By the inclusion-exclusion
principle, the number of integers in $I=[x,2x)$ which are coprime to $W(r)m$
is

$x+\sum_{k=1}^{M}(-1)^{k}\sum_{\begin{subarray}{c}p_{1}<p_{2}<\dots<p_{k},\\\
p_{1},p_{2},\dots,p_{k}|W(r)m\end{subarray}}\frac{x}{p_{1}p_{2}\cdots
p_{k}}+O(2^{M}),$

which is within an additive $O(2^{M})$ of $x\prod_{p|W(r)m}(1-1/p)$, where $M$
is the number of distinct primes that divide $W(r)m$. Since $M\leq r+2(\log
m)/(\log\log m)<(\log n)/10$ and $x\geq n^{1/6}$, the number of integers in
$I$ coprime to $W(r)m$ is at least $\frac{1}{2}\tau(r,m)x$ and at most
$2\tau(r,m)x$. ∎

######  Lemma 5.2.

Let $r$, $n$ and $m$ be positive integers such that $m\in[n,\binom{n}{2}]$,
$r\leq n$ and $r$ is sufficiently large. For any interval $I=[x,2x)$ with
$x\geq n^{1/4}$, there are at most $8(m/\phi(m))\tau(r,m)x$ integers in $I$ of
the form $qu$, where $u|m$, $u\leq x^{1/16}$ and $q$ is coprime to $W(r)m$. If
also $x\geq r^{2}$, then there are at least $\frac{1}{8}(m/\phi(m))\tau(r,m)x$
integers in $I$ of this form.

###### Proof.

Observe that for $x\geq n^{1/4}$ and each fixed $u|m$ with $u\leq x^{1/16}$,
Lemma B.2 implies that the number of integers in $I$ of the form $qu$ where
$q$ is coprime to $W(r)m$, which is the same as the number of integers in
$[x/u,2x/u)$ which are coprime to $W(r)m$, is at most $8\tau(r,m)x/u$, where
we used that $x/u\geq n^{1/6}$. If also $x\geq r^{2}$, then Lemma B.2
similarly implies that the number of integers in $I$ of the form $qu$ where
$q$ is coprime to $W(r)m$ is at least $\frac{1}{4}\tau(r,m)x/u$, where we used
that $x/u\geq r^{1.5}$.

Hence, the number of integers in $I$ of the form $qu$, where $u|m$, $u\leq
x^{1/16}$ and $q$ is coprime to $W(r)m$, is at least

$\displaystyle\frac{1}{4}\tau(r,m)\sum_{u|m,\,u\leq x^{1/16}}\frac{x}{u}$