Behrend’s construction


At first sight it may seem that the greedy algorithm yields the densest subset of {0,1,,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(Nlog32-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]dd and family of spheres x12+x22++xd2=t for t=1,,dn2. Each point in the cube is contained in one of the spheres, and so at least one of the spheres contains nd/dn2 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 defined as follows. If x={x1,x2,,xd} is a point of A, then f(x)=x1+x2(2n)+x3(2n)2++xd(2n)d-1, that is, we treat xi 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){1,2,,N=(2n)d}. If we set d=clnN, then we get that there is a progression-free subset of {1,2,,N} of size at least Ne-lnN(cln2+2/c+o(1). To maximize this value we can set c=2/ln2. Thus, there exists a progression-free set of size at least

Ne-8ln2lnN(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(logN)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 principleMathworldPlanetmath.

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