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 be a prime power, let be a positive integer, and consider the distribution of irreducible factors of degree in a random monic polynomial of degree over . Then, as , this distribution is asymptotically the distribution of cycles of length in a random permutation of elements.

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

Combined with our previous result, we conclude that as (with tending to infinity sufficiently quickly relative to ), the distribution of irreducible factors of degree is asymptotically independent Poisson with parameters .

Read Full Post »

Short cycles in random permutations

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

Theorem: As , the number of cycles of length of a random permutation of elements are asymptotically independent Poisson with parameters .

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

Read Full Post »

Fixed points of random permutations

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

1. The number of permutations on elements with no fixed points (derangements) is approximately .
2. The expected number of fixed points of a random permutation on elements is .

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 , the distribution of the number of fixed points of a random permutation on elements is asymptotically Poisson with rate .

Read Full Post »

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 -algebra . 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.

Read Full Post »

The Yoneda lemma I

For two categories let denote the functor category, whose objects are functors and whose morphisms are natural transformations. For a locally small category, the Yoneda embedding is the functor sending an object to the contravariant functor and sending a morphism to the natural transformation given by composition. The goal of the next few posts is to discuss some standard properties of this embedding and try to gain some intuition about it.

Below, whenever we talk about the Yoneda lemma we implicitly restrict our attention to locally small categories.

Read Full Post »

Ultrafilters in Ramsey theory

We continue our exploration of ultrafilters. Today we’ll discuss the infinite Ramsey theorem, which is the following classical result:

Theorem: Suppose the complete graph on countably many vertices has its edges colored in one of colors. Then there is a monochromatic (i.e. an infinite subgraph all of whose edges are the same color).

The finite Ramsey theorem implies that there is a monochromatic for every positive integer , but this is a strictly stronger result; it implies not only the finite Ramsey theorem but the “strengthened” finite Ramsey theorem, and by the Paris-Harrington theorem this is independent of Peano arithmetic (although Peano arithmetic can prove the finite Ramsey theorem). Indeed, while the standard proof of the finite Ramsey theorem uses the finite pigeonhole principle, the standard proof of the infinite Ramsey theorem uses the infinite pigeonhole principle, which is stronger; this is part of the subject of a post by Terence Tao which is quite enlightening.

Given a non-principal ultrafilter on , any partition of into finitely many disjoint subsets (that is, any coloring) has the property that exactly one of the subsets is in (that is, has “full measure”), and this subset must be infinite. This subset can, in turn, be colored (partitioned), and exactly one of the blocks of the partition is in , and it must again be infinite, and so forth. It follows that a non-principal ultrafilter lets us use the infinite pigeonhole principle repeatedly (in fact this is in some sense what a non-principal ultrafilter is), and since this is exactly what is needed to prove the infinite Ramsey theorem we might expect that we could use a non-principal ultrafilter to prove the infinite Ramsey theorem. Today we’ll describe this proof, and then describe how the infinite Ramsey theorem implies the finite Ramsey theorem, which involves a different use of a non-principal ultrafilter on .

Read Full Post »

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 is a non-empty subset such that

1. For every , there is some such that .
2. For every , if then .
3. is not the whole set .

If has finite infima (meets), then the first condition, given the second, can be replaced with the condition that if then . (This holds in particular if is the poset structure on a Boolean ring, in which case .) 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 either or , but not both. Recall that this condition tells us that ultrafilters are precisely complements of maximal ideals, and can be identified with morphisms in . If for some set , then we will sometimes call an ultrafilter on an ultrafilter on (for example, this is what people usually mean by “an ultrafilter on “).

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.

Read Full Post »

Boolean rings, ultrafilters, and Stone’s representation theorem

Recently, I have begun to appreciate the use of ultrafilters to clean up proofs in certain areas of mathematics. I’d like to talk a little about how this works, but first I’d like to give a hefty amount of motivation for the definition of an ultrafilter.

Terence Tao has already written a great introduction to ultrafilters with an eye towards nonstandard analysis. I’d like to introduce them from a different perspective. Some of the topics below are also covered in these posts by Todd Trimble.

Read Full Post »

The adjoint functor theorem for posets

Recently in Measure Theory we needed the following lemma.

Lemma: Let be non-constant, right-continuous and non-decreasing, and let . Define by . Then is left-continuous and non-decreasing. Moreover, for and ,

.

If you’re categorically minded, this last condition should remind you of the definition of a pair of adjoint functors. In fact it is possible to interpret the above lemma this way; it is a special case of the adjoint functor theorem for posets. Today I’d like to briefly explain this. (And who said category theory isn’t useful in analysis?)

The usual caveats regarding someone who’s never studied category talking about it apply. I welcome any corrections.

Read Full Post »

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 (that is, solutions such that are not equal to zero) is using modular arithmetic; that is, one might hope that for every it might be possible to find a modulus such that the equation has no nontrivial solution . To simplify matters, we’ll assume that are relatively prime to , or else there is some subtlety in the definition of “nontrivial” (e.g. we might have not divisible by but .) Note that it might be the case that 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 (in particular, such that any integer is relatively prime to at least one such ) 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 a prime power, say . If is relatively prime to , this is possible if and only if it is possible with . This is because given a nontrivial solution we can use Hensel’s lemma to lift it to a nontrivial solution for any (and even to ), and the converse is obvious. (Again to simplify matters, we’ll ignore the finitely many primes that divide .) So we are led to the following question.

For a fixed positive integer do there exist infinitely many primes relatively prime to such that 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 there exists a positive integer such that if is partitioned into disjoint subsets , then there exists such that there exist with . In other words, the Schur number exists. (Note that I am using a convention which is off by .)

If we let be a prime greater than and let the be the cosets of the subgroup of powers in , which has index at most , we obtain the following as a corollary.

Corollary: Fix a positive integer . For any sufficiently large prime , there exists a nontrivial solution to .

Read Full Post »