The Proof

Section 49.3 The Proof

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{.}$

🔗

Claim 49.3.1.

The sets $\{a_{i,j}+Nq_{d_{i,j}}(t): 1\leq j\leq m\}$ for $1\leq i\leq r-1$ together with the set $\{a+Nq_{0,j}(t):1\leq j\leq m\}$ are colour focused at $a-p_1(Nt)\text{.}$

🔗

Proof.

First, observe that by construction each of the points $a_{i,j}+Nq_{d_{i,j}}(t)$ has the same colour as the point $a_{i,j}\text{.}$ Thus the set $\{a_{i,j}+Nq_{d_{i,j}}(t):1\leq j\leq m\}$ has the same colour as $A_i\text{.}$ Thus these colours are all distinct. Also each of the points $a+Nq_{0,j}(t)$ has the same colour as $a\text{,}$ so the set $\{a+Nq_{o,j}(t):1\leq j\leq m\}$ is monochromatic. Also, $a$ has a colour distinct from that of the other sets.

Thus we only need to check the following:

\begin{align*} a_{i,j}+Nq_{d_{i,j}}(t)-(a-p_1(Nt)) \amp = p_j(d_i)+p_{d_{i,j}}(Nt)+p_1(Nt)\\ \amp =p_j(d_i)+p_j(Nt+d_i)-p_j(d_i)-p_1(Nt)+p_1(Nt)\\ \amp =p_j(Nt+d_i) \end{align*}

and we have

\begin{equation*} a+Nq_{0,j}(t)-(a-p_1(Nt))=p_{0,j}(Nt)+p_1(Nt)=p_j(Nt)\mbox{.} \end{equation*}

🔗

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.