Mean period statistics and cycle statistics of algebraic permutations of finite tori and projective lines (Arnold, 2006–2009)

An algebraic permutation is the permutation $\hat A$ of the $N=n^m$ points of the finite torus $\mathbb{Z}_n^m$ induced by a matrix $A$ in $\mathrm{SL}(m,\mathbb{Z}_n)$; its period $T(\hat A)$ is the order of $A$ in the finite group $\mathrm{SL}(m,\mathbb{Z}_n)$, and $A$ also permutes the projective space $\mathrm{P}^{m-1}(\mathbb{Z}_n)$, whose size for $m=2$ is $nK(n)$ with $K(n)=\prod_{p\mid n}(1+1/p)$. Arnold (2006–2009) asserted that $T(\hat A)$ is bounded by a power of $N$, conjectured from tables that the cycle statistics of such permutations are 'entirely different' from the Goncharov laws for random permutations (longest cycle, mean cycle length, and mean period growing linearly in the number of permuted points), and identified the Cesaro mean of $K(n)$ as $15/\pi^2=\zeta(2)/\zeta(4)$. The open core addressed here is the asymptotic statistics of the mean period over $A$ in $\mathrm{SL}(2,\mathbb{Z}_n)$ as $n$ varies — the average Arnold singled out as interesting and not trivial — together with rigorous limiting Young-diagram laws and their deviation from the Goncharov laws.

Background

Fix an integer $n\ge 2$ and a matrix $A\in\mathrm{SL}(m,\mathbb{Z}_n)$, the group of $m\times m$ matrices over the ring of residues modulo $n$ with determinant $1$. Iterating $A$ permutes the $N=n^m$ points of the finite torus $\mathbb{Z}_n^m$; following V. I. Arnold, the resulting permutation $\hat A\in S(N)$ is called an algebraic permutation, and its period $T(\hat A)$ — the least $t\ge 1$ with $A^t\equiv I\pmod n$ — is exactly the order of the element $A$ in the finite group $\mathrm{SL}(m,\mathbb{Z}_n)$. The same matrix also permutes the lines through the origin, that is, the projective space $\mathrm{P}^{m-1}(\mathbb{Z}_n)$; for $m=2$ this projective line has $N'(n)=nK(n)$ points, where $K(n)=\prod_{p\mid n}(1+1/p)=\psi(n)/n$ is the ratio of the Dedekind psi function $\psi$ to $n$.

