Feeds:
Posts

## Posts Tagged ‘Frobenius map’

In the previous post we showed that the splitting behavior of a rational prime $p$ in the ring of cyclotomic integers $\mathbb{Z}[\zeta_n]$ depends only on the residue class of $p \bmod n$. This is suggestive enough of quadratic reciprocity that now would be a good time to give a full proof.

The key result is the following fundamental observation.

Proposition: Let $q$ be an odd prime. Then $\mathbb{Z}[\zeta_q]$ contains $\sqrt{ q^{*} } = \sqrt{ (-1)^{ \frac{q-1}{2} } q}$.

Quadratic reciprocity has a function field version over finite fields which David Speyer explains the geometric meaning of in an old post. While this is very much in line with what we’ve been talking about, it’s a little over my head, so I’ll leave it for the interested reader to peruse.

## The arithmetic plane

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.

## The cyclotomic identity and Lyndon words

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.

## Newton’s sums, necklace congruences, and zeta functions

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.

## GILA V: The Polya enumeration theorem and applications

I ended the last post by asking whether the proof of baby Polya extends to the multi-parameter setting where we want to keep track of how many of each color we use. In fact, it does. First, we should specify what exactly we’re trying to compute. Recall the setup: we have colors $1, 2, ... n$ (represented by variables $r_1, r_2, ... r_n$), and we have a set of slots $S$ with $|S| = m$ acted on by a group $G$ where each slot will be assigned a color. Define $f_G(t_1, ... t_n)$ to be the number of orbits of functions $S \to \{ 1, 2, ... n \}$ under the action of $G$ where color $i$ is used $t_i$ times. (Since the action of $G$ only permutes slots, it doesn’t change the multiset of colors used.) What we want to compute is the generating function

$\displaystyle F_G(r_1, r_2, ... r_n) = \sum_{t_1 + ... + t_n = m} f_G(t_1, t_2, ... t_n) r_1^{t_1} r_2^{t_2} ... r_n^{t_n}$.

Note that setting $r_1 = r_2 = .... = r_n = 1$ we recover $F_G(n)$, which doesn’t contain information about particular color combinations. By the orbit-counting lemma, this is equivalent to computing

$\displaystyle \frac{1}{|G|} \sum_{g \in G} | \text{Fix}(g) |(r_1, r_2, ... r_n)$

where we must now count fixed points in a weighted manner, recording the multiset of colors in each fixed point. How do we go about doing this?

## The magic of the Frobenius map II

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?