## Abstract

We compute the mean two-point spectral form factor and the spectral number variance for permutation matrices of large order. The two-point correlation function is expressed in terms of generalized divisor functions, which are frequently discussed in number theory. Using classical results from number theory and casting them in a convenient form, we derive expressions which include the leading and next to leading terms in the asymptotic expansion, thus providing a new point of view on the subject, and improving some known results.

## 1. Introduction

The spectral statistics of the eigenvalues of permutation matrices of large dimension have been studied during the past decade from various points of view (e.g. [1–5]). In this article, we approach this subject by computing the spectral form factor [6] defined in the following way. Consider an *N*×*N* unitary matrix *U* drawn from a random ensemble with a given probability distribution over its elements. The form factor is
1.1Here and throughout, stands for the expectation with respect to the random ensemble. As the spectra of the matrices are confined to the unit circle, *K*(*t*;*N*) is the Fourier transform of the spectral two-point correlation function
1.2where the eigenvalues of *U* are . When the eigenphases *θ*_{l} are uniformly distributed on the unit circle, it is convenient to express their differences in units of the mean spacing 2*π*/*N*, and for the form factor limits to a function of the single parameter *τ*=*t*/*N*. Explicit expressions for the form factor are known for various matrix ensembles, the most prominent ones being Dyson's circular ensembles. For the Poissonian ensemble where the eigenphases are independent random variables with uniform distribution, *K*(*τ*)=1. The study of the form factor is motivated by its successful application in ‘quantum chaos’ [7] and spectral graph theory [8,9].

