Introduction to Ramsey Theory: Students' Projects

Remark 49.1.2. Importance of No Constant Terms.

Suppose $p_1(x) = 2x$ and $p_2(x) = 2x+1$ and $\mathbb{N}$ is 2–coloured such that even numbers are red and odd numbers are blue.

• Suppose that $a$ is even. Then $\color{red}{a}$ is red and for any natural number $d\text{,}$ $\color{red}{a+p_1(d)}$ is red because $a+p_1(d)=a+2d$ is even, but $\color{blue}{a+p_2(d)}$ is blue because $a+p_2(d)=a+2d+1$ is odd.

• Suppose that $a$ is odd. Then $\color{blue}{a}$ is blue and for any natural number $d\text{,}$ $\color{blue}{a+p_1(d)}$ is blue because $a+p_1(d)=a+2d$$ is odd, but $\color{red}{a+p_2(d)}$ is red because $a+p_2(d)=a+2d+1$ is even.

Contradiction!

Remark 49.1.3. Is the restriction of integer coefficients necessary?

Suppose the polynomials $p_1, p_2, \ldots, p_m$ have rational coefficients and no constant term. Then define $q_i(x) = p_i(cx)\text{,}$ for $1 \leq i \leq m$ where $c$ is the least common multiple of the denominators of the coefficients of all the polynomials. Now the polynomials $q_1, q_2, \ldots q_m$ have integer coefficients and no constant term.

For example, let $p_1(x)=\frac{2}{3}x^2+3x\text{,}$ $p_2(x)=\frac{5}{12}x^3+4x^2+\frac{2}{8}x\text{,}$ $p_3(x)=\frac{7}{24}x^4\text{,}$ $p_4(x)=\frac{8}{3}x^3+\frac{9}{2}x\text{.}$

Then $c=24\text{.}$

The coefficient of the term $x^n$ is multiplied by $c^n\text{,}$ so the obtained polynomials are with integral coefficients:

$q_1(x)=p_1(24x)=\frac{2}{3}(24x)^2+3(24x)=384x^2+72x\text{,}$
$q_2(x)=p_2(24x)=\frac{5}{12}(24x)^3+4(24x)^2+\frac{2}{8}(24x)=5760x^3+2304+6x\text{,}$
$q_3(x)=p_3(24x)=\frac{7}{24}(24x)^4=96768x^4\text{,}$ and
$q_4(x)=p_4(24x)=\frac{8}{3}(24x)^3+\frac{9}{2}(24x)=36864x^3+108x\text{.}$

If $a,d\in \mathbb{N}$ are such that $a+q_1(d),a+q_2(d),a+q_3(d)\text{,}$ and $a+q_4(d)$ are of the same colour, then $a+p_1(24d),a+p_2(24d),a+p_3(24d)\text{,}$ and $a+p_4(24d)$ are of the same colour too.

Remark 49.1.4. Why the name ``Polynomial van der Waerden Theorem''.

Suppose that $p_i(x) = ix$ for $1\leq i \leq l-1\text{.}$ Then whenever $\mathbb{N}$ is finitely coloured there exists natural numbers $a$ and $d$ such that the set $\{a, a + p_1(d), a + p_2(d), \ldots, a + p_{l-1}(d)\}$is monochromatic.

However we can also view this as a monochromatic set $\{a, a + d, a + 2d, ..., a + (l-1)d\text{.}$

This is van der Waerden's theorem!