Use finite fields

a repository of mathematical know-how

Use finite fields

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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.

[frame][proposition redp|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\}$.  [/proposition][/frame]

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 ex1|Ax-Grothendieck theorem]

The discussion here is cribbed from this [[arxiv:0903.0517|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 axgrot] Suppose that $P : \C^n \rightarrow \C^n$ is an injective polynomial map. Then $P$ is also surjective.[/theorem]

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 [[w:Hilbert's_Nullstellensatz|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 [ref Proposition #redp] 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

[maths] (P(x) - P(y))Q(x,y) = (x-y)^r, \quad (P(x) - t)\tilde Q(x) = 1 [/maths]

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.

[EXAMPLE ex2|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 [[w:Perfect_field|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-Chevalley decomposition exists and is unique.

[theorem jnf]  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-Chevalley decomposition; that is, if $x \in G$ then the semisimple  and unipotent parts $x_s$ and $x_u$ also lie in $G$. [/theorem]

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

[theorem jnff] 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$.[/theorem]

Let us give the deduction of [ref Theorem #jnf], as this is the 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 [[w: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 [ref Theorem #jnf] 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 [ref Proposition #redp] 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 [ref Theorem #jnff] (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 [ref Proposition #redp], 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 [ref Theorem #jnff]. 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 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-Grothendieck theorem is made on p642.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Use finite fields

Recent articles

Active forum topics

Recent comments