Introduction to Ramsey Theory: Students' Projects

Subsection 49.3.1 Initialization

First we need an ordering on the collection of polynomials \(p_1=p_1(x),p_2=p_2(x),\ldots,p_m=p_m(x)\) such that when we form a collection of difference polynomials, we already know that we can find a monochromatic set for this new collection.

Let \(A=\{p_1,p_2,....,p_m\}\) be a set of integral polynomials. Let \(D\) be the maximum degree of these polynomials. For \(1\leq i\leq D\text{,}\) let \(N_i\) be the number of distinct leading coefficients of polynomial in \(A\) of degree \(i\text{.}\)

Define the weight vector of \(A\) to be \((N_1,N_2,\ldots,N_D)\text{.}\) We say that \((N_1,N_2,\ldots.,N_D) \lt (M_1,M_2,\ldots,M_D)\) if there exists \(r\) such that \(N_r\lt M_r\) and \(N_i=M_i\) for \(i\gt r\text{.}\) This is easily seen to be a well ordering. The induction will be on the collection of polynomials in this ordering.

Suppose that all polynomials have the same degree and the same leading coefficient. If we take differences between one polynomial and shifts of another polynomial, then we always obtain a polynomial of a lower degree. This gives some indication that it is the number of distinct leading coefficients that is important rather than the number of polynomials.

Subsection 49.3.2 Outer Induction

We do a multiple induction, first let \(P=\{p_1,p_2,\ldots,p_m\}\text{.}\) We will do induction on the weight vector of \(P\text{,}\) however we need the theorem in it is compact form.

Outer Induction Hypothesis: Suppose that \(p_1,p_2,\ldots,p_m\) are integral polynomials. Then for all \(k\) there exists \(N\) such that whenever \([N]\) is k–coloured there exists \(a\) and \(d\) such that the set \(\{a,a+p_1(d),a+p_2(d),\ldots,a+p_m(d)\}\) is monochromatic.

Suppose that the outer induction hypothesis is true for all collections of polynomials with weight vectors less than that of \(P\text{.}\) We need to show that it is true for \(P\text{.}\)

We will say that a set A of points \(a_j\) for \(1\leq j\leq m\) is focused at \(a\) if there exists \(d\) such that \(a_j-a=p_j(d)\text{.}\) We will say that the sets \(A_1,A_2,\ldots,A_r\) are colour focused at \(a\) if each set \(A_i\) is focused at \(a\text{,}\) each set \(A_i\) is monochromatic, and the sets \(A_i\) for \(1\leq i\leq r\) have distinct colours. This is exactly the condition that forced \(a\) to have a colour different from that of any of the \(A_i\)s.

Subsection 49.3.3 Inner Induction

For all \(r\leq k\) there exists \(N\) such that if \([N]\) is \(k\)–coloured either there exists \(r\) colour focused sets \(A_1,A_2,\ldots,A_r\) together with their focus \(a\text{,}\) or there exists \(a\) and \(d\) such that the set \(\{a,a+p_1(d),\ldots,a+p_m(d)\}\) is monochromatic.

We can see that from the hypothesis the result is immediate. Set \(r=k\text{,}\) now if there exists \(a\) and \(d\) such that the set \(\{a,a+p_1(d),\ldots,a+p_m(d)\}\) is monochromatic then we are done. Otherwise there exists \(A_1,A_2,\ldots,A_r\) colour focused at \(a\text{.}\) The focus must have the same colour as one of the set \(A_i\) thus that point with the set is monochromatic.

Here we have \(r=k=3\) and we can see no matter which of the \(3\) colours \(10\) is we will have a monochromatic arithmetic progression.

The induction is on \(r\text{,}\) thus suppose that it is true for \(r-1\) and \(N\text{.}\) We will show that there is an \(N^\prime\) satisfying the hypothesis for \(r\text{.}\) We may assume there does not exists \(a\) and \(d\) with the set \(\{a\} \cup \{a+p_j(d):1\le j\leq m\}\) monochromatic.

