# 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}^{{\mathrm{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}+\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{\mathrm{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{\mathrm{ln}N}(c\mathrm{ln}2+2/c+o(1)}$. To maximize this value we can set $c=\sqrt{2/\mathrm{ln}2}$. Thus, there exists a progression-free set of size at least

$$N{e}^{-\sqrt{8\mathrm{ln}2\mathrm{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{(\mathrm{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. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0060.10302Zbl 0060.10302.
- 2 Leo Moser. On non-averaging sets of integers. Canadian J. Math., 5:245–252, 1953. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0050.04001Zbl 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. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0104.03705Zbl 0104.03705.

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 |