I've been running a series of computational experiments on Möbius orthogonality — the question of when the Möbius function μ(n) is "orthogonal" to other arithmetic functions. The results reveal a surprisingly clean dichotomy that extends well beyond what's currently known.
Given a function f: ℕ → {-1, +1}, define the partial sum:
If f has "nothing to do" with the Möbius function, we expect square-root cancellation: S(N) = O(√N). The terms cancel like a random walk. If f is correlated with μ, the sum grows linearly: S(N) = Θ(N).
Sarnak's conjecture (2010) predicts μ is orthogonal to any deterministic dynamical system with zero topological entropy. That's a strong prediction, but it says nothing about positive-entropy systems.
My experiments suggest something broader: the orthogonality depends not on entropy, but on whether f preserves multiplicative structure.
I tested 10 different functions across both categories. Every prediction holds.
| Function | Type | Max |S/√N| | Range |
|---|---|---|---|
| Collatz stopping time parity | 3n+1 dynamics | 1.77 | N ≤ 5×108 |
| Juggler stopping time parity | n3/2 dynamics | 3.34 | N ≤ 5×105 |
| Binary digit sum parity | Digit-based | 0.21 | N ≤ 105 |
| Decimal digit sum parity | Digit-based | 0.46 | N ≤ 105 |
| n mod 7 indicator | Additive | 0.55 | N ≤ 105 |
All bounded. The Collatz result is particularly striking — tested to 100 million integers with max ratio under 2. The binary digit sum case is actually proven (Mauduit-Rivat, 2009).
| Function | Type | |S/√N| at N=105 | Behavior |
|---|---|---|---|
| (-1)ω(n) | # prime factors | 97.9 | Growing ~√N |
| φ(n) mod 4 sign | Euler totient | 19.7 | Growing ~√N |
| Aliquot stopping parity | σ(n) based | 28.2* | Growing ~√N |
*Aliquot tested at N = 50,000.
All growing. The ratio |S/√N| increases monotonically, indicating S(N) = Θ(N).
| Function | Construction | Max |S/√N| |
|---|---|---|
| ω(n) ⊕ Collatz | Multiplicative × Non-mult | 0.23 |
| ω(n) ⊕ digit sum | Multiplicative × Non-mult | 0.86 |
When you XOR a multiplicative function with a non-multiplicative one, the result is orthogonal. The non-multiplicative component kills the correlation. Think of it as destructive interference — one "random" component is enough to wash out systematic structure.
The key is what the generating dynamics do to prime factorization.
The Collatz map n → 3n+1 (when n is odd) destroys the prime factorization of n. If you know vp(n) (the p-adic valuation of n), that tells you essentially nothing about vp(3n+1). The map mixes bits, not factors.
The aliquot map n → σ(n) - n preserves multiplicative structure. σ(n) = Σ d|n d is determined entirely by the prime factorization. So the number of steps in an aliquot sequence is deeply entangled with how n factors.
μ(n) is defined by prime factorization: μ(n) = (-1)k if n has k distinct prime factors. So:
Sarnak's conjecture says μ is disjoint from zero-entropy deterministic systems. The Collatz map has positive entropy (h = log 2 as a map on 2-adic integers), so Sarnak doesn't apply. Yet we observe orthogonality anyway.
Recent work by Downarowicz-Serafin (2019-2020) constructs positive-entropy subshifts uncorrelated to μ, and Drmota-Mauduit-Rivat-Spiegelhofer (2022) prove orthogonality for maximal-entropy b-multiplicative sequences. Our observation fits into this picture but comes from a different angle: the dynamics being non-multiplicative, rather than having specific entropy properties.
The suggestion is that entropy is a red herring. What matters is multiplicativity.
Perhaps the most interesting finding is the aliquot result. I originally expected aliquot sequences to show weaker orthogonality than Collatz (since aliquot has more information loss per step). Instead, they show no orthogonality at all.
This falsified my initial hypothesis (more info loss → weaker orthogonality) and pointed to the correct principle: it's not about how much information is lost, but what kind. Aliquot preserves multiplicative information. Collatz doesn't. That's the whole story.
1. Can this be proved? The KBS (Kátai-Bourgain-Sarnak) criterion provides a path: if f(pn) and f(qn) are decorrelated for distinct primes p, q, then Σ μ(n)f(n) = o(N). We verified this numerically for Collatz (correlations < 0.05 for all tested prime pairs).
2. Is there a universal constant? Both Collatz and juggler show max |S/√N| ≈ 2. Is this a coincidence, or is there a universal bound for "non-multiplicative" functions?
3. Where exactly is the boundary? What about functions that are "partially multiplicative" — preserving some factorization structure but not all?
4. Does this connect to the Chowla conjecture? Chowla predicts specific auto-correlations of μ vanish. Our dichotomy is about cross-correlations of μ with other functions.
All scripts are in Python. The Collatz-Möbius computation uses a sieve for μ(n) and cached stopping times:
# Key insight: sieve μ(n) for all n ≤ N in O(N log log N)
# Then iterate: S += μ(n) * (-1)^{stopping_time(n)}
# Check if S(N)/√N stays boundedThe most expensive computation (N = 5×108, about 18 minutes on an 8-core VPS) confirms S(N)/√N peaks at 1.77 at N=20M and doesn't grow through half a billion integers. The data strongly suggests S(N) = O(√N).