# example just slightly better than the greedy construction

Roth's theorem provides an estimate for the largest size of a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ (a set of integers is nonaveraging if it does not contain any nontrivial three-term arithmetic progression).

If we try to construct such a nonaveraging subset "naively" and "greedily", we obtain a Cantor subset (the integers $n$ such that the ternary expansion of $n-1$ does not contain a 2), whose density in $\lbrace 1,2, ... ,n \rbrace$ is $\frac{1}{n^{1-\frac{\log(3)}{log(2)}}}$. This is known to be far from optimal, since Behrend's construction (based on projecting a sphere onto the interval $[1(...)n]$) yields a set of density around $\frac{1}{2^{\sqrt{8\log_2(n)}}}$ (Elkin improved this, but this is not our concern here ; see http://gilkalai.wordpress.com/2008/07/10/pushing-behrend-around/). Behrend's construction is non-explicit in that it uses the pigeonhole principle, ans states that some radius provides us a sphere having enough points.

Since the gap between the two is huge, one may ask if there is a more "effective" construction explaining why the greedy algorithm does not produce an optimal result, in the following sense :

Let us denote by $C$ the set of all integers such that the ternary expansion of $n-1$ does not contain a 2, so that the greedy algorithm produces $C \cap \lbrace 1,2, \ldots ,n \rbrace$. Now, is there an infinite nonaveraging subset $T$ of $\mathbb N$, such that $|C \cap \lbrace 1,2, \ldots ,n \rbrace | < |T \cap \lbrace 1,2, \ldots ,n \rbrace |$ for all large enough $n$ ?

Update 02/01/2001 : to avoid "parasitic" and non-explicit examples as explained in fedja's comments, one may impose the additional hard requirement that $T$ is constructed by first imposing a condition of the form $T \cap X_0=Y_0$ where $X_0$ is a finite set and then filling $T$ greedily.

• The formal answer is "Yes, of course: just do Behrend's construction on intervals $5^k,2\cdot 5^k$ and skip the rest". You certainly meant something more interesting than that, but I am at loss as to how to state the question to eliminate such "parasitic answers". The word "elementary" might be the key but what is so non-elementary about projecting a sphere? – fedja Dec 31 '10 at 21:54
• Perhaps the right question asks how high the density can get as a function of how often we have the option to skip the greedy choice? – David Feldman Jan 1 '11 at 7:39
• @fedja : it is obvious that we may construct an infinite set that does better than the Cantor set for infinitely many $n$. It is not clear to me, however, that it will be better for all large enough $n$. In other words, the miscellaneous spheres we will obtain for a fast-growing sequence (say, the powers of 5) do not have to form a "coherent whole". – Ewan Delanoy Jan 1 '11 at 9:18
• -----It is not clear to me, however, that it will be better for all large enough $n$---- What do you mean? You have power on full $\mathbb N$ versus subpower on a set of positive lower density. The latter wins for all large $n$ hands down. I agree that it is not very explicit though. – fedja Jan 1 '11 at 14:12
• I am likely to miss something very basic, but why "if we try to construct such a nonaveraging subset "naively" and "greedily", we obtain a Cantor subset (the integers whose ternary expansion does not contain a 1)"? If we start with $1$, then we already have the "non-Cantor" element $1$ in our set. If you start with $2$, then, to continue greedily, you have to include $3$, which is a non-Cantor number again, etc. – Seva Jan 1 '11 at 20:46