A Note on Elkin’s Improvement of Behrend’s Construction

Summary

We provide a short proof of a recent result of Elkin in which large subsets of $\{1,\ldots,N\}$ free of three-term progressions are constructed.

To Mel Nathanson

Mathematics Subject Classifications (2010). Primary 11B25, Secondary 11B75

The first author holds a Leverhulme Prize and is grateful to the Leverhulme Trust for their support. This paper was written while the authors were attending the special semester in ergodic theory and additive combinatorics at MSRI.

1 Introduction

Write r ₃(N) for the cardinality of the largest subset of $\{1,\ldots,N\}$ not containing three distinct elements in arithmetic progression. A famous construction of Behrend [1] shows, when analysed carefully, that

$${r}_{3}(N) \gg { \frac{1} {\log }^{1/4}N} \cdot \frac{N} {{2}^{2\sqrt{2}\sqrt{{\log }_{2 } N}}}.$$

In a recent preprint [2], Elkin was able to improve this 62-year old bound to

$${r}_{3}(N) {\gg \log }^{1/4}N \cdot \frac{N} {{2}^{2\sqrt{2}\sqrt{{\log }_{2 } N}}}.$$

Our aim in this note is to provide a short proof of Elkin’s result. It should be noted that the only advantage of our approach is brevity: it is based on ideas morally close to those of Elkin, and moreover, his argument is more constructive than ours.

Throughout the paper, 0 < c < 1 < C denote absolute constants which may vary from line to line. We write ${\mathbb{T}}^{d} = {\mathbb{R}}^{d}/{\mathbb{Z}}^{d}$ for the d-dimensional torus.

2 The Proof

Let d be an integer to be determined later, and let δ ∈ (0, 1 ∕ 10) be a small parameter (we will have $d \sim C\sqrt{\log N}$ and $\delta \sim \exp (-C\sqrt{\log N}$)). Given $\theta,\alpha \in {\mathbb{T}}^{d}$, write ${\Psi }_{\theta,\alpha } :\{ 1,\ldots,N\} \rightarrow {\mathbb{T}}^{d}$ for the map n↦θn + α(mod 1).

Lemma 2.1.

Suppose that n is an integer. Then Ψ _θ,α (n) is uniformly distributed on ${\mathbb{T}}^{d}$ as θ,α vary uniformly and independently over ${\mathbb{T}}^{d}$ . Moreover, if n and n′ are distinct positive integers, then the pair (Ψ _θ,α (n),Ψ _θ,α (n′)) is uniformly distributed on ${\mathbb{T}}^{d} \times {\mathbb{T}}^{d}$ as θ,α vary uniformly and independently over ${\mathbb{T}}^{d}$.

Proof.

Only the second statement requires an argument to be given. Perhaps the easiest proof is via Fourier analysis, noting that

$$\int \nolimits \nolimits {\mathrm{e}}^{2\pi \mathrm{i}(k\cdot (\theta n+\alpha )+k^\prime\cdot (\theta n^\prime+\alpha ))}\,\mathrm{d}\theta \,\mathrm{d}\alpha = 0$$

unless k + k′ = kn + k′n′ = 0. Provided that k and k′ are not both zero, this cannot happen for distinct positive integers n, n′. Since the exponentials e^{2πi(kx + k′x′)} are dense in ${L}^{2}({\mathbb{T}}^{d} \times {\mathbb{T}}^{d})$, the result follows. □

Let us identify ${\mathbb{T}}^{d}$ with [0, 1)^d in the obvious way. For each $r\leq \frac{1} {2}\sqrt{d}$, write S(r) for the region

$$\{x \in {[0,1/2]}^{d} : r - \delta \leq \Vert {x\Vert }_{ 2}\leq r\}.$$

Lemma 2.2.

There is some choice of r for which vol (S(r))≥cδ2 ^−d.

Proof.

First note that if $({x}_{1},\ldots,{x}_{d})$ is chosen at random from [0, 1 ∕ 2]^d then, with probability at least c, we have $\vert \Vert {x\Vert }_{2} -\sqrt{d/12}\vert \leq C$. This is a consequence of standard tail estimates for sums of independent identically distributed random variables, of which $\Vert {x\Vert }_{2}^{2} ={ \sum \nolimits }_{i=1}^{d}{x}_{i}^{2}$ is an example. The statement of the lemma then immediately follows from the pigeonhole principle. □

