Feeds:
Posts

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

## Short cycles in random permutations

Previously we showed that the distribution of fixed points of a random permutation of $n$ elements behaves asymptotically (in the limit as $n \to \infty$) like a Poisson random variable with parameter $\lambda = 1$. As it turns out, this generalizes to the following.

Theorem: As $n \to \infty$, the number of cycles of length $1, 2, ... k$ of a random permutation of $n$ elements are asymptotically independent Poisson with parameters $1, \frac{1}{2}, ... \frac{1}{k}$.

This is a fairly strong statement which essentially settles the asymptotic description of short cycles in random permutations.

## Groupoid cardinality

Suitably nice groupoids have a numerical invariant attached to them called groupoid cardinality. Groupoid cardinality is closely related to Euler characteristic and can be thought of as providing a notion of integration on groupoids.

There are various situations in mathematics where computing the size of a set is difficult but where that set has a natural groupoid structure and computing its groupoid cardinality turns out to be easier and give a nicer answer. In such situations the groupoid cardinality is also known as “mass,” e.g. in the Smith-Minkowski-Siegel mass formula for lattices. There are related situations in mathematics where one needs to describe a reasonable probability distribution on some class of objects and groupoid cardinality turns out to give the correct such distribution, e.g. the Cohen-Lenstra heuristics for class groups. We will not discuss these situations, but they should be strong evidence that groupoid cardinality is a natural invariant to consider.

## Fixed points of random permutations

The following two results are straightforward and reasonably well-known exercises in combinatorics:

1. The number of permutations on $n$ elements with no fixed points (derangements) is approximately $\frac{n!}{e}$.
2. The expected number of fixed points of a random permutation on $n$ elements is $1$.

As it turns out, it is possible to say substantially more about the distribution of fixed points of a random permutation. In fact, the following is true.

Theorem: As $n \to \infty$, the distribution of the number of fixed points of a random permutation on $n$ elements is asymptotically Poisson with rate $\lambda = 1$.

## String diagrams, duality, and trace

Previously we introduced string diagrams and saw that they were a convenient way to talk about tensor products, partial compositions of multilinear maps, and symmetries. But string diagrams really prove their use when augmented to talk about duality, which will be described topologically by bending input and output wires. In particular, we will be able to see topologically the sense in which the following four pieces of information are equivalent:

• A linear map $U \to V$,
• A linear map $U \otimes V^{\ast} \to 1$,
• A linear map $V^{\ast} \to U^{\ast}$,
• A linear map $1 \to U^{\ast} \otimes V^{\ast}$.

Using string diagrams we will also give a diagrammatic definition of the trace $\text{tr}(f)$ of an endomorphism $f : V \to V$ of a finite-dimensional vector space, as well as a diagrammatic proof of some of its basic properties.

Below all vector spaces are finite-dimensional and the composition convention from the previous post is still in effect.

## Introduction to string diagrams

Today I would like to introduce a diagrammatic notation for dealing with tensor products and multilinear map. The basic idea for this notation appears to be due to Penrose. It has the advantage of both being widely applicable and easier and more intuitive to work with; roughly speaking, computations are performed by topological manipulations on diagrams, revealing the natural notation to use here is 2-dimensional (living in a plane) rather than 1-dimensional (living on a line).

For the sake of accessibility we will restrict our attention to vector spaces. There are category-theoretic things happening in this post but we will not point them out explicitly. We assume familiarity with the notion of tensor product of vector spaces but not much else.

Below the composition of a map $f : a \to b$ with a map $g : b \to c$ will be denoted $f \circ g : a \to c$ (rather than the more typical $g \circ f$). This will make it easier to translate between diagrams and non-diagrams. All diagrams were drawn in Paper.

## Non-unital rings

(This post was originally intended to go up immediately after the sequence on Gelfand duality.)

A rng (“ring without the i”) or non-unital ring is a semigroup object in $\text{Ab}$. Equivalently, it is an abelian group $A$ together with an associative bilinear map $m : A \otimes A \to A$ (which is not required to have an identity). This is what some authors mean when they say “ring,” but this does not appear to be standard. A morphism between rngs is an abelian group homomorphism which preserves multiplication (and need not preserve a multiplicative identity even if it exists); this defines the category $\text{Rng}$ of rngs (to be distinguished from the category $\text{Ring}$ of rings).

Until recently, I was not comfortable with non-unital rings. If we think of rings either algebraically as endomorphisms of abelian groups or geometrically as rings of functions on spaces, then there does not seem to be any reason to exclude the identity endomorphism resp. the identity function on a space. As for morphisms which don’t preserve identities, if $X \to Y$ is any map between spaces of some kind, then the identity function $Y \to F$ ($F$ is, say, a field) is sent to the identity function $X \to F$, so not preserving identities when they exist seems unnatural.

However, not requiring or preserving identities turns out to be natural in the theory of C*-algebras; in the commutative case, it corresponds roughly to thinking about locally compact Hausdorff spaces rather than just compact Hausdorff spaces. In this post we will discuss rngs generally, including a discussion of the geometric picture of commutative rngs, to get more comfortable with them. It turns out that we can study rngs by formally adjoining multiplicative identities to them. This is an algebraic version of taking the one-point compactification, and it allows us to extend Gelfand duality, in a suitable sense, to locally compact Hausdorff spaces (see this math.SE question for the precise statement, which we will not discuss here).