Thursday, July 19, 2007

W(6,2) = 1132! (excitment, not factorial)

A PhD Student, Michal Kouril, found a new van der Waerden number, W(6.2)=1132. See here for details. I had a list of known VDW numbers in an earlier post, but I redo it here with the new result.

VDW(k,c) is the least number W such that no matter how you c-color the elements {1,2,...,W} there will be k numbers equally spaced (e.g., 3,7,11,15) that are the same color. W(k,c) exists by VDW's Theorem. See Wikipedia or my post in Luca's blog

The only VDW numbers that are known are as follows: (see this paper) by Landman, Robertson, Culver from 2005 and the website above about W(6,2).
  1. VDW(3,2)=9, (easy)
  2. VDW(3,3)=27, (Chvátal, 1970, math review entry,
  3. VDW(3,4)=76, (Brown, Some new VDW numbers (prelim report), Notices of the AMS, Vol 21, (1974), A-432.
  4. VDW(4,2)=35, Chvátal ref above
  5. VDW(5,2)=178, Stevens and Shantarum, 1978 full article!
  6. VDW(6,2)=1132. Michal Kouril. 2007. (Not available yet.)
Over email I had the following Q & A iwth Michal Kouril.

BILL: Why is it worth finding out?

MICHAL: As my advisor Jerry Paul put it Why do we climb Mount Everest?" Because it is there! The advances we've made during the pursuit of W(6,2) can have implications on other worthy problems.

BILL: Predict when we will get W(7,2)

MICHAL: Septemer 30, 2034. Or any time before or after. Interest in Van der Waerden numbers has been growing lately and I would not be surprised if we saw W(7,2) lot sooner than this. Some unknown VDW numbers are already just a matter of the amount of computing power you throw at them in order to prove the exact value. But W(7,2) still need more analysis to make them provable in a reasonable amount of time.

(Back to bill's blog:) In a perfect world Michal would be interviewed by Steven Colbert instead of me. Oh well...


  1. Please clarify: this is for 2 colors and six elements?

  2. Or else what? Did you think 6 colors and 2 elements???

  3. Maybe i'm missing something here, but isn't W(2,k)=k+1 trivialy true?

  4. The result is 2 colors,
    you want a sequence
    of length 6. In my
    notation that I defined
    above W(6,2). I regard
    the sequence length as
    more important.

    YES W(2,k)=k+1 is trivial.
    This is not what was done.

  5. 1132 is much larger than one would be led to hope for with the most widely known elementary technique for avoiding long arithmetic progressions, namely, choosing the string randomly.

    So, my question for Michal Kouril would be: does your proof suggest generalizable ideas for the construction of these progression-avoiding strings?

  6. Ya know, Anon 2, I'm not afraid of giving my real name while asking a stupid question -- unlike, um, some people, who #1) post anonymously and #2) "answer" a question by asking another question instead of taking a concrete position. Please note that my willingness to embrace public dopiness perhaps inspired commenter #3 to ask a question that was also "stupid" -- and now things are much clearer for a lot of us, not just me.

    Have you ever done something nobody else ever did before without acting like a nitwit during the process? I haven't, and all the researchers, artists and business people I have talked to about this stuff have similar stories about having to crash through the "stupid wall" before coming up with something new.

    I attended the most recent Midwest Theory Day. Do you know who asked the most (and "most obvious") questions? Lance Fortnow. In general, I think it's dumber to not ask the dumb question. As Bill asked in a recent post, which is bigger, your curiosity or your ego?

  7. I agree that the comment of Anonymous #2 was rude and counterproductive.

  8. Re: Andy D

    Short answer is unfortunately No.
    Some ideas for constructing long progression free strings are described in my paper with Dr. Franco "Resolution Tunnels for Improved SAT Solver Performance." Recently a number of people have been working on various ways to construct long progression free strings. In particular Marijn Heule, David Mitchell, ...