Tricki
a repository of mathematical know-how

Revision of Use finite fields from Wed, 15/04/2009 - 10:26

Quick description

If you have an algebraic problem about the complex numbers, it might be possible to solve it by solving a similar, but easier, problem about finite fields.

Prerequisites

Basic notions of commutative and linear algebra (more sophisticated ideas are required to understand the proofs of the results quoted, but this is not needed to apply the trick).

This trick depends on the following proposition.

Proposition 1 (Reduction mod primes) Suppose that R is a finitely-generated (?) subring of \C. Then the quotient R/\mathfrak{m} of R by a maximal ideal \mathfrak{m} is always a finite field, and \bigcap_{\mathfrak{m}}\mathfrak{m} = \{0\}.

The proof of the first part of this theorem is not particularly easy to find in the literature. Some links are given below, and perhaps the standard reference would be Bourbaki's Algebre Commutative, Ch. V, Sec 3, no. 4, Corollaire I, p.64.

Example 1: Jordan-Chevalley decomposition in algebraic subgroups of \mbox{GL}_d(\C)] Suppose that x \in \mbox{GL}_d(k) is an invertible matrix, where k is any field (actually, it needs to be a perfect field, but the fields we mention below are all perfect). The [[w:Jordan-Chevalley_decomposition|Jordan–Chevalley Decomposition]

of x is a factorization x = x_u x_s = x_s x_u into commuting semisimple and unipotent parts x_s and x_u. Semisimple is the same thing as diagonalizable over the algebraic closure \overline{k}, and a matrix t is unipotent if and only if (t-1)^d = 0, or equivalently if t may be conjugated to an upper-triangular matrix with ones on the diagonal. It is a well-known theorem of linear algebra that the Jordan normal form exists and is unique.

Theorem 2 Let G \subseteq \mbox{GL}_d(\C) be an algebraic (Zariski-closed) subgroup, that is to say a subgroup which is also the zero set of a collection of polynomials in d^2 variables (the entries of the matrices). Then G is closed under taking components of the Jordan normal form; that is, if x \in G then the semisimple parts x_s and x_u also lie in G.

We will deduce this from the following finite field version of the result.

Theorem 3 Let G \subseteq \mbox{GL}_d(\mathbb{F}) be a group, where \mathbb{F} is some finite field. Then G is closed under taking components of the Jordan normal form; that is, if x \in G then the semisimple parts x_s and x_u also lie in G.

Let us give the deduction of Theorem 2, as this is main point of this discussion. Suppose that G is as in the theorem, and let x \in G. Membership of G is decided by the vanishing of some set of polynomials, but by Hilbert's basis theorem the ideal generated by these polynomials is generated by some finite collection f_1,\dots,f_m. Choose a matrix g such that g^{-1}x_s g is actually diagonal, and consider now the ring R generated by all the entries of x_s, x_u, g, their inverses and all the coefficients of the polynomials f_1,\dots,f_m. This is a finitely-generated ring, and Theorem 2 takes place over R. For each maximal ideal \mathfrak{m} of R, consider the natural reduction map  R \rightarrow R/\mathfrak{m}. This fairly obviously preserves Jordan normal form, that is to say the Jordan components of \pi(x) are \pi(x_s) and \pi(x_u). By Theorem 3 (applied to the subgroup of \mbox{GL}_d(\mathbb{F}) generated by \pi(x)), each of \pi(x_s) and \pi(x_u) is a power of \pi(x), and hence x_s \equiv x^a \mod{\mathfrak{m}} and x_u \equiv x^b \mod{\mathfrak{m}} for integers a,b. But the polynomials f_1,\dots,f_m vanish on the whole of the group G, and in particular at the elements x^a and x^b. Therefore f_i(x_s) \equiv f_i(x_u) \equiv 0 \mod{\mathfrak{m}} for i = 1,\dots,m. To conclude, we use the second part of Theorem (ref), which asserted that the intersection of all maximal ideals \mathfrak{m} is zero. Together with the preceding line this implies that f_i(x_s) = f_i(x_u) = 0 for i = 1,\dots,m, which of course means that both x_s and x_u lie in the group G.

It remains to prove Theorem 3. We leave the details as an exercise to the reader, using the following three observations: (1) If x \in \mbox{GL}_d(\mathbb{F}) then x has finite order; (2) if the order of an element y is coprime to \mbox{char}(\mathbb{F}) then y is semisimple; (3) if the oder of an element z is a power of \mbox{char}(\mathbb{F}) then z is unipotent.

Example 2: The Ax-Grothendieck theorem

This discussion is taken from a blog article of T. Tao. To be completed shortly.

General discussion

This trick, and much more, is covered in the article by Serre (ref). That article was blogged on by Tao (ref), and in the comments following that discussion one may find a proof of Principle (ref).