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.

## Key Definitions

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.

## 'Obvious' Remarks

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}
(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}
(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.

## Some Number Theory

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)

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)

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)

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}

## Deducing Asymptotic behaviour of a(x)

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}
(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

page revision: 26, last edited: 10 Oct 2011 09:30