We write [N] to denote {1,…,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)≥2k/ko(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⊂[N] with |S|≥N/2. By pigeonhole, we have that d(1/2,k)≥w(2;k).
Questions
Do we know if d(1/2,k)≫2k, 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)) 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)≤(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).
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 Fk is either constant or contains 0, thus any k-term progression in Z takes all possible values in the last nonconstant digit.
The intersection with [kn] has density (k−1)/kn≈e−n/k, letting us take n≈klog2, for a lower bound of kk(log2−o(1)), which is superexponential in k.
Attribution
Source : Link , Question Author : Zach Hunter , Answer Author : Will Sawin
