Feeds:
Posts
Comments

Posts Tagged ‘finite fields’

The goal of this post is to collect a list of applications of the following theorem, which is perhaps the simplest example of a fixed point theorem.

Theorem: Let G be a finite p-group acting on a finite set X. Let X^G denote the subset of X consisting of those elements fixed by G. Then |X^G| \equiv |X| \bmod p; in particular, if p \nmid |X| then G has a fixed point.

Although this theorem is an elementary exercise, it has a surprising number of fundamental corollaries.

(more…)

Read Full Post »

The Hecke algebra attached to a Coxeter system (W, S) is a deformation of the group algebra of W defined as follows. Take the free \mathbb{Z}[q^{ \frac{1}{2} }, q^{ - \frac{1}{2} }]-module \mathcal{H}_W with basis T_w, w \in W, and impose the multiplicative relations

T_w T_s = T_{ws}

if \ell(sw) > \ell(w), and

T_w T_s = q T_{ws} + (q - 1) T_w

otherwise. (For now, ignore the square root of q.) Humphreys proves that these relations describe a unique associative algebra structure on \mathcal{H}_W with T_e as the identity, but the proof is somewhat unenlightening, so I will skip it. (Actually, the only purpose of this post is to motivate the definition of the Kazhdan-Lusztig polynomials, so I’ll be referencing the proofs in Humphreys rather than giving them.)

The motivation behind this definition is a somewhat long story. When W is the Weyl group of an algebraic group G with Borel subgroup B, the above relations describe the algebra of functions on G(\mathbb{F}_q) which are bi-invariant with respect to the left and right actions of B(\mathbb{F}_q) under a convolution product. The representation theory of the Hecke algebra is an important tool in understanding the representation theory of the group G, and more general Hecke algebras play a similar role; see, for example MO question #4547 and this Secret Blogging Seminar post. For example, replacing G and B with \text{SL}_2(\mathbb{Q}) and \text{SL}_2(\mathbb{Z}) gives the Hecke operators in the theory of modular forms.

(more…)

Read Full Post »

If you haven’t seen them already, you might want to read John Baez’s week205 and Lieven le Bruyn’s series of posts on the subject of spectra. I especially recommend that you take a look at the picture of \text{Spec } \mathbb{Z}[x] to which Lieven le Bruyn links before reading this post. John Baez’s introduction to week205 would probably also have served as a great introduction to this series before I started it:

There’s a widespread impression that number theory is about numbers, but I’d like to correct this, or at least supplement it. A large part of number theory – and by the far the coolest part, in my opinion – is about a strange sort of geometry. I don’t understand it very well, but that won’t prevent me from taking a crack at trying to explain it….

Before we talk about localization again, we need some examples of rings to localize. Recall that our proof of the description of \text{Spec } \mathbb{C}[x, y] also gives us a description of \text{Spec } \mathbb{Z}[x]:

Theorem: \text{Spec } \mathbb{Z}[x] consists of the ideals (0), (f(x)) where f is irreducible, and the maximal ideals (p, f(x)) where p \in \mathbb{Z} is prime and f(x) is irreducible in \mathbb{F}_p[x].

The upshot is that we can think of the set of primes of a ring of integers \mathbb{Z}[\alpha] \simeq \mathbb{Z}[x]/(f(x)), where f(x) is a monic irreducible polynomial with integer coefficients, as an “algebraic curve” living in the “plane” \text{Spec } \mathbb{Z}[x], which is exactly what we’ll be doing today. (When f isn’t monic, unfortunate things happen which we’ll discuss later.) We’ll then cover the case of actual algebraic curves next.

(more…)

Read Full Post »

In number theory there is a certain philosophy that \mathbb{F}_q[x] is a good toy model for the integers \mathbb{Z}. The two rings share an important property: they are basically the canonical examples of Euclidean domains, hence PIDs, hence UFDs. However, many number-theoretic questions involving prime factorization over \mathbb{F}_q[x] are much easier than their corresponding questions over \mathbb{Z}. One way to see this is to look at their zeta functions.

