Feeds:
Posts

## The p-group fixed point theorem

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.

## Small factors in random polynomials over a finite field

Previously I mentioned very briefly Granville’s The Anatomy of Integers and Permutations, which explores an analogy between prime factorizations of integers and cycle decompositions of permutations. Today’s post is a record of the observation that this analogy factors through an analogy to prime factorizations of polynomials over finite fields in the following sense.

Theorem: Let $q$ be a prime power, let $n$ be a positive integer, and consider the distribution of irreducible factors of degree $1, 2, ... k$ in a random monic polynomial of degree $n$ over $\mathbb{F}_q$. Then, as $q \to \infty$, this distribution is asymptotically the distribution of cycles of length $1, 2, ... k$ in a random permutation of $n$ elements.

One can even name what this random permutation ought to be: namely, it is the Frobenius map $x \mapsto x^q$ acting on the roots of a random polynomial $f$, whose cycles of length $k$ are precisely the factors of degree $k$ of $f$.

Combined with our previous result, we conclude that as $q, n \to \infty$ (with $q$ tending to infinity sufficiently quickly relative to $n$), the distribution of irreducible factors of degree $1, 2, ... k$ is asymptotically independent Poisson with parameters $1, \frac{1}{2}, ... \frac{1}{k}$.

## Z[sqrt{-3}] is the Eisenstein integers glued together at two points

Today’s post is a record of a very small observation from my time at PROMYS this summer. Below, by $\text{Spec } R$ I mean a commutative ring $R$ regarded as an object in the opposite category $\text{CRing}^{op}$.

## Schanuel’s conjecture and the Mandelbrot Competition

A student I’m tutoring was working unsuccessfully on the following problem from the 2011 Mandelbrot Competition:

Let $a, b$ be positive integers such that $\log_a b = (\log 23)(\log_6 7) + \log_2 3 + \log_6 7$. Find the minimum value of $ab$.

After some tinkering, I concluded that the problem as stated has no solution. I am now almost certain it was printed incorrectly: $\log 23$ should be replaced by $\log_2 3$, and then we can solve the problem as follows:

$\log_a b + 1 = (\log_2 3 + 1)(\log_6 7 + 1) = \log_2 6 \log_6 42 = \log_2 42$.

It follows that $\log_a b = \log_2 21$. Since $a, b$ are positive integers we must have $a \ge 2$, and then it follows that the smallest solution occurs when $a = 2, b = 21$. But what I’d like to discuss, briefly, is the argument showing that the misprinted problem has no solution.

## A little more about zeta functions and statistical mechanics

In the previous post we described the following result characterizing the zeta distribution.

Theorem: Let $a_n = \mathbb{P}(X = n)$ be a probability distribution on $\mathbb{N}$. Suppose that the exponents in the prime factorization of $n$ are chosen independently and according to a geometric distribution, and further suppose that $a_n$ is monotonically decreasing. Then $a_n = \frac{1}{\zeta(s)} \left( \frac{1}{n^s} \right)$ for some real $s > 1$.

I have been thinking about the first condition, and I no longer like it. At least, I don’t like how I arrived at it. Here is a better way to conceptualize it: given that $n | X$, the probability distribution on $\frac{X}{n}$ should be the same as the original distribution on $X$. By Bayes’ theorem, this is equivalent to the condition that

$\displaystyle \frac{a_{mn}}{a_n + a_{2n} + a_{3n} + ...} = \frac{a_m}{a_1 + a_2 + ...}$

which in turn is equivalent to the condition that

$\displaystyle \frac{a_{mn}}{a_m} = \frac{a_n + a_{2n} + a_{3n} + ...}{a_1 + a_2 + a_3 + ...}$.

(I am adopting the natural assumption that $a_n > 0$ for all $n$. No sense in excluding a positive integer from any reasonable probability distribution on $\mathbb{N}$.) In other words, $\frac{a_{mn}}{a_m}$ is independent of $m$, from which it follows that $a_{mn} = c a_m a_n$ for some constant $c$. From here it already follows that $a_n$ is determined by $a_p$ for $p$ prime and that the exponents in the prime factorization are chosen geometrically. And now the condition that $a_n$ is monotonically decreasing gives the zeta distribution as before. So I think we should use the following characterization theorem instead.

