Arnold's Fermat–Euler progression statistics: asymptotic laws for the divisor functions of totient values, the all-residue mean period, and Gaussian-integer extensions

V. I. Arnold's 2010 study of Fermat–Euler geometric progressions — the eventually periodic residue sequences $a^t\bmod n$ — whose mean-period statistics generated six stated open questions: whether $\hat T(n)/n$ has a limit (in particular the random-divisor heuristic value $\lambda_0=\zeta(3)/\zeta^3(2)\approx 0.27$) and how it behaves at primes; whether totient values $m=\varphi(n)$ carry asymptotically enhanced divisor statistics, with conjectured laws $\hat\sigma_s(\varphi(n))\sim\lambda(s)n^s$; whether the answers are robust under changes of averaging scheme and under restriction to the unit group; whether the theory extends to Gaussian-integer moduli; and a call for computations to $10^6$ and beyond. The mean-period questions are largely settled: Luca and Shparlinski (2003) proved unconditionally that the unit-group average multiplicative order $u(n)$ has Cesàro mean $(x/\log x)\exp(b\log_2 x/\log_3 x(1+o(1)))$ with $b=0.3453\ldots$, so the Cesàro-averaged statistic tends to $0$ and the constant $0.27$ is untenable on the unit-group side, and that $u(n)/\lambda(n)$ is dense in $[0,1]$, so no pointwise limit exists; Luca (2005) and Hu and Pomerance (2012) determined that the prime-moduli statistic has mean $K_1=\prod_p(1-p/(p^3-1))\approx 0.57596$ with a limiting distribution; and the fixed-base conjecture $T_g(x)\sim c(g)x/\log x$ was refuted under GRH by Shparlinski (2007) and given its sharp GRH-conditional asymptotic by Kurlberg and Pomerance (2013); of these, only the unrestricted all-residue mean $\hat T(n)$ itself remains open. The divisor-statistics core remains open: no asymptotic law is known for the mean of $\sigma(\varphi(n))$ (only the open 1964 Mąkowski–Schinzel conjecture, the uniform constants of Pomerance and Ford, and Luca–Pomerance/Kim bounds for the mean of $\tau(\varphi(n))$ whose leading constant is not even pinned), and the Gaussian-integer extension is open. This surviving open core is formulated as the research objective below.

Background

For integers $a$ and $n\ge 1$, the sequence of residues $a^t\bmod n$ ($t=0,1,2,\ldots$) — which Arnold called a Fermat–Euler geometric progression — is eventually periodic; write $T(a,n)$ for its eventual period. When $\gcd(a,n)=1$ this is the multiplicative order of $a$ modulo $n$: the least $k\ge 1$ with $a^k\equiv 1\pmod n$, i.e. the order of $a$ as an element of the unit group $\Gamma(n)=(\mathbb Z/n\mathbb Z)^\times$ of invertible residue classes, whose size is Euler's totient $\varphi(n)$. Arnold organized the multiset of periods $\{T(a,n)\}_a$ as a Young diagram $D(n)$ (the partition of $n$ parts given by sorting the periods) and studied the mean period $\hat T(n)=\frac1n\sum_{a=1}^n T(a,n)$ together with its restriction $\hat T_\Gamma(n)=\frac1{\varphi(n)}\sum_{a\in\Gamma(n)}T(a,n)$ to the unit group. For a prime $p$ the classical identity $\sum_{a\in\Gamma(p)}T(a,p)=\sum_{d\mid p-1}d\,\varphi(d)$ gives $\hat T(p)=\frac{1+(p-1)\alpha(p-1)}{p}$, where $\alpha(m)=\frac1m\sum_{d\mid m}d\,\varphi(d)$ is the average order of an element of the cyclic group of order $m$; Arnold's data $\hat T(p)/p\approx 0.529,\,0.562,\,0.441$ for $p=11,101,1009$ are values of this quantity, which fluctuates around $0.576$. Several functions measure 'typical order' arithmetic. The Carmichael function $\lambda(n)$ is the exponent of $\Gamma(n)$ (the least $k$ with $a^k\equiv 1$ for every unit $a$), i.e. the maximal element order in $\Gamma(n)$. The average multiplicative order $u(n)=\hat T_\Gamma(n)$ was determined in its statistical behavior by Luca and Shparlinski: $u(n)/\lambda(n)$ is dense in $[0,1]$ and has no distribution function, so in particular it has no limit; and, unconditionally, its Cesàro mean (average over $n\le x$) satisfies

$$\frac1x\sum_{n\le x}u(n)=\frac{x}{\log x}\exp\Big(b\,\frac{\log_2 x}{\log_3 x}(1+o(1))\Big),\qquad b=e^{-\gamma}\prod_p\Big(1-\frac1{(p-1)^2(p+1)}\Big)=0.3453\ldots,$$

