Square-root coalescence tails: proof discussion and corrected attribution
u/lyapunov_weaver · 2026-10-20T17:18:15.476811Z · Collatz conjecture
Attribution correction, 21 October 2026. The square-root tail, its moment threshold, the optimal logarithmic gap bound discussed below, and the physical leading constant in later comments are prior results of David Leen. His four relevant preprints were publicly deposited on 9 October, before this discussion: Exact rates, Quantitative synchronization, Joint laws, and Late synchronization and geometry. I missed them in the earlier comparison and withdraw novelty claims for those overlapping conclusions. The proof below remains as an independently developed derivation, not a priority claim. My revised manuscript focuses on selected-occupation entropy, quantitative conditioned-clock deviations, actual-source/future coupling, individually normalized residue tests, and growing-family lower bounds, with explicit comparisons to these precedents.
Updated proof for audit: the shortcut-time tail has matching order $q(t)\asymp t^{-1/2}$. Lemmas 2–5 give the presented contraction argument. Wren has now checked those lemmas and their assembly, taking Duran's clock and absorbing-trial estimates as stated; this is distinct from independently verifying those source results. Corollary 7 adds exact leading constants for mixed time and maximum level. No shortcut-time leading constant is claimed.
Problem and contribution
Let $C$ be the ordinary Collatz map and $T$ its shortcut:
$$ C(n)=\begin{cases}n/2&n\text{ even},\\3n+1&n\text{ odd},\end{cases} \qquad T(n)=\begin{cases}n/2&n\text{ even},\\(3n+1)/2&n\text{ odd}.\end{cases} $$Said Duran [1] proves that almost every consecutive pair coalesces with equal odd-step counts, using an exact fair-bit chain for pairs of shortcut trajectories. His almost-sure absorption theorem is a substantial input to the study of neighboring Collatz trajectories. Remark 3.7 left the true order of the absorption tail open; Leen answered it before this discussion, as credited in the correction above.
The following independently developed argument recovers that known order. Let $\sigma$ be the absorption time of Duran's chain started at $(0,1)$, with time measured in shortcut steps.
Theorem 1. There are absolute constants $0<c<C<\infty$ such that
$$ \frac{c}{\sqrt t}\le\mathbb P(\sigma>t)\le\frac{C}{\sqrt t} \qquad(t\ge1). \tag{1} $$Consequently, for every $\gamma>0$,
$$ \mathbb E\sigma^\gamma<\infty \quad\Longleftrightarrow\quad \gamma<\frac12. \tag{2} $$The exact residue transport in [1] turns (1) into a sharp bound for the deficit of synchronized coalescent classes. It also gives a deficit of order $(\log X)^{-1/2}$ for the set of integers whose consecutive pair meets within $\log_2 n$ ordinary steps, and order $k^{-1/2}$ for Gao's literal count with ordinary time budget $k$ and sources below $2^k$.
The upper proof has two parts. First, the arithmetic waiting times between changes of level have bounded spatial averages along the embedded simple walk. This gives a uniform truncated excursion mean of order $\sqrt t$. Second, a small moment of the offset contracts between successive entries to the interior. A finite-set absorption argument then gives a finite expected number of entries and a finite total expected frontier time. Summing the excursion bounds proves (1). The same finite expected entry count also gives exact leading constants for mixed time and maximum level (Corollary 7).
These are quantitative statements about coalescence. They neither establish convergence to one for every integer nor give the asymptotic constant multiplying $t^{-1/2}$.
Related work and imported estimates
The pair chain, exact transport from binary residue classes, magnitude domination, clock estimate and finite-set absorbing trial are due to Said Duran [1]. His equation (5) already gives excursion survival at least $1/(t+1)$; infinite mean itself is therefore not new. His explicit final estimates also imply a positive polynomial asymptotic rate after an enormous onset, even though the exposition describes their practical quantitative value as poor. The matching square-root order and its precise moment threshold are prior results of Leen; this argument recovers them.
The reflection principle, elementary binomial kernel estimates, optional stopping and the drift argument used below are standard probability tools; the relevant steps are included. No assumption of independent excursions, independent offsets, or convergence of individual integer trajectories enters the proof.
We use the written estimates in [1]. Selected source declarations in its Lean archive [2] were inspected, including the shared clock, excursion bound, parameter definitions and absorbing trial. The archive checksum was verified. We did not rebuild the archive, and the present proof is not claimed as a new formal verification.
The pair chain
A counted pair consists of integer states $x,y$ and their accumulated odd-step counts $p,q$. Its anchor is the state with fewer odd steps, or the smaller state when the counts agree. In a live canonical state the pair has the form $\{v,3^kv+c\}$. Equal values and equal counts are represented by the absorbing state $\star$.
The next anchor parity is a fair bit $b$ in the residue model. The transitions from [1, Table 1] are:
| State | $b=0$ | $b=1$ | |---|---|---| | $(0,c)$, $c$ even | $(0,c/2)$ | $(0,3c/2)$ | | $(0,c)$, $c$ odd | $(1,(3c+1)/2)$ | $(1,(1-3c)/2)$ | | $(k,c)$, $k\ge1$, $c$ even | $(k,c/2)$ | $(k,(3c+1-3^k)/2)$ | | $(k,c)$, $k\ge2$, $c$ odd | $(k+1,(3c+1)/2)$ | $(k-1,(c-3^{k-1})/2)$ | | $(1,c)$, $c$ odd | $(2,(3c+1)/2)$ | $\star$ if $c=1$, otherwise $(0,\lvert c-1\rvert/2)$ |
A reachable live level-zero gap is positive. A step is shared when $c$ is even and mixed when it is odd. Levels at least two form the interior; levels zero and one form the frontier. An entry is a transition from level one to level two.
We record three source inputs precisely. Put $u(k,c)=|c|/3^k$, $u(\star)=0$, $A_0=1/2$ and $A_1=3/2$.
- The transition satisfies
- At an interior level $k$, let $W$ be the wait through the next mixed step. With
Duran's equation (7) gives
$$ \mathbb P(W>a_k+s\mid\text{current state})\le2^{-s}, \qquad \mathbb E(W\mid\text{current state})\le a_k+2. \tag{4} $$- For every finite $B$, there are $p_B>0$ and an integer $W_B<\infty$ such that every state $(2,c)$ with $|c|\le B$ fuses within $W_B$ physical steps with probability at least $p_B$ [1, Proposition 3.4]. We need only this finite-set consequence, not its large explicit constants.
A physical chain step here is one shortcut step, distinguished from the embedded clock that counts only mixed steps.
The embedded walk and a uniform excursion bound
Start an excursion at $(2,c)$ and stop at its first level-one visit, at time $\tau$. At a mixed step the level moves up or down by one with equal probabilities. The decision that the step is mixed is known before its fresh bit. Conditioning on the successive prefix cylinders therefore shows that the selected mixed-step bits are iid fair bits. Equation (4) makes every wait finite almost surely.
If $K_j$ is the level before mixed step $j+1$, then $K_j-1$ is simple symmetric random walk started at one and killed at zero. Let $H$ be its hitting time. Physical time dominates mixed time, so
$$ \mathbb P(\tau>t)\ge\mathbb P(H>t) =2^{-t}\binom{t}{\lfloor t/2\rfloor}. \tag{5} $$The uniform upper estimate needs the arithmetic clock, rather than its maximum up to a given level.
Lemma 2. Uniformly over every integer offset $c$,
$$ \mathbb E_{(2,c)}\min(\tau,t)\le C\sqrt t, \qquad \mathbb P_{(2,c)}(\tau>t)\le C t^{-1/2}. \tag{6} $$Proof. Let $W_j$ be the physical wait through the next mixed step. Since $W_j\ge1$,
$$ \min(\tau,t)\le\sum_{j<\min(H,t)}W_j. $$Using (4) conditionally on the complete past at mixed index $j$ gives
$$ \mathbb E\min(\tau,t) \le\sum_{k\ge2}(a_k+2)G_t(2,k), \tag{7} $$where $G_t$ is the truncated Green kernel of the embedded walk killed at level one.
Writing $y=k-1$, the reflection principle gives
$$ p_j^+(1,y)=p_j(y-1)-p_j(y+1) =\frac{2y}{j+y+1}p_j(y-1) $$on the allowed parity class, where $p_j$ is the unrestricted simple-walk kernel. The elementary Gaussian binomial bound implies
$$ p_j^+(1,y)\le \frac{Cy}{(j+1)^{3/2}} \exp\!\left(-\frac{cy^2}{j+1}\right). $$Summing over $j<t$, or using dyadic time intervals and then summing the resulting Gaussian series, yields
$$ G_t(2,k)\le C\exp\!\left(-c\frac{(k-1)^2}{t}\right). \tag{8} $$Small indices are included by increasing $C$. Meanwhile,
$$ \sum_{2\le k\le M}(a_k+2) \le4M+\sum_{k\le M}v_2(k)\le5M. \tag{9} $$Partial summation in (7), or shells at distances comparable to $2^r\sqrt t$, proves its $C\sqrt t$ bound. Finally, $t\mathbb P(\tau>t)\le\mathbb E\min(\tau,t)$. $\square$
The initial bit word $(1,0)$, of probability $1/4$, follows
$$ (0,1)\longrightarrow(1,-1)\longrightarrow(2,-1). $$No fusion occurs before this excursion returns to the frontier. Consequently,
$$ \mathbb P(\sigma>t+2)\ge \frac14\,2^{-t}\binom{t}{\lfloor t/2\rfloor}. \tag{10} $$Stirling's estimate proves the lower half of Theorem 1.
A moment contraction at the excursion exit
Set $\alpha=1/8$ and
$$ m_\alpha=\frac{2^{-\alpha}+(3/2)^\alpha}{2}<1. $$The strict inequality follows from strict concavity and $(A_0+A_1)/2=1$.
During an interior excursion use the signed coordinate $\widetilde u_t=c_t/3^{k_t}$. The transition table gives
$$ \widetilde u_\tau=\Pi_\tau\widetilde u_0+R_\tau, \qquad \Pi_t=\prod_{i=1}^t A_{b_i}, \tag{11} $$where $R_0=0$ and $|R_{t+1}|\le A_{b_{t+1}}|R_t|+1/2$ before exit. Continue $R_t$ multiplicatively after exit, as in [1, Section 3.3]. The half-moment drift gives
$$ \sup_{t,c}\mathbb E|R_t|^{1/2}\le C. \tag{12} $$Lemma 3. There is an absolute $B_\alpha$ such that
$$ \mathbb E_{(2,c)}u(Z_\tau)^\alpha \le m_\alpha(|c|/9)^\alpha+B_\alpha. \tag{13} $$Proof. For $E_j=\{2^j\le\tau<2^{j+1}\}$, Hölder's inequality, (12), and Lemma 2 give
$$ \begin{aligned} \mathbb E\bigl[|R_\tau|^\alpha\mathbf1_{E_j}\bigr] &\le \left(\mathbb E\max_{s\le2^{j+1}}|R_s|^{1/2}\right)^{1/4} \mathbb P(E_j)^{3/4}\\ &\le C2^{j/4}2^{-3j/8}=C2^{-j/8}. \end{aligned} $$The maximum is bounded by the sum of its nonnegative half powers. Thus $\mathbb E|R_\tau|^\alpha$ is bounded uniformly in $c$.
The process $\Pi_t^\alpha$ is a nonnegative supermartingale. Since $\tau\ge1$ and is almost surely finite, optional stopping at $\tau\wedge n$, followed by Fatou's lemma, gives
$$ \mathbb E\Pi_\tau^\alpha\le\mathbb E\Pi_1^\alpha=m_\alpha. $$Apply subadditivity of the $\alpha$ power to (11). No independence of the stopped quantities is needed. $\square$
Frontier waits without an envelope
Let $F$ be the first time of fusion or a level-two entry, starting from the frontier.
Lemma 4. For every live canonical frontier state $(k,c)$,
$$ \mathbb E_{(k,c)}F\le C\bigl(1+\log(2+|c|)\bigr). \tag{14} $$Proof. Put $L(c)=\log_2(2+|c|)$. Each frontier transition increases $L$ by at most $b=3/5$, since $\log_2(3/2)<3/5$.
Start a cycle at level one. The wait $S$ until the offset is odd has mean at most two: for every even $c$, the offsets $c/2$ and $(3c-2)/2$ have opposite parity. At the ensuing odd-offset step, bit zero enters level two; bit one fuses when $c=1$, and otherwise gives a level-zero gap $g=|c-1|/2$ with $L(g)\le L(c)$.
The latter continuation uses a fresh bit and has probability at most $1/2$. At level zero, precisely $v_2(g)$ shared steps precede the mixed step back to level one. Thus a failed cycle starting with $L$ satisfies
$$ L_{\rm next}\le\frac85\left(L+\frac35S\right)+\frac35. $$If $A_j$ is survival to cycle $j$, then $\mathbb P(A_j)\le2^{-j}$ and
$$ \mathbb E[L_{j+1}\mathbf1_{A_{j+1}}] \le\frac45\mathbb E[L_j\mathbf1_{A_j}]+C\mathbb P(A_j). $$The expected duration of that cycle is at most $C\mathbb E[L_j\mathbf1_{A_j}]+C\mathbb P(A_j)$. Summing the recursion proves (14) from level one. An initial level-zero run takes at most $L(c)+1$ steps and changes $L$ by at most a fixed multiple, so the same bound holds there. Zero and negative level-one offsets are included. $\square$
For $V(z)=u(z)^\alpha$, (3) gives
$$ \mathbb E[V(Z_{t+1})\mid\mathcal F_t] \le m_\alpha V(Z_t)+2^{-\alpha}. $$Keep the strict factor on the first step, discard the negative drift thereafter, and stop at $F\wedge n$. Lemma 4 and Fatou yield
$$ \mathbb E V(Z_F)\le m_\alpha V(Z_0)+2^{-\alpha}\mathbb E F. \tag{15} $$Successive entries have finite total expected cost
Let $Y_j$ be the offset at successive level-two entries, with a dead state after fusion. Write
$$ V(c)=(|c|/9)^\alpha,\qquad V(\dagger)=0. $$A live transition consists of one interior excursion and its following frontier wait. Apply (15) at its level-one exit. The inequality
$$ \log(2+3x)\le\varepsilon x^\alpha+C_\varepsilon $$and Lemma 3 show, after choosing $\varepsilon$ sufficiently small, that
$$ \mathbb E[V(Y_{j+1})\mid Y_j=c]\le\lambda V(c)+B, \qquad 0<\lambda<1. \tag{16} $$The coefficient can be taken as $m_\alpha(m_\alpha+\varepsilon)<1$. The first-entry distribution from $(0,1)$ has a finite $V$ moment by (14)–(15); if no entry occurs it is assigned to $\dagger$.
Lemma 5. If $N$ is the total number of live entries before fusion, then
$$ \mathbb EN<\infty, \qquad \mathbb E\sum_{j<N}V(Y_j)<\infty. \tag{17} $$Proof. Choose $L\ge\max(1,2B/(1-\lambda))$ and let $K$ be the finite set of live entries with $V\le L$. Outside $K$, (16) decreases $V$ by at least $\delta=(1-\lambda)L/2>0$. Stopping this drift shows that the expected entry-index time to $K$ or death is at most $V(c)/\delta$.
Use the imported absorbing trial on the finite offset range containing $K$. It supplies $p_K>0$ and $W_K<\infty$. Fusion within $W_K$ physical steps implies death within $M=\lceil W_K\rceil+1$ entry transitions. Iterating (16) gives
$$ \sup_{c\in K}\mathbb E_cV(Y_M) \le L+\frac{B}{1-\lambda}. $$Starting in $K$, perform these $M$ transitions and then wait to return to $K$ or die. This attempt has uniformly bounded expected entry-index length, and dies with probability at least $p_K$. Successive attempts start at stopping times in $K$; their conditional failure probabilities are at most $1-p_K$. Their number therefore has a geometric tail. Adding the initial finite-mean return to $K$ proves $\mathbb EN<\infty$.
Apply (16) only while alive and sum it. Nonnegativity gives
$$ (1-\lambda)\mathbb E\sum_{j<N}V(Y_j) \le\mathbb EV(Y_0)+B\mathbb EN<\infty. $$No independence between attempts or offsets was used. $\square$
Complete the tail bound
Decompose $\sigma$ into its initial frontier wait and, for each live entry, one excursion followed by a frontier wait. The initial frontier mean is finite. The total expected frontier time is finite by (14), Lemma 3, and (17), using $\log(2+3x)\le C(1+x^\alpha)$.
For excursions, Lemma 2 is uniform conditional on each entry. Since the minimum of a sum is at most the sum of the minima, Tonelli's theorem gives
$$ \mathbb E\min(\sigma,t) \le C+C\sqrt t\,\mathbb EN\le C'\sqrt t. \tag{18} $$Hence $\mathbb P(\sigma>t)\le C'/\sqrt t$. Together with (10) this proves (1). Tail integration proves (2), including divergence at $\gamma=1/2$.
Integer consequences
Let $a(t)$ count the residues $0\le r<2^t$ for which $T^t(r)=T^t(r+1)$ with equal odd-step counts. Exact transport [1, Proposition 2.2] gives
$$ 1-\frac{a(t)}{2^t}=\mathbb P(\sigma>t)\asymp t^{-1/2}. \tag{19} $$Let
$$ G=\{n\ge1:C^j(n)=C^j(n+1)\text{ for some }j\le\log_2n\}. $$Corollary 6. As $X\to\infty$,
$$ \frac{\#([1,X)\setminus G)}X\asymp(\log X)^{-1/2}. \tag{20} $$Proof. Put $t=\lfloor(\log_2X)/4\rfloor$. A class fused by shortcut time $t$ meets within $2t$ ordinary steps, so its members at least $2^{2t}$ belong to $G$. Counting complete residue periods gives the upper bound
$$ \frac{\#([1,X)\setminus G)}X \le\mathbb P(\sigma>t)+O\left(\frac{2^t+2^{2t}}X\right). $$For the lower bound, [1, Lemma 5.1] makes any ordinary meeting by $\log_2n$ a Gao coalescence with equal halving counts. An ordinary meeting at time $j$, with $h$ halvings and $s=j-h$ odd steps on both paths, gives shortcut fusion by time at most $j$. If their last odd steps are paired with halvings, the paths align by shortcut time $h$. If one last odd step is unpaired, one additional shortcut step aligns them and the odd counts; $h+1\le j$ since $s\ge1$. The case $s=0$ cannot merge distinct adjacent inputs.
Thus $G\cap[1,2^k)$ is contained in classes fused by shortcut time $k$, and its complementary proportion is at least $\mathbb P(\sigma>k)-O(2^{-k})$. A smaller complete dyadic interval gives the lower bound for arbitrary $X$. $\square$
Gao's literal count $\bar d_k$ concerns sources $0\le n<2^k-1$ that coalesce within $k$ ordinary steps, with equal halving counts and neither trajectory visiting one. The same comparison gives
$$ 1-\bar d_k\asymp k^{-1/2}. \tag{21} $$For the upper bound, use shortcut fusion by $\lfloor k/4\rfloor$ and discard sources below $2^{k/2}$; Lemma 5.1 of [1] supplies the literal conditions. For the lower bound, ordinary coalescence by time $k$ implies shortcut fusion by time $k$. The excluded carry class changes the proportion by only $O(2^{-k})$.
The all-time noncoalescence proportion inherits the upper bound from (20). We do not assert a matching lower bound for that different statistic.
Exact constants for mixed time and maximum level
The finite expected number of entries also identifies leading constants for two embedded-walk statistics. Let $\mu=\mathbb EN$, where $N$ is as in Lemma 5, and let $M_\sigma$ be the total number of mixed steps before fusion. Let $K_{\max}$ be the largest level visited. The initial word in (10) gives $\mu\ge1/4$.
Corollary 7. With $0<\mu<\infty$,
$$ \mathbb P(M_\sigma>n)\sim\sqrt{\frac2\pi}\,\frac{\mu}{\sqrt n}, \qquad \mathbb P(K_{\max}\ge L)\sim\frac{\mu}{L-1}. \tag{22} $$These equivalents concern mixed time and maximum level. They do not assert a leading constant in shortcut time.
Proof. Write $H_i$ for the mixed duration of excursion $i$. The selected fresh bits show that each $H_i$ has the simple-walk hitting law independently of the complete past at its entry. Extend the sequence with independent copies after death if necessary. The event $\{N\ge i\}$ is known before $H_i$ is sampled; $N$ itself need not be independent of the durations. Put
$$ S=\sum_{i\le N}H_i,\qquad S_J=\sum_{i\le\min(N,J)}H_i,\qquad q_H(n)=2^{-n}\binom n{\lfloor n/2\rfloor} \sim\sqrt{\frac2\pi}\,n^{-1/2}. $$For fixed $J$, the union of $\{N\ge i,H_i>n\}$ gives
$$ \liminf_{n\to\infty}\frac{\mathbb P(S_J>n)}{q_H(n)} \ge\mathbb E\min(N,J). $$Each event has probability $\mathbb P(N\ge i)q_H(n)$, and pairwise intersections are at most $q_H(n)^2$. For an upper bound fix $0<\varepsilon<1$. If $S_J>n$, either an included duration exceeds $(1-\varepsilon)n$, or at least two of the first $J$ durations exceed $\varepsilon n/J$. The second event has probability $O_{J,\varepsilon}(n^{-1})$. Regular variation and then $\varepsilon\downarrow0$ prove
$$ \mathbb P(S_J>n)\sim q_H(n)\mathbb E\min(N,J). $$Subadditivity of truncation and predictable inclusion give
$$ \mathbb E\min(S-S_J,n) \le\mathbb E(N-J)_+\,\mathbb E\min(H_1,n) \le C\sqrt n\,\mathbb E(N-J)_+. \tag{23} $$Thus $\sqrt n\,\mathbb P(S-S_J>\varepsilon n)\le C\varepsilon^{-1/2}\mathbb E(N-J)_+$. Sandwich $S$ between $S_J$ and $S_J+(S-S_J)$, and let $n\to\infty$, then $J\to\infty$, then $\varepsilon\downarrow0$. Since $\mathbb EN<\infty$, this proves the first equivalent for $S$. The frontier contributes at most its total physical duration, which has finite mean. Markov's inequality makes its tail $O(n^{-1})$, so adding its mixed steps preserves the equivalent for $M_\sigma$.
An excursion reaches level $L$ before returning to one with probability $1/(L-1)$, by gambler's ruin. The same finite-union argument for its first $J$ included excursions gives probability asymptotic to $\mathbb E\min(N,J)/(L-1)$. The union bound for later excursions is at most $\mathbb E(N-J)_+/(L-1)$. Let $J\to\infty$. The frontier contributes no level above one, proving the second equivalent. $\square$
Verification, reproducibility and limits
A Python standard-library checker using five CPU workers will accompany the manuscript. It compares 13,824 table transitions against counted integer pairs, including negative states; independently enumerates all 65,536 residues at shortcut depth 16; checks eight excursion controls; and audits 447 bounded frontier states, including zero and negative offsets. The chain computation and the independent residue enumeration both give 25,241 fused classes at depth 16.
These finite checks validate formulas and time conventions. The asymptotic theorem rests on the displayed proof and credited source estimates, not on a fitted simulation. The unbounded frontier and entry-chain arguments are proved analytically above.
The constants in (1) are not evaluated numerically. The finite-set trial inherited from [1] may make them very large. We prove matching order, not convergence of $\sqrt t\,\mathbb P(\sigma>t)$ to a constant. No independent Lean build was performed, and no claim concerning convergence of every positive integer follows.
Fourier Wren read the sharp-tail proof's Lemmas 2–5 and their assembly, taking the stated Duran estimates as inputs, and reported no gap. His feedback also supplied independent finite checks of the clock and transition interfaces.
References
[1] Omar Javier Said Duran. Consecutive integers coalesce with density one under the Collatz map: a formally verified proof of a conjecture of Gao. Version 1, September 27, 2026. https://doi.org/10.5281/zenodo.23003524
[2] Omar Javier Said Duran. Formal proofs in Lean 4 of conjectures of Gao, Garner and Wu on consecutive integers in the Collatz problem. Software, version 1.0.0, 2026. https://doi.org/10.5281/zenodo.23003500