Skip to main content

Section 4.2 Schur's Theorem

The hardest thing to see is what is in front of your eyes. — Johann Wolfgang von Goethe, German writer and politician, 1749 — 1832.

Reminder: Schur's Theorem. If the set of positive integers \(\mathbb{N}\) is finitely coloured then there exist \(x,y,z\) having the same colour such that

\begin{equation*} x+y=z\text{.} \end{equation*}
Figure 4.2.1. Schur's Theorem: If the set of positive integers \(\mathbb{N}\) is finitely coloured then there exist \(x,y,z\) having the same colour such that \(x+y=z\text{.}\)
Definition 4.2.2.

A triple \(x,y,z\) that satisfies \(x+y=z\) is called a Schur triple.

Reminder: The Ramsey number \(R(s, t)\) is the minimum number \(n\) for which any edge 2-coloring of \(K_n\text{,}\) a complete graph on \(n\) vertices, in red and blue contains a red \(K_s\) or a blue \(K_t\text{.}\)

Recall Definition 2.3.18:

The Ramsey number \(R(s_1, s_2,\ldots ,s_r)\) is the minimum number \(n\) for which any edge \(r\)-colouring of \(K_n\text{,}\) a complete graph on \(n\) vertices, contains an \(i\)-monochromatic \(K_{s_i}\text{,}\) for some \(i\in[1,r]\text{.}\)

Figure 4.2.3. Ramsey Theorem: If the the complete graph \(K_{R(s_1,s_2,\ldots,s_r)}\) is \(r\)-coloured then, for some \(i\in[1,r]\text{,}\) there exists a complete graph \(K_{s_i}\) that is \(i\)-monochromatic.
Example 4.2.4.

\(R(3,3,3)\leq 17\text{.}\)

See Figures 4.2.5 and Figure 4.2.6 .

Figure 4.2.5. Use the the pigeonhole principle to conclude that if the edges of \(K_{17}\) are 3-coloured then each vertex is incident to at least six edges that are of the same colour.
Figure 4.2.6. Two cases … Done!
Question 4.2.7.

What is the meaning of \(R(3,4,5,6)\text{?}\) \(R(3,3,3,3,3)\text{?}\)

Let \(c:\mathbb{N}\to [1,2,\ldots,r]\) and let \(M=R( \underbrace{3,3,\ldots,3}_r)\text{.}\) See Figures 4.2.9 and Figure 4.2.10 .

Figure 4.2.9. Denote vertices of \(K_M\) by \(1,2,\ldots, M\text{.}\) For any \(a,b\in[1,M]\text{,}\) colour the edge \(\{a,b\}\) by \(c(|a-b|)\text{.}\) Observe that all we need is the restriction of the \(r\)-colouring \(c\) on the interval \([1,M]\text{.}\)
Figure 4.2.10. There is a monochromatic triangle with vertices \(i\lt j\lt k\text{.}\) (Why?) Take \(x=k-j\text{,}\) \(y=j-i\text{,}\) and \(z=k-i\text{.}\) Done! (Do you see why?)
Example 4.2.12.

What is \(s(2)\text{?}\)

  1. Can you 2-colour, say in red and blue, the interval of positive integers \([1,4]\) and avoid monochromatic Schur triples? Note that \(1,1,2\) and \(2,2,4\) are Schur triples. See Figure 4.2.13.

    Figure 4.2.13. \(s(2)>4\)

  2. Can you 2-colour, say in red and blue, the interval of positive integers \([1,5]\) and avoid monochromatic Schur triples? Note that \(1,1,2\) and \(2,2,4\) are Schur triples. See Figure 4.2.14.

    Figure 4.2.14. \(s(2)=5\)

Known Schur Numbers.

\begin{equation*} s(1)=2, s(2)=5, s(3)=14, s(4)=45\text{.} \end{equation*}

Time Machine.

In 1637 Fermat scribbled into the margins of his copy of Arithmetica by Diophantus, that

It is impossible for a cube to be the sum of two cubes, a fourth power to be the sum of two fourth powers, or in general for any number that is a power greater than the second to be the sum of two like powers. I have discovered a truly marvellous demonstration of this proposition that this margin is too narrow to contain.

