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,,N} contains progression-free sets of size O(Nlog1/4N/222log2N) (Elkin, 2011). However, when N is of moderate size (say 220), the original Erdős-Turán progression-free subset of [N] of size Nlog32 is much larger.

Question: for small values of N (say 1<N225), 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.

Answer

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 Nlog32 or at least Nc 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 Nlog32 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
n!(n/d)!d below (2d1)n for d>2 and any multiple n of d
based on the digits in base 2d1.

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=527 which is between 262 and 263. (For larger d it is still later, but asymptotically it is 'better'; optimizing the dependence of d and n one gets
N1c/loglogN.)

Let me add the following complement: The 'building blocks' (before optimizing the parameters) of Behrend's construction yields also up to (2d1)n a set of size
dn2n
for any d2 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).

Attribution
Source : Link , Question Author : Community , Answer Author : Community

Leave a Comment