Theorem: Let $a_n = \mathbb{P}(X = n)$ be a probability distribution on $\mathbb{N}$. Suppose that $a_{nm} = c a_n a_m$ for all $n, m \ge 1$ and some $c$, and further suppose that $a_n$ is monotonically decreasing. Then $a_n = \frac{1}{\zeta(s)} \left( \frac{1}{n^s} \right)$ for some real $s > 1$.

More generally, the following situation covers all the examples we have used so far. Let $M$ be a free commutative monoid on generators $p_1, p_2, ...$, and let $\phi : M \to \mathbb{R}$ be a homomorphism. Let $a_m = \mathbb{P}(X = m)$ be a probability distribution on $M$. Suppose that $a_{nm} = c a_n a_m$ for all $n, m \in M$ and some $c$, and further suppose that if $\phi(n) \ge \phi(m)$ then $a_n \le a_m$. Then $a_m = \frac{1}{\zeta_M(s)} e^{-\phi(m) s}$ for some $s$ such that the zeta function

$\displaystyle \zeta_M(s) = \sum_{m \in M} e^{-\phi(m) s}$

converges. Moreover, $\zeta_M(s)$ has the Euler product

$\displaystyle \zeta_M(s) = \prod_{i=1}^{\infty} \frac{1}{1 - e^{- \phi(p_i) s}}$.

Recall that in the statistical-mechanical interpretation, we are looking at a system whose states are finite collections of particles of types $p_1, p_2, ...$ and whose energies are given by $\phi(p_i)$; then the above is just the partition function. In the special case of the zeta function of a Dedekind abstract number ring, $M = M_R$ is the commutative monoid of nonzero ideals of $R$ under multiplication, which is free on the prime ideals by unique factorization, and $\phi(I) = \log N(I)$. In the special case of the dynamical zeta function of an invertible map $f : X \to X$, $M = M_X$ is the free commutative monoid on orbits of $f$ (equivalently, the invariant submonoid of the free commutative monoid on $X$), and $\phi(P) = \log |P|$, where $|P|$ is the number of points in $P$.

## Zeta functions, statistical mechanics and Haar measure

An interesting result that demonstrates, among other things, the ubiquity of $\pi$ in mathematics is that the probability that two random positive integers are relatively prime is $\frac{6}{\pi^2}$. A more revealing way to write this number is $\frac{1}{\zeta(2)}$, where

$\displaystyle \zeta(s) = \sum_{n \ge 1} \frac{1}{n^s}$

is the Riemann zeta function. A few weeks ago this result came up on math.SE in the following form: if you are standing at the origin in $\mathbb{R}^2$ and there is an infinitely thin tree placed at every integer lattice point, then $\frac{6}{\pi^2}$ is the proportion of the lattice points that you can see. In this post I’d like to explain why this “should” be true. This will give me a chance to blog about some material from another math.SE answer of mine which I’ve been meaning to get to, and along the way we’ll reach several other interesting destinations.

## Mathematics in real life II

Another small example I noticed awhile ago and forgot to write up.

Prime numbers, as one of the most fundamental concepts in mathematics, have a way of turning up in unexpected places. For example, the life cycles of some cicadas are either $13$ or $17$ years. It’s thought that this is a response to predation by predators with shorter life cycles; if your life cycle is prime, a predator with any shorter life cycle can’t reliably predate upon you.

A month or so ago I noticed a similar effect happening in the card game BS. In BS, some number of players (usually about four) are dealt the same number of cards from a standard deck without jokers. Beginning with one fixed card, such as the two of clubs, players take turns placing some number of cards face-down in the center. The catch is that the players must claim that they are placing down some number of a specific card; Player 1 must claim that they are placing down twos, Player 2 must claim that they are placing down threes, and so forth until we get to kings and start over. Any time cards are played, another player can accuse the current player of lying. If the accusation is right, the lying player must pick up the pile in the center. If it is wrong, the accusing player must pick up the pile in the center. The goal is to get rid of all of one’s cards.

