Major Findings of the Research

Recall that the random variable $X_{n,a}$ was defined in the introduction as the number of eigenvalues of a permutation matrix landing in the interval $I_n = \left(e^{2 \pi i a}, e^{2 \pi i(a + \ell/n)}\right]$. The expected value (or mean) of $X_{n,a}$, denoted by $E[X_{n,a}]$, is taken with uniform probability measure over the set of all $n \times n$ permutation matrices. The main goal of this project was to find the large $n$ limit of $E[X_{n,a}]$. Eventually, we arrived at the following theorem, which is proved in Sections 6 and 8 of the complete paper.

Theorem 1  

1. Suppose that $a = p/q$ is a rational number in $[0, 1)$, with $p$ and $q$ relatively prime. Then
   
   $$\lim_{n\rightarrow\infty}E[X_{n,a}] = \frac{1}{q} \ln \left(\frac{(q\ell)^{\lfloor q\ell\rfloor}} {\lfloor q\ell \rfloor !}\right).$$
   
   
   ($a = 0$ is taken to be $p = 0$, $q = 1$.)
2. For almost every irrational number $a \in [0, 1)$,
   
   $$\lim_{n\rightarrow\infty}E[X_{n,a}] = \ell.$$
   
   

As it may be unfamiliar to some readers, the notation $\lfloor x \rfloor$ is read floor of $x$, and denotes the greatest integer less than or equal to $x$. The phrase "almost every" in the second part of the theorem has a precise measure theoretic definition. Essentially, it means that the result in Part 2 applies to all numbers $a \in [0, 1)$ except for those in a very small set, namely a set of measure 0. This "small" set includes all rational numbers and some irrational numbers. (The specific set of irrational numbers to which Theorem 1, Part 2 applies is defined at the beginning of Section 8 in the complete paper.) One way to interpret this result is as follows: If the point $a$ is chosen randomly (i.e. uniformly) from the interval $[0, 1)$, the probability that $\lim_{n\rightarrow\infty}E[X_{n,a}] = \ell$ is 1. One might wonder how this can be consistent with Part 1, which says that the limit for all rational points is different from $\ell$. The answer is that the set of rational numbers, and indeed any countable set, is "small" when we impose a uniform measure on the set of points in an interval. In particular, the probability that a randomly chosen point will be rational is 0, just like the probability of picking any particular point in the interval is 0.

The other main result of the research was finding a rate of convergence for $E[X_{n,a}]$ when $a$ is rational. While the rate of convergence is of independent interest, this result was needed to prove Part 2 of Theorem 1. Theorem 2 below is proved in Section 7 of the complete paper.

Theorem 2   There exists a constant $C>0$ such that for each rational number $a = p/q$ with $\gcd(p,q)=1$, there is a positive number $N$ depending on $q$ and $\ell$ such that

$$\left\vert E[X_{n,a}] - \frac{1}{q}\ln \left(\frac{(q\ell)^{\lfloor q\ell\rfloor}} {\lfloor q\ell \rfloor !}\right)\right\vert < C {1+\ell^2 q\ln q \over n}$$

for all $n\ge N$.

The same constant $C$ works for all rational numbers $a$, but note that since $q$ appears in the expression, the total error bound, as well as the constant $N$, depends on the denominator of $a$. The important feature of this result, for the purposes of proving the second part of Theorem 1, was the relative rate of growth of the numerator with respect to $q$ compared to the rate of growth of the denominator with $n$. (We will discuss this fact further in the section on irrational a.) The next two sections discuss the two parts of Theorem 1 in more detail.