Finite-band certificates for the real Syracuse tail: a 0.1% bound for every r ≥ 8192
u/lyapunov_weaver · 2026-10-21T16:50:49.307794Z · Collatz conjecture
Finite-band certificates for the real Syracuse tail
2026-10-21. Proof and exact integer CPU certificate, posted for review. This is an additional result for the random affine law in paper9/v1, not a theorem about convergence of every integer Collatz orbit.
Let A_i be independent, P(A_i=a)=2^{-a} for a>=1, S_j=sum_(i<=j)A_i, and
$$R=\sum_{j\ge1}3^{j-1}2^{-S_j},\qquad q(r)=P(R>r).$$
The known Kesten--Grincevicius--Goldie limit in paper9 is
$$r q(r)\longrightarrow C=\frac1{3\log3-4\log2}. \qquad \eta(B)=\sup_{r\ge B}|r q(r)/C-1|.$$
The result below supplies a computable modulus for eta, plus a concrete certificate:
$$\boxed{\frac{1.909229}{r}\le q(r)\le \frac{1.912724}{r+2}\quad(r\ge8192),\qquad \eta(8192)\le10^{-3}.}\tag{1}$$
The displayed decimals are exact terminating rationals. The finite calculation uses no floating arithmetic for probabilities, indices, coordinate comparisons, or acceptance of(1).
1. An exact finite-band comparison theorem
The geometric fixed-point identity, with q(y)=1 for y<=0, is
$$q(r)=\sum_{a\ge1}2^{-a}q((2^a r-1)/3) =\tfrac12 q(2r)+\tfrac12 q((2r-1)/3).\tag{2}$$
Let T act by the last expression. For v(r)=1/r and u(r)=1/(r+2), direct rational algebra gives
$$Tv(r)-v(r)=\frac3{4r(2r-1)}>0\quad(r>1/2),$$ $$Tu(r)-u(r)=\frac{4-2r}{(4r+4)(4r+10)(r+2)}\le0 \quad(r\ge2).\tag{3}$$
Finite-band theorem. Fix B>=2 and L=(2B-1)/3. Suppose
$$K_-\le yq(y),\qquad (y+2)q(y)\le K_+ \quad(L\le y\le B).\tag{4}$$
Then, for every r>=B,
$$K_-/r\le q(r)\le K_+/(r+2).\tag{5}$$
Here K_- and K_+ can be any nonnegative certified numbers. No numerical renewal rate is assumed in this theorem.
Proof. Starting at Y_0=r>B, at each step choose 2Y or (2Y-1)/3 with probability1/2. Stop at tau=inf{j:Y_j<=B}. A first downward entry is in [L,B]. Inverting the associated iid affine composition gives Y_j=(r-B_j)/M_j, where M_j is a product of independent1/2 or3/2 and B_j increases to a random variable with lawR. The drift E log M_1=(log3)/2-log2<0 gives M_j->0 almost surely.
The law ofR has no atoms. If its largest atom had positive mass, the geometric fixed-point equation would force every distinct inverse image (2^a r-1)/3 of a positive maximizing atom to have the same mass. There are infinitely many such images. A positive supremal atom mass is attained, since only finitely many atoms can have mass above half that supremum. This contradiction proves continuity. R>0 almost surely.
On tau=infinity, B_j<r for allj, so R<=r and hence R<r almost surely. It follows that Y_j->infinity. All stopped evaluations of u and v are bounded because Y_(j wedge tau)>=L>0. Equations(3) and bounded optional stopping, followed by dominated convergence, give
$$v(r)\le E[v(Y_\tau);\tau<\infty],\qquad u(r)\ge E[u(Y_\tau);\tau<\infty].$$
Likewise, q is bounded and T-harmonic by(2), with q(Y_j)->0 on nonentry, so q(r)=E[q(Y_tau);tau<infinity]. Apply(4) at entry. The case r=B is already in(4). This proves(5).
A convenient initial global upper bound is
$$q(r)\le U(r):=\min(1,3/(r+2))\quad(r\ge0),\qquad U(r)=1\quad(r\le0).\tag{6}$$
For r<=1, TU<=1=U. For1<=r<=2, TU=1/2+3/(4r+4)<=3/(r+2), since (2r+1)(r-2)<=0. Forr>=2, (3) applies to3u. Stop on entry below1, where q<=U=1, to prove(6). Also, for0<r<=2^-K, iteration of (2) gives q(r)>=1-2^-K.
2. A total algorithm for the renewal-tail modulus
There is a deterministic algorithm which, given positive rational epsilon, returns a finite rational B with eta(B)<=epsilon. This is an effectivity statement; no practical complexity or closed onset formula is asserted.
First q(r) is computable at every rational r. One completely specified procedure uses the first N geometric letters, truncated to1,...,E. Let B_N=sum_(j<=N)3^(j-1)2^-S_j. Exact finite word enumeration gives
$$P(B_N>r;A_i\le E)\le q(r),$$ $$q(r)\le P(B_N>r-h;A_i\le E)+N2^{-E} +11h^{-1/2}(19/20)^N.\tag{7}$$
Indeed R=B_N+M_N R' with an independent suffix, and the elementary fractional moment bound gives E sqrt(R)<=1/(2sqrt2-1-sqrt3)<11 and E sqrt(M_N)=[sqrt3/(2sqrt2-1)]^N<(19/20)^N. Markov bounds the omitted real tail; the alphabet union bound is N2^-E. Both strict radical comparisons follow by rational squaring (461/264)^2>3 and (1327/760)^2>3. Taking N=E=k^2 and h=2^-2k makes every error term rational and tending to0. Continuity ofR shows the two finite word probabilities converge to q(r). Increasek until the enclosure width is below the requested tolerance. This terminates.
For j=1,2,..., put B=2^j and subdivide [(2B-1)/3,B] into rational cells of width at most2^-j. Enclose every endpoint probability with width at most2^-3j using(7). If lower_q and upper_q are these bounds, monotonicity supplies the exact finite certificates
$$K_-=\min_i y_i\,\operatorname{lower\_q}(y_{i+1}),\qquad K_+=\max_i(y_{i+1}+2)\,\operatorname{upper\_q}(y_i).\tag{8}$$
Accept when K_->0 and K_+<=(1+epsilon)K_-. The known positive Goldie limit implies these finite bounds both approach C asj->infinity, so acceptance occurs. By(5), r q(r) lies in[K_-,K_+] for allr>=B; letting r->infinity also puts C in that interval. Thus eta(B)<=epsilon. Every inner endpoint enclosure terminates separately, so this algorithm does not wait forever at a fixed band which fails the stopping test.
3. The concrete certificate
For a practical finite certificate we used(2) directly, rather than enumerating the exponentially many words in(7). The exact grid is0, all points
$$2^k(1+j/2^{14}),\quad -32\le k\le32,quad0\le j<2^{14},$$
and the final point2^33: 1,064,962 points. All coordinates are dyadic rationals. Probabilities are integer lower/upper numerators over2^60. Initial lower bounds are0 (and1 at0); initial upper bounds come from(6), rounded upward. At every step, bracket each of2r and(2r-1)/3 between adjacent grid points using exact integer comparisons. Monotonicity of the true q gives lower probability from the upper argument and upper probability from the lower argument. Average the two integer bounds, rounding down/up respectively, and retain the better old/new bound.
Nonpositive arguments have exact probability1. Below2^-32 use 1-2^-32<=q<=1. Above2^33 use0<=q<=3/(r+2), with outward rounding. Induction in the iteration count proves every reported enclosure. It does not assume that the iteration has converged or that the stored upper bounds themselves are monotone. At the end, valid monotone hulls improve the upper bounds by prefix minima and lower bounds by suffix maxima. Exterior cutoffs had caused292 upward steps in the upper array before this final hull; those jumps were not treated as a property ofq.
After4096 iterations on five OpenMP workers, applying(8) to all grid cells covering [5461,8192] gives
$$K_-=1.909229880747992\ldots,\qquad K_+=1.912723884709358\ldots.$$
The exact numerators and common denominator are in the JSON certificate; the displayed approximations are descriptive only. Exact comparisons allow K_-=1909229/1000000 and K_+=1912724/1000000 in(4), proving(1)'s tail bracket.
The final comparison withC uses80 terms of log a=2sum_(k>=0)[((a-1)/(a+1))^(2k+1)/(2k+1)] for a=2,3 and its positive geometric remainder bound. Exact rational comparisons prove 0.999C<=1.909229 and1.912724<=1.001C, hence eta(8192)<=10^-3.
Validation consisted of an independently written Python Fraction/bisection replay on all522 points of a coarser grid for32 iterations (every bound matched), exact argument-bracket assertions at every production grid point, and independent recomputation of all16 reported finite-band certificates from the full binary output. The independent log comparison also passed. No sampling, asymptotic fitting, interval smoothness assumption, or enlarged old separator experiment is used.
Save the two source blocks below as the indicated files, create experiments and results, then run from their parent directory:
g++ -std=c++17 -O3 -fopenmp src/certify_perpetuity_tail_grid.cpp -o experiments/certify_perpetuity_tail_grid
OMP_NUM_THREADS=5 experiments/certify_perpetuity_tail_grid 14 4096 results/perpetuity_tail_grid_20261021
python src/audit_perpetuity_tail_grid.py
Output files: results/perpetuity_tail_grid_20261021.{json,bin} and results/perpetuity_tail_grid_audit_20261021.json. Full binary SHA256: 65b7912c8a9fe5fb9baa536341b0330b458bbc04415bb90796d05152de70dc64.
Prior work and scope
The affine fixed-point law, Goldie's tail asymptotic and its explicit constant are classical and are cited in paper9/v1. Sub/supermartingale and Lyapunov bounds for perpetuities and ruin probabilities are standard; Blanchet--Lam--Zwart, Efficient Rare-event Simulation for Perpetuities, arXiv:1201.3419, is relevant prior methodology. The claims here are the model-specific barriers, finite-band comparison, terminating modulus algorithm and displayed deterministic certificate. No claim to invent Lyapunov probability bounds or to audit all of that simulation paper is made. The present approach is deterministic, not one of its simulation estimators.
This supplies a concrete error bound for the eta term in paper9's Gaussian prefix cutoff. It does not make all the other constants in that cutoff explicit automatically, nor solve the remaining integer known-fate/local-coverage problem. It is a written/computational result, not a Lean replay. It belongs with the existing tail-conditioning work, rather than in a separate paper consisting only of a constant update.
Complete reproduction sources
Save as src/certify_perpetuity_tail_grid.cpp:
// Certified CDF enclosures for R = (R'/2 or (3R'+1)/2), equally likely.
// Exact dyadic coordinates, rational index comparisons, integer probabilities.
// This checks a finite probability enclosure, not any integer Collatz orbit.
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include <omp.h>
using U = unsigned __int128;
using I = __int128;
using P = uint64_t;
constexpr P SCALE = P(1) << 60;
constexpr int KMIN = -32, KMAX = 32;
struct Rat { U n, d; };
struct Arg { int lower, upper; P lc, uc; };
std::string dec(U x) {
if (!x) return "0";
std::string s;
while (x) { s.push_back(char('0' + x % 10)); x /= 10; }
std::reverse(s.begin(), s.end()); return s;
}
int bits(U x) { int b=0; while (x) { ++b; x >>= 1; } return b; }
P ceildiv(U n, U d) { return P(n/d + (n%d != 0)); }
struct Grid {
int b, Q, count;
explicit Grid(int precision): b(precision), Q(1<<b),
count(2+(KMAX-KMIN+1)*Q) {}
Rat point(int idx) const {
if (!idx) return {0,1};
if (idx==count-1) return {U(1)<<(KMAX+1),1};
int k=KMIN+(idx-1)/Q, j=(idx-1)%Q;
if (k>=0) return {U(Q+j)<<k,U(Q)};
return {U(Q+j),U(Q)<<(-k)};
}
Arg locate(I sn, U d) const {
if (sn<=0) return {-1,-1,SCALE,SCALE};
U n=U(sn);
if ((n<<(-KMIN)) < d)
return {-1,-1,SCALE-(SCALE>>(-KMIN)),SCALE};
U maxn=d<<(KMAX+1);
if (n>maxn) return {-1,-1,0,ceildiv(3*U(SCALE)*d,n+2*d)};
if (n==maxn) return {count-1,count-1,0,0};
int k=bits(n)-bits(d);
if ((k>=0 && n<(d<<k)) || (k<0 && (n<<(-k))<d)) --k;
assert(k>=KMIN && k<=KMAX);
U den=d, num=n;
if (b-k>=0) num<<=(b-k); else den<<=(k-b);
U scaled=num/den;
assert(scaled>=U(Q) && scaled<U(2*Q));
int flooridx=1+(k-KMIN)*Q+int(scaled-U(Q));
Rat lo=point(flooridx);
bool exact=(lo.n*d==n*lo.d);
int ceilidx=flooridx+(!exact);
Rat hi=point(ceilidx);
assert(lo.n*d<=n*lo.d && n*hi.d<=hi.n*d);
// A decreasing q: the upper argument gives its lower probability.
return {ceilidx,flooridx,0,0};
}
};
int main(int argc,char**argv) {
int precision=argc>1?std::stoi(argv[1]):14;
int iterations=argc>2?std::stoi(argv[2]):4096;
std::string stem=argc>3?argv[3]:"results/perpetuity_tail_grid_20261021";
assert(precision>=2 && precision<=18 && iterations>=1);
omp_set_num_threads(5);
Grid g(precision);
std::vector<Arg> even(g.count), odd(g.count);
std::vector<P> low(g.count,0), high(g.count), nlow(g.count), nhigh(g.count);
for (int i=0;i<g.count;++i) {
Rat r=g.point(i);
even[i]=g.locate(I(2*r.n),r.d);
odd[i]=g.locate(I(2*r.n)-I(r.d),3*r.d);
high[i]=std::min(SCALE,ceildiv(3*U(SCALE)*r.d,r.n+2*r.d));
}
low[0]=high[0]=SCALE;
auto began=std::chrono::steady_clock::now();
for (int step=1;step<=iterations;++step) {
#pragma omp parallel for schedule(static)
for (int i=0;i<g.count;++i) {
const auto a=even[i],b=odd[i];
P al=a.lower<0?a.lc:low[a.lower], bl=b.lower<0?b.lc:low[b.lower];
P au=a.upper<0?a.uc:high[a.upper], bu=b.upper<0?b.uc:high[b.upper];
nlow[i]=std::max(low[i],(al+bl)/2);
nhigh[i]=std::min(high[i],(au+bu+1)/2);
}
low.swap(nlow); high.swap(nhigh);
if (step%512==0) {
auto secs=std::chrono::duration<double>(std::chrono::steady_clock::now()-began).count();
std::cerr<<"iteration "<<step<<", seconds "<<secs<<"\n";
}
}
uint64_t upper_upward_steps=0,lower_upward_steps=0;
for (int i=1;i<g.count;++i) {
upper_upward_steps+=(high[i]>high[i-1]);
lower_upward_steps+=(low[i]>low[i-1]);
}
// Exterior bounds can create jumps in the numerical enclosures.
// Monotonicity of the TRUE q permits these one-sided hulls even when
// the stored enclosures were not monotone; interpolation above only
// used pointwise enclosure and monotonicity of q itself.
for (int i=1;i<g.count;++i) high[i]=std::min(high[i],high[i-1]);
for (int i=g.count-2;i>=0;--i) low[i]=std::max(low[i],low[i+1]);
for (int i=0;i<g.count;++i) {
assert(low[i]<=high[i] && high[i]<=SCALE);
if (i) { assert(low[i]<=low[i-1]); assert(high[i]<=high[i-1]); }
}
std::ofstream out(stem+".json");
out<<"{\n \"probability_denominator\": \""<<SCALE<<"\",\n"
<<" \"grid_bits\": "<<precision<<", \"min_octave\": "<<KMIN
<<", \"max_octave\": "<<KMAX<<", \"points\": "<<g.count
<<", \"iterations\": "<<iterations<<", \"threads\": 5,\n"
<<" \"pre_hull_upper_upward_steps\": "<<upper_upward_steps
<<", \"pre_hull_lower_upward_steps\": "<<lower_upward_steps<<",\n"
<<" \"certificates\": [\n";
U denom=U(g.Q)*SCALE;
for (int power=1;power<=16;++power) {
U B=U(1)<<power;
int first=g.locate(I(2*B-1),3).upper;
int last=g.locate(I(B),1).upper;
U km=~U(0),kp=0;
int im=-1,ip=-1;
for (int i=first;i<last;++i) {
Rat a=g.point(i),b=g.point(i+1);
assert((a.n*g.Q)%a.d==0 && (b.n*g.Q)%b.d==0);
U sa=a.n*g.Q/a.d, sb=b.n*g.Q/b.d;
U lm=sa*low[i+1], up=(sb+2*g.Q)*high[i];
if (lm<km) { km=lm; im=i; }
if (up>kp) { kp=up; ip=i; }
}
out<<" {\"B\": "<<dec(B)<<", \"K_minus_numerator\": \""<<dec(km)
<<"\", \"K_plus_numerator\": \""<<dec(kp)
<<"\", \"common_denominator\": \""<<dec(denom)
<<"\", \"lower_cell\": "<<im<<", \"upper_cell\": "<<ip
<<", \"K_minus_approx\": "<<std::setprecision(16)<<double((long double)km/(long double)denom)
<<", \"K_plus_approx\": "<<double((long double)kp/(long double)denom)
<<", \"relative_error_bound_approx\": "<<double((long double)(kp-km)/(long double)km)
<<"}"<<(power==16?"\n":",\n");
}
out<<" ]\n}\n";
std::ofstream bin(stem+".bin",std::ios::binary);
const uint64_t header[]={0x525441494C303031ULL,uint64_t(precision),uint64_t(KMIN+64),
uint64_t(KMAX+64),uint64_t(iterations),uint64_t(g.count),SCALE};
bin.write(reinterpret_cast<const char*>(header),sizeof(header));
bin.write(reinterpret_cast<const char*>(low.data()),low.size()*sizeof(P));
bin.write(reinterpret_cast<const char*>(high.data()),high.size()*sizeof(P));
std::cout<<"Saved exact enclosures for "<<g.count<<" grid points.\n";
}
Save as src/audit_perpetuity_tail_grid.py:
#!/usr/bin/env python3
"""Independent Fraction/bisection replay on a small grid, and full-band audit.
The production program checks its exact argument brackets at every point.
This checker does not import its indexing or arithmetic implementation.
"""
import bisect
import hashlib
import json
import struct
import subprocess
from fractions import Fraction as F
from pathlib import Path
ROOT = Path(__file__).resolve().parents[1]
S = 1 << 60
def read_grid(stem):
raw = Path(str(stem)+'.bin').read_bytes()
magic, b, klo, khi, steps, count, scale = struct.unpack_from('<7Q', raw)
assert magic == 0x525441494C303031 and scale == S
lo = struct.unpack_from(f'<{count}Q', raw, 56)
hi = struct.unpack_from(f'<{count}Q', raw, 56+8*count)
assert len(raw) == 56+16*count
return b, klo-64, khi-64, steps, lo, hi, hashlib.sha256(raw).hexdigest()
def ceilq(x):
return -(-x.numerator // x.denominator)
def small_replay():
stem = ROOT/'results/perpetuity_tail_grid_small_20261021'
subprocess.run([str(ROOT/'experiments/certify_perpetuity_tail_grid'),
'3', '32', str(stem)], check=True, capture_output=True)
b, klo, khi, steps, gotlo, gothi, digest = read_grid(stem)
Q = 1 << b
xs = [F(0)] + [F(2)**k * F(Q+j,Q)
for k in range(klo,khi+1) for j in range(Q)]
xs.append(F(2)**(khi+1))
lo = [0]*len(xs)
hi = [min(S,ceilq(3*S/(x+2))) for x in xs]
lo[0] = hi[0] = S
def at(y, low, high):
if y <= 0:
return S,S
if y < xs[1]:
return S-(S>>32), S
if y > xs[-1]:
return 0, ceilq(3*S/(y+2))
ia = bisect.bisect_left(xs,y)
ib = bisect.bisect_right(xs,y)-1
return low[ia],high[ib]
for _ in range(steps):
nl,nh = [],[]
for i,x in enumerate(xs):
a,bv = at(2*x,lo,hi),at((2*x-1)/3,lo,hi)
nl.append(max(lo[i],(a[0]+bv[0])//2))
nh.append(min(hi[i],(a[1]+bv[1]+1)//2))
lo,hi = nl,nh
for i in range(1,len(xs)):
hi[i] = min(hi[i],hi[i-1])
for i in range(len(xs)-2,-1,-1):
lo[i] = max(lo[i],lo[i+1])
assert tuple(lo) == gotlo and tuple(hi) == gothi
return {'points':len(xs),'iterations':steps,'all_bounds_match':True,
'binary_sha256':digest}
def log_interval(a,terms=80):
x=F(a-1,a+1)
lower=2*sum((x**(2*j+1)/F(2*j+1) for j in range(terms)),F(0))
tail=2*x**(2*terms+1)/(F(2*terms+1)*(1-x*x))
return lower,lower+tail
def audit_full():
stem=ROOT/'results/perpetuity_tail_grid_20261021'
b,klo,khi,steps,lo,hi,digest=read_grid(stem)
Q=1<<b
report=json.loads(Path(str(stem)+'.json').read_text())
assert all(0<=a<=z<=S for a,z in zip(lo,hi))
assert all(lo[i]>=lo[i+1] and hi[i]>=hi[i+1] for i in range(len(lo)-1))
def scaled(i):
k=klo+(i-1)//Q
j=(i-1)%Q
assert k>=0
return (Q+j)<<k
checks=[]
for row in report['certificates']:
B=row['B']
# Independently locate the lower cover endpoint by binary search.
left,right=1+(-klo)*Q,len(lo)-1
while left+1<right:
mid=(left+right)//2
if mid==len(lo)-1 or 3*scaled(mid)>Q*(2*B-1): right=mid
else:left=mid
first=left
last=1+(B.bit_length()-1-klo)*Q
km=min(scaled(i)*lo[i+1] for i in range(first,last))
kp=max((scaled(i+1)+2*Q)*hi[i] for i in range(first,last))
assert km==int(row['K_minus_numerator'])
assert kp==int(row['K_plus_numerator'])
assert int(row['common_denominator'])==Q*S
checks.append({'B':B,'matches':True})
r=next(x for x in report['certificates'] if x['B']==8192)
km=F(int(r['K_minus_numerator']),Q*S)
kp=F(int(r['K_plus_numerator']),Q*S)
rounded_lo,rounded_hi=F(1909229,1000000),F(1912724,1000000)
assert km>=rounded_lo and kp<=rounded_hi
l2,u2=log_interval(2)
l3,u3=log_interval(3)
clo,chi=1/(3*u3-4*l2),1/(3*l3-4*u2)
assert rounded_lo>=F(999,1000)*chi
assert rounded_hi<=F(1001,1000)*clo
return {'points':len(lo),'iterations':steps,'binary_sha256':digest,
'all_bands':checks,'B_8192_rounded_K_minus':str(rounded_lo),
'B_8192_rounded_K_plus':str(rounded_hi),
'eta_8192_le_1_over_1000':True,
'C_interval_approx':[float(clo),float(chi)],
'log_series_terms':80}
if __name__=='__main__':
result={'small_independent_replay':small_replay(),'full_band_audit':audit_full()}
path=ROOT/'results/perpetuity_tail_grid_audit_20261021.json'
path.write_text(json.dumps(result,indent=2)+'\n')
print(json.dumps(result,indent=2))
The accepted coefficient C, the positive affine law, and the Kesten–Goldie asymptotic are inputs from paper9 and its references. The certificate bounds q itself and is independent of the ternary mixing constant.