I’ve been playing this game for years, but I didn’t notice until quite recently that the reason the game terminates in practice is that $13$, the number of types of cards in a standard deck, is prime. If, for example, we stopped playing with aces and only used $12$ types of cards, then a game with $4 | 12$ people need not terminate. Consider a game in which Player 1 has only cards $2, 6, 10$, Player 2 has only cards $3, 7, J$, Player 3 has only cards $4, 8, Q$, and Player 4 has only cards $5, 9, K$, and suppose that Player 1 has to play threes at some point in the game. Then no player can get rid of their cards without lying; since the number of players divides the number of card types, every player will always be asked to play a card they don’t have. Once every player is aware of this, every player can call out every other player’s lies, and it will become impossible to end the game reasonably.

More generally, such situations can occur if $13$ is replaced by a composite number $n$ such that the number of players is at least the smallest prime factor of $n$. This is because people who get rid of their cards will leave the game until the number of players is equal to the smallest prime factor of $n$, at which point the game may stall. But because $13$ is prime, any game played with less than $13$ people has the property that each player will eventually be asked to play a card that they have.

## Ramsey theory and Fermat’s Last Theorem

In the first few lectures of Graph Theory, the lecturer (Paul Russell) presented a cute application of Ramsey theory to Fermat’s Last Theorem. It makes a great introduction to the general process of casting a problem in one branch of mathematics as a problem in another and is the perfect size for a blog post, so I thought I’d talk about it.

The setup is as follows. One naive way to go about proving the nonexistence of nontrivial integer solutions to $x^n + y^n = z^n, n > 2$ (that is, solutions such that $x, y, z$ are not equal to zero) is using modular arithmetic; that is, one might hope that for every $n > 2$ it might be possible to find a modulus $m$ such that the equation has no nontrivial solution $\bmod m$. To simplify matters, we’ll assume that $x, y, z$ are relatively prime to $m$, or else there is some subtlety in the definition of “nontrivial” (e.g. we might have $x, y, z$ not divisible by $m$ but $x^n \equiv 0 \bmod m$.) Note that it might be the case that $m$ is not relatively prime to a particular nontrivial solution in the integers, but if we can prove non-existence of nontrivial solutions for infinitely many $m$ (in particular, such that any integer is relatively prime to at least one such $m$) then we can conclude that no nontrivial integer solutions exist.

By the Chinese Remainder Theorem, this is possible if and only if it is possible with $m$ a prime power, say $m = p^k$. If $p$ is relatively prime to $n$, this is possible if and only if it is possible with $m = p$. This is because given a nontrivial solution $\bmod p$ we can use Hensel’s lemma to lift it to a nontrivial solution $\bmod p^k$ for any $k$ (and even to $\mathbb{Z}_p$), and the converse is obvious. (Again to simplify matters, we’ll ignore the finitely many primes that divide $n$.) So we are led to the following question.

For a fixed positive integer $n > 2$ do there exist infinitely many primes $p$ relatively prime to $n$ such that $x^n + y^n \equiv z^n \bmod p$ has no nontrivial solutions?

As it turns out, the answer is no. In 1916 Schur found a clever way to prove this by proving the following theorem.

Theorem: For every positive integer $k$ there exists a positive integer $m$ such that if $\{ 1, 2, ... m \}$ is partitioned into $k$ disjoint subsets $A_1, ... A_k$, then there exists $i$ such that there exist $a, b, c \in A_i$ with $a + b = c$. In other words, the Schur number $S(k) = m$ exists. (Note that I am using a convention which is off by $1$.)

If we let $p$ be a prime greater than $S(n)$ and let the $A_i$ be the cosets of the subgroup of $n^{th}$ powers in $(\mathbb{Z}/p\mathbb{Z})^{*}$, which has index at most $n$, we obtain the following as a corollary.

Corollary: Fix a positive integer $n > 2$. For any sufficiently large prime $p$, there exists a nontrivial solution to $x^n + y^n \equiv z^n \bmod p$.

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.