Van der Waerden's theorem
Encyclopedia
Van der Waerden's theorem is a theorem in the branch of mathematics
called Ramsey theory
. Van der Waerden's theorem states that for any given positive integer
s r and k, there is some number N such that if the integers {1, 2, ..., N} are colored
, each with one of r different colors, then there are at least k integers in arithmetic progression
all of the same color. The least such N is the Van der Waerden number W(r, k). It is named after the Dutch mathematician B. L. van der Waerden
.
For example, when r = 2, you have two colors, say red
and blue
. W(2, 3) is bigger than 8, because you can color the integers from {1, ..., 8} like this:
1 2 3 4 5 6 7 8
B R R B B R R B
and no three integers of the same color form an arithmetic progression
. But you can't add a ninth integer to the end without creating such a progression. If you add a red 9
, then the red 3
, 6
, and 9
are in arithmetic progression. Alternatively, if you add a blue 9
, then the blue 1
, 5
, and 9
are in arithmetic progression. In fact, there is no way of coloring 1 through 9 without creating such a progression. Therefore, W(2, 3) is 9.
It is an open problem to determine the values of W(r, k) for most values of r and k. The proof of the theorem provides only an upper bound. For the case of r = 2 and k = 3, for example, the argument given below shows that it is sufficient to color the integers {1, ..., 325} with two colors to guarantee there will be a single-colored arithmetic progression of length 3. But in fact, the bound of 325 is very loose; the minimum required number of integers is only 9. Any coloring of the integers {1, ..., 9} will have three evenly spaced integers of one color.
For r = 3 and k = 3, the bound given by the theorem is 7(2·37 + 1)(2·37·(2·37 + 1) + 1), or approximately 4.22·1014616. But actually, you don't need that many integers to guarantee a single-colored progression of length 3; you only need 27. (And it is possible to color {1, ..., 26} with three colors so that there is no single-colored arithmetic progression of length 3; for example, RRYYRRYBYBBRBRRYRYYBRBBYBY.)
Anyone who can reduce the general upper bound to any 'reasonable' function can win a large cash prize. Ronald Graham
has offered a prize of US$1000 for showing W(2,k)<2k2. The current record is due to Timothy Gowers, who establishes
by first establishing a similar result for Szemerédi's theorem
, which is a stronger version of Van der Waerden's theorem. The previously best known bound was due to Saharon Shelah
and proceeded via first proving a result for the Hales–Jewett theorem, which is another strengthening of Van der Waerden's theorem.
The best-known lower bound for
is that 
for all positive ε.
and B.L. Rothschild. Khinchin gives a fairly simple proof of the theorem without estimating W(r, k).
We will prove the special case mentioned above, that W(2, 3) ≤ 325. Let c(n) be a coloring of the integers {1, ..., 325}. We will find three elements of {1, ..., 325} in arithmetic progression that are the same color.
Divide {1, ..., 325} into the 65 blocks {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, thus each block is of the form {b ·5 + 1, ..., b ·5 + 5} for some b in {0, ..., 64}. Since each integer is colored either red or blue, each block is colored in one of 32 different ways. By the pigeonhole principle, there are two blocks among the first 33 blocks that are colored identically. That is, there are two integers b1 and b2, both in {0,...,32}, such that
for all k in {1, ..., 5}. Among the three integers b1·5 + 1, b1·5 + 2, b1·5 + 3, there must be at least two that are the same color. (The pigeonhole principle again.) Call these b1·5 + a1 and b1·5 + a2, where the ai are in {1,2,3} and a1 < a2. Suppose (without loss of generality) that these two integers are both red. (If they are both blue, just exchange 'red' and 'blue' in what follows.)
Let a3 = 2·a2 − a1. If b1·5 + a3 is red, then we have found our arithmetic progression: b1·5 + ai are all red.
Otherwise, b1·5 + a3 is blue. Since a3 ≤ 5, b1·5 + a3 is in the b1 block, and since the b2 block is colored identically, b2·5 + a3 is also blue.
Now let b3 = 2·b2 − b1. Then b3 ≤ 64. Consider the integer b3·5 + a3, which must be ≤ 325. What color is it?
If it is red, then b1·5 + a1, b2·5 + a2, and b3·5 + a3 form a red arithmetic progression. But if it is blue, then b1·5 + a3, b2·5 + a3, and b3·5 + a3 form a blue arithmetic progression. Either way, we are done.
A similar argument can be advanced to show that V(3, 3) ≤ 7(2·37+1)(2·37·(2·37+1)+1). One begins by dividing the integers into 2·37·(2·37 + 1) + 1 groups of 7(2·37 + 1) integers each; of the first 37·(2·37 + 1) + 1 groups, two must be colored identically.
Divide each of these two groups into 2·37+1 subgroups of 7 integers each; of the first 37 + 1 subgroups in each group, two of the subgroups must be colored identically. Within each of these identical subgroups, two of the first four integers must be the same color, say red; this implies either a red progression or an element of a different color, say blue, in the same subgroup.
Since we have two identically-colored subgroups, there is a third subgroup, still in the same group that contains an element which, if either red or blue, would complete a red or blue progression, by a construction analogous to the one for W(2, 3). Suppose that this element is yellow. Since there is a group that is colored identically, it must contain copies of the red, blue, and yellow elements we have identified; we can now find a pair of red elements, a pair of blue elements, and a pair of yellow elements that 'focus' on the same integer, so that whatever color it is, it must complete a progression.
The proof for W(2, 3) depends essentially on proving that W(32, 2) ≤ 33. We divide the integers {1,...,325} into 65 'blocks', each of which can be colored in 32 different ways, and then show that two blocks of the first 33 must be the same color, and there is a block coloured the opposite way. Similarly, the proof for W(3, 3) depends on proving that
By a double induction
on the number of colors and the length of the progression, the theorem is proved in general.
consists of
numbers of the form:
where a is the basepoint, the s's are the different step-sizes, and the i's range from 0 to L-1. A d-dimensional AP is homogenous for some coloring when it is all the same color.
A D-dimensional arithmetic progression with benefits is all numbers of the form above, but where you add on some of the "boundary" of the arithmetic progression, i.e. some of the indices i's can be equal to L. The sides you tack on are ones where the first k i's are equal to L, and the remaining i's are less than L.
The boundaries of a D-dimensional AP with benefits are these additional arithmetic progressions of dimension d-1,d-2,d-3,d-4, down to 0. The 0 dimensional arithmetic progression is the single point at index value (L,L,L,L...,L). A D-dimensional AP with benefits is homogenous when each of the boundaries are individually homogenous, but different boundaries do not have to necessarily have the same color.
Next define the quantity MinN(L, D, N) to be the least integer so
that any assignement of N colors to an interval of length MinN or more
necessarily contains a homogenous D-dimensional arithmetical progression with benefits.
The goal is to bound the size of MinN. Note that MinN(L,1,N) is an upper bound for Van-Der-Waerden's
number. There are two inductions steps, as follows:
1. Assume MinN is known for a given lengths L for all dimensions of arithmetic progressions with benefits up to D. This formula gives a bound on MinN when you increase the dimension to D+1:
let
Proof:
First, if you have an n-coloring of the interval 1...I, you can define a block coloring of k-size
blocks. Just consider each sequence of k colors in each k block to define a unique color. Call this k-blocking an n-coloring. k-blocking an n coloring of length l produces an n^k coloring of length l/k.
So given a n-coloring of an interval I of size M*MinN(L,1,n^M)) you can M-block it into an n^M coloring
of length MinN(L,1,n^M). But that means, by the definition of MinN, that you can find a 1-dimensional arithmetic sequence (with benefits) of length L in the block coloring, which is a sequence of blocks equally spaced, which are all the same block-color, i.e. you have a bunch of blocks of length M in the original sequence, which are equally spaced, which have exactly the same sequence of colors inside.
Now, by the definition of M, you can find a d-dimensional arithmetic sequence with benefits in any one of these blocks, and since all of the blocks have the same sequence of colors, the same d-dimensional AP with benefits appears in all of the blocks, just by translating it from block to block. This is the definition of a d+1 dimensional arithmetic progression, so you have a homogenous d+1 dimensional AP. The new stride parameter s_{D+1} is defined to be the distance between the blocks.
But you need benefits. The boundaries you get now are all old boundaries, plus their translations into identically colored blocks, because i_{D+1} is always less than L. The only boundary which is not like this is the 0 dimensional point when
. This is a single point, and is automatically homogenous.
2. Assume MinN is known for one value of L and all possible dimensions D. Then you can bound MinN for length L+1.
proof:
Given an n-coloring of an interval of size MinN(L,n,n), by definition, you can find an arithmetic sequence with benefits of dimension n of length L. But now, the number of "benefit" boundaries is equal to the number of colors, so one of the homogenous boundaries, say of dimension k, has to have the same color as another one of the homogenous benefit boundaries, say the one of dimension p
if
then
This constructs a sequence of dimension 1, and the "benefits" are automatic, just add on another point of whatever color. To include this boundary point, one has to make the interval longer by the maximum possible value of the stride, which is certainly less than the interval size. So doubling the interval size will definitely work, and this is the reason for the factor of two. This completes the induction on L.
Base case: MinN(1,d,n)=1, i.e. if you want a length 1 homogenous d-dimensional arithmetic sequence, with or without benefits, you have nothing to do. So this forms the base of the induction. The VanDerWaerden theorem itself is the assertion that MinN(L,1,N) is finite, and it follows from the base case and the induction steps.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
called Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
. Van der Waerden's theorem states that for any given positive integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s r and k, there is some number N such that if the integers {1, 2, ..., N} are colored
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
, each with one of r different colors, then there are at least k integers in arithmetic progression
Arithmetic progression
In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...
all of the same color. The least such N is the Van der Waerden number W(r, k). It is named after the Dutch mathematician B. L. van der Waerden
Bartel Leendert van der Waerden
Bartel Leendert van der Waerden was a Dutch mathematician and historian of mathematics....
.
For example, when r = 2, you have two colors, say red
Red
Red is any of a number of similar colors evoked by light consisting predominantly of the longest wavelengths of light discernible by the human eye, in the wavelength range of roughly 630–740 nm. Longer wavelengths than this are called infrared , and cannot be seen by the naked eye...
and blue
Blue
Blue is a colour, the perception of which is evoked by light having a spectrum dominated by energy with a wavelength of roughly 440–490 nm. It is considered one of the additive primary colours. On the HSV Colour Wheel, the complement of blue is yellow; that is, a colour corresponding to an equal...
. W(2, 3) is bigger than 8, because you can color the integers from {1, ..., 8} like this:
1 2 3 4 5 6 7 8
B R R B B R R B
and no three integers of the same color form an arithmetic progression
Arithmetic progression
In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...
. But you can't add a ninth integer to the end without creating such a progression. If you add a red 9
Red
Red is any of a number of similar colors evoked by light consisting predominantly of the longest wavelengths of light discernible by the human eye, in the wavelength range of roughly 630–740 nm. Longer wavelengths than this are called infrared , and cannot be seen by the naked eye...
, then the red 3
Red
Red is any of a number of similar colors evoked by light consisting predominantly of the longest wavelengths of light discernible by the human eye, in the wavelength range of roughly 630–740 nm. Longer wavelengths than this are called infrared , and cannot be seen by the naked eye...
, 6
Red
Red is any of a number of similar colors evoked by light consisting predominantly of the longest wavelengths of light discernible by the human eye, in the wavelength range of roughly 630–740 nm. Longer wavelengths than this are called infrared , and cannot be seen by the naked eye...
, and 9
Red
Red is any of a number of similar colors evoked by light consisting predominantly of the longest wavelengths of light discernible by the human eye, in the wavelength range of roughly 630–740 nm. Longer wavelengths than this are called infrared , and cannot be seen by the naked eye...
are in arithmetic progression. Alternatively, if you add a blue 9
Blue
Blue is a colour, the perception of which is evoked by light having a spectrum dominated by energy with a wavelength of roughly 440–490 nm. It is considered one of the additive primary colours. On the HSV Colour Wheel, the complement of blue is yellow; that is, a colour corresponding to an equal...
, then the blue 1
Blue
Blue is a colour, the perception of which is evoked by light having a spectrum dominated by energy with a wavelength of roughly 440–490 nm. It is considered one of the additive primary colours. On the HSV Colour Wheel, the complement of blue is yellow; that is, a colour corresponding to an equal...
, 5
Blue
Blue is a colour, the perception of which is evoked by light having a spectrum dominated by energy with a wavelength of roughly 440–490 nm. It is considered one of the additive primary colours. On the HSV Colour Wheel, the complement of blue is yellow; that is, a colour corresponding to an equal...
, and 9
Blue
Blue is a colour, the perception of which is evoked by light having a spectrum dominated by energy with a wavelength of roughly 440–490 nm. It is considered one of the additive primary colours. On the HSV Colour Wheel, the complement of blue is yellow; that is, a colour corresponding to an equal...
are in arithmetic progression. In fact, there is no way of coloring 1 through 9 without creating such a progression. Therefore, W(2, 3) is 9.
It is an open problem to determine the values of W(r, k) for most values of r and k. The proof of the theorem provides only an upper bound. For the case of r = 2 and k = 3, for example, the argument given below shows that it is sufficient to color the integers {1, ..., 325} with two colors to guarantee there will be a single-colored arithmetic progression of length 3. But in fact, the bound of 325 is very loose; the minimum required number of integers is only 9. Any coloring of the integers {1, ..., 9} will have three evenly spaced integers of one color.
For r = 3 and k = 3, the bound given by the theorem is 7(2·37 + 1)(2·37·(2·37 + 1) + 1), or approximately 4.22·1014616. But actually, you don't need that many integers to guarantee a single-colored progression of length 3; you only need 27. (And it is possible to color {1, ..., 26} with three colors so that there is no single-colored arithmetic progression of length 3; for example, RRYYRRYBYBBRBRRYRYYBRBBYBY.)
Anyone who can reduce the general upper bound to any 'reasonable' function can win a large cash prize. Ronald Graham
Ronald Graham
Ronald Lewis Graham is a mathematician credited by the American Mathematical Society as being "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years"...
has offered a prize of US$1000 for showing W(2,k)<2k2. The current record is due to Timothy Gowers, who establishes
by first establishing a similar result for Szemerédi's theorem
Szemerédi's theorem
In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...
, which is a stronger version of Van der Waerden's theorem. The previously best known bound was due to Saharon Shelah
Saharon Shelah
Saharon Shelah is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey.-Biography:...
and proceeded via first proving a result for the Hales–Jewett theorem, which is another strengthening of Van der Waerden's theorem.
The best-known lower bound for
is that for all positive ε.Proof of Van der Waerden's theorem (in a special case)
The following proof is due to Ron GrahamRonald Graham
Ronald Lewis Graham is a mathematician credited by the American Mathematical Society as being "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years"...
and B.L. Rothschild. Khinchin gives a fairly simple proof of the theorem without estimating W(r, k).
We will prove the special case mentioned above, that W(2, 3) ≤ 325. Let c(n) be a coloring of the integers {1, ..., 325}. We will find three elements of {1, ..., 325} in arithmetic progression that are the same color.
Divide {1, ..., 325} into the 65 blocks {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, thus each block is of the form {b ·5 + 1, ..., b ·5 + 5} for some b in {0, ..., 64}. Since each integer is colored either red or blue, each block is colored in one of 32 different ways. By the pigeonhole principle, there are two blocks among the first 33 blocks that are colored identically. That is, there are two integers b1 and b2, both in {0,...,32}, such that
- c(b1·5 + k) = c(b2·5 + k)
for all k in {1, ..., 5}. Among the three integers b1·5 + 1, b1·5 + 2, b1·5 + 3, there must be at least two that are the same color. (The pigeonhole principle again.) Call these b1·5 + a1 and b1·5 + a2, where the ai are in {1,2,3} and a1 < a2. Suppose (without loss of generality) that these two integers are both red. (If they are both blue, just exchange 'red' and 'blue' in what follows.)
Let a3 = 2·a2 − a1. If b1·5 + a3 is red, then we have found our arithmetic progression: b1·5 + ai are all red.
Otherwise, b1·5 + a3 is blue. Since a3 ≤ 5, b1·5 + a3 is in the b1 block, and since the b2 block is colored identically, b2·5 + a3 is also blue.
Now let b3 = 2·b2 − b1. Then b3 ≤ 64. Consider the integer b3·5 + a3, which must be ≤ 325. What color is it?
If it is red, then b1·5 + a1, b2·5 + a2, and b3·5 + a3 form a red arithmetic progression. But if it is blue, then b1·5 + a3, b2·5 + a3, and b3·5 + a3 form a blue arithmetic progression. Either way, we are done.
A similar argument can be advanced to show that V(3, 3) ≤ 7(2·37+1)(2·37·(2·37+1)+1). One begins by dividing the integers into 2·37·(2·37 + 1) + 1 groups of 7(2·37 + 1) integers each; of the first 37·(2·37 + 1) + 1 groups, two must be colored identically.
Divide each of these two groups into 2·37+1 subgroups of 7 integers each; of the first 37 + 1 subgroups in each group, two of the subgroups must be colored identically. Within each of these identical subgroups, two of the first four integers must be the same color, say red; this implies either a red progression or an element of a different color, say blue, in the same subgroup.
Since we have two identically-colored subgroups, there is a third subgroup, still in the same group that contains an element which, if either red or blue, would complete a red or blue progression, by a construction analogous to the one for W(2, 3). Suppose that this element is yellow. Since there is a group that is colored identically, it must contain copies of the red, blue, and yellow elements we have identified; we can now find a pair of red elements, a pair of blue elements, and a pair of yellow elements that 'focus' on the same integer, so that whatever color it is, it must complete a progression.
The proof for W(2, 3) depends essentially on proving that W(32, 2) ≤ 33. We divide the integers {1,...,325} into 65 'blocks', each of which can be colored in 32 different ways, and then show that two blocks of the first 33 must be the same color, and there is a block coloured the opposite way. Similarly, the proof for W(3, 3) depends on proving that
By a double induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
on the number of colors and the length of the progression, the theorem is proved in general.
Proof
A D-dimensional arithmetic progressionGeneralized arithmetic progression
In mathematics, a multiple arithmetic progression, generalized arithmetic progression, or k-dimensional arithmetic progression, is a set of integers constructed as an arithmetic progression is, but allowing several possible differences. So, for example, we start at 17 and may add a multiple of 3 or...
consists of
numbers of the form:
where a is the basepoint, the s's are the different step-sizes, and the i's range from 0 to L-1. A d-dimensional AP is homogenous for some coloring when it is all the same color.
A D-dimensional arithmetic progression with benefits is all numbers of the form above, but where you add on some of the "boundary" of the arithmetic progression, i.e. some of the indices i's can be equal to L. The sides you tack on are ones where the first k i's are equal to L, and the remaining i's are less than L.
The boundaries of a D-dimensional AP with benefits are these additional arithmetic progressions of dimension d-1,d-2,d-3,d-4, down to 0. The 0 dimensional arithmetic progression is the single point at index value (L,L,L,L...,L). A D-dimensional AP with benefits is homogenous when each of the boundaries are individually homogenous, but different boundaries do not have to necessarily have the same color.
Next define the quantity MinN(L, D, N) to be the least integer so
that any assignement of N colors to an interval of length MinN or more
necessarily contains a homogenous D-dimensional arithmetical progression with benefits.
The goal is to bound the size of MinN. Note that MinN(L,1,N) is an upper bound for Van-Der-Waerden's
number. There are two inductions steps, as follows:
1. Assume MinN is known for a given lengths L for all dimensions of arithmetic progressions with benefits up to D. This formula gives a bound on MinN when you increase the dimension to D+1:
let
Proof:
First, if you have an n-coloring of the interval 1...I, you can define a block coloring of k-size
blocks. Just consider each sequence of k colors in each k block to define a unique color. Call this k-blocking an n-coloring. k-blocking an n coloring of length l produces an n^k coloring of length l/k.
So given a n-coloring of an interval I of size M*MinN(L,1,n^M)) you can M-block it into an n^M coloring
of length MinN(L,1,n^M). But that means, by the definition of MinN, that you can find a 1-dimensional arithmetic sequence (with benefits) of length L in the block coloring, which is a sequence of blocks equally spaced, which are all the same block-color, i.e. you have a bunch of blocks of length M in the original sequence, which are equally spaced, which have exactly the same sequence of colors inside.
Now, by the definition of M, you can find a d-dimensional arithmetic sequence with benefits in any one of these blocks, and since all of the blocks have the same sequence of colors, the same d-dimensional AP with benefits appears in all of the blocks, just by translating it from block to block. This is the definition of a d+1 dimensional arithmetic progression, so you have a homogenous d+1 dimensional AP. The new stride parameter s_{D+1} is defined to be the distance between the blocks.
But you need benefits. The boundaries you get now are all old boundaries, plus their translations into identically colored blocks, because i_{D+1} is always less than L. The only boundary which is not like this is the 0 dimensional point when
. This is a single point, and is automatically homogenous.2. Assume MinN is known for one value of L and all possible dimensions D. Then you can bound MinN for length L+1.
proof:
Given an n-coloring of an interval of size MinN(L,n,n), by definition, you can find an arithmetic sequence with benefits of dimension n of length L. But now, the number of "benefit" boundaries is equal to the number of colors, so one of the homogenous boundaries, say of dimension k, has to have the same color as another one of the homogenous benefit boundaries, say the one of dimension p
if
-
has the same color as
then
-
have the same color
i.e. u makes a sequence of length L+1.
This constructs a sequence of dimension 1, and the "benefits" are automatic, just add on another point of whatever color. To include this boundary point, one has to make the interval longer by the maximum possible value of the stride, which is certainly less than the interval size. So doubling the interval size will definitely work, and this is the reason for the factor of two. This completes the induction on L.
Base case: MinN(1,d,n)=1, i.e. if you want a length 1 homogenous d-dimensional arithmetic sequence, with or without benefits, you have nothing to do. So this forms the base of the induction. The VanDerWaerden theorem itself is the assertion that MinN(L,1,N) is finite, and it follows from the base case and the induction steps.
See also
- Van der Waerden numbers for all known values for W(n,r) and the best-known bounds for unknown values