Arnold's discrete conjecture on the Kolmogorov stochasticity parameter of residues of geometric progressions modulo N

In a 2009 empirical study, V. I. Arnold computed the Kolmogorov stochasticity parameter (the Kolmogorov-Smirnov statistic of a sample against a theoretical counting function) for residues of geometric progressions modulo 100, such as the powers of 2 and 3, and found that its empirical distribution over many starting points resembles Kolmogorov's universal limit distribution for random samples, while arithmetic progressions of residues are grossly non-random in the same sense. He conjectured that as the modulus N tends to infinity, with sample lengths equal to a fixed fraction of the orbit period of the map x -> ax on the residue ring Z_N, the distribution of the parameter over the N starting points converges to Kolmogorov's distribution. The continuous analogues are now theorems: Aistleitner (2014) proved the sharp almost-all-base law of the iterated logarithm (the optimal almost-sure bound on the fluctuations) for the discrepancy of fractional parts of geometric progressions, and Aistleitner (2015) proved convergence to Kolmogorov's distribution over starting points for almost every real base, while Fukuyama's results show non-universal behavior for integer bases. The original discrete mod-N conjecture - precisely the setting of Arnold's experiments - remains open, with only uniform-distribution-level partial results (Chang 2007; Shparlinski 2007), and the only expert assessment (Aistleitner 2015) calls it probably extremely difficult. The problem asks for a rigorous proof, refutation, or identification of the true limiting law for the discrete conjecture; a secondary item from the same source, the apparent Kolmogorov-randomness of Fibonacci residues, is recorded as an additional open observation.

Background

Kolmogorov's limit theorem and the stochasticity parameter. Let $x_1,\dots,x_n$ be independent samples of a random variable $x$ whose distribution is continuous, let $C_n(X)$ count how many samples satisfy $x_m\le X$, and let $C_0(X)=nP(x\le X)$ be its expected value. Kolmogorov proved in 1933 that the normalized maximal deviation

$$\lambda_n=\frac{\sup_X|C_n(X)-C_0(X)|}{\sqrt n}$$

converges in distribution, as $n\to\infty$, to a universal law $\Phi$ - Kolmogorov's distribution - which does not depend on the distribution of $x$. Explicitly, $\Phi(x)=1-2\sum_{k\ge1}(-1)^{k-1}e^{-2k^{2}x^{2}}$, and the mean of $\Phi$ is $\sqrt{\pi/2}\ln 2\approx 0.87$. This is the foundation of the Kolmogorov-Smirnov statistical test of whether a sample is consistent with a proposed distribution. Arnold called $\lambda_n$ the stochasticity parameter and proposed it as a quantitative degree of randomness for finite deterministic sequences.

Arnold's program and the source paper. In his final years Arnold applied $\lambda_n$ to deterministic sequences of number-theoretic origin: permutations, continued-fraction data, quadratic residues, and residues of arithmetic and geometric progressions. Arnold's 2009 paper (Functional Analysis and Other Mathematics) is the empirical study for geometric progressions. For the residues of $\{s\cdot 3^k\bmod 100\}$ and $\{2^j+t\bmod 100\}$ with $n=50$ terms each, the values of $\lambda_n$ over many starting points $s$ and shifts $t$ were computed, and their empirical distribution resembled $\Phi$ (mean about $0.863$, versus the theoretical mean $\sqrt{\pi/2}\ln 2\approx 0.869$); by contrast the arithmetic progression $\{37k\bmod 100\}$ gave $\lambda\approx 0.277$, with a Kolmogorov probability reported by the paper as $\Phi(0.277)\approx 4\times 10^{-4}$, that is, gross non-randomness, and the first 50 Fibonacci numbers reduced mod 100 gave $\lambda\approx 0.696$ with $\Phi(0.696)\approx 0.29$, suggesting a moderate degree of randomness. Arnold acknowledged the method's flaws - Kolmogorov's theorem assumes a continuous distribution while residues take only finitely many values, and the comparison line fitted in the experiments used the observed extremes - writing that the approach was, in his words, more a method of natural sciences than a mathematical theorem, and conjectured that a rigorous theorem should nevertheless hold. The formal conjectures are stated in the companion paper (Transactions of the Moscow Mathematical Society, 2009): (i) the discrete conjecture - as $N\to\infty$, the distribution of the values of the Kolmogorov parameter for the mod-$N$ remainders of the $N$ geometric progressions corresponding to the $N$ starting points $A$ of $\mathbb{Z}_N$ tends to $\Phi$, the lengths being $n\approx\theta T(N,a)$ with $\theta\in(0,1)$ separated from 0 and 1 and $T(N,a)$ the period of the sequence of remainders; (ii) for almost all real bases $a>1$ in the sense of Lebesgue measure, $\lambda_n$ of the fractional parts of $a^xA$ does not tend to 0 as $n\to\infty$; (iii) for almost all $a>1$, the distribution of $\lambda_n(A)$ over starting points $A$ uniformly distributed on $[0,N]$ tends to $\Phi$.

The discrepancy-theory connection. When the comparison law $C_0$ is the uniform distribution on a finite interval, $\lambda_n$ equals $\sqrt n$ times the star-discrepancy $D_n^\ast=\sup_X|C_n(X)/n-X|$, the classical number-theoretic measure of the quality of uniform distribution (a sequence of fractional parts is uniformly distributed modulo 1 if and only if $D_n^\ast\to 0$; the fractional parts $\{kx\}$ are uniformly distributed for every irrational $k$). This links Arnold's question to metric discrepancy theory. A theorem of Koksma (1935) asserts that $\{a^x\}$ is uniformly distributed mod 1 for almost all real $a>1$; yet no explicit such $a$ is known, and for specific bases such as $a=3/2$ even uniform distribution is open. For genuinely random samples, the law of the iterated logarithm (the sharp almost-sure bound on the magnitude of the fluctuations of sums of independent random variables) for the Kolmogorov statistic yields $\limsup\lambda_n/\sqrt{\log\log n}=1/\sqrt2$ almost surely.

What later work settled. Aistleitner (Israel Journal of Mathematics, 2014) proved that for every $\xi>0$ and every increasing integer sequence $(s_n)$, the discrepancy of the fractional parts of $\xi x^{s_n}$ obeys exactly this law of the iterated logarithm for almost all $x>1$; in particular $\lambda_n\not\to 0$ for almost every base, settling conjecture (ii) in sharp form. Aistleitner (Nonlinearity, 2015) then settled the remaining continuous questions: Theorem 1 proves conjecture (iii) for every $a$ such that $a^x$ is irrational for all integers $x\ge 1$ (a full-measure set containing all transcendental $a$), while for $a$ with some rational power the limit law exists but differs from $\Phi$; this is consistent with Fukuyama's earlier theorem that the law-of-the-iterated-logarithm constant for the discrepancy of $\{\theta^nx\}$ depends sensitively on $\theta$ (for example $\sqrt{84}/9$ for $\theta=2$, versus $1/\sqrt2$ in the random case), refined in 2021 to perturbed geometric progressions $\{\theta^kx+\gamma_k\}$. The 2015 paper also resolves the arithmetic-progression companion question: for almost every real step $k$, the stochasticity parameter of the fractional parts $\{kx\}$ tends to 0 (Arnold had proved the rational-step case in Russian Mathematical Surveys 2008). Finally it explains, via the classical functional limit theorem for empirical processes (whose limit is the Brownian bridge, a Brownian motion conditioned to return to 0), that the correct limit object for finite-valued variables is the maximum of a Brownian bridge sampled at $N$ equally spaced points, which is close to $\Phi$ when $N$ is large - the rigorous version of Arnold's unlawful application of $\Phi$ to discrete data.

What remains open. The discrete conjecture (i) - precisely the setting of Arnold's experiments with integer bases and moduli - has neither proof nor disproof. The partial results in the discrete direction (Chang 2007; Shparlinski 2007, for the analogous systems in finite fields) establish uniform-distribution-type estimates, that is, deviations $o(n)$ from the uniform counting function, but conjecture (i) concerns the next-order $\sqrt n$-scale fluctuations of the counting functions along orbits, which is far finer. Moreover, the continuous case already shows that the limit law need not be exactly $\Phi$ for integer bases, so the discrete limit law may also depend on the arithmetic of $a$ and $N$. Aistleitner's 2015 assessment is that the discrete conjecture is probably extremely difficult.

Problem Statement

Prove or disprove Arnold's discrete conjecture on the Kolmogorov stochasticity parameter of geometric progressions of residues.

Fix a modulus $N\ge 2$ and an integer ratio (base) $a$ with $1<a<N$, and consider the discrete dynamical system $x\mapsto ax$ on the residue ring $\mathbb{Z}_N=\mathbb{Z}/N\mathbb{Z}$. For a starting point $A\in\mathbb{Z}_N$, let $T=T(N,a)$ denote the period of the sequence of residues $a^xA\bmod N$ (the generic orbit period; starting points sharing arithmetic factors with $N$ may lie on shorter or eventually absorbed orbits). Fix $\theta\in(0,1)$ bounded away from 0 and 1, set $n=\lfloor\theta T\rfloor$, and for each starting point $A$ compute the Kolmogorov stochasticity parameter

$$\lambda_n(A)=\frac{\sup_X|C_n(X)-C_0(X)|}{\sqrt n}$$

of the $n$ residues of the orbit of $A$, where $C_n$ is the empirical counting function of the residues and $C_0(X)=nX/N$ is the theoretical counting function of the uniform distribution on $[0,N]$.

Arnold's conjecture: as $N\to\infty$, the distribution of the values $\lambda_n(A)$, when the starting point $A$ is taken uniformly over the $N$ points of $\mathbb{Z}_N$, converges to Kolmogorov's universal distribution $\Phi$ (the limit law of $\lambda_n$ for independent samples from any continuous distribution, defined in the Background); that is, for every continuity point $X$ of $\Phi$,

$$\lim_{N\to\infty}\frac{\#\{A\in\mathbb{Z}_N:\lambda_n(A)\le X\}}{N}=\Phi(X).$$

The problem includes making precise the orbit and period conventions under which the statement is asserted - in particular how starting points whose orbits have period shorter than $T(N,a)$, including those absorbed into shorter cycles, are treated, and for which bases $a$ (a fixed base such as 2 or 3, or bases ranging with $N$) the statement is claimed - together with the faithfulness of this formalization to Arnold's conjecture; the research target is to prove convergence to $\Phi$ under those conventions, or to disprove the conjecture by exhibiting a rigorous counterexample family, or to prove convergence to an explicit different limiting law and identify how it depends on $a$ and $\theta$.

Secondary open observation from the same source, not required for the primary completion boundary: the source paper also found that the first 50 Fibonacci numbers reduced mod 100 have Kolmogorov stochasticity parameter approximately 0.696 with $\Phi\approx 0.29$, suggesting that Fibonacci residues are 'satisfactorily' random in the Kolmogorov sense for long sequences. No rigorous limit law for the stochasticity parameter of Fibonacci residues modulo $N$ (over blocks comparable to the Pisano period, the period of the Fibonacci sequence modulo $N$) is known; resolving or refuting this companion observation is a natural secondary deliverable of a solution; in Arnold's published accounts the item appears as an empirical observation rather than a labeled formal conjecture.

References

1. A. N. Kolmogorov, 'Sulla determinazione empirica di una legge di distribuzione', Giornale dell'Istituto Italiano degli Attuari 4 (1933) 83-91; English translation in S. Kotz and N. L. Johnson (eds.), Breakthroughs in Statistics, Vol. II: Methodology and Distribution, Springer, New York, 1992, DOI 10.1007/978-1-4612-4380-9, https://doi.org/10.1007/978-1-4612-4380-9
2. Vladimir I. Arnold, 'Empirical study of stochasticity for deterministic chaotical dynamics of geometric progressions of residues', Functional Analysis and Other Mathematics 2 (2009) 139-149, DOI 10.1007/s11853-009-0034-7, https://doi.org/10.1007/s11853-009-0034-7
3. V. I. Arnold, 'Stochastic and deterministic characteristics of orbits in chaotically looking dynamical systems', Transactions of the Moscow Mathematical Society 70 (2009) 31-69, DOI 10.1090/S0077-1554-09-00180-0, https://doi.org/10.1090/S0077-1554-09-00180-0
4. V. I. Arnol'd, 'To what extent are arithmetic progressions of fractional parts stochastic?', Russian Mathematical Surveys 63 (2008) 205-220, DOI 10.1070/RM2008v063n02ABEH004514, https://doi.org/10.1070/RM2008v063n02ABEH004514
5. J. F. Koksma, 'Ein mengentheoretischer Satz über die Gleichverteilung modulo Eins', Compositio Mathematica 2 (1935) 250-258, https://www.numdam.org/item/CM_1935__2__250_0/
6. Christoph Aistleitner, 'Quantitative uniform distribution results for geometric progressions', Israel Journal of Mathematics 204 (2014) 155-197, arXiv:1210.4215, DOI 10.1007/s11856-014-1080-5, https://arxiv.org/abs/1210.4215
7. Christoph Aistleitner, 'On some questions of V.I. Arnold on the stochasticity of geometric and arithmetic progressions', Nonlinearity 28 (2015) 3663-3675, arXiv:1406.5785, DOI 10.1088/0951-7715/28/10/3663, https://arxiv.org/abs/1406.5785
8. Mei-Chu Chang, 'On a problem of Arnold on uniform distribution', Journal of Functional Analysis 242 (2007) 272-280, DOI 10.1016/j.jfa.2006.06.009, https://doi.org/10.1016/j.jfa.2006.06.009
9. Igor E. Shparlinski, 'On some dynamical systems in finite fields and residue rings', Discrete and Continuous Dynamical Systems 17 (2007) 901-917, arXiv:math/0607779, DOI 10.3934/dcds.2007.17.901, https://arxiv.org/abs/math/0607779
10. Katusi Fukuyama, 'The law of the iterated logarithm for discrepancies of {theta^n x}', Acta Mathematica Hungarica 118 (2008) 155-170, DOI 10.1007/s10474-007-6201-8, https://doi.org/10.1007/s10474-007-6201-8
11. Katusi Fukuyama, 'The law of the iterated logarithm for the discrepancy of perturbed geometric progressions', Acta Mathematica Hungarica 164 (2021) 157-177, DOI 10.1007/s10474-020-01120-8, https://doi.org/10.1007/s10474-020-01120-8
12. Mikhail R. Gabdullin, 'The stochasticity parameter of quadratic residues', International Mathematics Research Notices (2023) 18108-18141, arXiv:2010.04982, DOI 10.1093/imrn/rnac338, https://arxiv.org/abs/2010.04982
13. Pär Kurlberg and Carl Pomerance, 'On a problem of Arnold: the average multiplicative order of a given integer', Algebra & Number Theory 7 (2013) 981-999, arXiv:1108.5209, DOI 10.2140/ant.2013.7.981, https://arxiv.org/abs/1108.5209
14. Clarissa Hoffman, Jingheng Cheng, Daoyun Ji and Yuri Dabaghian, 'Pattern dynamics and stochasticity of the brain rhythms', PNAS 120 (2023) e2218245120, arXiv:2205.03503, DOI 10.1073/pnas.2218245120, https://arxiv.org/abs/2205.03503
15. N. Galikyan, A. A. Kocharyan and V. G. Gurzadyan, 'Kolmogorov analysis of pulsar TOA' (2026), arXiv:2602.17188, https://arxiv.org/abs/2602.17188