Archive for the ‘Ramsey theory’ Category

We continue our exploration of ultrafilters. Today we’ll discuss the infinite Ramsey theorem, which is the following classical result:

Theorem: Suppose the complete graph K_{\infty} on countably many vertices has its edges colored in one of k colors. Then there is a monochromatic K_{\infty} (i.e. an infinite subgraph all of whose edges are the same color).

The finite Ramsey theorem implies that there is a monochromatic K_n for every positive integer n, but this is a strictly stronger result; it implies not only the finite Ramsey theorem but the “strengthened” finite Ramsey theorem, and by the Paris-Harrington theorem this is independent of Peano arithmetic (although Peano arithmetic can prove the finite Ramsey theorem). Indeed, while the standard proof of the finite Ramsey theorem uses the finite pigeonhole principle, the standard proof of the infinite Ramsey theorem uses the infinite pigeonhole principle, which is stronger; this is part of the subject of a post by Terence Tao which is quite enlightening.

Given a non-principal ultrafilter F on \mathbb{N}, any partition of \mathbb{N} into finitely many disjoint subsets (that is, any coloring) has the property that exactly one of the subsets is in F (that is, has “full measure”), and this subset must be infinite. This subset can, in turn, be colored (partitioned), and exactly one of the blocks of the partition is in F, and it must again be infinite, and so forth. It follows that a non-principal ultrafilter lets us use the infinite pigeonhole principle repeatedly (in fact this is in some sense what a non-principal ultrafilter is), and since this is exactly what is needed to prove the infinite Ramsey theorem we might expect that we could use a non-principal ultrafilter to prove the infinite Ramsey theorem. Today we’ll describe this proof, and then describe how the infinite Ramsey theorem implies the finite Ramsey theorem, which involves a different use of a non-principal ultrafilter on \mathbb{N}.


Read Full Post »

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.


Read Full Post »


Get every new post delivered to your Inbox.

Join 282 other followers