Over the weekend I made an observation that gives a new (is it new?) lower bound on W(k,c). I will describe what all of this means, but my real interest are in the meta question if you have an easy proof of an interesting result, what to make of that?
Van der Waerden's theorem: For all k, for all c, there exists W=W(k,c) such that for all c-colorings of {1,...,W} there exists a,d such that a, a+d, ..., a+(k-1)d are the same color.Chanda-Lipton-Furst showed (Lemma 4.4)
If there exists A, a k-free set (a set with no arithmetic sequence of length k) that is a subset of [n], then there is a c-coloring of [n] with no monochromatic arithmetic sequence, where c=O((nlog n)/|A|).Laba and Lacey showed
There is a constant a such that, for all k that is a power of 2, for all n, there is a k-free set of size n× exp(-a(log n)1/(log k). (There result is sharper than this but this will suffice for us. They acknowledge that the result was already known in 1960 by Rankin.)If you combine these two you obtain
W(k,c) &ge exp((log c)&Omega(log k))I have looked at the literature and used google and this appears to be new. I seemed to have proven something new and interesting with very little effort. I pose questions that anyone should pose in this situation and answer them for my case.
- Is the result new? I think so- I've been looking at VDW papers for about 5 years now and have not run across it. Even so, would not be surprised (or even disappointed) if someone points to some paper I missed.
- Is the result interesting? YES Upper bounds on VDW have gotten alot of attention. Lower bounds less so, but some. And they are a nice check on upper bounds.
- Is the proof correct? In this case its just to easy to have gotten it wrong. (Famous last words...)
- Are the results you used not commonly known to the same people? While the Chandra et. al paper is not well known to combinatorics people, its the same principle as the Symmetric Hypergraph Lemma, which is known. However, the k-free set result is not that well known.
- Did the other people who knew all this stuff not care? Quite possible that the k-free set folks didn't care about this, or didn't think it was worth writing down.
- Are you connecting two areas that have not been connected before? NO- k-free sets were studied because of VDW theorem.
- What to do with the result? It deserves to be out there (for one thing, if I publicize it I may find out if its already known). I will probably write it up for a short note in some combinatorics journal (will check which ones take notes), and may put it on arXiv. Or might not bother hassling with referees (For more on that train of thought, see Zeilberg's opinion 77
Seems to me, Zeilberg is pretty much a nut. All his Opinion is lacking is the explicit phrase "I'll show them all".
ReplyDeleteRegarding the original question, there's always the approach "can I do something more needlessly complicated to extend the connection"...
The first paper you cite is by Chandra, Lipton, and Furst, not Chanda[sic]-Stockmeyer-Lipton.
ReplyDeleteDear Anon 2,
ReplyDeleteThank you, I have made
the correction.
bill g.
Zeilberg is a nut, but he is also right. There is no reason why you can't publish it on arxiv and call it a technical report. The great thing about technical reports, is that you can throw them on your c.v. too! Sure, someone may object that they are not peer reviewed, but if your result is significant, then chances are you will get cited.
ReplyDeletewhy is gasarch gasarch and lance lance?
ReplyDeleteWhat is the best known lower bound?
ReplyDeleteI think that for
ReplyDeleteW(k,c), asym in k and c,
I think this Is the best
known (part of why its
interesting).
For c=2 better is known.
I think its W(k,2) \ge
k2^k.
for one thing, if I publicize it I may find out if its already known
ReplyDeleteI'd recommend running a draft by some experts before publicizing it too much. If they are enthusiastic, then it's a great sign, but I suspect they will already know it.
It will be Hillary vs. McCain, and then McCain!
ReplyDelete