Write S : = S(r) for the choice of r whose existence is guaranteed by the preceding lemma; thus vol(S) ≥ cδ2^{− d}. Write $\tilde{S}$ for the same set S but considered now as a subset of ${[0,1/2]}^{d} \subseteq {\mathbb{R}}^{d}$. Since there is no “wraparound”, the three-term progressions in S and $\tilde{S}$ coincide and henceforth we abuse notation, regarding S as a subset of ${\mathbb{R}}^{d}$ and dropping the tildes. (To use the additive combinatorics jargon, S and $\tilde{S}$ are Freiman isomorphic.) Suppose that (x, y) is a pair for which x − y, x and x + y lie in S. By the parallelogram law

$$2\Vert {x\Vert }_{2}^{2} + 2\Vert {y\Vert }_{ 2}^{2} =\Vert x + {y\Vert }_{ 2}^{2} +\Vert x - {y\Vert }_{ 2}^{2}$$

and straightforward algebra we have

$$\Vert {y\Vert }_{2}\leq \sqrt{{r}^{2 } - {(r - \delta )}^{2}}\leq \sqrt{2\delta r}.$$

It follows from the formula for the volume of a sphere in ${\mathbb{R}}^{d}$ that the volume of the set $B \subseteq {\mathbb{T}}^{d} \times {\mathbb{T}}^{d}$ in which each such pair (x, y) must lie is at most $\mathrm{vol}(S){C}^{d}{(\delta /\sqrt{d})}^{d/2}$.

The next lemma is an easy observation based on Lemma 2.1.

Lemma 2.3.

Suppose that N is even. Define A _θ,α :={ n ∈ [N] : Ψ _θ,α (n) ∈ S}. Then

$${\mathbb{E}}_{\theta,\alpha }\vert {A}_{\theta,\alpha }\vert = N\mathrm{vol}(S)$$

whilst the expected number of nontrivial three-term arithmetic progressions in A _θ,α is

$${\mathbb{E}}_{\theta,\alpha }T({A}_{\theta,\alpha }) = \frac{1} {4}N(N - 5)\mathrm{vol}(B).$$

Proof.

The first statement is an immediate consequence of the first part of Lemma 2.1. Now each nontrivial three-term progression is of the form (n − d, n, n + d) with d≠0. Since N is even there are N(N − 5) ∕ 4 choices for n and d, and each of the consequent progressions lies inside A _{θ, α} with probability vol(B) by the second part of Lemma 2.1. □

02.0

To finish the argument, we just have to choose parameters so that

$$\frac{1} {3}\mathrm{vol}(S)\geq \frac{1} {4}(N - 5)\mathrm{vol}(B).$$

(1)

Then, we shall have

$$\mathbb{E}\left (\frac{2} {3}\vert {A}_{\theta,\alpha }\vert - T({A}_{\theta,\alpha })\right )\geq \frac{1} {3}N\mathrm{vol}(S).$$

In particular, there is a specific choice of A : = A _{θ, α} for which both T(A) ≤ 2 | A | ∕ 3 and $\vert A\vert \geq \frac{1} {2}N\mathrm{vol}(S)$. Deleting up to two thirds of the elements of A, we are left with a set of size at least $\frac{1} {6}N\mathrm{vol}(S)$ that is free of three-term arithmetic progressions.

To do this, it suffices to have ${C}^{d}{(\delta /\sqrt{d})}^{d/2}\leq c/N$, which can certainly be achieved by taking $\delta := c\sqrt{d}{N}^{-2/d}$. For this choice of parameters we have, by the earlier lower bound on vol(S), that

$$\vert A\vert \geq \frac{1} {6}N\mathrm{vol}(S)\geq c\sqrt{d}{2}^{-d}{N}^{1-2/d}.$$

Choosing $d := \lceil \sqrt{{2\log }_{2 } N}\rceil$ we recover Elkin’s bound. □

3 A Question of Graham

The authors did not set out to try and find a simpler proof of Elkin’s result. Rather, our concern was with a question of Ron Graham (personal communication to the first-named author, see also [3, 4]). Defining W(2; 3, k) to be the smallest N such that any red-V-blue colouring of [N] contains either a three-term red progression or a k-term blue progression, Graham asked whether W(2; 3; k) < k ^A for some absolute constant A or, even more ambitiously, whether W(2; 3, k) ≤ Ck ². Our initial feeling was that the answer was surely no, and that a counterexample might be found by modifying the Behrend example in such a way that its complement does not contain long progressions. Reinterpreting the Behrend construction in the way that we have done here, it seems reasonably clear that it is not possible to provide a negative answer to Graham’s question in this way.