Parity, geometric realization, and mean asymptotics of projective permutations of the finite projective line over $\mathbb{Z}_n$ (Arnold, 2009)

Arnold's 2009 survey 'Permutations' contrasts the cycle statistics of random permutations with those of permutations of algebraic origin, and leaves a cluster of open questions on the algebraic side. The finite projective line $P^1(\mathbb{Z}_n)$ over the residue ring $\mathbb{Z}_n$ has $N(n)=n\prod_{p\mid n}(1+1/p)$ points, permuted by the finite modular group $\mathrm{PSL}(2,\mathbb{Z}_n)$; the elements of this action are Arnold's projective permutations. He proved that for every odd prime $p$ all projective permutations of the $p+1$ points are even, verified computationally that evenness persists for composite moduli such as $n=8$ and $n=9$ (it fails for $n=4$ and also for $n=2$, which is prime and therefore outside the odd-prime theorem), and left open the general statement for composite $n$. Three further questions of the same circle are open: a geometric description (by regular polyhedra or by the projective geometry of the Galois fields $\mathbb{F}_{p^\alpha}$) of the actions of $\mathrm{PSL}(2,\mathbb{Z}_{p^\alpha})$ on $P^1(\mathbb{Z}_{p^\alpha})$ for prime powers; the mean behaviour as $n\to\infty$ of $Q(n)=|\mathrm{PSL}(2,\mathbb{Z}_n)|$ and of the counts $|E_n|$ of solutions of $z^2=1$ in $\mathbb{Z}_n$, together with the Cesàro means of $L(n)=|\mathrm{SL}(2,\mathbb{Z}_n)|$ and $L(n)/n^3$; and the statistics of the Frobenius-type permutations induced by the power maps $q\mapsto q^k$ with $\gcd(k,p^\alpha-1)=1$ on the lines of the finite fields $\mathbb{F}_{p^\alpha}$. The survey's conjecture that the Cesàro means of the dilation coefficient $K(n)=N(n)/n$ tend to $15/\pi^2$ was proved by Aicardi as the case $s=2$ of the limit $\zeta(s)/\zeta(2s)$. The problem asks for the four remaining open questions, which jointly serve Arnold's objective of determining how algebraic origin constrains permutation statistics.

Background

In the theory of permutations, every permutation $\sigma$ of a finite set decomposes uniquely into disjoint cyclic permutations (its cycles), and the multiset of cycle lengths, conventionally arranged as left-justified rows of non-increasing length, is called the Young diagram of $\sigma$. Two statistics used throughout are the total number $y(\sigma)$ of cycles and the parity (sign) of $\sigma$: a cycle of length $r$ has sign $(-1)^{r-1}$, so $\sigma$ is even — a composition of an even number of transpositions (swaps of two elements) — exactly when $n-y(\sigma)$ is even, $n$ being the size of the permuted set. For a uniformly random permutation of $N$ elements the mean number of cycles is the harmonic number $H_N=1+\dots+1/N$, each cycle length $s$ occurs on average $1/s$ times per permutation, and the asymptotic distribution of the ordered cycle lengths is classical (Shepp and Lloyd 1966); the largest cycle occupies asymptotically about $0.62N$ of the elements.

Arnold's 2009 survey 'Permutations' compared these classical statistics with those of permutations produced by algebraic constructions, and the deepest of his examples is the following. Let $\mathbb{Z}_n$ be the ring of residue classes modulo $n$. A vector in $\mathbb{Z}_n^2$ is primitive if for every prime $p\mid n$ at least one component is a unit modulo $p$ (equivalently, $\gcd(a,b,n)=1$); two primitive vectors are equivalent when they differ by multiplication by a unit, and the equivalence classes — the lines through the origin — are the points of the projective line $P^1(\mathbb{Z}_n)$. Its cardinality is $N(n)=n\prod_{p\mid n}(1+1/p)$, the product running over the prime divisors $p$ of $n$; thus $N(p)=p+1$ for a prime $p$ and $N(p^\alpha)=p^{\alpha-1}(p+1)$ for a prime power (for instance $N(8)=N(9)=12$).

The special linear group $\mathrm{SL}(2,\mathbb{Z}_n)$ consists of the $2\times 2$ matrices with entries in $\mathbb{Z}_n$ and determinant $1$; reduction of integer matrices modulo $n$ maps $\mathrm{SL}(2,\mathbb{Z})$ onto it, and $\mathrm{SL}(2,\mathbb{Z})$ is generated by the two elementary matrices $T=(1\ 1;\,0\ 1)$ and $S=(1\ 0;\,1\ 1)$ (row-by-row entries). A matrix acts on lines, hence on the $N(n)$ points of $P^1(\mathbb{Z}_n)$. The scalar matrices $\alpha I$ with $\alpha^2\equiv 1\pmod n$ form a normal subgroup $E_n$ that acts trivially, and the quotient $\mathrm{PSL}(2,\mathbb{Z}_n)=\mathrm{SL}(2,\mathbb{Z}_n)/E_n$ is the finite modular group; its elements in this action are Arnold's projective permutations. The subgroup $E_n$ has order equal to the number of solutions of $z^2=1$ in $\mathbb{Z}_n$, and, writing $\varphi$ for Euler's totient function (the number of integers $1\le k\le n$ coprime to $n$), the group orders are $L(n)=|\mathrm{SL}(2,\mathbb{Z}_n)|=n\varphi(n)N(n)$ and $Q(n)=|\mathrm{PSL}(2,\mathbb{Z}_n)|=L(n)/|E_n|$. By the Chinese remainder theorem the rings $\mathbb{Z}_{mn}$ and $\mathbb{Z}_m\times\mathbb{Z}_n$ are isomorphic for coprime $m,n$, so the actions on $P^1(\mathbb{Z}_{mn})$ are products of the actions for $m$ and $n$, and $Q$ is multiplicative on coprime arguments (the survey notes $Q(12)=Q(3)Q(4)=288$).

