Finite-Size Equidistribution of Ω ⁢ ( n ) Modulo m : Theory and Computation

Consider the number 12. Since $12=2^2\times 3$, the function counts $2+1=3$ prime factors with multiplicity: $\mathrm{\Omega }(12)=3$. Similarly, $\mathrm{\Omega }(100)=\mathrm{\Omega }(2^2\times 5^2)=2+2=4$, while for any prime $p$, we have $\mathrm{\Omega }(p)=1$. This function $\mathrm{\Omega }(n)$ appears throughout number theory—it counts prime factors with repetition.

What happens when we look at $\mathrm{\Omega }(n)$ modulo 3? Anyone computing these values notices something curious. For small $n$, the residue classes don’t appear with equal frequency. There’s a visible pattern: one class seems slightly favored over the others. Is this a real bias, or just a finite-size artifact?

After computing $\mathrm{\Omega }(n)mod3$ for all $n\le {10}^8$, we found that the apparent bias is real—but it’s not mysterious. The deviations from uniformity follow a precise law predicted by classical analytic number theory. The differences shrink, but they shrink slowly, like ${(\log x)}^{-3/2}$. This slow decay creates persistent structure at computational scales.

Our initial observation suggested a surprising asymmetry. Computation to ${10}^8$ shows these deviations match classical finite-size predictions. The key insight: residue classes are equidistributed asymptotically, but the approach to uniformity follows a power law in $\log x$, not $x$ itself.

At $x={10}^8$, the maximum deviation from $1/3$ is approximately 1.5%. This matches the prediction $|S(x)|/x\sim C_3{(\log x)}^{-3/2}$ with $C_3\approx 1.708$, where $S(x)={\sum }_{n\le x}{\omega }^{\mathrm{\Omega }(n)}$ is the first Fourier coefficient. So the pattern is real, just not anomalous—it’s exactly what classical theory predicts.

Computational number theory often encounters finite-size effects that look like biases. Theory and high-precision computation together distinguish asymptotic behavior from slow convergence. Our work provides a template for this kind of analysis.

To our knowledge, these are the first regression-quality estimates of the constants $C_m$ for several moduli, with uncertainty quantification from dyadic-shell bootstraps, and the first short-interval threshold map for the decay law.

The residue class deviations decay with a universal exponent determined by the modulus:

The maximum deviation from uniform distribution follows ${\max }_r|A_r(x)/x-1/m|\approx \frac{2C_m}{m}{(\log x)}^{\cos (2\pi /m)-1}$. This single formula captures the finite-size structure across all moduli.

The function $\mathrm{\Omega }(n)$ counts prime factors with multiplicity [10]. Examples: $\mathrm{\Omega }(8)=3$ from $8=2^3$, and $\mathrm{\Omega }(6)=2$ from $6=2\times 3$. This differs from $\omega (n)$, which counts distinct prime factors: $\omega (8)=1$ but $\omega (6)=2$.

This property implies that $\mathrm{\Omega }(n)modm$ behaves additively under multiplication [1]. When we multiply two numbers, their $\mathrm{\Omega }$ values add. This additive structure drives the Fourier analysis we’ll use later.

On average, $\mathrm{\Omega }(n)$ grows logarithmically. Most numbers near $x$ have roughly $\log \log x$ prime factors. This slow growth is why the Erdős-Kac theorem applies.

This raises a natural question: if $\mathrm{\Omega }(n)$ is normally distributed, what about its residue classes modulo $m$? Are they uniform? The Erdős-Kac theorem doesn’t directly answer this—it tells us about the shape of the distribution, not its behavior modulo fixed integers.

To answer the modular question, we use discrete Fourier analysis of the additive function $\mathrm{\Omega }(n)$. The key insight is that discrete Fourier methods allow us to reconstruct the entire residue class distribution from a single complex-valued sum.

For a fixed modulus $m$, consider the primitive $m$-th root of unity $z=e^{2\pi i/m}$. This complex number satisfies $z^m=1$, meaning powers of $z$ cycle through $m$ distinct phases. When we form the character sum

