# Can we do better than random when constructing dense kk-AP-free sets

We write $$[N][N]$$ to denote $${1,…,N}\{1,\dots,N\}$$. We say a set $$SS$$ is $$kk$$-AP-free if it lacks non-trivial arithmetic progressions of length $$kk$$.

We define the 2-color van der Waerden number, $$w(2;k)w(2;k)$$, to be the largest integer $$NN$$ where $$[N][N]$$ can be partitioned into two $$kk$$-AP-free sets. For general $$kk$$, the best lower bound is $$w(2;k)≥2k/ko(1)w(2;k)\ge 2^k/k^{o(1)}$$ and is achieved by essentially using a uniformly random partition (and then using LLL to ensure a secondary correction phase succeeds).

I am curious about a related quantity. Let $$d(1/2,k)d(1/2,k)$$ be the largest $$NN$$ where there exists a $$kk$$-AP-free set $$S⊂[N]S\subset [N]$$ with $$|S|≥N/2|S| \ge N/2$$. By pigeonhole, we have that $$d(1/2,k)≥w(2;k)d(1/2,k) \ge w(2;k)$$.

Questions

Do we know if $$d(1/2,k)≫2kd(1/2,k)\gg 2^k$$, or is the inequality above the limit of our knowledge currently? Edit: actually, it’s straight-forward to prove $$d(1/2,k)≥2k/(e2+o(1))d(1/2,k) \ge 2^k/(e^2+o(1))$$ by probabilistic method (first include each element with prob $$1/2+1/k1/2+1/k$$ then delete a member of each $$kk$$-AP).

Is it reasonable to suspect $$d(1/2,k)≤(2+o(1))kd(1/2,k) \le (2+o(1))^k$$ (i.e. that for this density we can’t do much better than random)? I think such an upper bound is expected for $$w(2;k)w(2;k)$$.

We can take the set of all numbers in base $$kk$$ that don’t contain the digit $$00$$, for $$kk$$ prime.
This is $$kk$$-term-progression-free since every $$kk$$-term progression in $$Fk\mathbb F_k$$ is either constant or contains $$00$$, thus any $$kk$$-term progression in $$Z\mathbb Z$$ takes all possible values in the last nonconstant digit.
The intersection with $$[kn][k^n]$$ has density $$(k−1)/kn≈e−n/k(k-1)/k^n \approx e^{-n/k}$$, letting us take $$n≈klog2n \approx k \log 2$$, for a lower bound of $$kk(log2−o(1))k^{ k (\log 2-o(1))}$$, which is superexponential in $$kk$$.