Arnold's Theorem 4 with its lemma asserts that for an odd prime $p$ the generators $T$ and $S$ act on the $p+1$ points of $P^1(\mathbb{Z}_p)$ each as one cycle of length $p$ plus one fixed point, whence every projective permutation is even and has an even number of cycles. (Evenness is automatic for commutators — elements $aba^{-1}b^{-1}$ — because the commutator subgroup of the symmetric group is the alternating group of even permutations; the generators lie outside that subgroup, so this argument does not cover them.) For $n=5$ the group $\mathrm{PSL}(2,\mathbb{Z}_5)$ is isomorphic to the rotation group of the regular dodecahedron (the icosahedral group, isomorphic to the alternating group $A_5$) acting on its six five-fold symmetry axes, and $\mathrm{PSL}(2,\mathbb{Z}_2)$ is the full symmetric group $S_3$ of the triangle. Computationally, Arnold found that evenness persists for composite moduli such as $n=8$ and $n=9$ but fails for $n=4$ — and also for $n=2$, a prime outside the scope of the odd-prime theorem — and that the cycle statistics of these algebraic permutations differ visibly from the random ones: his tables for $n=7,8$ list, for each cycle length $s$, the total number of cycles of length $s$ over the group, to be compared with the value $Q(n)/s$ expected if the group elements behaved like random permutations of the same points.

The survey also poses asymptotic questions about these quantities as $n\to\infty$. The dilation coefficient is $K(n)=N(n)/n=\prod_{p\mid n}(1+1/p)$, and its Cesàro mean — the ordinary average $(1/x)\sum_{m\le x}K(m)$ of the first $x$ values — was conjectured, on the basis of Aicardi's computations up to $n\sim 10^7$, to tend to $15/\pi^2$. Arnold states that studying the mean behaviour of the functions $Q$, $|E_n|$ and $1/|E_n|$, and deriving the asymptotics of the Cesàro means of $L(n)$ and of $L(n)/n^3$, 'is not simple' and leaves them open. Finally, for a prime power $p^\alpha$ let $\mathbb{F}_{p^\alpha}$ be the Galois field (finite field) with $p^\alpha$ elements, viewed as a vector space over its prime subfield $\mathbb{F}_p$; the multiplicative group $\mathbb{F}_{p^\alpha}^{\times}$ is cyclic, and every power map $q\mapsto q^k$ with $\gcd(k,p^\alpha-1)=1$ permutes the $(p^\alpha-1)/(p-1)$ lines through the origin (one-dimensional $\mathbb{F}_p$-subspaces); for exponents failing this condition — e.g. $k=2$ over $\mathbb{F}_9$, where the image of a line need not be a line — the map does not induce a permutation of the line set. Arnold calls the permutations of the line set so obtained Frobenius-type permutations (his text leaves the admissible exponents unconstrained) and states that their statistics have not been studied, even empirically.

Problem Statement

Common objective: determine how the algebraic origin of the permutations induced by the finite modular groups $\mathrm{PSL}(2,\mathbb{Z}_n)$ and by the finite-field power maps constrains their parity, their geometric realization, and their mean asymptotics — the part of Arnold's programme that his 2009 survey explicitly leaves open after his prime-modulus parity theorem. Concretely, writing $P_n=P^1(\mathbb{Z}_n)$ for the projective line over $\mathbb{Z}_n$ (with $N(n)=n\prod_{p\mid n}(1+1/p)$ points), the survey's four remaining open questions of this circle are the following.

(i) Parity. Determine, with proof, for exactly which composite integers $n$ every projective permutation — every element of $\mathrm{PSL}(2,\mathbb{Z}_n)$ in its action on the $N(n)$ points of $P_n$ — is even; in particular prove or refute the observed evenness for all composite $n$ outside the known composite exception $n=4$ (it is verified for $n=8$ and $n=9$; evenness fails also for the prime $n=2$, which lies outside the odd-prime theorem).