we obtain a complex number that encodes how $\mathrm{\Omega }(n)$ distributes across residue classes modulo $m$. If the residues were perfectly uniformly distributed, this sum would vanish. Instead, it decays slowly—and the rate of decay tells us precisely how fast the residues approach uniformity.

Why study this particular character? Because $z=e^{2\pi i/m}$ is the fundamental character that detects $m$-fold symmetry. The sum $S(x)$ measures the first Fourier coefficient of the residue class distribution. Through discrete Fourier inversion (which we’ll demonstrate in Section 4.2.1), this single coefficient completely determines all $m$ residue class proportions. Computing one complex number gives us everything.

The following theorem characterizes the asymptotic behavior of $S(x)$, from which the residue class distribution follows as a corollary.

What we’re computing here is the first Fourier coefficient of the residue class distribution. The character $z=e^{2\pi i/m}$ detects the $m$-fold symmetry. If the distribution were perfectly uniform, this sum would vanish. Instead, it decays like ${(\log x)}^{\mathrm{Re}(z)-1}$.

For $m=3$, we have $\mathrm{Re}(e^{2\pi i/3})=\cos (2\pi /3)=-1/2$, so $\mathrm{Re}(z)-1=-3/2$. That’s where the ${(\log x)}^{-3/2}$ decay comes from.

The proof shows that residue classes approach uniformity with a logarithmic convergence rate, not polynomial. The exponent $\cos (2\pi /m)-1$ is always negative (except $m=1$, which is trivial), so the decay is real. But for small $m$, the decay is slow—at $m=3$, we get $-3/2$, which means very slow convergence.

Classical methods developed by Selberg, Delange, and Halász imply equidistribution with a modulus-dependent decay exponent for the Fourier coefficient $z^{\mathrm{\Omega }(n)}$. Our contribution is an explicit, computationally verified finite-size law for multiple moduli, including regression-based estimates of the Euler-product constants and robust validation across dyadic shells.

This connects to existing work through several pathways:

To investigate the distribution of $\mathrm{\Omega }(n)$ modulo $m$, we implemented an efficient algorithm using a smallest prime factor (SPF) sieve, following modern computational number theory practices [2]. The SPF sieve factors each $n$ in $O(\log n)$ time after one $O(N\log \log N)$ preprocessing step.

Algorithm: SPF-based Computation
1. Precompute SPF[i] for i in [2, N] using sieve
2. For each n in range [2, N]:
    a. Factor n using SPF table
    b. Sum all exponents to get Omega(n)
    c. Compute Omega(n) mod m
    d. Update counters and character sums

The SPF-based approach achieves $O(N\log \log N)$ for the sieve and $O(\log n)$ per factorization. For $N={10}^8$, this runs in under an hour on a standard desktop.

We computed the distribution for values up to $N={10}^8$. Table 2 shows the progression.

Notice something interesting: at $x={10}^8$, the maximum deviation from uniformity is approximately 1.5%. This is consistent with the theoretical prediction $|S(x)|/x\approx C_3{(\log x)}^{-3/2}\approx 1.708\times {18.42}^{-1.5}\approx 0.022$. The pattern is visible but shrinking.

To quantify the finite-size deviations, we define the constants

We estimate these complex constants through dyadic shell regression. Importantly, these constants are greater than 1 for small $m$, with $C_3\approx 1.708$.

The value $C_3>1$ has important implications: the deviations decay more slowly than naive expectations might suggest. The Gamma function and Euler product combine to amplify the coefficient, making the bias more persistent.

Let ${\zeta }_3=e^{2\pi i/3}$ denote the primitive cube root of unity, and define

where the last equality follows from ${\zeta }_3^2=\overline{{\zeta }_3}$ for ${\zeta }_3=e^{2\pi i/3}$. If $A_r(x)=|\{n\le x:\mathrm{\Omega }(n)\equiv r(mod3)\}|$, then

All deviations from uniformity are captured by the single complex-valued sum $S(x)$. You don’t need to track three separate residue classes—just compute one Fourier coefficient, and you can reconstruct everything.

