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
yields
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
Is this a typo, Bill?
ReplyDeleteYou 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.
fixed, thanks.
ReplyDeleteBill, a simple probabilistic/greedy construction shows that W(3,r) > exp(C(ln r)^2), I believe. This comes from the Salem-Spencer construction.
ReplyDeleteI was unable to reconstruct your proof given your comments. Please email me directly to discuss by email.
ReplyDeleteI figured it out and have modified my post to point to a writeup of the lower bound.
DeleteTo 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.