Behrend’s construction

At first sight it may seem that the greedy algorithm yields the densest subset of $\{0,1,\mathrm{\dots },N\}$ that is free of arithmetic progressions of length $3$. It is not hard to show that the greedy algorithm yields the set of numbers that lack digit $2$ in their ternary development (http://planetmath.org/Base3). Density (http://planetmath.org/AsymptoticDensity) of such numbers is $O(N^{{\log }_{3}2-1})$.

However, in 1946 Behrend[1] constructed much denser subsets that are free of arithmetic progressions. His major idea is that if we were looking for a progression-free sets in ${ℝ}^n$, then we could use spheres. So, consider an $d$-dimensional cube ${[1,n]}^d\cap {\mathbb{Z}}^d$ and family of spheres $x_1^2+x_2^2+\mathrm{\cdots }+x_d^2=t$ for $t=1,\mathrm{\dots },d{n}^2$. Each point in the cube is contained in one of the spheres, and so at least one of the spheres contains $n^d/d{n}^2$ lattice points. Let us call this set $A$. Since sphere does not contain arithmetic progressions, $A$ does not contain any progressions either. Now let $f$ be a Freiman isomorphism from $A$ to a subset of $\mathbb{Z}$ defined as follows. If $x=\{x_1,x_2,\mathrm{\dots },x_d\}$ is a point of $A$, then $f(x)=x_1+x_2(2n)+x_3{(2n)}^2+\mathrm{\cdots }+x_d{(2n)}^{d-1}$, that is, we treat $x_i$ as $i$’th digit of $f(x)$ in base $2n$. It is not hard to see that $f$ is indeed a Freiman isomorphism of order $2$, and that $f(A)\subset \{1,2,\mathrm{\dots },N={(2n)}^d\}$. If we set $d=c\sqrt{\ln N}$, then we get that there is a progression-free subset of $\{1,2,\mathrm{\dots },N\}$ of size at least $N{e}^{-\sqrt{\ln N}(c\ln 2+2/c+o(1)}$. To maximize this value we can set $c=\sqrt{2/\ln 2}$. Thus, there exists a progression-free set of size at least

$$N{e}^{-\sqrt{8\ln 2\ln N}(1+o(1))}.$$

This result was later generalized to sets not containing arithmetic progressions of length $k$ by Rankin[3]. His construction is more complicated, and depends on the estimates of the number of representations of an integer as a sum of many squares. He proves that the size of a set free of $k$-term arithmetic progression is at least

$$N{e}^{-c{(\log N)}^{1/(k-1)}}.$$

On the other hand, Moser[2] gave a construction analogous to that of Behrend, but which was explicit since it did not use the pigeonhole principle.

Title	Behrend’s construction
Canonical name	BehrendsConstruction
Date of creation	2013-03-22 13:40:53
Last modified on	2013-03-22 13:40:53
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	11
Author	bbukh (348)
Entry type	Result
Classification	msc 05D10
Classification	msc 11B25