The usual zeta function \zeta(s) = \sum_{n \ge 1} \frac{1}{n^s} reflects the structure of prime factorization through its Euler product

\displaystyle \zeta(s) = \prod_p \frac{1}{1 - p^{-s}}

where the product runs over all primes; this is essentially equivalent to unique factorization. Since we know that monic polynomials over \mathbb{F}_q[x] also enjoy unique factorization, it’s natural to ask whether there’s a sum over monic polynomials that would give a similar Euler product.

In fact, there is such a product, and investigating it leads naturally to a seemingly unrelated subject: the combinatorics of words.

(more…)

Read Full Post »

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

\displaystyle p_k - e_1 p_{k-1} \pm ... = (-1)^{k+1} ke_k.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial C(t) with non-negative integer coefficients and C(0) = 0, let r_1, ... r_n be the reciprocals of the roots of C(t) - 1 = 0. Then

\displaystyle \frac{t C'(t)}{1 - C(t)} = \sum_{k \ge 1} p_k(r_1, ... r_n) t^k.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by C(t). Today we’ll describe this species when C(t) is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

(more…)

Read Full Post »

I’ve decided to start blogging a little more about the algebraic combinatorics I’ve learned over the past year. In particular, I’d like to present one of my favorite proofs from Stanley’s Enumerative Combinatorics I.

The theory of Young tableaux is a great example of the richness of modern mathematics: although they can be defined in an elementary combinatorial fashion, interest in the theory is primarily driven (as I understand it) by their applications to representation theory and other fields of mathematics. The standard application is in describing the irreducible representations of the symmetric group in characteristic zero. I’ll be describing a more elementary aspect of the theory: the relationship between Young diagrams and q-binomial coefficients.

Young diagrams can be defined as a visual representations of partitions. A partition of k is a weakly decreasing sequence \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_i such that \lambda_1 + ... + \lambda_i = k. Partitions uniquely describe cycle decompositions, hence conjugacy classes, of the symmetric group, which is a hint at the connection to representation theory. A Young diagram of the partition \lambda consists of i rows of boxes where the j^{th} row has \lambda_j boxes. Let L(m, n) denote the poset of Young diagrams that fit into an m \times n box, ordered by inclusion: equivalently, one can define the full Young lattice and define L(m, n) to be the elements less than or equal to the m \times n partition. (One can then define a standard Young tableau to be a chain in the Young lattice, but we will not need this notion.) One can easily check that the following is true.

Proposition: |L(m, n)| = {m+n \choose m}.

The rest of this post explains the q-analogue of this result.

(more…)

Read Full Post »

Once upon a time I discussed some interesting uses of the Frobenius map to solve some Putnam-style problems. Unfortunately, I wrote that post before becoming really interested in combinatorics, so I neglected to develop that particular side of the story, which I’d like to do now.

The beginning of this story is the folklore combinatorial proof of Fermat’s little theorem: for any positive integer a and prime p, we have

a^p \equiv a \bmod p.

The proof is simple but powerful. Consider the set of possible ways to color p beads with a colors. The cyclic group \mathbb{Z}/p\mathbb{Z} acts on this set in the obvious way. (One says that the beads are “on a necklace.”) The great thing about actions of a prime cyclic group is that elements arrange themselves into two kinds of orbits: fixed points and orbits of size p. (This is just a special case of the orbit-stabilizer theorem.) The total number of colorings is a^p, but if we only want to work \bmod p it suffices to count the number of fixed points under the action of \mathbb{Z}/p\mathbb{Z}. These are precisely the colorings using only one color, of which there are a, and the result follows.

The standard generalization of this result to finite fields is as follows: \text{Gal}(\mathbb{F}_{p^n}/\mathbb{F}_p) \simeq \mathbb{Z}/n\mathbb{Z} and is generated by the Frobenius map x \mapsto x^p. Does this result also have a combinatorial proof?

(more…)

Read Full Post »

Follow

Get every new post delivered to your Inbox.

Join 315 other followers