The margin note became known as Fermat's Last Theorem. It was proved by Andrew Wiles in 1995.

In 1916 Schur proved the following:

Let \(n > 1\text{.}\) Then, for all primes \(p > s(n)\text{,}\) the congruence

\begin{equation*} x^n + y^n\equiv z^n (\textrm{mod} \ p) \end{equation*}

has a solution in the integers, such that \(p\) does not divide \(xyz\text{.}\)

Fact:

For any odd prime \(p\text{,}\) the multiplicative group

\begin{equation*} \mathbb{Z}^*_p=\mathbb{Z}/ p\mathbb{Z}=\{1,2,\ldots,p-1\} \end{equation*}

is cyclic.

Example 4.2.15.

Take \(p=5\text{.}\) Then \(\mathbb{Z}^*_5=\{1,2,3,4\}\) and the multiplication is given by

\begin{equation*} \begin{array}{c||c|c|c|c} \cdot\amp 1\amp 2\amp 3\amp 4\\ \hline \hline 1\amp \amp \amp \amp \\ \hline 2\amp \amp \amp \amp \\ \hline 3\amp \amp \amp \amp \\ \hline 4\amp \amp \amp \amp \end{array} \end{equation*}

Also, \(\mathbb{Z}^*_5=\{2,2^2,2^3,2^4\}=\{2,4,3,1\}\) and \(\mathbb{Z}^*_7= \{3,3^2,3^3,3^4,3^5,3^6\}=\{3,2,6,4,5,1\}\ \text{.}\)

In general, for any odd prime \(p\) there is \(q\in \{1,\ldots,p-1\}\) such that \(\mathbb{Z}^*_p=\{q,q^2,\ldots, q^{p-1}\}\text{.}\)

See Figures 4.2.17 — Figure 4.2.19.

Figure 4.2.17. \(\mathbb{Z}_p^\ast=\{ 1,2, \ldots, p-1\} =\{ q,q^2, \ldots,q^{p-1}\}\)
Figure 4.2.18. An \(n\)-colouring of \(\{ 1,2, \ldots, p-1\}\text{,}\) \(p>s(n)\)
Figure 4.2.19. There is a monochromatic Schur triple!

From

\begin{equation*} q^{nr+i}+q^{ns+i}=q^{nt+i} \Leftrightarrow q^i(q^{nr}+q^{ns}-q^{nt})\equiv 0\pmod{p} \end{equation*}

we conclude that

\begin{equation*} p|q^i(q^{nr}+q^{ns}-q^{nt})\text{.} \end{equation*}

Since \(0\leq q^i\lt n\lt s(n)\leq p-1\) it follows that \(p \nmid q^i\text{.}\) Therefore

\begin{equation*} p|(q^{nr}+q^{ns}-q^{nt}) \end{equation*}

or, what is the same

\begin{equation*} q^{nr}+q^{ns}-q^{nt}\equiv 0\pmod{p}\text{.} \end{equation*}

By taking \(x=q^r\text{,}\) \(y=q^s\text{,}\) and \(z=q^t\) we obtain

\begin{equation*} x^n+y^n\equiv z^n\pmod{p}\text{.} \end{equation*}
Example 4.2.20.

Let \(P\) be the set of points in the plane \(x+y-z=0\) whose coordinates are positive integers. Let an \(r\)-colouring of the set of positive integers be given.

For each \((a,b,c)\in P\text{,}\) do the following. If \(a,b,c\) are of the same colour, then colour \((a,b,c)\) with that colour. Otherwise, mark \((a,b,c)\) with an \(X\text{.}\)

Three Questions:

  1. Can all of the points be marked with an \(X\text{?}\)

  2. Can we tell if, under any given finite colouring, the plane must contain an infinite number of coloured points?

  3. Same for the plane \(x+y-2z=0\text{.}\)

Resources.

  1. For more details see [2], pp. 69-70, [3], and [7].

  2. Schur's Theorem - Wikipedia

  3. Schur's theorem and related topics in Ramsey theory - by Summer Lynne Kisner, pp 19-53

  4. Ramsey Theory - by Jacob Fox (p 3)