Exact Mean Rho-Length Formula for Power Map Dynamics via d-Adic Valuation

Abstract

We study the functional graphs of power maps f_d(x) = x^d mod p over finite fields F_p for d in {2,3,5,7} and all primes p up to 10^5. For each prime, we compute the complete cycle structure: cycle lengths, rho-lengths (tail lengths before entering a cycle), number of connected components, and the fraction of cyclic versus tail points. We prove that the mean rho-length is controlled by the d-adic valuation v_d(p-1): when d divides p-1, the trees in the functional graph are complete d-ary trees of height h = v_d(p-1), and the mean rho-length over tail points is exactly (h * d^(h+1) - (h+1) * d^h + 1) / ((d-1)(d^h - 1)), which is asymptotically h - 1/(d-1). Primes with anomalously large rho-lengths have p-1 = d^k * m for large k and small m; for d=2, the extremal prime is p = 65537 = 2^16 + 1 (a Fermat prime) with mean rho = 15. We verify computationally that this formula matches the measured mean rho-length exactly (to machine precision) across all 18,355 non-permutation (d,p) pairs surveyed.

Cite This Work