where $\log_2$ and $\log_3$ denote twice- and thrice-iterated logarithms and $\gamma$ is Euler's constant; Erdős, Pomerance and Schmutz had earlier obtained the same shape for the Cesàro mean of $\lambda(n)$ itself. By partial summation the Cesàro mean of $u(n)/n$ therefore tends to $0$. On the cyclic-group side, von zur Gathen, Knopfmacher, Luca, Lucht and Shparlinski showed $\frac1x\sum_{n\le x}\alpha(n)=\frac{3\zeta(3)}{\pi^2}x+O((\log x)^{2/3}(\log\log x)^{4/3})$; Luca determined that $\alpha(n)/n$ for $n=p-1$ (and for $n=2^m-1$) has a limiting distribution as $p$ varies and computed its mean; and Hu and Pomerance proved the effective version uniform in $k$: $\frac1{\pi(x)}\sum_{p\le x}\frac{\alpha(p^k-1)}{p^k-1}\to K_k$ for $k\le\frac{\log x}{2\log\log x}$, with explicit Euler-product constants such as $K_1=\prod_p(1-\frac{p}{p^3-1})=0.5759599689\ldots$. Via the identity above this fixes the mean of $\hat T(p)/p$ over primes at $K_1$ and shows it fluctuates without converging. For a fixed integer base $g$, writing $\ell_g(n)$ for the order of $g$ modulo $n$ and $T_g(x)$ for its average over $n\le x$ coprime to $g$, Arnold conjectured $T_g(x)\sim c(g)x/\log x$; Shparlinski showed under GRH (the generalized Riemann Hypothesis for Dedekind zeta functions) that this is false, with $T_g(x)\ge\frac{x}{\log x}\exp(C(g)(\log_3 x)^{3/2})$ for non-square $g$, and Kurlberg and Pomerance proved under GRH the sharp form $T_g(x)=\frac{x}{\log x}\exp(B\frac{\log_2 x}{\log_3 x}(1+o(1)))$ with the same constant $B=0.3453\ldots$ (the upper bound holds unconditionally). The second half of Arnold's program concerns the divisibility structure of totient values. Write $\sigma_s(m)=\sum_{d\mid m}d^s$ for the sum of $s$-th powers of the divisors of $m$, so $\sigma_1=\sigma$ is the sum-of-divisors function and $\sigma_0=\tau$ counts divisors; write $\hat\sigma_s(\varphi(n))$ for the average of $\sigma_s(\varphi(n))$ over $n$ up to a bound. Since a prime $q$ can divide $\varphi(n)$ only when $q\mid p-1$ for some prime $p\mid n$ (or $q\mid n$ with multiplicity), totient values were expected — and empirically observed by Arnold — to carry more divisors than typical integers of their size. Rigorous knowledge is partial. Erdős and Pomerance determined the normal order (typical size) of the number of prime factors of $\varphi(n)$. The Mąkowski–Schinzel conjecture $\sigma(\varphi(n))\ge n/2$, open since 1964, is known only in the weakened form $\sigma(\varphi(n))>\kappa n$ for all $n$, with $\kappa\ge 1/39.4$ (Pomerance 1989, then Ford 2001). De Koninck and Luca determined extremal and average orders of the quotient $\sigma(\varphi(n))/\varphi(\sigma(n))$. For the Cesàro mean of $\tau(\varphi(n))$, Luca and Pomerance proved $\frac1x\sum_{n\le x}\tau(\varphi(n))=\exp\big(c_\varphi(x)(\frac{\log x}{\log\log x})^{1/2}(1+O(\frac{\log_3 x}{\log_2 x}))\big)$ with $c_\varphi(x)$ confined to $[7^{-1}e^{-\gamma/2},\,2^{3/2}e^{-\gamma/2}]$, and the analogous lower bound for $\tau(\lambda(n))$; Kim raised the lower constant to $2e^{-\gamma/2}$ (within a factor $\sqrt2$ of the upper bound) and gave a heuristic that the optimal constant for the $\lambda$-analogue is $2\sqrt2 e^{-\gamma/2}$. No asymptotic law — an equality with a $1+o(1)$ factor and a pinned constant — is known for any of these means, and nothing is known about the means of $\sigma_s(\varphi(n))$ for $s\ge 1$. Arnold's paper finally asks for the extension of the whole family $T$, $D$, $\hat T$ to the Gaussian integers $\mathbb Z[i]$ (moduli $n=u+iv$), where the unit group and a Gaussian totient must first be defined; this extension is open.

Problem Statement

