Computational Complexity

Thursday, January 31, 2008

 
If you get a new result of interest with little effort...

Posted by GASARCH

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.

1. 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.
2. 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.
3. Is the proof correct? In this case its just to easy to have gotten it wrong. (Famous last words...)
4. 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.
5. 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.
6. Are you connecting two areas that have not been connected before? NO- k-free sets were studied because of VDW theorem.
7. 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

2:19 PM #

1.  Anonymous says:  
   
   Seems to me, Zeilberg is pretty much a nut. All his Opinion is lacking is the explicit phrase "I'll show them all".
   
   Regarding the original question, there's always the approach "can I do something more needlessly complicated to extend the connection"...
   

   3:17 PM, January 31, 2008

2.  Anonymous says:  
   
   The first paper you cite is by Chandra, Lipton, and Furst, not Chanda[sic]-Stockmeyer-Lipton.
   

   3:49 PM, January 31, 2008

3.  GASARCH says:  
   
   Dear Anon 2,
   Thank you, I have made
   the correction.
   bill g.
   

   4:02 PM, January 31, 2008

4.  Daniel Lemire says:  
   
   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.
   

   5:05 PM, January 31, 2008

5.  Anonymous says:  
   
   why is gasarch gasarch and lance lance?
   

   3:59 AM, February 01, 2008

6.  Boris says:  
   
   What is the best known lower bound?
   

   9:37 AM, February 01, 2008

7.  GASARCH says:  
   
   I think that for
   W(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.
   

   10:14 AM, February 01, 2008

8.  Anonymous says:  
   
   for one thing, if I publicize it I may find out if its already known
   
   I'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.
   

   12:37 PM, February 01, 2008

9.  Anonymous says:  
   
   It will be Hillary vs. McCain, and then McCain!
   

   5:44 PM, February 02, 2008