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.