Arnold's 2010 paper (DOI 10.1007/s11853-010-0042-7) posed six questions on the statistics of Fermat–Euler progression periods and totient values. Of its mean-period questions, the unit-group restriction $\hat T_\Gamma(n)$ (no pointwise limit, by the density of $u(n)/\lambda(n)$ in $[0,1]$), the prime subsequence (mean tending to $K_1\approx0.576$, with a limiting distribution), the robustness across averaging schemes, and the fixed-base conjecture are settled in the literature (see Background); the unrestricted all-residue mean $\hat T(n)$ itself survives as part (2) of the open core below. The surviving open core has one common objective: replace the empirical observations and unpinned bounds for Arnold's statistics with precise asymptotic laws. Its three linked parts: (1) Divisor statistics of totient values. Establish an asymptotic law — an equality with a $1+o(1)$ factor and explicit constants, not only exponent-constant bounds — for the Cesàro mean $\frac1x\sum_{n\le x}\sigma_s(\varphi(n))$, where $\sigma_s(m)=\sum_{d\mid m}d^s$, required for every fixed $s\ge0$ — with $s=0$, the divisor count $\tau$, and $s=1$, the sum of divisors $\sigma$, as the two cases Arnold singles out; equivalently, for Arnold's averaged statistic $\hat\sigma_s(\varphi(n)):=\frac1n\sum_{k\le n}\sigma_s(\varphi(k))$. This includes deciding whether Arnold's conjectured shape $\hat\sigma_s(\varphi(n))\sim\lambda(s)n^s$ — where $\lambda(s)$ is a constant depending on $s$ in Arnold's notation, to be distinguished from the Carmichael function $\lambda(n)$ and from the mean-period heuristic constant $\lambda_0$ — holds with an explicit constant $\lambda(s)$ or requires a slowly varying correction factor; for $s=0$ it includes pinning the constant $c_\varphi$ in the Luca–Pomerance estimate $\frac1x\sum_{n\le x}\tau(\varphi(n))=\exp\big((c_\varphi+o(1))(\frac{\log x}{\log\log x})^{1/2}\big)$, currently confined to $[7^{-1}e^{-\gamma/2},\,2^{3/2}e^{-\gamma/2}]$ with Kim's lower bound $2e^{-\gamma/2}$ and his heuristic $2\sqrt2\,e^{-\gamma/2}$ for the $\lambda$-analogue; and for $s=1$ it subsumes the quantitative form of the enhanced-divisibility phenomenon, whose uniform analogue is the Mąkowski–Schinzel conjecture $\sigma(\varphi(n))\ge n/2$, a separate uniform-side problem outside the averaged laws required here. (2) The unrestricted mean period. Determine the asymptotic (or other limiting) behavior of the Cesàro mean of Arnold's all-residue average $\hat T(n)=\frac1n\sum_{a=1}^nT(a,n)$ (non-units included) and determine the limiting or distributional behavior of $\hat T(n)/n$ beyond the prime subsequence, to match the settled unit-group case ($u(n)$, Luca–Shparlinski) and fixed-base case ($T_g(x)$, Kurlberg–Pomerance). (3) Gaussian-integer extension. Define the analogue of the unit group, the totient, the periods $T(a,n)$, the diagrams $D(n)$ and the mean statistics for Gaussian-integer moduli $n=u+iv$ by the canonical construction over $\mathbb Z[i]$ (the unit group $(\mathbb Z[i]/n\mathbb Z[i])^\times$, the totient its cardinality, the periods $T(a,n)$ the eventual periods of $a^t\bmod n$ for residue classes $a$ modulo $n$, and the diagram $D(n)$ the sorted multiset of those periods), and determine their asymptotic behavior as $|n|\to\infty$, testing whether the integer-side phenomena documented in the Background persist — in particular the Cesàro-mean laws for the mean period, the enhanced divisor statistics of totient values, and the existence of a limiting distribution for the prime subsequence. Together these three parts constitute the surviving open core of the source's program.

References

