We write $[N]$ to denote $\{1,\dots,N\}$. We say a set $S$ is $k$-AP-free if it lacks non-trivial arithmetic progressions of length $k$.
We define the 2-color van der Waerden number, $w(2;k)$, to be the largest integer $N$ where $[N]$ can be partitioned into two $k$-AP-free sets. For general $k$, the best lower bound is $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)$ be the largest $N$ where there exists a $k$-AP-free set $S\subset [N]$ with $|S| \ge N/2$. By pigeonhole, we have that $d(1/2,k) \ge w(2;k)$.
Questions
Do we know if $d(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) \ge 2^k/(e^2+o(1))$ by probabilistic method (first include each element with prob $1/2+1/k$ then delete a member of each $k$-AP).
Is it reasonable to suspect $d(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)$.
Best Answer
We can take the set of all numbers in base $k$ that don't contain the digit $0$, for $k$ prime.
This is $k$-term-progression-free since every $k$-term progression in $\mathbb F_k$ is either constant or contains $0$, thus any $k$-term progression in $\mathbb Z$ takes all possible values in the last nonconstant digit.
The intersection with $[k^n]$ has density $(\frac{k-1}{k})^n \approx e^{-n/k}$, letting us take $n \approx k \log 2$, for a lower bound of $k^{ k (\log 2-o(1))}$, which is superexponential in $k$.