6
$\begingroup$

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.

$\endgroup$
8
  • $\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$ Jun 22, 2013 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$ Jun 22, 2013 at 23:18
  • 1
    $\begingroup$ Also, I think you mean $log_3 2$ rather than $log_2 3$. $\endgroup$ Jun 22, 2013 at 23:25
  • $\begingroup$ $2^{35}$ is a small value of $N$? $\endgroup$ Jun 23, 2013 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, 2013 at 12:30

2 Answers 2

4
$\begingroup$

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).

$\endgroup$
2
  • $\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, 2013 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, 2013 at 17:00
1
$\begingroup$

I know this is an old post, but I wanted to mention a little known construction that beats the Erdos-Turan bound a bit faster. It was noted by Ruzsa in 1999 (see Section 13 of [1]), and is a bit surprising it wasn't known earlier.

Let $A(r,N)$ be the set of integers less than $N$ with all digits belonging to $\{0,1,2\}$ in base 5, and exactly $r$ being equal to 1.

We can show that $A(r,N)$ is 3-AP-free. Indeed, first observe that there's no wrap around effects. Then note $1+a = 2b$ for $a,b\in \{0,1,2\}$ implies $a= b=1$. Thus for any 3-AP $\{x,y,z\} \subset A$, $x,y,z$ all have the same 1's digits. But then the only solutions to $a+b = 2c$ with $a,b,c \in \{0,2\}$ are when $a=b=c$, thus $x=y=z$ and the AP is trivial.

Taking $r= \lfloor \log_5(x)/3\rfloor$ has size roughly $x^{\log_5(3)}/\sqrt{\log_5(x)}$, and plugging in a proper lower bound into a calculator, I found it starts beating Erdos-Turan at $N=3 \cdot 5^{23}< 2^{55}$.

[1] Ruzsa, Imre Z., Erdős and the integers, J. Number Theory 79, No. 1, 115-163 (1999). ZBL0956.11002.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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