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.

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

## Noncommutative probability and group theory

There are, roughly speaking, two kinds of algebras that can be functorially constructed from a group $G$. The kind which is covariantly functorial is some variation on the group algebra $k[G]$, which is the free $k$-module on $G$ with multiplication inherited from the multiplication on $G$. The kind which is contravariantly functorial is some variation on the algebra $k^G$ of functions $G \to k$ with pointwise multiplication.

When $k = \mathbb{C}$ and when $G$ is respectively either a discrete group or a compact (Hausdorff) group, both of these algebras can naturally be endowed with the structure of a random algebra. In the case of $\mathbb{C}[G]$, the corresponding state is a noncommutative refinement of Plancherel measure on the irreducible representations of $G$, while in the case of $\mathbb{C}^G$, the corresponding state is by definition integration with respect to normalized Haar measure on $G$.

In general, some nontrivial analysis is necessary to show that the normalized Haar measure exists, but for compact groups equipped with a faithful finite-dimensional unitary representation $V$ it is possible to at least describe integration against Haar measure for a dense subalgebra of the algebra of class functions on $G$ using representation theory. This construction will in some sense explain why the category $\text{Rep}(G)$ of (finite-dimensional continuous unitary) representations of $G$ behaves like an inner product space (with $\text{Hom}(V, W)$ being analogous to the inner product); what it actually behaves like is a random algebra, namely the random algebra of class functions on $G$.

## Moments, Hankel determinants, orthogonal polynomials, Motzkin paths, and continued fractions

Previously we described all finite-dimensional random algebras with faithful states. In this post we will describe states on the infinite-dimensional $^{\dagger}$-algebra $\mathbb{C}[x]$. Along the way we will run into and connect some beautiful and classical mathematical objects.

A special case of part of the following discussion can be found in an old post on the Catalan numbers.

## Finite noncommutative probability, the Born rule, and wave function collapse

The previous post on noncommutative probability was too long to leave much room for examples of random algebras. In this post we will describe all finite-dimensional random algebras with faithful states and all states on them. This will lead, in particular, to a derivation of the Born rule from statistical mechanics. We will then give a mathematical description of wave function collapse as taking a conditional expectation.

## Noncommutative probability

The traditional mathematical axiomatization of probability, due to Kolmogorov, begins with a probability space $P$ and constructs random variables as certain functions $P \to \mathbb{R}$. But start doing any probability and it becomes clear that the space $P$ is de-emphasized as much as possible; the real focus of probability theory is on the algebra of random variables. It would be nice to have an approach to probability theory that reflects this.

Moreover, in the traditional approach, random variables necessarily commute. However, in quantum mechanics, the random variables are self-adjoint operators on a Hilbert space $H$, and these do not commute in general. For the purposes of doing quantum probability, it is therefore also natural to look for an approach to probability theory that begins with an algebra, not necessarily commutative, which encompasses both the classical and quantum cases.

Happily, noncommutative probability provides such an approach. Terence Tao’s notes on free probability develop a version of noncommutative probability approach geared towards applications to random matrices, but today I would like to take a more leisurely and somewhat scattered route geared towards getting a general feel for what this formalism is capable of talking about.

## Lower bounds on off-diagonal Ramsey numbers

The goal of this post is to prove the following elementary lower bound for off-diagonal Ramsey numbers $R(s, t)$ (where $s \ge 3$ is fixed and we are interested in the asymptotic behavior as $t$ gets large):

$\displaystyle R(s, t) = \Omega \left( \left( \frac{t}{\log t} \right)^{ \frac{s}{2} } \right).$

The proof does not make use of the Lovász local lemma, which improves the bound by a factor of $\left( \frac{t}{\log t} \right)^{ \frac{1}{2} }$; nevertheless, I think it’s a nice exercise in asymptotics and the probabilistic method. (Also, it’s never explicitly given in Alon and Spencer.)

## Ultrafilters in topology

Remark: To forestall empty set difficulties, whenever I talk about arbitrary sets in this post they will be non-empty.

We continue our exploration of ultrafilters from the previous post. Recall that a (proper) filter on a poset $P$ is a non-empty subset $F$ such that

1. For every $x, y \in F$, there is some $z \in F$ such that $z \le x, z \le y$.
2. For every $x \in F$, if $x \le y$ then $y \in F$.
3. $P$ is not the whole set $F$.

If $P$ has finite infima (meets), then the first condition, given the second, can be replaced with the condition that if $x, y \in F$ then $x \wedge y \in F$. (This holds in particular if $P$ is the poset structure on a Boolean ring, in which case $x \wedge y = xy$.) A filter is an ultrafilter if in addition it is maximal under inclusion among (proper) filters. For Boolean rings, an equivalent condition is that for every $x \in B$ either $x \in F$ or $1 - x \in F$, but not both. Recall that this condition tells us that ultrafilters are precisely complements of maximal ideals, and can be identified with morphisms in $\text{Hom}_{\text{BRing}}(B, \mathbb{F}_2)$. If $B = \text{Hom}(S, \mathbb{F}_2)$ for some set $S$, then we will sometimes call an ultrafilter on $B$ an ultrafilter on $S$ (for example, this is what people usually mean by “an ultrafilter on $\mathbb{N}$“).

Today we will meander towards an ultrafilter point of view on topology. This point of view provides, among other things, a short, elegant proof of Tychonoff’s theorem.

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