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.

  • $\begingroup$ Do you mean computationally or are there constructions (more general than just 'found by computer search') which give better bounds for small N? There are some calculations floating around for small N - I ran some a while ago which go up to around 2^12. These are not best possible, but hopefully not too far off the truth, and certainly better than the Erdos-Turan bound. $\endgroup$ – Thomas Bloom Jun 22 '13 at 23:13
  • 1
    $\begingroup$ Some data for N up to around 10,000 can be found at math.uni.wroc.pl/~jwr/non-ave/DATABASE.TXT $\endgroup$ – Thomas Bloom Jun 22 '13 at 23:18
  • 1
    $\begingroup$ Also, I think you mean $log_3 2$ rather than $log_2 3$. $\endgroup$ – Thomas Bloom Jun 22 '13 at 23:25
  • $\begingroup$ $2^{35}$ is a small value of $N$? $\endgroup$ – Gerry Myerson Jun 23 '13 at 0:41
  • 1
    $\begingroup$ Thomas, thanks for your link. Starting from it I found the following recent paper of Dybizbanski that claims to compute the optimal constructions for $N \leq 123$: combinatorics.org/ojs/index.php/eljc/article/view/v19i2p15/pdf $\endgroup$ – CCat Jun 23 '13 at 12:30

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 $$\frac{n!}{(n/d)!^d}$$ 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 $$\frac{d^{n-2}}{n}$$ 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).

  • $\begingroup$ Thanks! I did some calculations but they did not really beat the asymptotically optimal value of $d$. Let $s = (2 d - 1)^n$ be the endpoint of interval. For $s = 2^{65}$, $N = d^{n - 2} / n$ is optimal when $d = 27$, $N = 2115250501872$. Erdős-Turán gives $N = s^{\log_3 2} \approx 2214984869027$. For $s = 2^{66}$, optimal $d = 28$, then $N = 3706171023373$, while Erdős-Turán gives $N approx 3430042844317$. So this seems to be the break-even point. (Calculating the same for Elkin would be very interesting.) $\endgroup$ – CCat Jun 24 '13 at 16:17
  • $\begingroup$ More data - I wrote a simple mathematica program that computes log2 of the size of the densest progression-free set according to Erdős-Turán and Behrend (NB: numerically optimized $d$, allowing $d$ to be a real number). The list of the values for $s = 2^k$ and $k = 62$ to $70$: {{39.1176, 38.5269, 62}, {39.7486, 39.3309, 63}, {40.3795, 40.1366, 64}, {41.0104, 40.944, 65}, {41.6414, 41.7531, 66}, {42.2723, 42.5638, 67}, {42.9032, 43.3761, 68}, {43.5342, 44.1899, 69}, {44.1651, 45.0053, 70}} One can see that 66 is the break-even point where the Behrend 's set is becoming smaller $\endgroup$ – CCat Jun 24 '13 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.