Return to Question

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 whose ternary expansion does not contain a 1), whose density in $\lbrace 1,2, ... ,n \rbrace$ is $\frac{1}{n^{1-\frac{\log(3)}{log(2)}}}$. This is known not to be 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 whose ternary expansion does not contain a $1$, 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$ ?

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.

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 whose ternary expansion does not contain a 1), whose density in $\lbrace 1,2, ... ,n \rbrace$ is $\frac{1}{n^{1-\frac{\log(3)}{log(2)}}}$. This is known not to be optimal, since Behrend's construction (based on projecting a sphere onto the interval $[1(...)n]$) yields a set of density around $\frac{1}{e^{\sqrt{log(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 whose ternary expansion does not contain a $1$, 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$ ?

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 whose ternary expansion does not contain a 1), whose density in $\lbrace 1,2, ... ,n \rbrace$ is $\frac{1}{n^{1-\frac{\log(3)}{log(2)}}}$. This is known not to be 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 whose ternary expansion does not contain a $1$, 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$ ?

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 whose ternary expansion does not contain a 1), whose density in $\lbrace 1,2, ... ,n \rbrace$ is $\frac{1}{n^{1-\frac{\log(3)}{log(2)}}}$. This is known not to be optimal, since Behrend's construction (based on projecting a sphere onto the interval $[1(...)n]$) yields a set of density around $\frac{1}{e^{\sqrt{log(n)}}}$ (Elkin improved this, but this is not our concern here ; see http://gilkalai.wordpress.com/2008/07/10/pushing-behrend-around/).

Since the gap between the two is huge, one may ask if there is a more "elementary" 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 whose ternary expansion does not contain a $1$, 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$ ?

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 whose ternary expansion does not contain a 1), whose density in $\lbrace 1,2, ... ,n \rbrace$ is $\frac{1}{n^{1-\frac{\log(3)}{log(2)}}}$. This is known not to be optimal, since Behrend's construction (based on projecting a sphere onto the interval $[1(...)n]$) yields a set of density around $\frac{1}{e^{\sqrt{log(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 whose ternary expansion does not contain a $1$, 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$ ?