About Van Der Waerden Numbers
Today (2/2/2021) we have re-launched the project following acceptance for publication of a paper on our previous phase (see arxiv). Our research objectives in phase 2 are to focus on the two-color case, for which we have found several improvements in memory and compute efficiency. The last iteration of the project found 12 new bounds, and the current one should find about 5. Strange properties in our best primes have caused us to save the results for each prime (in short, the best primes p seem to be such that p-1 has few factors). You can monitor our development progress and view frequently asked questions here and post to the message boards or message me (id=1) with any problems. You can also check our latest bounds here and the last prime used here.
Van Der Waerden Numbers is a research project that uses Internet-connected
computers to find better lower bounds for these numbers. The bold numbers in the table below are bounds improved or discovered by this project.
You can participate by downloading and running a free program
that runs on your computer when you're not using it. To participate,
Download and run BOINC,
and add Project 'vdwnumbers.org'. It only works with Windows and Linux computers. You can also Read our rules and policies.
This is a project of Daniel Monroe.
Returning participants
Your account,
Server status,
Certificate,
Applications,
Teams
Community
Profiles,
User search,
Message boards,
Questions and Answers,
Statistics
|
User of the day
  KPX
Greetings from Prague! |
Background
The sequence of colors BRRBBRRB
(where B is blue and R is red) does not have an
evenly spaced subsequence of length 3 that are the same color. However,
if you add a B to the end, you get BRRBBRRBB, which has the same color B in positions 1,5, and 9 which are
evenly spaced 4 apart. If you add an R to the end, you
get BRRBBRRBR, which has R at position 3, 6, and 9. In fact, with only two colors,
there is no sequence of length 9 of Bs and Rs that does not have a subsequence of
3 evenly spaced of the same color. Van der Waerden's Theorem states that for any number of colors r and length k, a long enough sequence always has an evenly
spaced subsequence of the same color. The smallest length guaranteed to have an evenly spaced subsequence is called the Van Der Waerden Number and is written
W(k,r). For example, W(3,2)=9. This project is to find better lower bounds for Van Der Waerden Numbers by finding sequences like BRRBBRRB.
See a table of the results so far below.
Here is how the program works. Take a prime number n (shown in parentheses on the table) and a primitive root of that number. For example, let n equal 11. See that W(4,2)-length 4, 2 colors has 11 in parentheses. Let's use the primitive root 2. 2 is a primitive root of 11 because its powers up to 2^10
[2,4,8,16,32,64,128,256,512,1024] modulo 11 (the remainder when dividing by 11) are all distinct and equal
[2,4,8,5,10,9,7,3,6,1]
which we color red, blue, red, blue.
Now all we have to do is reorder this is sequence, getting us [1,2,3,4,5,6,7,8,9,10].
We can add the color 11, which should be blue. Rabung proved that under certain conditions we can concatenate 3 more copies of this 11-term sequence while avoiding 4 evenly spaced of the same color. We can add a 34th term, so we will. The existence of this sequence of 34 proves that W(4,2) is more than 34.
|