Feeds:
Posts
Comments

Posts Tagged ‘asymptotics’

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

(more…)

Read Full Post »

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.

(more…)

Read Full Post »

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.

(more…)

Read Full Post »

Optimizing parameters

I came across a fun problem recently that gave me a good opportunity to exercise my approximation muscles.

Problem: Compute \displaystyle \lim_{n \to \infty} \frac{n + \sqrt{n} + \sqrt[3]{n} + ... + \sqrt[n]{n}}{n}, if it exists.

The basic approach to such sums is that the first few terms contribute to the sum because they are large and the rest of the terms contribute to the sum because there are a lot of them, so it makes sense to approximate the two parts of the sum separately. This is an important idea, for example, in certain estimates in functional analysis.

Since \sqrt[k]{n} \ge 1, k \ge 2 it follows that the limit, if it exists, is at least \lim_{n \to \infty} \frac{2n-1}{n} = 2. In fact, this is the precise value of the limit. We’ll show this by giving progressively sharper estimates of the quantity

\displaystyle E_n = \frac{1}{n} \sum_{k=2}^{n} \left( \sqrt[k]{n} - 1 \right).

In the discussion that follows I’m going to ignore a lot of error terms to simplify the computations.

(more…)

Read Full Post »

Follow

Get every new post delivered to your Inbox.

Join 324 other followers