## You are here

HomeBehrend's construction

## Primary tabs

# Behrend’s construction

At first sight it may seem that the greedy algorithm yields the densest subset of $\{0,1,\ldots,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. Density 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 $\mathbb{R}^{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}+\cdots+x_{d}^{2}=t$ for $t=1,\ldots,dn^{2}$. Each point in the cube is contained in one of the spheres, and so at least one of the spheres contains $n^{d}/dn^{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},\ldots,x_{d}\}$ is a point of $A$, then $f(x)=x_{1}+x_{2}(2n)+x_{3}(2n)^{2}+\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,\ldots,N=(2n)^{d}\}$. If we set $d=c\sqrt{\ln N}$, then we get that there is a progression-free subset of $\{1,2,\ldots,N\}$ of size at least $Ne^{{-\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

$Ne^{{-\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

$Ne^{{-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.

# References

- 1 Felix A. Behrend. On the sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci., 23:331–332, 1946. Zbl 0060.10302.
- 2 Leo Moser. On non-averaging sets of integers. Canadian J. Math., 5:245–252, 1953. Zbl 0050.04001.
- 3 Robert A. Rankin. Sets of integers containing not more than a given number of terms in arithmetical progression. Proc. Roy. Soc. Edinburgh Sect. A, 65:332–344, 1962. Zbl 0104.03705.

## Mathematics Subject Classification

05D10*no label found*11B25

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections