Ramsey theory and Fermat’s Last Theorem

« Update, and the combinatorics of quintic equations

Ramsey theory and Fermat’s Last Theorem

October 13, 2010 by Qiaochu Yuan

In the first few lectures of Graph Theory, the lecturer (Paul Russell) presented a cute application of Ramsey theory to Fermat’s Last Theorem. It makes a great introduction to the general process of casting a problem in one branch of mathematics as a problem in another and is the perfect size for a blog post, so I thought I’d talk about it.

The setup is as follows. One naive way to go about proving the nonexistence of nontrivial integer solutions to $x^n + y^n = z^n, n > 2$ (that is, solutions such that $x, y, z$ are not equal to zero) is using modular arithmetic; that is, one might hope that for every $n > 2$ it might be possible to find a modulus $m$ such that the equation has no nontrivial solution $\bmod m$ . To simplify matters, we’ll assume that $x, y, z$ are relatively prime to $m$ , or else there is some subtlety in the definition of “nontrivial” (e.g. we might have $x, y, z$ not divisible by $m$ but $x^n \equiv 0 \bmod m$ .) Note that it might be the case that $m$ is not relatively prime to a particular nontrivial solution in the integers, but if we can prove non-existence of nontrivial solutions for infinitely many $m$ (in particular, such that any integer is relatively prime to at least one such $m$ ) then we can conclude that no nontrivial integer solutions exist.

By the Chinese Remainder Theorem, this is possible if and only if it is possible with $m$ a prime power, say $m = p^k$ . If $p$ is relatively prime to $n$ , this is possible if and only if it is possible with $m = p$ . This is because given a nontrivial solution $\bmod p$ we can use Hensel’s lemma to lift it to a nontrivial solution $\bmod p^k$ for any $k$ (and even to $\mathbb{Z}_p$ ), and the converse is obvious. (Again to simplify matters, we’ll ignore the finitely many primes that divide $n$ .) So we are led to the following question.

For a fixed positive integer $n > 2$ do there exist infinitely many primes $p$ relatively prime to $n$ such that $x^n + y^n \equiv z^n \bmod p$ has no nontrivial solutions?

As it turns out, the answer is no. In 1916 Schur found a clever way to prove this by proving the following theorem.

Theorem: For every positive integer $k$ there exists a positive integer $m$ such that if $\{ 1, 2, ... m \}$ is partitioned into $k$ disjoint subsets $A_1, ... A_k$ , then there exists $i$ such that there exist $a, b, c \in A_i$ with $a + b = c$ . In other words, the Schur number $S(k) = m$ exists. (Note that I am using a convention which is off by $1$ .)

If we let $p$ be a prime greater than $S(n)$ and let the $A_i$ be the cosets of the subgroup of $n^{th}$ powers in $(\mathbb{Z}/p\mathbb{Z})^{*}$ , which has index at most $n$ , we obtain the following as a corollary.

Corollary: Fix a positive integer $n > 2$ . For any sufficiently large prime $p$ , there exists a nontrivial solution to $x^n + y^n \equiv z^n \bmod p$ .

Ramsey theory

As one might expect, the heart of the proof of Schur’s theorem is Ramsey theory, by which I mean it consists of iterated application of the pigeonhole principle. We induct on $k$ . The result is obvious for $k = 1$ and gives $S(1) = 2$ . For an arbitrary value of $k$ we would like to reduce the result to the corresponding result for $k-1$ , which we do as follows. Let $m$ be a positive integer to be chosen later. If $\{ 1, 2, ... m \}$ is partitioned into $k$ disjoint subsets $A_1, ... A_k$ , then by pigeonhole at least one, say $A_s$ , has at least $r = \lceil \frac{m}{k} \rceil$ elements in it, say $a_1 < ... < a_r$ . If there is a solution to $a + b = c$ among these, we are done; otherwise, for any $1 \le i < j \le r$ we know that $a_j - a_i \not \in A_s$ , hence it must be in one of the remaining $k-1$ partitions.

We are done if we can show there exists a triple of indices $u < v < w$ such that $a_u - a_v, a_w - a_u, a_w - a_v$ are all in the same partition. (Note that it is not necessary that these numbers be distinct.) A convenient way to recast this problem is to use the language of graph theory. The partitioning of the terms $a_j - a_i$ into one of the $k-1$ partitions which is not $A_s$ is equivalent to the coloring of the edges of the complete graph $K_r$ using $k-1$ colors, and we want to find a monochromatic triangle in this graph.

Theorem: For any positive integer $t$ , there exists a smallest positive integer $R_t$ such that if the edges of the complete graph $K_{R_t}$ are colored using $t$ colors, then there exists a monochromatic triangle. In other words, the Ramsey number $R_t = R(\underbrace{3, 3, ...}_{t \text{ times}})$ exists.

Proof. It is not hard to see that $R_1 = 3$ . For general $t$ we proceed by induction. Let $m$ be a positive integer to be chosen later. Pick a vertex $v \in K_m$ . Among the $m-1$ edges attached to $v$ , at least $\lceil \frac{m-1}{t} \rceil$ will be the same color by pigeonhole. If among the $\lceil \frac{m-1}{t} \rceil$ corresponding vertices there is some edge of the same color, we have found a monochromatic triangle; otherwise, these vertices make up a complete graph colored using at most $t-1$ colors and we can use the inductive hypothesis as long as $\lceil \frac{m-1}{t} \rceil \ge R_{t-1}$ . This gives $R_t \le t R_{t-1} - t + 2$ (in particular $R_t$ exists), hence for example $R_2 \le 6, R_3 \le 17, R_4 \le 66$ . (The first two are equalities, but the value of $R_4$ is unknown; the best upper bound appears to be due to R. L. Kramer, who showed that $R_4 \le 62$ .)

Now to complete the proof of Schur’s theorem it suffices to pick $m$ large enough so that $\lceil \frac{m}{k} \rceil \ge R_{k-1}$ . This gives $S(k) \le k R_{k-1} - k + 1$ (in particular $S(k)$ exists).

Comments

What I find instructive about this example is that it is a good illustration of how ignoring extraneous information can help you gain perspective on a problem. The decomposition of $\{ 1, 2, ... p-1 \}$ into cosets of $n^{th}$ powers has a lot of structure, but as it turns out, for finding solutions to linear equations like $a + b = c$ our lives are easier if we ignore that structure, as long as we are willing to make $p$ as large as necessary. And in the actual proof of Schur’s theorem, we needed to ignore even more structure (the identity of the numbers $a_j - a_i$ ) to get a reduction to a stronger statement on which induction could work. (So this is also an example of strengthening the inductive hypothesis.)

So much for the Ramsey theory. To close, I’d like to make one more comment about the number theory. If we lift the requirement that $x, y, z$ are relatively prime to $m$ , we run into triviality problems. It might be that for some prime power divisor $p^k$ of $m$ we have $x, y, z \not \equiv 0 \bmod p^k$ but $x^n \equiv 0 \bmod p^k$ (for example). So we should insist that this not be the case. But even if it isn’t, if we allow one of $x, y, z$ to be divisible by $p$ then we still get lots of nontrivial solutions for any $p$ relatively prime to $n$ (not necessarily large). This is again because of Hensel’s lemma; if $p$ is relatively prime to $n$ then $n^{th}$ roots of numbers relatively prime to $p$ exist in $\mathbb{Z}_p$ , so we can let $x = 1, y = 1$ (for odd $p$ ; we can take $x = 1, y = 3$ for $p = 2$ ) and let $z$ be an $n^{th}$ root in $\mathbb{Z}_p$ . Then this solution reduces to a nontrivial solution $\bmod p^k$ for sufficiently large $k$ .

About these ads

Posted in graph theory, number theory, Ramsey theory | Tagged pigeonhole principle | 3 Comments

3 Responses

on January 7, 2011 at 3:18 am | Reply liuxiaochuan

Suppse, for contradiction, that there exist nontrivial integer solutions to $x^n + y^n = z^n$ for some fixed $n > 2$ . Then for all but finite number of primes $p$ , we have $x^n + y^n = z^n (mod p)$ . I guess the question is thus raised, instead of invoke Hensel’s lemma?
- on January 7, 2011 at 3:42 am | Reply liuxiaochuan
  
  I think I get it, I should notice there are differences between “infinite” and “all but finite”.
on November 9, 2011 at 2:33 pm | Reply Blitz Krieger | Out of the Norm

[...] mathematical machinery than congruences alone are required for a successful proof. You can find a more detailed explanation on Qiaochu Yuan’s blog Annoying Precision: the proof of the theorem is a nice application of [...]

Comments RSS

	Viliam Búr on Writing a blog post every day…
	Qiaochu Yuan on A puzzle about operations
	Omar on A puzzle about operations
	A puzzle about opera… on Operations and Lawvere th…
	Qiaochu Yuan on Operations and Lawvere th…

Annoying Precision

"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is." – John von Neumann