A closely related quantity of interest is the number variance , which measures the fluctuations in the number of eigenphases in an arc [*θ*,*θ*+2*π*(*L*/*N*)] which covers *L* eigenphases on average,
1.3This can be written in terms of the form factor as
1.4

The ensemble to be discussed in the sequel is the ensemble of permutation matrices of *N* objects in the large *N* limit. A permutation *ρ* of *N* objects is represented by an *N*×*N* unitary matrix *P*_{ρ} with elements from {0,1}. The spectrum of *P*_{ρ} is determined by the cycle structure of *ρ*: let *ρ* consist of cycles of lengths *k* with multiplicities *a*_{k}(*ρ*). Clearly,
1.5Each cycle in *ρ* of length *k* contributes to the spectrum *k* roots of unity: , with multiplicity *a*_{k}(*ρ*). Thus,
1.6By assigning a uniform probability distribution to the permutations, the form factor reads
1.7where the expectation is with respect to the ensemble of permutation matrices as defined above.

Figure 1 shows the numerical computation of the form factor for *N*=500. The rapid fluctuations almost hide the mean smooth behaviour of the form factor. The fluctuations are not the result of any approximation or an insufficient sample of matrices taken in the simulations. Rather, it is inherent to the problem, and its origin is number theoretical. In the remainder of the article, we shall provide an asymptotic expression for *K*(*t*;*N*) and show that, after appropriate smoothing, it is described by a simple formula which will be given explicitly.

The spectral statistics of the random permutation matrices have been studied by various authors. Focusing our attention on the uniform probability measure (Ewens parameter *θ*=0 [10]), and on subjects directly relevant to this work, the following asymptotic results in the limit are known:

— On average, the eigenphases are uniformly distributed on the unit circle: [1].

— The leading term in the mean number variance is [2].

— The leading expression for the spectral two-point correlation function is explicitly given in [4], 1.8

The Fourier transform of the above gives the leading asymptotic expressions for the form factor which coincides with the expression derived here in §3*b*.

This approach provides an alternative way of deriving the known results, and enables us to present the next terms in the 1/*N* asymptotic expansion, as will be shown in §3*c*.

## 2. The spectral form factor

The following theorem [2,11] enables us to proceed with the computation of *K*(*t*,*N*).

### Theorem 2.1 (Wieand)

*If a permutation ρ is chosen at random, then, for large N, the numbers a*_{2}(*ρ*),*a*_{3}(*ρ*),*…,a*_{k}(*ρ*) *are asymptotically independent Poisson random variables with parameters* 1/2,1/3,…,1/*k. In particular,*
*For k≠m*
*and*

A straightforward application of the theorem provides an explicit expression of the form factor. It is convenient to write it as a sum of two terms: the first is the leading term which remains finite in the limit of interest here (, ); the second term vanishes in this limit.
2.1and
2.2The restricted divisor functions *σ*_{a}(*t*,*N*) [12] are defined by
2.3where *σ*_{a}(*t*,*N*) generalize the well-known divisor functions *σ*_{a}(*t*) [13]. Indeed, for *t*≤*N*, *σ*_{a}(*t*,*N*)=*σ*_{a}(*t*).

The divisor functions *σ*_{a}(*t*) display considerable fluctuations (see, for example, the drawings of *σ*_{a}(*t*) in [14] for *a*=0,1,…). The fluctuation of *σ*_{1}(*t*) which provides the dominant contribution to *K*(*t*,*N*) obtain their lowest value (*t*+1), for prime *t*. They can also reach values of order . A further smoothing is required to deduce the smooth behaviour of *K*(*t*,*N*). The smoothing procedure used here is explained in the next section.

## 3. The smooth version of the form factor

The computation of the restricted divisor functions *σ*_{a}(*t*;*N*) is simplified by recalling that when *k* is a divisor of *t*, then *t*/*k* is also a divisor. Hence to every divisor, corresponds to the divisor *t*/*k* in the interval . Therefore,
3.1When *t*<*N*, *σ*_{a}(*t*;*N*)=*σ*_{a}(*t*), which takes the simpler form
3.2In this case and if *t* is itself a square of an integer, the last term in the sum above is replaced by *t*^{a/2}.

It is convenient to define the indicator *χ*_{t}(*k*), which takes the value 1 if *k*|*t* and 0 otherwise. Thus,
3.3

The smoothing of the form factor will be achieved using the following procedure.

### (a) Smoothing of divisor functions

Let be an arbitrary function. We define its smooth form 〈*F*(*t*)〉 at *t* in the following way. Choose a smoothing interval of size Δ so that *t*≫Δ≫1. Then,
3.4The choice of Δ is dictated by the properties of *F*(*t*) and the required degree of smoothing. The functions to be smoothed here are all of the form , where , and it will be shown that the optimal choice of Δ is .

We shall first consider the smoothing in the case *t*<*N*. Then, *σ*_{a}(*t*;*N*)=*σ*_{a}(*t*) and
3.5

Before extracting the leading terms in an asymptotic expansion in powers of , one should note the following. The sum above extends over the integer lattice points in the (*r*,*k*) plane inside a (slightly deformed) trapezoid with corners at (*t*−⌊Δ/2⌋,1), (*t*+⌊Δ/2⌋,1), and (figure 2). Most of the lattice points are covered by the rectangle (*t*−⌊Δ/2⌋,1), (*t*+⌊Δ/2⌋,1), and . The two domains differ by two triangles (marked in grey in figure 2), one just below the line (for *r*<*t*) and the other just above this line (for *r*>*t*). Note that differs from by , which is smaller than 1/4 in absolute value. Thus, the number of lattice points inside the triangles is bounded by Δ. The sum (3.5) over the trapezoid therefore equals the sum over the rectangle plus the contribution of each of the triangles, which are added with opposite signs. As *t* is varying, the total contribution from the two triangles fluctuates about zero, thus contributing a fluctuating correction which vanishes upon further smoothing. Another important observation applies to the second term in (3.5) only. It is proportional to *r*^{a} and replacing it by *t*^{a} incurs an error bounded by (*a*(*a*−1)/2)*t*^{a−2}Δ^{2}, because the summation over symmetric points with respect to the middle line *r*=*t* removes the linear terms in Δ. The above should be borne in mind when we proceed now with some approximations, whose accuracy will be estimated in light of these observations.

The leading terms in the asymptotic expansion of (3.5) are obtained by restricting the sum to the points inside the rectangle outlined above, and by replacing *r*^{a} by *t*^{a} in the second term. In the resulting sum, the order of summations can be interchanged, so that
3.6

where is a reminder to be discussed later. The expression in the curly brackets equals the number of times the integer *k* divides the integers *r* in the interval [*t*−⌊Δ/2⌋,*t*+⌊Δ/2⌋], normalized by the number of integers in the interval. As , for any , the curly bracket can be approximated by 1/*k* for all the *k* values appearing in the *k*-sum. This introduces an error term of order 1/Δ whose sign fluctuates depending on *k* and *t*, and which is included in the reminder term .

The minimal smoothing interval is and is chosen because it provides the best possible resolution of details which survive smoothing. With this choice,
3.7In particular, for *a*=0,
3.8where *H*_{n} is the *n*th harmonic number. For general
3.9where *B*_{a}(*x*) are the Bernoulli polynomials, *B*_{a} are the Bernoulli numbers and *ζ*(*a*,*x*) is the generalized (Hurwitz) *ζ* function: . Explicit expressions can be obtained by using the asymptotic expression and similar expressions for *B*_{a}(*x*). In this work, only 〈*σ*_{0}(*t*)〉 and 〈*σ*_{1}(*t*)〉 are required,
3.10and
3.11

These results are consistent with the known asymptotic expressions [15–18]: for 〈*σ*_{0}(*t*)〉,
3.12where *γ* is the Euler constant and the lowest known upper bound for *θ* is 131/416 [19].

For 〈*σ*_{a}(*t*)〉, with *a*≥1,
3.13

The magnitude of the fluctuations of *σ*_{a}(*t*) about their smooth form for *a*≥2 and large *t* can be bounded using an identity due to Ramanujan [16]
3.14Both bounds converge rapidly to 1 as *a* increases. The divisor functions with *a*=0,1 fluctuate much more. A measure of their fluctuations is given by comparing their RMS with their mean. Using another result of Ramanujan [16], one can show that, for *a*=0, the mean square amplitude exceeds the mean by a factor which increases as . MN Huxley (2012, private communication) showed that , from which it follows that the ratio between the variance of the fluctuation and the mean (smooth) term approaches a constant. These results imply that the reminder terms are fluctuating functions of *t* with mean which approaches zero as *t* grows. For the relevant cases to this study, .

The computation of the restricted divisor functions follows the same lines and to avoid repetitions only the results will be quoted, 3.15Similarly, 3.16

### (b) The smooth form factor: leading-order term

The evaluation of the leading term of the smoothed form factor (2.1) makes use of the asymptotic expression for 〈*σ*_{1}(*t*;*N*)〉.

Substituting in (2.1) and taking the limit , , one finds that the leading term of *K*(*t*,*N*) depends on its arguments through *τ*=*t*/*N* exclusively, and
3.17Writing *τ*=*M*+*ξ* with *M*=⌊*τ*⌋, *ξ*∈(0,1], we have,
3.18with *a*_{0}=−1, *b*_{0}=*π*^{2}/6. For large *M*, and to the leading order, *a*_{M}=−1/(2(*M*+1)), *b*_{M}=1/(*M*+1). Hence, for large *τ*,
3.19

Figure 3 summarizes graphically the results above, and illustrates the accuracy by which the leading-order term reproduces the numerically smoothed *K*(*τ*).

### (c) The smooth form factor: next to leading-order term

We shall examine in detail the next to leading-order corrections for the smooth form factor in the interval 0<*τ*≤1. They arise from two sources: the lower order terms in 〈*σ*_{1}(*t*;*N*)〉 and *C*(*t*,*N*) in (2.1). The former are all of order 1/*N* or less, and the main contribution is the constant −1/2*N*.

The largest term in *C*(*t*,*N*) (2.1) is because of the smooth value of *σ*_{0}(*t*)^{2}. It can be computed by making use of the following asymptotic result due to Ramanujan [16] and Wilson [17]:
3.20and the explicit expressions for *A* and *B* are given by *A*=1/*π*^{2} and *B*=(12*γ*−3)/*π*^{2}−(36/*π*^{4})*ζ*′(2). Hence, to leading order, , and the corresponding correction to the smooth form factor is obtained by division by *N*. The computation of for *t*>*N* requires much more delicate considerations which are beyond the power of the smoothing method proposed above.

## 4. The number variance

Previous studies [2] have shown that, in the limit of large *N*, the expected number of eigenvalues in an arc [*α*,*β*] on the unit circle with *α*,*β* being irrational fractions of 2*π* and independent over is . In other words, the mean distribution of the eigenvalues on the unit circle is uniform. The variance of the was also computed in [2] and with the same restrictions on *α*,*β*,
4.1The explicit expression for the smooth form factor derived above allows one to compute the smooth number variance and provide an exact formula in the limit and while . This is the limit of interest in most studies of spectral statistics of random matrix ensembles. The computation of the mean number variance in terms of the form factor makes use of the definition
4.2where the spectral density on the unit circle is given by
4.3An elementary computation using the definition (1.7) gives
4.4Substituting (3.18) above provides an explicit expression for the mean number variance
4.5The leading contribution comes from the upper line and it reads explicitly
4.6where Si(*x*) and Ci(*x*) are the sine and cosine integrals, respectively. The large *L* asymptotic behaviour is dominated by
4.7which is consistent with (4.1) if one recalls the fact that the limits taken here and in [2] are not quite the same. The leading terms in the expansion near *L*=0 are
4.8The infinite sum in (4.5) can be evaluated term by term. The series converges rapidly, and most of its contribution comes from the term with *M*=1. Its large *L* asymptotic is and its expansion near *L*=0 is (*πL*/2)^{2}(*π*^{2}−10). Thus, the large and small *L* asymptotics of the number variance are given by the main terms as quoted in (4.7) and (4.8), respectively.

## Funding statement

This work was supported by the Minerva Center for Nonlinear Physics, the Einstein (Minerva) Center at the Weizmann Institute and the Wales Institute of Mathematical and Computational Sciences (WIMCS). Support from the Israel Science Foundation grant no. ISF-861/11 (F.I.R.S.T.) is acknowledged.

## Acknowledgements

It is a pleasure to thank Prof. Martin Huxley, Prof. Ofer Zeitouni and Dr Igor Wigman for instructive discussions and comments.

## Footnotes

One contribution of 13 to a Theo Murphy Meeting Issue ‘Complex patterns in wave functions: drums, graphs and disorder’.

- © 2013 The Author(s) Published by the Royal Society. All rights reserved.