(ii) Geometric realization. For prime powers $p^\alpha$ with $\alpha\ge 2$, give an explicit geometric description of the action of $\mathrm{PSL}(2,\mathbb{Z}_{p^\alpha})$ on $P^1(\mathbb{Z}_{p^\alpha})$ — for example by a regular polyhedron whose symmetry group realizes it, as the dodecahedron rotation group realizes $\mathrm{PSL}(2,\mathbb{Z}_5)$ on its six five-fold axes, or by a configuration of the projective geometry over the Galois field $\mathbb{F}_{p^\alpha}$.

(iii) Mean asymptotics. Determine the mean behaviour as $n\to\infty$ of $Q(n)=|\mathrm{PSL}(2,\mathbb{Z}_n)|$, of $|E_n|$ (the number of solutions of $z^2\equiv 1\pmod n$) and of $1/|E_n|$, and the asymptotics of the Cesàro means $(1/x)\sum_{n\le x}L(n)$ and $(1/x)\sum_{n\le x}L(n)/n^3$, where $L(n)=|\mathrm{SL}(2,\mathbb{Z}_n)|=n\varphi(n)N(n)$. (The Cesàro mean of $K(n)=N(n)/n$ is known to tend to $15/\pi^2$ by Aicardi's theorem and is not part of the question.)

(iv) Frobenius-type statistics. Determine the cycle statistics of the Frobenius-type permutations, i.e. of the permutations induced on the $(p^\alpha-1)/(p-1)$ lines through the origin of $\mathbb{F}_{p^\alpha}$ (viewed as a vector space over $\mathbb{F}_p$) by the power maps $q\mapsto q^k$ with $\gcd(k,p^\alpha-1)=1$ (equivalently, the exponents for which the map induces a permutation of the line set; they include the Frobenius powers $k=p^j$): the distributions of the numbers of cycles of each length, the mean total number of cycles, the mean largest cycle length, and how these compare with the corresponding statistics of random and of projective permutations.

The four items are separate open questions of the survey, grouped here because they interrogate the same finite permutation families from the same standpoint; each is an independent target, and the task is resolved in full only when all four components are resolved, an answer to any single item resolving that component alone and leaving the remaining ones open.

References

1. V. I. Arnold, 'Permutations', Russian Mathematical Surveys 64 (2009), no. 4, 583–624. doi:10.1070/RM2009v064n04ABEH004628, https://www.mathnet.ru/eng/rm9313.
2. V. I. Arnold, 'Random and algebraic permutations' statistics', Functional Analysis and Other Mathematics 2 (2009), no. 2–4, 247–248 (online first December 2008). doi:10.1007/s11853-008-0025-0, https://doi.org/10.1007/s11853-008-0025-0.
3. F. Aicardi, 'Cesaro averages of Euler-like functions', Functional Analysis and Other Mathematics 3 (2010), no. 1, 85–89 (online first January 2009). doi:10.1007/s11853-008-0030-3, https://doi.org/10.1007/s11853-008-0030-3.
4. V. I. Arnold, 'Periods and Young's diagram of Fermat–Euler's geometrical progressions of residues', Functional Analysis and Other Mathematics 3 (2010), no. 1, 21–38. doi:10.1007/s11853-010-0042-7, https://doi.org/10.1007/s11853-010-0042-7.
5. F. Aicardi, 'Empirical estimates of the average orders of orbits period lengths in Euler groups', Comptes Rendus. Mathématique 339 (2004), no. 1, 15–20. doi:10.1016/j.crma.2004.02.021, https://doi.org/10.1016/j.crma.2004.02.021.
6. P. Kurlberg and C. Pomerance, 'On a problem of Arnold: the average multiplicative order of a given integer', Algebra & Number Theory 7 (2013), no. 4, 981–999. arXiv:1108.5209, doi:10.2140/ant.2013.7.981, https://doi.org/10.2140/ant.2013.7.981.
7. C. Aistleitner, 'On some questions of V.I. Arnold on the stochasticity of geometric and arithmetic progressions', Nonlinearity 28 (2015), no. 10, 3663–3675. arXiv:1406.5785, doi:10.1088/0951-7715/28/10/3663, https://doi.org/10.1088/0951-7715/28/10/3663.
8. L. A. Shepp and S. P. Lloyd, 'Ordered cycle lengths in a random permutation', Transactions of the American Mathematical Society 121 (1966), no. 2, 340–357. doi:10.1090/S0002-9947-1966-0195117-8, https://doi.org/10.1090/S0002-9947-1966-0195117-8.
9. F. Benaych-Georges, 'Cycles of random permutations with restricted cycle lengths', arXiv:0712.1903 (2007), https://arxiv.org/abs/0712.1903.
10. S. Asgarli, K.-W. Lai, M. Nakahara, and S. Zimmermann, 'Bijective Cremona transformations of the plane', Selecta Mathematica. New Series 28 (2022), no. 3, article 53. arXiv:1910.05302, doi:10.1007/s00029-022-00768-0, https://doi.org/10.1007/s00029-022-00768-0.
11. Y. Wu, Z. Xu, and Y. Zhu, 'A five-element transformation monoid on labelled trees', European Journal of Combinatorics 80 (2019), 401–415. doi:10.1016/j.ejc.2018.07.014, https://doi.org/10.1016/j.ejc.2018.07.014.