Editing Van der Waerden's theorem (section)

== Proof ==

A [[Generalized arithmetic progression|''D-dimensional arithmetic progression'' (AP)]] consists of
numbers of the form:
: <math> a + i_1 s_1 + i_2 s_2 + \cdots + i_D s_D </math>
where {{mvar|''a''}} is the basepoint, the {{mvar|''s''}}'s are positive step-sizes, and the {{mvar|''i''}}'s range from 0 to {{math|''L''&nbsp;−&nbsp;1}}. A {{mvar|''d''}}-dimensional AP is ''homogeneous'' for some coloring when it is all the same color.

A ''{{mvar|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 {{mvar|''i''}}'s can be equal to {{mvar|''L''}}. The sides you tack on are ones where the first {{mvar|''k''}} {{mvar|''i''}}'s are equal to {{mvar|''L''}}, and the remaining {{mvar|''i''}}'s are less than {{mvar|''L''}}.

The boundaries of a {{mvar|D}}-dimensional AP with benefits are these additional arithmetic progressions of dimension <math>d-1, d-2, d-3, d-4</math>, down to 0. The 0-dimensional arithmetic progression is the single point at index value <math>(L, L, L, L, \ldots, L)</math>. A {{mvar|D}}-dimensional AP with benefits is ''homogeneous'' when each of the boundaries are individually homogeneous, but different boundaries do not have to necessarily have the same color.

Next define the quantity {{math|MinN(''L'', ''D'', ''N'')}} to be the least integer so that any assignment of {{mvar|N}} colors to an interval of length {{math|MinN}} or more necessarily contains a homogeneous {{mvar|D}}-dimensional arithmetical progression with benefits.

The goal is to bound the size of {{math|MinN}}. Note that {{math|MinN(''L'',1,''N'')}} is an upper bound for Van der Waerden's number. There are two inductions steps, as follows:

{{Math_theorem|name=Lemma 1|math_statement=Assume {{math|MinN}} is known for a given lengths {{mvar|''L''}} for all dimensions of arithmetic progressions with benefits up to {{mvar|''D''}}. This formula gives a bound on {{math|MinN}} when you increase the dimension to {{math|''D''&nbsp;+&nbsp;1}}:

let <math> M = \operatorname{MinN}(L,D,n)</math>, then

: <math> \operatorname{MinN}(L, D+1 , n) \le  M \cdot \operatorname{MinN}(L,1,n^M)</math>
}}
{{Math_proof|First, if you have an {{mvar|''n''}}-coloring of the interval 1...{{mvar|''I''}}, you can define a ''block coloring'' of {{mvar|''k''}}-size blocks. Just consider each sequence of {{mvar|''k''}} colors in each {{mvar|''k''}} block to define a unique color. Call this ''{{mvar|k}}-blocking'' an {{mvar|''n''}}-coloring. {{mvar|''k''}}-blocking an {{mvar|''n''}} coloring of length {{mvar|''l''}} produces an {{math|''n''{{sup|''k''}}}} coloring of length {{math|l/''k''}}.

So given a {{mvar|''n''}}-coloring of an interval {{mvar|''I''}} of size <math>M \cdot \operatorname{MinN}(L,1,n^M))</math> you can {{mvar|''M''}}-block it into an {{math|''n''{{sup|''M''}}}} coloring of length <math>\operatorname{MinN}(L,1,n^M)</math>. But that means, by the definition of {{math|MinN}}, that you can find a 1-dimensional arithmetic sequence (with benefits) of length {{mvar|''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 {{mvar|''M''}} in the original sequence, which are equally spaced, which have exactly the same sequence of colors inside.

Now, by the definition of {{mvar|''M''}}, you can find a {{mvar|''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 {{mvar|''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 {{math|''d''&nbsp;+&nbsp;1}} dimensional arithmetic progression, so you have a homogeneous {{math|''d''&nbsp;+&nbsp;1}} dimensional AP. The new stride parameter {{math|s{{sub|''D''&nbsp;+&nbsp;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 {{math|i{{sub|D+1}}}} is always less than {{mvar|L}}. The only boundary which is not like this is the 0-dimensional point when <math>i_1=i_2=\cdots=i_{D+1}=L</math>. This is a single point, and is automatically homogeneous.
}}
{{Math_theorem|name=Lemma 2|math_statement=Assume {{math|MinN}} is known for one value of {{mvar|''L''}} and all possible dimensions {{mvar|''D''}}. Then you can bound MinN for length {{math|''L''&nbsp;+&nbsp;1}}.

: <math>\operatorname{MinN}(L+1,1,n) \le 2\operatorname{MinN}(L,n,n)</math>
}}
{{Math_proof|Given an {{mvar|n}}-coloring of an interval of size {{math|MinN(''L'',''n'',''n'')}}, by definition, you can find an arithmetic sequence with benefits of dimension {{mvar|n}} of length {{mvar|L}}. But now, the number of "benefit" boundaries is equal to the number of colors, so one of the homogeneous boundaries, say of dimension {{mvar|k}}, has to have the same color as another one of the homogeneous benefit boundaries, say the one of dimension {{math|''p''&nbsp;<&nbsp;''k''}}. This allows a length {{math|''L''&nbsp;+&nbsp;1}} arithmetic sequence (of dimension 1) to be constructed, by going along a line inside the {{mvar|''k''}}-dimensional boundary which ends right on the {{mvar|''p''}}-dimensional boundary, and including the terminal point in the {{mvar|''p''}}-dimensional boundary. In formulas:

if
: <math> a+ L s_1 + L s_2 + \cdots + L s_{D-k}</math> has the same color as
: <math> a + L s_1 + L s_2 + \cdots +L s_{D-p}</math>
then
: <math> a + L \cdot (s_1 + \cdots +s_{D-k}) + u \cdot (s_{D-k+1} + \cdots +s_p) </math> have the same color
: <math> u = 0,1,2,\cdots,L-1,L </math> i.e. {{mvar|u}} makes a sequence of length {{mvar|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 {{mvar|''L''}}.
}}
Base case: {{math|MinN(1,''d'',''n'') {{=}} 1}}, i.e. if you want a length 1 homogeneous {{mvar|d}}-dimensional arithmetic sequence, with or without benefits, you have nothing to do. So this forms the base of the induction. The Van der Waerden theorem itself is the assertion that {{math|MinN(''L'',1,''N'')}} is finite, and it follows from the base case and the induction steps.<ref name="Graham1974">{{cite journal |author-link=Ronald Graham |first1=R. L. |last1=Graham |first2=B. L. |last2=Rothschild |title=A short proof of van der Waerden's theorem on arithmetic progressions |journal=[[Proceedings of the American Mathematical Society]] |volume=42 |issue=2 |year=1974 |pages=385–386 |doi=10.1090/S0002-9939-1974-0329917-8 |doi-access=free }}</ref>