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

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


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


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 (k1)/knen/k, letting us take nklog2, for a lower bound of kk(log2o(1)), which is superexponential in k.

Source : Link , Question Author : Zach Hunter , Answer Author : Will Sawin

Leave a Comment