https://arxiv.org/pdf/1909.03562

COLLATZ ORBITS ATTAIN ALMOST BOUNDED VALUES 11 Remark 1.13. One could view the Syracuse random variables Syrac(Z/3nZ) as pro- jections Syrac(Z/3nZ) ≡ Syrac(Z3) mod 3n (1.25) of a single random variable Syrac(Z3) taking values in the 3-adics Z3 := lim ←−n Z/3nZ (equipped with the usual metric d(x, y) := 3−ν3(x−y)), which can for instance be defined as Syrac(Z3) ≡ ∞X j=0 3j 2−a[1,j+1] = 2−a1 + 312−a[1,2] + 322−a[1,3] + . . . where a1, a2, . . . are iid copies of Geom(2); note that this series converges in Z3, and the equivalence of distribution (1.25)follows from (1.22), (1.5) after reversing4 the order of the tuple (a1, . . . , an) (cf. (1.24)). One can view the distribution of Syrac(Z3) as the unique stationary measure for the discrete Markov process5 on Z3 that maps each x ∈ Z3 to 3x+1 2a for each a ∈ N + 1 with transition probability 2−a (this fact is implicit in the proof of Lemma 1.12). However, we will not explicitly adopt the 3-adic perspective in this paper, preferring to work instead with the finite projections Syrac(Z/3nZ) of Syrac(Z3). While the Syracuse random variables Syrac(Z/3nZ) fail to be uniformly distributed on Z/3nZ, we can show that they do approach uniform distribution n → ∞ at fine scales (as measured in a 3-adic sense), and this turns out to be the key ingredient needed to establish Proposition 1.11. More precisely, we will show Proposition 1.14 (Fine scale mixing of n-Syracuse offsets). For all 1 ≤ m ≤ n one has Oscm,n (P(Syrac(Z/3nZ) = Y mod 3n))Y ∈Z/3nZ ≪A m−A (1.26) for any fixed A > 0, where the oscillation Oscm,n(cY )Y ∈Z/3nZ of a tuple of real numbers cY ∈ R indexed by Z/3nZ at 3-adic scale 3−m is defined by Oscm,n(cY )Y ∈Z/3nZ := X Y ∈Z/3nZ cY − 3m−n X Y ′∈Z/3nZ:Y ′=Y mod 3m cY ′ . (1.27) Informally, the above proposition asserts that the Syracuse random variable Syrac(Z/3nZ) is approximately uniformly distributed in “fine-scale” or “high-frequency” cosets Y + 4As an alternative to reversing the order of the tuple (a1, . . . , an), one could instead index time by the negative integers −1, −2, −3, . . . rather than the positive integers 1, 2, 3, . . . , viewing Syrac(Z3) as the outcome of an “ancient” Syracuse iteration that extends to arbitrarily large negative times (and whose initial condition is irrelevant). This perspective towards the Syracuse variables is arguably more natural, and could be adopted elsewhere in the paper; however, we have chosen (mostly for aesthetic reasons) to index time by positive integers rather than negative ones, which necessitates some reversal of the labeling at some junctures. 5This Markov process may possibly be related to the 3-adic Markov process for the inverse Collatz map studied in [24]. See also a recent investigation of 3-adic irregularities of the Collatz iteration in [23].

12 TERENCE TAO 3mZ/3nZ, after conditioning to the event Syrac(Z/3nZ) = Y mod 3m. Indeed, one could write the left-hand side of (1.26) if desired as dTV(Syrac(Z/3nZ), Syrac(Z/3nZ) + Unif (3mZ/3nZ)) where the random variables Syrac(Z/3nZ), Unif (3mZ/3nZ) are understood to be inde- pendent. In Section 5, we show how Proposition 1.11 (and hence Theorem 1.3) follows from Proposition 1.14 and Proposition 1.9. Remark 1.15. One can heuristically justify this mixing property as follows. The geo- metric random variable Geom(2) can be computed to have a Shannon entropy of log 4; thus, by asymptotic equipartition, the random variable Geom(2)n is expected to behave like a uniform distribution on 4n+o(n) separate tuples in (N + 1)n. On the other hand, the range Z/3nZ of the map⃗a 7 → F n(⃗a) mod 3 n only has cardinality 3n. While this map does have substantial irregularities at coarse 3-adic scales (for instance, it always avoids the multiples of 3), it is not expected to exhibit any such irregularity at fine scales, and so if one models this map by a random map from 4n+o(n) elements to Z/3nZ one is led to the estimate (1.26) (in fact this argument predicts a stronger bound of exp(−cm) for some c > 0, which we do not attempt to establish here). Remark 1.16. In order to upgrade logarithmic density to natural density in our results, it seems necessary to strengthen Proposition 1.14 by establishing a suitable fine scale mixing property of the entire random affine map AffGeom(2)n , as opposed to just the offset Fn(Geom(2)n). This looks plausibly attainable from the methods in this paper, but we do not pursue this question here. To prove Proposition 1.14, we use a partial convolution structure present in the n- Syracuse offset map, together with Plancherel’s theorem, to reduce matters to estab- lishing a superpolynomial decay bound for the characteristic function (or Fourier coef- ficients) of a Syracuse random variable Syrac(Z/3nZ). More precisely, in Section 6 we derive Proposition 1.14 from Proposition 1.17 (Decay of characteristic function). Let n ≥ 1, and let ξ ∈ Z/3nZ be not divisible by 3. Then Ee−2πiξSyrac(Z/3nZ)/3n ≪A n−A (1.28) for any fixed A > 0. A key point here is that the implied constant in (1.28) is uniform in the parameters n ≥ 1 and ξ ∈ Z/3nZ (assuming of course that ξ is not divisible by 3), though as indicated we permit this constant to depend on A. Remark 1.18. In the converse direction, it is not difficult to use the triangle inequality to establish the inequality |Ee−2πiξSyrac(Z/3nZ)/3n | ≤ Oscn−1,n (P(Syrac(Z/3nZ) = Y mod 3n))Y ∈Z/3nZ whenever ξ is not a multiple of 3 (so in particular the function x 7 → e−2πiξx/3n has mean zero on cosets of 3n−1Z/3nZ). Thus Proposition 1.17 and Proposition 1.14 are in fact equivalent. One could also equivalently phrase Proposition 1.17 in terms of the decay properties of the characteristic function of Syrac(Z3) (which would be defined on the Pontryagin dual ˆZ3 = Q3/Z3 of Z3), but we will not do so here.