5 Extremal Combinatorics 5.3 Ramsey Theory and Probabilistic method 5.5 ***Some other methods***

5.4 Applications to Number theory

We shall show an application of pigeonhole principle to Number theory - Dirichlet’s theorem and then an application of coloring to Number theory - Schur’s theorem or that Fermat’s last theorem fails for finite fields.

Theorem 5.14 (Dirichlet’s approximation theorem, 1879 ).

Let $x$ be a real number. For any natural number $n$ , there is a rational number $p/q$ such that $1\leq q\leq n$ and

\left|x-\frac{p}{q}\right|\leq\frac{1}{nq}\leq\frac{1}{q^{2}}.

It is easy to obtain that error of $1/q$ or equivalently,

|qx-p|\leq 1.

A consequence of the theorem is that there are infinitely many rationals $p/q$ such that the above conclusion holds. This theorem is one of the basic theorems in what is known as Diophantine approximation. See also the following popular article on Duffin-Schaeffer conjecture which is a quantitative refinement of Dirichlet’s theorem.

Proof.

Let $\{x\}=x-\lfloor x\rfloor$ be the fractional part of $x$ . Consider $\{ax\},a=1,2,\ldots,n+1$ . By pigeonhole principle, two of them should belong to some interval $[i/n,(i+1)/n)$ for $i=0,\ldots,n-1$ . Say $\{ax\},\{bx\}$ belong to the same interval and $a>b$ . Thus $\{ax\}-\{bx\}\leq n^{-1}$ . Writing it differently,

|ax-\lfloor ax\rfloor-bx+\lfloor bx\rfloor|\leq n^{-1},

and so the theorem follows by setting $q=a-b$ and $p=\lfloor ax\rfloor-\lfloor bx\rfloor$ . Also since $1\leq b<a\leq n+1$ , $q\leq n$ . ∎

The famous Fermat’s last theorem states that if $n>2$ , there are no solutions to $x^{n}+y^{n}=z^{n}$ for natural numbers $x, y, z$ . Schur (1916) used pigeonhole principle via a colouring argument to show that there are infinitely many solutions in a finite field $\mathbb{Z}_{p}$ for large prime $p$ .

Theorem 5.15 (Schur, 1916).

For any $r\geq 1$ and a $r$ -coloring of $\{1,\ldots,n\}$ where $n=\lceil er!\rceil$ , there are three integers $x, y, z$ of the same colour and such that $x+y=z$ .

Before the proof, we disprove Fermat’s last theorem for finite fields.

Theorem 5.16.

For every integer $r\geq 1$ , there exists $p_{0}$ such that for any prime $p\geq p_{0}$ , the congruence

x^{r}+y^{r}=z^{r}\,\text{mod}\,p

has a solution.

Proof.

The multiplicative group $\mathbb{Z}^{*}_{p}=\{1,2,\ldots,p-1\}$ is cyclic and so has a generator $g$ . Thus $x=g^{rj_{x}+i}$ for any $x\in\mathbb{Z}^{*}_{p}$ for $0\leq i<r$ . We colour $\mathbb{Z}^{*}_{p}$ by $r$ colours where $c(x)=i$ for $x=g^{nj_{x}+i}$ . By Schur’s theorem for $p=\lceil er!\rceil$ , there are $x,y,z\in\mathbb{Z}^{*}_{p}$ such that $x+y=z$ (in $\mathbb{Z}$ ) with $c(x)=c(y)=c(z)$ . Say $c(x)=i$ . Therefore,

g^{rj_{x}+i}+g^{rj_{y}+i}\equiv g^{rj_{z}+i}

or equivalently,

(g^{j_{x}})^{r}+(g^{j_{y}})^{r}\equiv(g^{j_{z}})^{r}.

∎

Proof of 5.15.

Let $c:[n]\to[r]$ be a colouring. Suppose that there exists no $x+y\leq n$ for $x,y,x+y$ of the same colour, we will show that $n<er!$ .

WLOG, let $c_{0}$ be the most frequently appearing colour and let $x_{0}<x_{1}\ldots<x_{n_{1}-1}$ be the elements of color $c_{0}$ . By pigeonhole principle, $n\leq rn_{1}$ .

Define $A_{0}:=\{x_{i}-x_{0}:1\leq i<n_{1}\}$ . By assumption, there is no element in $A_{0}$ of colour $c_{0}$ . So $A_{0}$ is covered by $r-1$ colours and let $c_{1}$ be the most frequently appearing colour in $A_{0}$ . Let $y_{0}<\ldots<y_{n_{2}-1}$ be the elements of colour $c_{1}$ . Again by pigeonhole principle, we have that $n_{1}-1\leq(r-1)n_{2}$ .

Define $A_{1}:=\{y_{i}-y_{0}:1\leq i<n_{2}\}$ . By assumption, there is no element in $A_{1}$ of colour $c_{0},c_{1}$ . So $A_{1}$ is covered by $r-2$ colours and let $c_{2}$ be the most frequently appearing colour in $A_{1}$ . Let $z_{0}<\ldots<z_{n_{3}-1}$ be the elements of colour $c_{2}$ . Again by pigeonhole principle, we have that $n_{2}-1\leq(r-2)n_{3}$ .

Proceeding similarly, we get $n_{k}=1$ . Given that there are $r$ colours at most, $k\leq r$ . Thus, we have that $n\leq rn_{1}$ , $n_{i}\leq 1+(r-i)n_{i+1}$ for $i=1,\ldots,k-1$ . Thus substituting recursively,

n\leq\sum_{i=0}^{r-1}r(r-1)\ldots(r-i)=\sum_{i=0}^{r-1}\frac{r!}{(r-i-1)!}=% \sum_{i=0}^{r-1}\frac{r!}{i!}<r!\sum_{i=0}^{\infty}\frac{1}{i!}=er!.

∎