Revision of Use finite fields from Wed, 15/04/2009 - 12:54

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\}$ .

In fact for the first example below we only require the fact that $R$ has some maximal ideal $\mathfrak{m}$ such that the quotient $R/\mathfrak{m}$ is a finite field. The proof of this (and a fortiori of the first statement in the proposition) 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: Ax-Grothendieck theorem] The discussion here is cribbed from this article by Serre and a [http://terrytao.wordpress.com/2009/03/07/infinite-fields-finite-fields-and-the-ax-grothendieck-theorem/ blog by Tao

that followed from it, together with comments on that blog.

Theorem 2 Suppose that $\C^n \rightarrow \C^n$ is an injective polynomial map. Then $P$ is also surjective.

The proof is by contradiction. If $P$ is injective but not surjective then

$x-y$ vanishes whenever $P(x) - P(y)$ does and
there is some $t \in \C^n$ such that $P(x) -t$ vanishes whenever $1$ does (i.e. never).

The rather odd way of expressing these statements is so that we may apply Hilbert's Nullstellensatz. The two statements imply, in turn, that

some power $(x-y)^r$ lies in the ideal generated by $P(x) - P(y)$ and
some power $1^r$ lies in the ideal generated by $P(x) - t$ .

More concretely,

There is a polynomial $Q(x,y)$ such that $(x-y)^r = (P(x) - P(y))Q(x,y) and * There is a polynomial$ \tilde Q(x) such that $1 = (P(x) - t)\tilde Q(x). Now let$ R $be the subring of$ \C $generated by the (finite list of) coefficients of$ P,Q $and$ \tilde Q $. Let$ \mathfrak{m} $be a maximal ideal of$ R $, and consider the reduction map$ \pi : R \rightarrow R/\mathfrak{m}. By Proposition 1 the image is a finite field \mathbb{F} $. Let us abuse notation by omitting explicit mention of the reduction map$ \pi $in the next few lines. We still have the polynomial relations [[ (P(x) - P(y))Q(x,y) = (x-y)^r, (P(x) - t)\tilde Q(x)]] over$ \mathbb{F} $, which means that the polynomial$ P $, regarded as a map from$ \mathbb{F}^n $to$ \mathbb{F}^n, is injective but not surjective. This is manifestly nonsense on cardinality grounds.

</div> </d...\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 menti...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 theor...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-Chevalley decomposition; that is, if$ x \in G $then the semisimple and unipotent parts$ x_s $and$ x_u $also lie in$ G.</div> We will deduce this from the following finite field version of the result. <div class="tri...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.</div> Let us give the deduction of Theorem 3, as this is main point of this discussion. ...G $is as in the theorem, and let$ x \in G $. Membership of$ G $Hilbert's_basis_theorem|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 3 takes place ''over R $''. For each maximal ideal$ \mathfrak{m} $of$ R $, consider the natural reduction map$ \pi : R \rightarrow R/\mathfrak{m}. By the first part of Proposition 1 the image R/\mathfrak{m} $is a finite field. This reduction map fairly obviously preserves the Jordan-Chevalley decomposition, that is to say the Jordan-Chevalley components of$ \pi(x) $are$ \pi(x_s) $and$ \pi(x_u). By Theorem 4 (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 Proposition 1, which asserted that the intersecti...\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 4. We leave the details as an exercise to the reader, usin...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 order of an element$ z $is a power of$ \mbox{char}(\mathbb{F}) $then$ z $is unipotent. Using this it is not hard to exhibit$ x_s $and$ x_u $as powers of$ x$.

General discussion

There are connections between ideas of this kind and logic/model theory, but this author is not qualified to discuss them. More details may be found in the "Princeton Companion" article by David Marker, where explicit mention of the Ax-Grothendick theorem is made on p642.