# Non-asymptotically densest progression-free sets

For the context of this question, a progression-free set is a subset of integers that does not contain length-three arithmetic progressions.

For large $N$, it is known that $[N] = \{1, \ldots, N\}$ contains progression-free sets of size $O (N \log^{1 / 4} N / 2^{2 \sqrt{2 \log_2 N}} )$ (Elkin, 2011). However, when $N$ is of moderate size (say $2^{20}$), the original Erdős-Turán progression-free subset of $[N]$ of size $N^{\log_3 2}$ is much larger.

Question: for small values of $N$ (say $1 < N \leq 2^{25}$), what are the densest progression-free sets of $[N]$ known to exist?

Edit: I am interested in all different kind of answers: exhaustive search for very small $N$, different families of progression-free sets that beat Erdős-Turán for some concrete values of $N$, etc.

More a comment than and answer, but a bit too long.

First, two things to keep in mind:

On the one hand, people conjectured for a while that the thing actually is $N^{\log_3 2}$ or at least $N^c$ for $c<1$ so there should not be any "simple" (general) constructions that beats this.

On the other hand, all constructions I am aware of (Erdős-Turán, Salem-Spencer, Behrend, Moser and also Elkin) are somehow based on the digits of the numbers (sometimes in larger basis), so that it is at least not suprising the asympt. better construction become only better somewhat latter when there are actually enough digits that there is some flexibility to do something with them.

In particular, in view of this latter point I would not be surprised if for let us say mid-sized numbers (that is beyond explicit constructions but before the good asymp. constructions kick in) the $N^{\log_3 2}$ is actually the best known, as the in some sense first (to small basis) digital constructions.

One more remark: The construction of Salem-Spencer yields a set of cardinality
below $(2d-1)^n$ for $d >2$ and any multiple $n$ of $d$
based on the digits in base $2d-1$.

For $d=3$, this is (if I did not commit an error in calculation) the first time better than Erdős-Turán construction for $n=27$ so $N=5^{27}$ which is between $2^{62}$ and $2^{63}$. (For larger $d$ it is still later, but asymptotically it is 'better'; optimizing the dependence of $d$ and $n$ one gets
$N^{1 - c/ \log \log N}$.)

Let me add the following complement: The 'building blocks' (before optimizing the parameters) of Behrend's construction yields also up to $(2d-1)^n$ a set of size

for any $d\ge 2$ and $n$. For $d=2$ this is worse than Erdős-Turán but for other $d$ it is eventually always better. Now, one could play around with the parameters in specific cases, instead of taking the general 'good choice'. I did so a bit, but somehow did not find anything much better than the above, and in particular could not find anything as good as Thomas Bloom suggests (which might however also be my lack of good or somewhat exhaustive searching).