In late publications Arnold contrasted algebraic permutations with uniform random permutations of $N$ points. For random permutations, the classical theorems of Goncharov (1944) give precise limiting laws for the Young diagram of the cycle decomposition: the expected number of cycles is $\ln N+\gamma+o(1)$, the numbers of cycles of any fixed lengths are asymptotically Poisson, and the longest cycle occupies a positive fraction of $N$. Arnold observed, mostly through extensive tables for the Fibonacci automorphism $(u,v)\mapsto(2u+v,u+v)$ of $\mathbb{Z}_n^2$ — the famous 'Arnold cat map', a hyperbolic toral automorphism of chaotic dynamics, here taken modulo $n$ — and for projective permutations, that algebraic permutations behave very differently: for the projective ensembles he tabulated, he conjectured from the data that the longest cycle, the mean cycle length, and the mean period all grow linearly in the number of permuted points (with explicit numerical constants near $0.36N'(n)$, $0.22N'(n)$, and $0.36N'(n)$), so that the number of cycles stays bounded on average — but he explicitly kept these hypotheses outside his theorems. What he proved are exact counting statements, such as $N'(n)=nK(n)$ (by Euler's product method), the formula $|\mathrm{SL}(2,\mathbb{Z}_{p^\alpha})|=p(p^2-1)p^{3(\alpha-1)}$ communicated by F. Aicardi, and tables of statistics; his survey also reports Aicardi's computations up to $n\sim 10^7$ showing the Cesaro means of $K(n)$ tending to $15/\pi^2=\zeta(2)/\zeta(4)\approx 1.5198177$, while stating that at the time it was 'not even clear' whether that mean converges.

Several neighboring strands are classical or have since been settled. For the single fixed cat map, the period as a function of the side length $n$ was essentially determined by Dyson and Falk (1992): the period is $O(n)$ — hence $O(N^{1/2})$ in the point count $N=n^2$ — with exact values such as $3n$ for $n=2\cdot 5^s$ and $2n$ for $n=5^s$ or $6\cdot 5^s$, and the general bound $M\le n^2/2$; the connection with Fibonacci (Pisano) periods is recounted by Nance. For a fixed hyperbolic matrix $A\in\mathrm{SL}_2(\mathbb{Z})$ with varying modulus $N$, Kurlberg (2003), motivated by the quantum ergodicity results of Kurlberg and Rudnick (2001) for the quantized cat map — the finite-dimensional quantum analogue of the cat map, for which equidistribution of almost all eigenstates was proved once the order of $A$ modulo $N$ slightly exceeds $N^{1/2}$ — proved under the Generalized Riemann Hypothesis that $\mathrm{ord}_N(A)\gg N^{1-\epsilon}$ for a density-one set of moduli, and $\mathrm{ord}_N(A)>c_A N$ for parabolic $A$ unconditionally. Aicardi (2004) studied empirically the average orders of orbit periods in Euler groups (the analogous one-dimensional multiplicative setting), and Aicardi (2010) rigorously computed the limits of the Cesaro means of the Euler-like functions $\prod_{p\mid n}(1\pm p^{-s})$, a family containing $K(n)$, thereby establishing the $15/\pi^2$ mean-value claim that Arnold's survey had left open. An engineering strand — Chen, Wong, Liao and Xiang (2012, 2014), Li, Tan, Feng and Lü (2022), Tan and Li (2025) — computes exact period distributions and complete functional-graph and cycle structures of the generalized cat map over $\mathbb{Z}_{p^k}$, oriented toward pseudorandom sequence generation and encryption; a physics strand (Barash and Shchur 2006) studies orbit periods of ensembles of cat maps through the arithmetic of quadratic integer rings. Closest to the average-order question, Fulman (1999) computed cycle indices for the finite classical groups and used them to derive the average order of a random matrix over a finite field; this works over finite fields rather than the composite moduli $\mathbb{Z}_n$ and provides no Cesaro averaging in $n$ or Young-diagram limiting laws. None of these works addresses the average over $A\in\mathrm{SL}(2,\mathbb{Z}_n)$ or limiting Young-diagram laws. Aistleitner (2015) settled other questions from Arnold's program on the stochasticity of finite deterministic sequences (geometric and arithmetic progressions, continued fractions).

The open questions are: (i) the asymptotic statistics of the mean values of the periods of algebraic permutations — the average over $A\in\mathrm{SL}(2,\mathbb{Z}_n)$ as $n$ varies, which Arnold singled out as interesting and not trivial; and (ii) rigorous limiting laws for the Young diagrams of cycles of algebraic permutations and their deviation from the Goncharov laws.

Problem Statement

Let $n\ge 2$ and $A\in\mathrm{SL}(m,\mathbb{Z}_n)$; $A$ induces the algebraic permutation $\hat A$ of the $N=n^m$ points of the finite torus $\mathbb{Z}_n^m$, with period $T(\hat A)$ equal to the order of $A$ in $\mathrm{SL}(m,\mathbb{Z}_n)$, and also a permutation of the projective space $\mathrm{P}^{m-1}(\mathbb{Z}_n)$, which for $m=2$ has $N'(n)=nK(n)$ points with $K(n)=\prod_{p\mid n}(1+1/p)=\psi(n)/n$. Arnold asserted that $T(\hat A)$ is bounded by a power of $N$, and similarly for the projective action, and conjectured from tables that for projective algebraic permutations the longest cycle, the mean cycle length, and the mean period grow linearly in the number of permuted points, while keeping all such asymptotics outside his theorems. The problem is to settle the following two linked parts. The two parts are distinct: part (1) asks for the asymptotic law in $n$ of the average over $A$ of $T(A,n)$, whereas part (2) asks for the ordinary limiting law in $n$ of the cycle decomposition.

(1) Mean periods. Determine the asymptotic statistics of the mean values of the periods $T(A,n)$ of $A\in\mathrm{SL}(2,\mathbb{Z}_n)$ — averaging over the choice of $A$ and studying this mean value as the parameter $n$ varies — which Arnold's survey states explicitly to be interesting in its own right and not trivial, and whose answer may turn out to depend strangely on the arithmetic nature of the modulus $n$. Arnold's survey poses the question with Cesaro averaging over the parameter $n$; since the mean period is unbounded in $n$, that un-normalised Cesaro mean over $n$ diverges, and the question is instead about the asymptotic law of the mean value itself. The single fixed cat map for $m=2$ is classical (Dyson–Falk) and is excluded: the open content lies in the mean behavior over the whole group $\mathrm{SL}(2,\mathbb{Z}_n)$ as $n$ grows.

(2) Young-diagram laws. Prove or disprove limiting laws for the cycle decompositions of algebraic permutations, for both ensembles: $A$ uniform in $\mathrm{SL}(2,\mathbb{Z}_n)$ acting on the torus points, with period the order of $A$ in $\mathrm{SL}(2,\mathbb{Z}_n)$, and its image in $\mathrm{PSL}(2,\mathbb{Z}_n)$ — the quotient of $\mathrm{SL}(2,\mathbb{Z}_n)$ by its scalar matrices, which is the group that acts on the projective line $\mathrm{P}^1(\mathbb{Z}_n)$ — acting on the projective points, with period the order of the image in $\mathrm{PSL}(2,\mathbb{Z}_n)$; in each case describe the asymptotic joint distribution of the numbers of cycles of each length, the total number of cycles, the longest cycle, and the period, and quantify the deviation from the Goncharov laws for uniform random permutations (expected cycle count $\sim\ln N$, asymptotically Poisson counts of cycles of fixed lengths). Arnold's linear-in-the-number-of-permuted-points conjectures for these statistics (e.g. longest cycle near $0.36\,N'(n)$, mean cycle length near $0.22\,N'(n)$, mean period near $0.36\,N'(n)$ for the projective ensembles) remain unproved.

References

1. V. I. Arnold, 'Random and algebraic permutations' statistics', Functional Analysis and Other Mathematics 2(2–4) (2009) 247–248, DOI: 10.1007/s11853-008-0025-0, https://link.springer.com/article/10.1007/s11853-008-0025-0.
2. V. I. Arnold, 'Permutations', Russian Mathematical Surveys 64(4) (2009) 583–624 (Russian original: Uspekhi Mat. Nauk 64:4 (2009) 3–44), DOI: 10.1070/RM2009v064n04ABEH004628, https://www.mathnet.ru/eng/rm9313.
3. V. I. Arnold, 'Statistics of Young diagrams of cycles of dynamical systems for finite tori automorphisms', Moscow Mathematical Journal 6(1) (2006) 43–56, DOI: 10.17323/1609-4514-2006-6-1-43-56, https://www.mathnet.ru/eng/mmj234.
4. V. I. Arnold, Dynamics, Statistics and Projective Geometry of Galois Fields, Cambridge University Press (2010), DOI: 10.1017/CBO9780511975783, https://doi.org/10.1017/cbo9780511975783.
5. V. I. Arnold, 'Periods and Young's diagram of Fermat–Euler's geometrical progressions of residues', Functional Analysis and Other Mathematics 3(1) (2010) 21–38, DOI: 10.1007/s11853-010-0042-7, https://doi.org/10.1007/s11853-010-0042-7.
6. V. L. Goncharov, 'On the field of combinatory analysis' (Russian original: Izv. Akad. Nauk SSSR Ser. Mat. 8(1) (1944) 3–48), English translation: American Mathematical Society Translations Series 2, vol. 19 (1962) 1–46, DOI: 10.1090/trans2/019/01, https://doi.org/10.1090/trans2/019/01.
7. F. J. Dyson and H. Falk, 'Period of a discrete cat mapping', The American Mathematical Monthly 99(7) (1992) 603–614, DOI: 10.1080/00029890.1992.11995900, https://doi.org/10.1080/00029890.1992.11995900.
8. P. Kurlberg, 'On the order of unimodular matrices modulo integers', Acta Arithmetica 110(2) (2003) 141–151, DOI: 10.4064/aa110-2-4, https://arxiv.org/abs/math/0202053.
9. P. Kurlberg and Z. Rudnick, 'On quantum ergodicity for linear maps of the torus', Communications in Mathematical Physics 222(1) (2001) 201–227, DOI: 10.1007/s002200100501, https://doi.org/10.1007/s002200100501.
10. F. Aicardi, 'Empirical estimates of the average orders of orbits period lengths in Euler groups', Comptes Rendus Mathematique 339(1) (2004) 15–20, DOI: 10.1016/j.crma.2004.02.021, https://doi.org/10.1016/j.crma.2004.02.021.
11. F. Aicardi, 'Cesaro averages of Euler-like functions', Functional Analysis and Other Mathematics 3(1) (2010) 85–89, DOI: 10.1007/s11853-008-0030-3, https://link.springer.com/article/10.1007/s11853-008-0030-3.
12. J. Fulman, 'Cycle indices for the finite classical groups', Journal of Group Theory 2(3) (1999), DOI: 10.1515/jgth.1999.017, https://arxiv.org/abs/math/9712239.
13. C. Aistleitner, 'On some questions of V.I. Arnold on the stochasticity of geometric and arithmetic progressions', Nonlinearity 28(10) (2015) 3663–3675, DOI: 10.1088/0951-7715/28/10/3663, https://arxiv.org/abs/1406.5785.
14. L. Barash and L. N. Shchur, 'Periodic orbits of the ensemble of Sinai–Arnold cat maps and pseudorandom number generation', Physical Review E 73 (2006) 036701, DOI: 10.1103/PhysRevE.73.036701, https://arxiv.org/abs/physics/0409069.
15. F. Chen, K.-W. Wong, X. Liao and T. Xiang, 'Period distribution of generalized discrete Arnold Cat map for N = p^e', IEEE Transactions on Information Theory 58(1) (2012) 445–452, DOI: 10.1109/TIT.2011.2171534, https://doi.org/10.1109/TIT.2011.2171534.
16. F. Chen, K.-W. Wong, X. Liao and T. Xiang, 'Period distribution of generalized discrete Arnold cat map', Theoretical Computer Science 552 (2014) 13–25, DOI: 10.1016/j.tcs.2014.08.002, https://doi.org/10.1016/j.tcs.2014.08.002.
17. C. Li, K. Tan, B. Feng and J. Lü, 'The graph structure of the generalized discrete Arnold's Cat map', IEEE Transactions on Computers 71(2) (2022) 364–377, DOI: 10.1109/TC.2021.3051387, https://doi.org/10.1109/TC.2021.3051387.
18. K. Tan and C. Li, 'The graph structure of a class of permutation maps over ring Z_{p^k}', preprint (2025), arXiv:2506.20118, https://arxiv.org/abs/2506.20118.
19. J. Nance, 'Periods of the discretized Arnold Cat Map and its extension to n dimensions', preprint (2011), arXiv:1111.2984, https://arxiv.org/abs/1111.2984.