To estimate the constant $C_3$ in the asymptotic $|S(x)|/x\sim C_3{(\log x)}^{-3/2}$, we performed log-log regression on dyadic intervals $[2^k,2^{k+1}]$ for $k=10,11,\mathrm{\dots },26$. Dyadic shells provide geometrically spaced samples that avoid overweighting large $x$ values.

The excellent fit ($R^2>0.99$) confirms the theoretical prediction. The constant $C_3=1.708\pm 0.025$ represents the first explicit estimation of this constant, matching the theoretical value from the Euler product. When we computed the truncated Euler product directly, we got $C_3^{\text{(trunc)}}\approx 1.708$—exact agreement with regression.

We extended our analysis to $m=4,5,6$, confirming the universal decay law with exponent $\cos (2\pi /m)-1$. The pattern extends across moduli $m=4,5,6$ with distinct exponents as shown in Table 4.

We also analyzed $\omega (n)$ modulo 3, which counts distinct prime factors. Both functions share the same Dirichlet series singularity structure, yielding identical decay exponents.

Both functions exhibit the same decay exponent $\cos (2\pi /3)-1=-3/2$ due to having the same singularity structure in their Dirichlet series. However, the constants differ because $\omega (n)$ counts distinct primes while $\mathrm{\Omega }(n)$ counts with multiplicity, yielding different Euler products $G_z^{(\omega )}(1)\ne G_z^{(\mathrm{\Omega })}(1)$.

The finite-size distribution of $\mathrm{\Omega }(n)$ modulo $m$ admits a natural information-theoretic interpretation through its connection to entropy and coding theory. The residue class carries information quantified by arithmetic entropy.

The ”information content” of the arithmetic distribution approaches its theoretical maximum at the rate determined by our decay law. The residue classes become increasingly random as $x$ grows, but the approach to randomness is logarithmic.

The computational complexity of detecting finite-size deviations connects to questions in algorithmic number theory. The detection complexity depends on the deviation threshold.

This establishes a connection between arithmetic structure and computational complexity, where the decay rate determines the ”hardness” of detecting deviations from uniformity.

The Dirichlet series ${\sum }_{n=1}^{\mathrm{\infty }}{z}^{\mathrm{\Omega }(n)}{n}^{-s}$ belongs to a broader class of L-functions with arithmetic significance.

This connection suggests potential applications to the Langlands program, where arithmetic functions modulo $m$ could provide new examples of L-functions with controlled analytic behavior.

The uniform measure (equal weight on all $n\le x$) exhibits finite-size deviations. A natural question: can we control these deviations by introducing non-uniform weights? We study Dirichlet-weighted averages $n^{-(1+\beta )}$ where $\beta >0$ provides a tunable parameter that breaks the residue symmetry explicitly. This weighted ensemble framework connects our results to statistical mechanics models where $\beta$ plays a temperature-like role.

We can study controlled deviations from uniform distribution by introducing a weighting parameter $\beta >0$ in the Dirichlet series framework:

For $\beta >0$, the mean character value ${𝔼}_{\beta }[z^{\mathrm{\Omega }}]$ is non-zero, representing controlled symmetry breaking in the residue distribution. As $\beta \downarrow 0$, this approaches the uniform distribution limit.

This framework provides a mathematical mechanism for controlled symmetry breaking via weighted averages, with potential applications to understanding transitions between uniform and non-uniform distributions in arithmetic settings.

To understand the mathematical origin of finite-size deviations, we analyze the contribution structure through the Euler product representation.

The finite-size law can be understood through the density function:

This theorem establishes that all residue classes approach their asymptotic density $1/m$ at the same universal rate, with the maximum deviation achieved by a specific residue class determined by the phase of the dominant Fourier coefficient.

The complete additivity of $\mathrm{\Omega }$ induces a multiplicative structure in the character sums that explains the universal decay rate.

This multiplicative independence property ensures that the finite-size law is robust across different arithmetic progressions and prime factor restrictions.

Several questions remain: