Asymptotic statistics of the maximal cycle lengths in Arnold's complexity graphs, and the homogeneity theory for nonlinear operations

Arnold (2006) defined the complexity of a cyclic binary sequence through the functional graph $G_n$ of the finite-difference operator $\Delta$ on $\mathbb{F}_2^n$: a sequence is the more complex, the longer the cycle of its component, with ties broken by the distance to that cycle. From computations for $n \le 12$ he recorded four regularities of the maximal cycle lengths $m(n)$ — including divisibility $n \mid m(n)$ and a tendency of the quotient $m(n)/n$ toward Mersenne numbers — asked for theorems explaining them, and posed the problem of a general theory unifying the homogeneity of the graph's components with the analogous (already proved) homogeneity for other operations, such as the squaring map on finite groups. Garber (2007) reduced the cycle structure over $\mathbb{F}_p$ to the factorization of $((z+1)^n-1)/z^{p^\alpha}$ over $\mathbb{F}_p$, resolving divisibility and the complete cycle structure, and treated the linear case of the homogeneity question; Lerner (2007-2008) tabulated $G_n$ widely and developed the statistical theory in prime dimensions. The open core that survives: (1) the asymptotic behavior of the quotients $m(n)/n$ and the frequency of exceptional dimensions with non-Mersenne quotient, such as $n = 23$, explicitly posed by Arnold with only heuristic conjectures available; (2) the unified homogeneity theory beyond the difference operator — a general result containing Theorem 3 together with the already-proved homogeneity of the squaring map on finite groups, and, as an extension beyond Arnold's stated $x \mapsto x^2$ case, covering the power maps $x \mapsto x^k$, $k \ge 2$, on finite groups — where the polynomial-factorization technique does not apply.

Background

Arnold's 2006 paper 'Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions' starts from the intuition that the periodic binary sequence $001\,001\,001\,001$ is simpler than $01\,001\,0111\,001$, and presents, in his words, 'a formal mathematical theory that gives an exact meaning' to that statement. The theory is dynamical. Let $x = (x_1, \ldots, x_n)$ be a cyclic sequence of length $n$ (indices understood modulo $n$) over the finite field $\mathbb{F}_p$ of $p$ elements (the source paper's case is binary, $p = 2$). The finite-difference operator $\Delta$ — Arnold's 'Newton operation', since repeated differencing annihilates polynomials — sends $x$ to its sequence of consecutive differences, $(\Delta x)_j = x_{j+1} - x_j$. Because the state space $\mathbb{F}_p^n$ is finite, iteration of $\Delta$ from any start eventually becomes periodic, and the whole dynamics is captured by the functional graph $G_n$ (Arnold calls it a monad): the directed graph on all $p^n$ sequences with an edge $x \to \Delta x$ from each sequence to its image. Each connected component of a functional graph consists of one directed cycle with rooted trees, directed toward the cycle, attached to the cycle's vertices; the preperiod of a vertex is its distance to the cycle of its component.

Arnold's complexity ordering ranks sequences by their position in $G_n$: a sequence is the more complex, the longer the cycle of its component, and among sequences on equal-length cycles, the one farther from the cycle (on higher branches of its tree) is the more complex. In this ordering the reductions modulo 2 of integer-valued polynomials — the 'binary polynomials' — form the component of the zero sequence, the analogue of Newton's characterization of polynomials by vanishing differences. Writing $n = 2^k(2a+1)$, Arnold's Theorem 2 identifies this component as $(O_1 * T_{2^{2^k}})$, and his Theorem 3 shows that every component of $G_n$ has the same shape $(O_m * T_{2^{2^k}})$: a directed cycle of some length $m$ with all attached trees isomorphic to the full tree of the maximal possible size. Here $(O_m * T_h)$ denotes a component made of a directed cycle of length $m$ with a copy of the rooted tree $T_h$ on $h$ vertices attached to each cycle vertex; this uniformity of the attached trees is the homogeneity property at the heart of the theory. Arnold computed $G_n$ for $n \le 12$ and studied the arithmetic logarithm (the binary sequence whose terms are the parities of the discrete logarithms, equivalently the indicator of quadratic non-residues), which his tables ranked among the most complex sequences — connecting the subject to his 2003 survey 'Topology and statistics of formulae of arithmetics' on the statistics of arithmetical formulae.

From these computations Arnold extracted the empirical regularities that constitute the source question of this record: (i) the maximal cycle length $m(n)$ of $G_n$ appears to be divisible by $n$; (ii) the quotient $m(n)/n$ appears to be of Mersenne form $2^{q(n)} - 1$ (a Mersenne number is an integer of the form $2^q - 1$), with $q(n)$ undetermined and no explanation of the form; (iii) ratios of distinct cycle lengths within the same $G_n$ are not always powers of two (e.g. $63/3 = 21$ for $n = 9$), with no characterizing conjecture; and (iv) no general result was known containing Theorem 3's homogeneity together with the analogous homogeneity assertion for the squaring map $x \mapsto x^2$ in an arbitrary finite group — the latter already proved in Arnold's 2003 survey 'Topology and statistics of formulae of arithmetics' (the operation underlying his statistics of arithmetical formulae). In a companion public lecture of 13 May 2006 — cited in the reference list of Garber's follow-up paper — Arnold additionally disclosed that (ii) already fails at $n = 23$: there $m(23) = 2047 = 23 \cdot 89$, so the quotient is $89$, which 'has no relation to any power of two' (although $2047 = 2^{11} - 1$ itself is a Mersenne number). He described the divisibility observation as 'my theorem', and he posed the refined question that survives: how do the quotients $m(n)/n$ behave for large $n$, and how often do exceptional cases like 23 occur — adding that only his students' heuristic hypotheses existed, with 'no real theorems'.

For a prime $p$, the same questions make sense for the difference operator on $\mathbb{F}_p^n$, whose graph orders the complexity of $p$-ary sequences. The key technical tool introduced by Garber (2007) is the decomposition $\mathbb{F}_p^n = A^0 \oplus A^*$ — where $A^0$ is the subspace eventually annihilated by iterates of $\Delta$ (of dimension $p^\alpha$, with $p^\alpha$ the largest power of $p$ dividing $n$) and $A^*$ is the invariant complement on which $\Delta$ is invertible — together with the polynomial $P_n(z) = ((z+1)^n - 1)/z^{p^\alpha}$ over $\mathbb{F}_p$: the cycle structure of $G_n$ reduces completely to the factorization of $P_n$ into irreducible polynomials over $\mathbb{F}_p$, the cycle lengths being multiplicative orders of the residue of $z$ modulo the irreducible factors (the multiplicative order being the smallest $t$ with $z^t \equiv 1$ modulo the factor), combined by least common multiples, with explicit multiplicity formulas. A finite-field extension $\mathbb{F}_{p^d}$ is the unique (up to isomorphism) degree-$d$ extension field of $\mathbb{F}_p$; the multiplicative order of any nonzero element of such a field divides $p^d - 1$, which for $p = 2$ is a Mersenne number — the origin of the observed near-Mersenne statistics of the quotients.

Problem Statement

Two linked problems survive from Arnold's 2006 source question on the graphs $G_n$ of the difference operator $\Delta$ on cyclic sequences of length $n$ over $\mathbb{F}_p$ ($p = 2$ the primary case), understood through Garber's reduction of the cycle structure of $G_n$ to the factorization of $P_n(z) = ((z+1)^n - 1)/z^{p^{\alpha}}$ over $\mathbb{F}_p$, where $p^{\alpha}$ is the largest power of $p$ dividing $n$; throughout, $m(n)$ denotes the length of a longest cycle of $G_n$ lying in the invertible part $A^*$, so that $m(n)$ is defined exactly on the non-degenerate dimensions $n$ with $A^* \ne 0$, i.e. $n$ not a power of $p$ (over $p = 2$, where the only cycle outside $A^*$ is the fixed point $0$, this is Arnold's largest period $> 1$; over other primes $A^*$ may carry only fixed points, and then $m(n) = 1$).

(1) Asymptotic statistics of the maximal cycle lengths — the open residue of Arnold's observation (ii). The divisibility observation (i) and the cycle-length-ratio observation (iii) are resolved by Garber's theorems; in particular $n \mid m(n)$ is a theorem of the factorization theory for $p = 2$, and over general primes $p$ it fails only on the family $n = 2p^{\alpha}$, where $m(n) = p^{\alpha}\operatorname{ord}_p(-2)$ and the quotient $m(n)/n$ need not be an integer (e.g. $m(6) = 3$ over $\mathbb{F}_3$, $m(2) = 5$ over $\mathbb{F}_{11}$). The Mersenne-form observation (ii) is false as a universal claim: already at $n = 23$, $m(23) = 2047 = 23 \cdot 89$ and the quotient $89$ is not of the form $2^q - 1$. The degenerate dimensions $n = p^{\alpha}$ lie outside this range: there $\Delta$ is nilpotent, $A^* = 0$, and $G_n$ is the single component $(O_1 * T_{p^n})$, whose only cycle has length $1$, so no cycle of period $>1$ exists. What remains open, exactly as posed by Arnold in the companion 2006 lecture with only his students' heuristic hypotheses available, is to replace the observed statistics by theorems: determine the asymptotic behavior of the quotients $m(n)/n$ as $n \to \infty$ through the non-degenerate dimensions (over $p = 2$, and over general primes $p$) — limit laws, or two-sided (order-of-magnitude) bounds on the quotients $m(n)/n$ holding asymptotically as $n \to \infty$ (not required to hold pointwise at every non-degenerate $n$) and quantitatively stronger than the trivial estimate $m(n)/n \le p^n/n$ — and determine the frequency of the exceptional dimensions: either the natural density of the set of $n$ for which $m(n)/n$ is not of the Mersenne form $2^q - 1$ in the binary case — its exact value, or matching two-sided bounds on the counting function of that set — or a quantitatively non-trivial upper bound on that counting function, namely one of the form $(1-c)N$ for some constant $c > 0$, or $o(N)$; the exceptional set in question contains the single known element $n = 23$.

(2) Homogeneity beyond the difference operator — the open residue of Arnold's observation (iv). For linear operators over finite fields the graph-construction theory is treated in Garber's work (his 2008 paper studies to which linear operators the factorization-based algorithm applies), settling the linear case of the homogeneity question; that settled linear case is nonetheless an instance the general statement sought below must contain, together with the finite-group and power-map homogeneity. The homogeneity assertion for the squaring map $x \mapsto x^2$ in an arbitrary finite group is itself a proved theorem, not an open model case: Arnold's 2003 survey 'Topology and statistics of formulae of arithmetics' (§6) shows that the connected components of the squaring graphs are attracting cycles homogeneously equipped with products of binary rooted trees, with homogeneity also holding for the symmetric and alternating groups. What Arnold recorded as open, in the remark following the proof of Theorem 3, is that he knew no general result containing Theorem 3 together with this fact of finite-group theory. The open problem is to establish such a general theory of functional graphs (monads) that unifies and extends the homogeneity of components beyond the difference operator: a single general statement, with an explicit hypothesis that is a verifiable condition on the operation itself rather than on its already-formed component structure and is not satisfied by every self-map of a finite set, from which both Theorem 3's difference-operator homogeneity and the homogeneity of the squaring map $x \mapsto x^2$ on an arbitrary finite group follow, and which moreover covers the power maps $x \mapsto x^k$, $k \ge 2$, on arbitrary finite groups. The polynomial-factorization technique of the linear theory does not apply here.

Both halves ask for theorems explaining observed regularities within the same complexity-ordering framework, and the open core comprises both: quantitative asymptotic laws for (1), and a general unifying theory with proofs for (2) — not merely extended tables.

References

1. V. I. Arnold, 'Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions', Functional Analysis and Other Mathematics 1(1), 1-15 (2006). DOI: 10.1007/s11853-007-0001-0. https://doi.org/10.1007/s11853-007-0001-0 — the author's Moscow Mathematical Society talk text of the same work is publicly accessible at https://elementy.ru/lib/430178/430282.
2. V. I. Arnold, 'Calculus of inequalities and complexity of tables' (public lecture of 13 May 2006, elementy.ru transcript, in Russian; companion primary source, cited in the reference list of Garber's 2007 paper). https://elementy.ru/lib/430178/430281
3. V. I. Arnold, 'Topology and statistics of formulae of arithmetics', Russian Mathematical Surveys 58(4), 637-664 (2003). DOI: 10.1070/RM2003v058n04ABEH000641. https://doi.org/10.1070/RM2003v058n04ABEH000641
4. E. Yu. Lerner, 'Two papers on Arnold's complexity of finite sequences' (tables of the graphs $G_n$), arXiv:0704.2947 (2007). https://arxiv.org/abs/0704.2947
5. E. Yu. Lerner, 'Complexity of prime-dimensional sequences over a finite field', arXiv:0710.3451 (2007); published as Functional Analysis and Other Mathematics 2(2-4), 251-255 (2008). DOI: 10.1007/s11853-008-0024-1. https://doi.org/10.1007/s11853-008-0024-1 — https://arxiv.org/abs/0710.3451
6. E. Yu. Lerner, 'Multiplicative function instead of logarithm (an elementary approach)', arXiv:0710.2088 (2007). https://arxiv.org/abs/0710.2088
7. O. N. Karpenkov, 'On examples of difference operators for {0,1}-valued functions on finite sets', Functional Analysis and Other Mathematics 1(2), 175-180 (2007). DOI: 10.1007/s11853-007-0010-Z. https://doi.org/10.1007/s11853-007-0010-Z
8. A. I. Garber, 'Graph complexity of the action of the difference operator in the space $\mathbb{Z}_p^n$', Functional Analysis and Other Mathematics 1(2), 159-173 (2007). DOI: 10.1007/s11853-007-0011-Y. https://doi.org/10.1007/s11853-007-0011-Y
9. A. I. Garber, 'On the graph complexity of the action of a linear operator in the space $\mathbb{Z}_p^n$ over the finite field', Proceedings of the Steklov Institute of Mathematics 263(1), 57-64 (2008). DOI: 10.1134/S0081543808040056. https://doi.org/10.1134/S0081543808040056
10. A. Yu. Rumyantsev, 'Maximally complex periodic sequences and matrix images of linear feedback shift registers', Moscow University Mathematics Bulletin 65(1), 39-43 (2010). DOI: 10.3103/S0027132210010079. https://doi.org/10.3103/S0027132210010079
11. Yu. V. Merekin, 'On the computation of Arnold complexity of length $2^n$ binary words', Asian-European Journal of Mathematics 4(2), 295-300 (2011). DOI: 10.1142/S179355711100023X. https://doi.org/10.1142/S179355711100023X
12. A. S. Parfinenko and A. L. Perezhogin, 'The functional graph of a linear discrete dynamical system with two dominating vertices', Journal of Applied and Industrial Mathematics 12(4), 706-715 (2018). DOI: 10.1134/S1990478918040117. https://doi.org/10.1134/S1990478918040117
13. F. Breuer, 'Periods of Ducci sequences and odd solutions to a Pellian equation', Bulletin of the Australian Mathematical Society 100(2), 201-205 (2019). DOI: 10.1017/S0004972719000212. https://doi.org/10.1017/S0004972719000212
14. A. D. Ramos and A. Toom, 'Trajectories in random monads', Journal of Statistical Physics 142(1), 201-219 (2011). DOI: 10.1007/S10955-010-0087-5. https://doi.org/10.1007/S10955-010-0087-5