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)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)Finally we have the trivial inequality

(6)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)where $\alpha$ is a real number. For each $\alpha$ there exist $h, q$ such that

(8)Suppose $m < M-1$, and put

(9)(so that $S'=0$ if $q > 1$). We prove that

(10)To prove this we start from the relation

(11)This relation is obvious on noting that for given $u_k, m, q$ there are exactly $mq$ integers $n$, satisfying

(12)and that these integers $n$ also satisfy $1 \leq n \leq M$ provided that

(13)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)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)If we put $\beta = 0$ ad $h=0$ (legitimate since we have not yet used $(h,q)=1$, we obtain

(16)Using this as an estimate for

(17)in the preceeding relation we obtain 10, on noting that $q \leq M^{\frac{1}{2}}$, $q|\beta| \leq M^{-\frac{1}{2}}$.

## Adapted Hardy-Littlewood Method

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)Further, since the number of odd integers among the $u_k$ does not exceed $A(N)$, we have, by 4,

(20)We define

(21)We now show that, for any $\alpha$,

(24)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)This inequality is in fact satisfied, since for any $\alpha$,

(26)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)Finally, by 24 and 26, if $0 < \eta < \alpha < 1- \eta$ we have

(30)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)From now on we shall suppose that $\eta = \eta(m)$ satisfies

(32)Since

(33)Finally, by 26 and 32, we have

(36)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)Hence writing

(38)we obtain, noting that $2N = m^4$,

(39)Here $\delta = \delta(m)$ is subject only to the restriction implied by 32.

We now write

(40)where $x$ is any positive integer, so that 39 becomes

(41)## 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)so that 32 is satisfied for large $x$. Thus 41 implies

(44)Now $b(x)$ is a decreasing function, by 4, and hence

(45)for all integers $P > c_4$.

Hence, if $P > c_4$ and $2Pb(2P) > 4c_5$, we have

(46)This clearly implies (by a backward induction) that if $c_4 < 2^{t_0} < 2^t$, then

(47)and hence, since $b(x)$ is a decreasing function,

(49)Finally, corresponding to any large integer $y$ we may choose $x$ to satisfy

(50)Q.E.D.

K.F.Roth, University College, London