At first sight it may seem that the greedy algorithm yields the densest subset of that is free of arithmetic progressions of length . It is not hard to show that the greedy algorithm yields the set of numbers that lack digit in their ternary development (http://planetmath.org/Base3). Density (http://planetmath.org/AsymptoticDensity) of such numbers is .
However, in 1946 Behrend 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 , then we could use spheres. So, consider an -dimensional cube and family of spheres for . Each point in the cube is contained in one of the spheres, and so at least one of the spheres contains lattice points. Let us call this set . Since sphere does not contain arithmetic progressions, does not contain any progressions either. Now let be a Freiman isomorphism from to a subset of defined as follows. If is a point of , then , that is, we treat as ’th digit of in base . It is not hard to see that is indeed a Freiman isomorphism of order , and that . If we set , then we get that there is a progression-free subset of of size at least . To maximize this value we can set . Thus, there exists a progression-free set of size at least
This result was later generalized to sets not containing arithmetic progressions of length by Rankin. 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 -term arithmetic progression is at least
- 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.