next up previous
Next: A Technical Lemma Up: Preliminary Observations Previous: The Number of Eigenvalues

Description of Xn,a when a=0 and $l \leq 1 $

This is a special case for which very little calculation is involved in determining the behavior of Xn,a. With a=0, the interval starts at 0 and ends at $2\pi l/n$, and equation (10) simplifies to

 \begin{displaymath}X_{n,0} = \sum_{k=1}^n C_k \left\lfloor \frac{kl}{n} \right\rfloor.
\end{displaymath} (18)

Since the largest cycle that can occur in $\sigma$ is an n-cycle, the first position on the unit circle where an eigenvalue can occur is at $\theta = 2\pi l/n$. If l<1, then Xn,0 = 0 because the interval ends before reaching the first possible eigenvalue. This can also be seen from (18) by noting that $\lfloor kl/n \rfloor = 0$ if l<1.

Now if l=1, then the interval ends exactly where the first eigenvalue can occur, so we have

\begin{displaymath}X_{n,0} = \cases{ 1 & if $\sigma$ has an $n$-cycle \cr
0 & otherwise. \cr}\end{displaymath}

The probability that $\sigma$ has an n-cycle is just 1/n, and it is easy to show that in this case,

 \begin{displaymath}E[X_{n,0}] = \frac{1}{n}
\end{displaymath} (19)


 \begin{displaymath}Var[X_{n,0}] = \frac{1}{n} \left(1 - \frac{1}{n} \right) = \frac{n-1}{n^2}.
\end{displaymath} (20)

Both the mean and the variance approach 0 as $n\rightarrow\infty$.

Remark. A similar analysis shows that an analogous `gap' occurs around each rational point a. In particular, if a = p/q in lowest terms, then no eigenvalues can fall in the interval In if l<1/q. For irrational values of a, this sort of gap does not occur. No matter how small l is, there always will be some values of n that produce eigenvalues in the interval In.

These results illuminate some of the differences between the distribution of eigenvalues and that of independent points on the circle. Equations (19) and (20) describe a particularly simple situation, and in this case, the results for random permutations are strikingly different from the results for random independent points. When l>1, the simple argument used here no longer works, and it may not be possible to find explicit formulas for E[Xn,a] or Var[Xn,a] in terms of n. In that case, when n is small, it is easy to calculate the value of Xn,a, and of E[Xn,a] or other quantities describing the distribution of eigenvalues. As n increases, however, exact results require more and more computation, and it is more useful to try to find general trends that will provide a picture of what is happening. The following sections use a different approach to find the large nlimit of E[Xn,a], and the goal will be to see whether this limit might resemble the independent points case more closely when the constant l is larger.

next up previous
Next: A Technical Lemma Up: Preliminary Observations Previous: The Number of Eigenvalues