Big News on W(3,r) !

This is a JOINT POST with   Evangelos Georgiadis who brought this problem to my attention.)

In 2010 I posted about how dense a set of integers has to be before you know there is a 3-AP in it (a 3-AP is a set of three numbers equally spaced). Such results were motivated by and are applied to getting upper bounds on

W(3,r) = the least W such that any r-coloring of {1,...,W} has a monochromatic 3-AP.

That blog, which also has history and context, is here

At the time of that post the following was known (and had just been proven by Sanders see here)

If A ⊂  {1,...,N} and |A|  ≥ N*(log log N)⁵  / log N  then A has a 3-AP

and hence

W(3,r) ≤ 2^{r(log r)5}





(Added later: Bloom's paper (see link on next line) reports that Sanders result is a bit weaker than claimed- the 5's should be 6's, calculation error.)

This has now been improved!. Thomas Bloom, in this paper has shown

If A ⊂  {1,...,N} and |A|  ≥ N*(log log N)⁴  / log N  then A has a 3-AP

and hence

W(3,r) ≤ 2^{r(log r)4}

An easy prob argument gives

W(3,r)  ≥ r^3/2


So is W(3,r)'s growth rate poly? Exp? in between? Is there a connection to SAT?

One can phrase the question  W(k,r)=m as asking of a certain Boolean Formula is it satisfiable.  IF we can get theorems about that kind of formula, that might help.

However, I doubt that it has much real connection to the general SAT problem.

I don't know if the consensus of the community is that W(3,r) is poly or exp.

(Warning: I've seen W(3,r) to mean something else: W(3,r) is the least W such that any 2-coloring of {1,...,W} with colors 0 and 1 has either a 0-colored 3-AP or a 1-colored k-AP. This is NOT the function we are talking about, though that one is also interesting. )

ADDED LATER: Knuth's Volume 4, Fascicle 6 has theorems about this W(3,r)

ADDED LATER: A commenter said that a simple prob greedy algorithm using salem-spencer sets
yields

W(3,r) ≥ exp(C (ln r)²)

I reconstructed the proof from these comments, though using Behrends sets instead of SS

The proof is here: here