r/mathriddles • u/Mathematics875 • 2d ago
Medium Van der Waerden Numbers
Given **n** symbols, what's the longest string we can form such that no three indices i, j, and k where k-j = j-i can have the same symbol (AKA no **arithmetic progressions** in the string)? The **Van de**r **Waerden Numbers** (W(3; n)) are precisely the length of such a string plus one.
Let's start with 2 symbols: A and B (or 0 and 1 if you prefer binary)
The 6 longest strings we can form are AABBAABB, AABBABBA, ABBAABBA, BAABBAAB, BBAABBAA, and ABABBABA, all sharing a length of 8. Thus, W(3; 2) is 8+1 = 9.
If we introduce a third symbol C, we can form AABBCABBCBACCAABBCABBCBACA, which has a length of 26 characters and cannot be extended further without forming an arithmetic progression. This is not a unique solution, there are 47 more strings all at 26 characters. Thus, W(3; 3) = 26+1 = 27.
For 10 symbols (like in the standard base-10 or decimal system we use to count) nobody knows the exact value of W(3; 10) because it's not easy to compute it. It has been shown that W(3; 10) is at least **10,036,978**, meaning you can form a string of 10 million symbols, using only 10 distinct symbols, such that there's no arithmetic progression (AP). All we know is that W(3; n) is finite for all n > 0, so no matter how many distinct symbols you start with, you will reach a **3AP** eventually.
It's proven that the lower bound of its growth is W(3; n) ≥ n^(cn) (where c is a constant), and the upper bound is W(3; n) ≤ 2^(2\^cn) meaning these numbers grow faster than any single exponential function can describe but not as fast as tetration, pentation, or the TREE function.
