Monday, June 05, 2017

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)5  / log N  then A has a 3-AP

and hence

W(3,r) ≤ 2r(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)4  / log N  then A has a 3-AP

and hence

W(3,r) ≤ 2r(log r)4

An easy prob argument gives

W(3,r)  ≥ r3/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

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

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

The proof is here: here


  1. Is this a typo, Bill?

    You say that the result
    W(3,r) ≤ 2^{r(log r)}
    is improved to
    W(3,r) ≤ 2^{r(log r)^4}

    but is not 2^{r(log r)} < 2^{r(log r)^4} for r > b, where b is the base of the log?

    Alas, Blogger doesn't allow sup tags so this comment is slightly less readable. Oh well.

  2. Bill, a simple probabilistic/greedy construction shows that W(3,r) > exp(C(ln r)^2), I believe. This comes from the Salem-Spencer construction.

  3. I was unable to reconstruct your proof given your comments. Please email me directly to discuss by email.

    1. I figured it out and have modified my post to point to a writeup of the lower bound.

      To rephrase it

      r^{Omega(ln r)) \le W(3,r) \le 2^{r(log r)^4}

      so NOT poly. I still wonder what the consensus opinion is.