Let \(d_{max}\) be the maximum possible \(d\) for which points \(a,a_1,a_2,\ldots,a_k \in [N]\) exist with \(a_i-a=p_i(d)\text{.}\) (Since all polynomial tend to infinity this exists).

We cannot necessarily take \(d_{max}=N\) since the polynomials could all be zero simultaneously for some \(d\gt N\text{.}\) However, this case is trivial, if we take this \(d\) and any \(a\) then the set of points \(\{a\} \cup \{a+p_i(d):1\le i\leq m\}=\{a\}\) is monochromatic. Moreover, if this does not occur then the bound can be replaced by \(N\text{.}\) Indeed, since the value of each polynomial is a multiple of its argument, if \(d\gt N\) and not all the polynomials are zero at \(d\text{,}\) then at least one of them is larger than \(N\text{.}\)

We may assume that \(p_1\) has minimal degree amongst the \(p_i\)s. Now define polynomials \(p_{i,j}(n)=p_j(n+i)-p_j(i)-p_1(n)\) for \(0\leq i\leq d_{max}\) and \(1\leq j\leq m\text{.}\) Observe that these are integral polynomials and we can see that the constant in \(p_j(i)\) cancels the constant term in \(p_j(n+i)\) and they clearly have integer coefficients. These are smaller in the ordering defined earlier.

Suppose that \(p_j\) either has a larger degree than \(p_1\) or a different leading coefficient from that of \(p_1\text{.}\) Then all the polynomials \(p_{i,j}\) for \(0\le i\le d_{max}\) have the same leading coefficient and the same degree as \(p_j\text{.}\) If \(p_j\) has the same degree and leading coefficients as \(p_1\) then the polynomials \(p_{i,j}\) for \(1\leq i\leq d_{max}\) all have smaller degree than \(p_1\text{.}\) Thus the weight vector of this set is the same as for \(P\) in its \(i^{\mbox{th}}\) components for \(i\gt \mbox{deg}p_1\) and is one smaller for \(i=\mbox{deg}p_1\text{.}\)

Thus the weight vector of this set is less than that of \(P\text{.}\) We now have to modify these polynomials slightly. We need to do this since later in the proof we are going to divide \([N^\prime]\) into blocks of length \(N\) and we need to take account of this. So let \(q_{i,j}(n)=\frac{p_{i,j}(Nn)}{N}\text{.}\) These are integral polynomials since the \(p_{i,j}\) are. Also, observe that this collection has the same weight vector as the collection of \(p_{i,j}\) since, although the leading coefficients change the number of distinct leading coefficients of the polynomial of a given degree has not changed. Thus the outer induction hypothesis applies to \(q_{i,j}\text{.}\)

Again we divide \([N^\prime]\) into blocks of size \(N\text{,}\) setting \(B_s=\{(s-1)N+1,(s-1)N+2,\ldots,SN\}\text{.}\) Then, since there are only \(k^n\) ways of colouring a block, we can apply the outer induction to find \(s\) and \(t\) such that the blocks \(B_{s_{i,j}}\) and \(B_s\) are all coloured identically and \(s_{i,j}-s=q_{i,j}(t)\text{,}\) provided that we have chosen \(N^\prime\) large enough.

By the choice of \(N\) and the assumption that there do not exist \(a\) and \(d\) with the set \(\{a\} \cup \{a+p_j(d):1\leq j\leq m\}\) monochromatic, we know that \(B_s\) contains \(r-1\) colour focused sets \(A_1,A_2,\ldots,A_{r-1}\) together with their focus \(a\) such that \(a\) has a colour distinct from the \(r-1\) colours in any of the \(A_i\)

Suppose \(A_i=\{a_{i,j}:1\leq j\leq m\}\) and that \(a_{i,j}-a=p_j(d)\text{.}\)

Therefore the points are colour focused and the induction is almost done.

To finish the proof we note that all the properties that we have used are translation–invariant and that we can bound \(a-p_1(Nt)\) below, by \(-M\) say. Thus we can apply the above arguments to the blocks \(B^\prime_s=M+B_s\) to ensure that the new focus \((a-p_1(Nt))\) is positive.