1. A. Mąkowski and A. Schinzel, "On the functions φ(n) and σ(n)", Colloquium Mathematicum 13, no. 1 (1964), 95–99. DOI: 10.4064/cm-13-1-95-99. URL: https://doi.org/10.4064/cm-13-1-95-99
2. P. Erdős and C. Pomerance, "On the normal number of prime factors of φ(n)", Rocky Mountain Journal of Mathematics 15, no. 2 (1985), 343–352. DOI: 10.1216/rmj-1985-15-2-343. URL: https://doi.org/10.1216/rmj-1985-15-2-343
3. C. Pomerance, "On the composition of the arithmetic functions σ and φ", Colloquium Mathematicum 58, no. 1 (1989), 11–15. DOI: 10.4064/cm-58-1-11-15. URL: https://doi.org/10.4064/cm-58-1-11-15
4. P. Erdős, C. Pomerance, and E. Schmutz, "Carmichael's lambda function", Acta Arithmetica 58, no. 4 (1991), 363–385. DOI: 10.4064/aa-58-4-363-385. URL: https://doi.org/10.4064/aa-58-4-363-385
5. K. Ford, "An explicit sieve bound and small values of σ(φ(m))", Periodica Mathematica Hungarica 43, no. 1–2 (2001), 15–29. DOI: 10.1023/A:1015273313270. URL: https://doi.org/10.1023/A:1015273313270
6. F. Luca and C. Pomerance, "On some problems of Mąkowski–Schinzel and Erdős concerning the arithmetical functions φ and σ", Colloquium Mathematicum 92, no. 1 (2002), 111–130. DOI: 10.4064/cm92-1-10. URL: https://doi.org/10.4064/cm92-1-10
7. F. Luca and I. E. Shparlinski, "Average multiplicative orders of elements modulo n", Acta Arithmetica 109, no. 4 (2003), 387–411. DOI: 10.4064/aa109-4-7. URL: https://doi.org/10.4064/aa109-4-7
8. J. von zur Gathen, A. Knopfmacher, F. Luca, L. G. Lucht, and I. E. Shparlinski, "Average order in cyclic groups", Journal de Théorie des Nombres de Bordeaux 16, no. 1 (2004), 107–123. DOI: 10.5802/jtnb.436. URL: https://doi.org/10.5802/jtnb.436
9. F. Aicardi, "Empirical estimates of the average orders of orbits period lengths in Euler groups", Comptes Rendus Mathématique 339, no. 1 (2004), 15–20. DOI: 10.1016/j.crma.2004.02.021. URL: https://doi.org/10.1016/j.crma.2004.02.021
10. V. I. Arnold, "Number-theoretical turbulence in Fermat–Euler arithmetics and large Young diagrams geometry statistics", Journal of Mathematical Fluid Mechanics 7, suppl. 1 (2005), S4–S50. DOI: 10.1007/s00021-004-0130-x. URL: https://doi.org/10.1007/s00021-004-0130-x
11. F. Luca, "Some mean values related to average multiplicative orders of elements in finite fields", The Ramanujan Journal 9, no. 1–2 (2005), 33–44. DOI: 10.1007/s11139-005-0823-7. URL: https://doi.org/10.1007/s11139-005-0823-7
12. I. E. Shparlinski, "On some dynamical systems in finite fields and residue rings", Discrete and Continuous Dynamical Systems 17, no. 4 (2007), 901–917. DOI: 10.3934/dcds.2007.17.901; arXiv: math/0607779. URL: https://arxiv.org/abs/math/0607779
13. F. Luca and C. Pomerance, "On the average number of divisors of the Euler function", Publicationes Mathematicae Debrecen 70, no. 1–2 (2007), 125–148. DOI: 10.5486/pmd.2007.3476. URL: https://doi.org/10.5486/pmd.2007.3476 (corrigendum: Publicationes Mathematicae Debrecen 89, no. 1–2 (2016), 257–260, DOI: 10.5486/pmd.2016.7645)
14. J.-M. De Koninck and F. Luca, "On the composition of the Euler function and the sum of divisors function", Colloquium Mathematicum 108, no. 1 (2007), 31–51. DOI: 10.4064/cm108-1-4. URL: https://doi.org/10.4064/cm108-1-4
15. J. Sándor and L. Tóth, "Extremal orders of compositions of certain arithmetical functions", Integers: Electronic Journal of Combinatorial Number Theory 8 (2008), #A34. arXiv: 0802.1106. URL: https://arxiv.org/abs/0802.1106
16. V. I. Arnold, "Periods and Young's diagram of Fermat–Euler's geometrical progressions of residues", Functional Analysis and Other Mathematics 3, no. 1 (2010), 21–38. DOI: 10.1007/s11853-010-0042-7. URL: https://doi.org/10.1007/s11853-010-0042-7
17. Y. Hu and C. Pomerance, "The average order of elements in the multiplicative group of a finite field", Involve, a Journal of Mathematics 5, no. 2 (2012), 229–236. DOI: 10.2140/involve.2012.5.229. URL: https://doi.org/10.2140/involve.2012.5.229
18. P. Kurlberg and C. Pomerance, "On a problem of Arnold: The average multiplicative order of a given integer", Algebra & Number Theory 7, no. 4 (2013), 981–999. DOI: 10.2140/ant.2013.7.981. URL: https://doi.org/10.2140/ant.2013.7.981
19. S. Kim, "The average number of divisors of the Euler function", The Ramanujan Journal 47, no. 1 (2018), 155–183. DOI: 10.1007/s11139-017-9897-2; arXiv: 1605.04933. URL: https://arxiv.org/abs/1605.04933
20. S. Kim, "Some theorems on multiplicative orders modulo p on average", Journal of Number Theory 208 (2020), 180–207. DOI: 10.1016/j.jnt.2019.07.024. URL: https://doi.org/10.1016/j.jnt.2019.07.024