On Certain Sets Of Integers
We will reproduce Roth's seminal 1953 paper On Certain Sets of Integers, however we will link to expository pages on statements contained in the proof.
A set of positive integers $u_1, u_2, \ldots$ will be called an $\mathcal{A}$-set if no three of the numbers are in arithmetic progression, so that $u_h+u_k=2u_l$ only if $h=l=k$. Let $A(x)$ denote the greatest number of integers that can be selected from $1,2,\ldots,x$ to form an $\mathcal{A}$-set. We write $a(x)=x^{-1}A(x)$. In a recent note I proved that $a(x) \rightarrow 0$ as $x \rightarrow \infty$, a result which had been conjectured for many years. The purpose of the present paper, which will be self-contained, is partly to give a more detailed account of the method, and partly to prove a more precise result, namely
(1)
\begin{align} a(x) = O \left( \frac{1}{\log \log x} \right) \end{align}
I would like to thank Prof. Davenport for suggesting simplifications of the method, which are incorporated both in the Comptes Rendus note and in the present paper.
The following obvious remarks will be important later.
$A(x)$ is also the greatest number of integers that can be selected from $x$ consecutive terms of an arithmetic progression to form an $\mathcal{A}$-set. For if $au_1+b, au_2+b, \ldots$ form an $\mathcal{A}$-set then so do $u_1, u_2, \ldots$, and conversely.
Further, for any two positive integers $x$ and $y$ we have
(2)
\begin{align} A(x+y) \leq A(x) + A(y). \end{align}
Thus
(3)
\begin{align} A(xy) \leq xA(y), \quad A(x) \leq \left\{ \left( \left[ \frac{x}{y}\right] + 1\right) y \right\} \leq \frac{x+y}{y} A(y); \end{align}
so that
(4)
\begin{align} a(xy) \leq a(y), \end{align}
(5)
\begin{align} a(x) \leq (1 + yx^{-1})a(y). \end{align}
Finally we have the trivial inequality
(6)
\begin{align} x^{-1} \leq a(x) \leq 1. \end{align}
Throughout the paper, small Latin letters (other than $c,e,h$) denoted positive integers. $h$ denotes any integer. $c_1, c_2, \ldots$ are positive absolute constants. The constants implied by the $O$ notation are absolute.
Let $u_1, u_2, \ldots, u_U$ be any $\mathcal{A}$-set selected from $1,2,\ldots,M$. In this section we will investigate the exponential sum
(7)
\begin{align} S=\sum_{k=1}^U e(\alpha u_k) \qquad \left[e(\theta) = e^{2 \pi i \theta}\right] \end{align}
where $\alpha$ is a real number. For each $\alpha$ there exist $h, q$ such that
(8)
\begin{align} \alpha=\frac{h}{q} + \beta, \quad (h,q)=1, \quad q\leq M^{\frac{1}{2}}, \quad q|\beta| \leq M^{-\frac{1}{2}} \end{align}
Suppose $m < M-1$, and put
(9)
\begin{align} S' = a(m) q^{-1} \left( \sum^q_{r=1} e\left( \frac{rh}{q} \right) \right) \left( \sum_{n=1}^M e(\beta n) \right), \end{align}
(so that $S'=0$ if $q > 1$). We prove that
(10)
\begin{align} |S - S'| < Ma(m) - U + O(mM^{\frac{1}{2}}). \end{align}
To prove this we start from the relation
(11)
\begin{align} S = \frac{1}{mq} \sum_{r=1}^q \sum_{n=1}^M \sum_{\substack{n \leq u_k \leq n+mq \\ u_k \equiv r (\mod q) }} e(\alpha u_k) + O(mq). \end{align}
This relation is obvious on noting that for given $u_k, m, q$ there are exactly $mq$ integers $n$, satisfying
(12)
\begin{align} n \leq u_k < n+mq, \end{align}
and that these integers $n$ also satisfy $1 \leq n \leq M$ provided that
(13)
\begin{align} mq \leq u_k < M-mq. \end{align}
Thus the coefficient of $e(\alpha u_k)$ on the right-hand side of 11 is unity, except when $u_k < mq$ or $M - mq \leq u_k \leq M$; these terms being compensated by the error term.
In the inner sum on the right-hand side of 11, we have
(14)
\begin{align} e(\alpha u_k) = e\left( \frac{rh}{q} \right) e(\beta n) + O(mq |\beta|). \end{align}
The number of terms in this inner sum is at most $A(m)$, by a remark of the previous section, and is therefore $A(m) - D(n,m,q,r)$, where $D \geq 0$. Hence
(15)
\begin{align} S = S' - \frac{1}{mq} \sum_{r=1}^q e \left( \frac{rh}{q} \right) \sum_{n=1}^M e(\beta n)D(n,m,q,r) + O(mq) + O(Mmq|\beta|). \end{align}
If we put $\beta = 0$ ad $h=0$ (legitimate since we have not yet used $(h,q)=1$, we obtain
(16)
\begin{align} U = Ma(m) - \frac{1}{mq} \sum_{r=1}^q \sum_{n=1}^M D(n,m,q,r) + O(mq). \end{align}
Using this as an estimate for
(17)
\begin{align} \sum_{r=1}^q \sum_{n=1}^M D(n,m,q,r) \end{align}
in the preceeding relation we obtain 10, on noting that $q \leq M^{\frac{1}{2}}$, $q|\beta| \leq M^{-\frac{1}{2}}$.
In this section we use an adaptation of the Hardy-Littlewood method to obtain a functional inequality for the function $a(x)$.
Let $m$ be an even integer, $2N=m^4$, and let now $u_1, u_2, \ldots, u_U$ be a maximal $\mathcal{A}$-set selected from $1,2,\ldots, 2N$, so that $U=A(2N)$. Let $2v_1, 2v_2. \ldots, 2v_V$ be the even integers among the $u_k$. We note that
(18)
\begin{equation} U = 2Na(2N) \end{equation}
andby 4,
(19)
\begin{align} U \leq 2Na(m), \quad V \leq A(N) \leq Na(m). \end{align}
Further, since the number of odd integers among the $u_k$ does not exceed $A(N)$, we have, by 4,
(20)
\begin{align} V \geq A(2N) - A(N) \geq 2Na(2N) - Na(m). \end{align}
We define
(21)
\begin{align} f_1(\alpha) = \sum_{k=1}^U e(\alpha u_k), \qquad f_2(\alpha) = \sum_{k=1}^V e(\alpha v_k); \end{align}
(22)
\begin{align} F_1(\alpha) = a(m) \sum_{n=1}^2N e(\alpha n), \qquad F_2(\alpha) = a(m) \sum_{n=1}^N e(\alpha n). \end{align}
In view of 19, we have
(23)
\begin{align} f_r(\alpha) = O\left(Na(m)\right), \qquad F_r(\alpha) = O\left(Na(m)\right); \quad r=1,2. \end{align}
We now show that, for any $\alpha$,
(24)
\begin{align} f_r(\alpha) - F_r(\alpha) = O\left( N{a(m)-a(2N)}+N^{\frac{3}{4}} \right); \quad r=1,2. \end{align}
If $q=1$ in 8, this follows at once from 10 (with $M=2N$ or $M=N$ according as $r=1$ or $2$) in view of 18 and 20. On the other hand, if it is impossible to choose $q=1$ in 8 [so that $S'=0$ in 10, 10 (with $M=2N$ or $N$) will imply 24 provided that
(25)
\begin{align} F_r(\alpha) = O(N^{\frac{3}{4}}). \end{align}
This inequality is in fact satisfied, since for any $\alpha$,
(26)
\begin{align} \sum_{n=1}^M e(\alpha n) = O\left( \left\| \alpha \right\|^{\-1}\right), \end{align}
where $\| \alpha \|$ denotes the distance of $\alpha$ from the nearest integer, and $\| \alpha \| > M^{-\frac{1}{2}}$ if it is impossible to choose $q=1$ in 8.
Further, using the inequality
(27)
\begin{equation} |f_1{f_2}^2 - F_1{F_2}^2| = |f_1({f_2}^2 - {F_2}^2) + {f_2}^2(f_1 - F_1)| \end{equation}
(28)
\begin{align} . \qquad \qquad \qquad \qquad \qquad \quad \leq |f_1(f_2 + F_2)(f_2 - F_2)| + |{F_2}^2(f_1 - F_1)|, \end{align}
we obtain, by 23 and 24,
(29)
\begin{align} f_1(\alpha){f_2}^2(-\alpha) - F_1(\alpha){F_2}^2(-\alpha) = O \left( \left\{ Na(m)\right\}^2 \left( N\left\{a(m) - a(2N)\right\} + N^{\frac{3}{4}} \right) \right). \end{align}
Finally, by 24 and 26, if $0 < \eta < \alpha < 1- \eta$ we have
(30)
\begin{align} f_1(\alpha) = O\left( a(m) \eta^{-1} + N\left\{ a(m) - a(2N) \right\} + N^{\frac{3}{4}} \right). \end{align}
The fact that $u_1, u_2, \ldots u_U$ form an $\mathcal{A}$-set implies that $u_h = v_k + v_l$ if and only if $k=l$ and $u_h = 2v_k$. This can be expressed, following the method of Hardy and Littlewood, by
(31)
\begin{align} \int_{-\eta}^{1-\eta} f_1(\alpha) {f_2}^2(-\alpha) \text{d}\alpha = V \leq Na(m). \end{align}
From now on we shall suppose that $\eta = \eta(m)$ satisfies
(32)
\begin{align} 0 < \eta < \frac{1}{2}. \end{align}
Since
(33)
\begin{align} \int_0^1 |f_2(\alpha)|^2 \text{d}\alpha = V \leq Na(m), \end{align}
we have, by 30,
(34)
\begin{align} \int_{\eta}^{1- \eta} f_1(\alpha) {f_2}^2(-\alpha) \text{d}\alpha = ) \left( \left\{ a(m)\eta^{-1} + N \left( a(m) - a(2N) \right) + N^{\frac{3}{4}}\right\}Na(m)\right). \end{align}
Further, by 29, we have
(35)
\begin{align} \int_{-\eta}^{\eta} f_1(\alpha){f_2}^2(-\alpha) \text{d}\alpha = \int_{-\eta}^{\eta} F_1(\alpha) {F_2}^2(-\alpha) \text{d}\alpha + O\left( \eta \left\{Na(m)\right\}^2\left(N\left\{a(m)-a(2N)\right\} + N^{\frac{3}{4}} \right) \right). \end{align}
Finally, by 26 and 32, we have
(36)
\begin{align} \int_{-\eta}^{\eta} F_1(\alpha) {F_2}^2(-\alpha) \text{d}\alpha = \int_{-\frac{1}{2}}^{\frac{1}{2}} F_1(\alpha) {F_2}^2(-\alpha) \text{d}\alpha + O \left(a^3(m)\eta^{-2} \right). \end{align}
Now the integral on the right represents $a^3(m)$ times the number of solutions of $n=n' + n''$ in integers $n,n',n''$ satisfying $n \leq 2N$, $n' \leq N$, $n'' \leq N$. This number is $N^2$. Thus collecting together the results 31, 34, 35, 36, we obtain
(37)
\begin{align} a^2(m) = \left\{ N^2a(m)\right\}^{-1} \int^{\frac{1}{2}}_{-\frac{1}{2}}F_1(\alpha) {F_2}^2(-\alpha) \text{d}\alpha = O \left( a^2(m)N^{-2}\eta^{-2} + \left\{\eta N a(m) + 1 \right\} \left\{ a(m) - a(2N) + N^{-\frac{1}{4}}\right\} + a(m)N^{-1}\eta^{-1} \right). \end{align}
Hence writing
(38)
\begin{align} \delta = \left( N \eta \right)^{-1}, \end{align}
we obtain, noting that $2N = m^4$,
(39)
\begin{align} a^2(m) < c_1 \left\{ a(m) \delta + a^2(m) \delta^2 + \left(\delta^{-1}a(m) + 1\right) \left(a(m) - a(m^4) + m^{-1} \right) \right\}. \end{align}
Here $\delta = \delta(m)$ is subject only to the restriction implied by 32.
We now write
(40)
\begin{align} m = 2^{4^x}, \qquad b(x) = a(m), \end{align}
where $x$ is any positive integer, so that 39 becomes
(41)
\begin{align} b^2(x) < c_1 \left\{ b(x) \delta + b^2(x)\delta^2 + \left( \delta^{-1}b(x) + 1\right) \left( b(x) - b(x+1) + 2^{-4^x} \right) \right\}. \end{align}
In this section we shall deduce 1 from 4, 5, 6 and 41.
We assume $c_1 > 1$ ($c_1$ can be so chosen), and write $\delta = (2c_1)^{-1}b(x)$. Then, noting that $b(x) \leq 1$ by 6, we have
(42)
\begin{align} c_1 \left\{ b(x)\delta + b^2(x)\delta^2 \right\} \leq b^2(x) \left\{ \frac{1}{2} + \frac{1}{4c_1} \right\} < \frac{3}{4} b^2(x). \end{align}
Further, by 38 and 6
(43)
\begin{align} \eta = N^{-1} \delta^{-1} = c_2 m^{-4} \{a(m)\}^{-1} < c_2 m^{-3}, \end{align}
so that 32 is satisfied for large $x$. Thus 41 implies
(44)
\begin{align} b^2(x) < c_3 \left( b(x) - b(x+1) + 2^{-4^x} \right) \quad \text{for} \quad x > c_4. \end{align}
Now $b(x)$ is a decreasing function, by 4, and hence
(45)
\begin{align} Pb^2(2P) \leq \sum_{x=P}^{2P-1} b^2(x) <c_5 \left( b(P) - b(2P) + \frac{4c_5}{2P} \right) \end{align}
for all integers $P > c_4$.
Hence, if $P > c_4$ and $2Pb(2P) > 4c_5$, we have
(46)
\begin{align} 2Pb(2P) < \frac{1}{4c_5} \{2Pb(2P)\}^2 < P \left\{ b(P) - b(2P) + \frac{4c_5}{2P} \right\} < Pb(P). \end{align}
This clearly implies (by a backward induction) that if $c_4 < 2^{t_0} < 2^t$, then
(47)
\begin{align} 2^tb(2^t) \leq \max \left( 4c_5, 2^{t_0}b(2^{t_0}) \right), \end{align}
so that
(48)
\begin{equation} b(2^t) = O(2^{-t}); \end{equation}
and hence, since $b(x)$ is a decreasing function,
(49)
\begin{equation} b(x) = O(x^{-1}). \end{equation}
Finally, corresponding to any large integer $y$ we may choose $x$ to satisfy
(50)
\begin{align} 2^{4^x} < y \leq 2^{4^{x+1}}. \end{align}
Then, by 5, we have
(51)
\begin{align} a(y) \leq 2a(2^{4^x}) = 2b(x), \end{align}
so that 49 implies 1.
Q.E.D.
K.F.Roth, University College, London