\documentclass[11pt,reqno]{amsart} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb,mathtools,mathrsfs} \usepackage[T1]{fontenc} \usepackage{lmodern,microtype} \microtypesetup{expansion=false} \usepackage[hidelinks]{hyperref} \usepackage{xurl} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\R}{\mathbb R} \newcommand{\E}{\mathbb E} \newcommand{\Prob}{\mathbb P} \newcommand{\calM}{\mathcal M} \newcommand{\calH}{\mathcal H} \newcommand{\av}[2]{\langle #2\rangle_{#1}} \newcommand{\ceil}[1]{\left\lceil #1\right\rceil} \newcommand{\floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\bl}{\operatorname{bitlen}} \newcommand{\off}{\operatorname{off}} \newcommand{\Src}{\operatorname{Src}} \newcommand{\src}{\operatorname{src}} \newcommand{\Lint}{X_{\mathrm{int}}} \newcommand{\cint}{c_{\mathrm{int}}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\pr}{\operatorname{pr}} \newcommand{\lift}{\operatorname{lift}} \newcommand{\Exc}{\operatorname{Exc}} \newcommand{\tip}{\operatorname{tip}} \newcommand{\row}{\operatorname{row}} \newcommand{\Osc}{\operatorname{Osc}} \newcommand{\mass}{\operatorname{mass}} \newcommand{\C}{\mathbb C} \newcommand{\wt}{\operatorname{wt}} \newcommand{\FC}{\operatorname{FC}} \newcommand{\term}{\mathrm{term}} \title{Explicit positive lower density for the Collatz Conjecture} \author{Kenny Lau} \address{Axiom Math, 124 University Avenue, Palo Alto, CA 94301} \email{kenny@axiommath.ai} \date{} \subjclass[2020]{Primary 11B83; Secondary 37P99, 60G50} \keywords{Collatz conjecture, arithmetic dynamics} \begin{document} \begin{abstract} Lech Mazur proved that a positive proportion of integers $n$ reach $1$ under the Collatz map in at most $10.46\log n$ steps. We give a quantitative refinement of his construction. For every $N$, at least $\lfloor N/2^{2^{2^{163}}} \rfloor$ odd positive integers $n 0$ with the property that for every $X \ge X_0$, at least $cX$ starting values $n < X$ reach $1$ within $10.46 \log n$ steps. \end{theorem} The pair of constants $(X_0, c)$ is not explicitly specified in Mazur's proof, but Appendix~\ref{app:mazur} reconstructs their values to be \begin{equation}\label{eq:mazur-bounds} (X_0, c) = \left(D_M, D_M^{-1}\right), \quad D_M = 2^{2^{2^{2^{2^{2^{2^{173}}}}}}}. \end{equation} Mazur also proved \cite{MazurPred} that, more generally, for any prescribed target $t$ with $3 \nmid t$, a positive proportion of integers eventually reach $t$, without a bound on the number of steps. Shaik \cite{Shaik}, building on Mazur's construction, obtains a positive proportion reaching $1$ within $c\log n$ steps for every $c>3/\log(4/3)\approx10.428$. The paper is organized as follows: Section~\ref{sec:outline} provides a summary of the main argument in Sections~\ref{sec:words}--\ref{sec:steps}. Then Sections~\ref{sec:fb-black}--\ref{sec:fb-cases} establishes a key Fourier bound, while Sections~\ref{sec:est-families} and~\ref{sec:est-histogram} provide key estimates. Then Appendices~\ref{app:constants} and~\ref{app:mazur} contain numerical computations, Appendix~\ref{app:lean} produces the formal Lean certificate, and Appendix~\ref{app:ai} declares the AI usage in this paper. \section{Outline of the proof}\label{sec:outline} We provide a high-level overview of the argument in this paper. Recall that we require $3 \nmid t$ (Remark~\ref{rem:three-nmid}). We now further assume that: \begin{equation}\label{hyp:odd} \text{$t$ is odd} \tag{H1} \end{equation} We will explain the minor modification to the argument for even $t$ in Section~\ref{sec:outline-seed}. \subsection{Preliminaries} We outline some basic facts about the Collatz problem. \subsubsection{The random model} Recall that the Syracuse map $S$, which is the accelerated Collatz map, sends an odd number $n$ to $\frac{3n+1}{2^a}$ where $a = \ord_2(3n+1)$. Given a random even number, there is a $\frac12$ chance that it is exactly divisible by $2$ once, then a $\frac14$ chance that it is exactly divisible by $2$ twice, and so on. Therefore, $a$ can be modeled by a geometric random variable $A$ where $\Prob(A=a) = 2^{-a}$. The average value of $a$ is \[\E(A) = \sum_{a=1}^{\infty} a 2^{-a} = 2.\] \subsubsection{The heuristic number of steps} Since the expected value of $a$ is $2$, heuristically the Syracuse map is expected to send $n$ to $\frac{3n+1}{2^2} \approx \frac34 n$. This means that $n$ should reach $1$ in about \[\log_{4/3}(n) \approx 3.476 \log n\] accelerated steps using the Syracuse map. Since each Syracuse application with $a$ corresponds to $a+1$ ordinary steps using the Collatz map, and the expected value of $a$ is $2$, this means that $n$ should reach $1$ in about \[(2+1)\log_{4/3}(n) \approx 10.428 \log n\] ordinary steps. More generally, if we want $n$ to reach $t$ instead, then heuristically that would take $3.476 \log \frac{n}{t}$ accelerated steps and $10.428 \log \frac{n}{t}$ ordinary steps. \subsection{First reduction: lower bound for total weight of words landing in a window} In this section we explain the backward tree model and reduce the goal to obtaining a lower bound for the total weight of the words that result in a starting value in the window $[X, 32X)$. \subsubsection{Walking backwards}\label{sec:backwards} Instead of following the Syracuse map $S$ forwards, we analyze the preimages under $S$, in order to construct a large set of sources that will reach the given target $t$. Suppose $S(n') = n$ for some odd $n$ and $n'$. We know that for some $a \in \N_{>0}$ we have \[n = \frac{3n'+1}{2^a},\] which is equivalent to \[n' = \frac{2^a n - 1}{3}.\] This parametrizes the solutions $n'$ given $n$ in terms of $a$, provided the expression gives an integer. The set of valid solutions depends on the residue class of $n$ modulo $6$. If $n \equiv 1 \pmod 6$, then the valid solutions are given by $a = 2, 4, 6, \cdots$. For example, \[S^{-1}(7) = \{9, 37, 149, 597, 2389, \cdots\}.\] If $n \equiv 5 \pmod 6$, then the valid solutions are given by $a = 1, 3, 5, \cdots$. For example, \[S^{-1}(11) = \{7, 29, 117, 469, 1877, \cdots\}.\] Finally, if $n \equiv 3 \pmod 6$ then there are no valid solutions. \subsubsection{Letters and words}\label{sec:word} Consider the Syracuse orbit $11 \to 17 \to 13 \to 5 \to 1$. The values of $a$ in each step are $(1, 2, 3, 4)$. So if we want to start from the target $1$ and describe the path backwards to reach the source $11$, we would write $w = (4, 3, 2, 1)$, which we call a \emph{word}. Each component is called a \emph{letter}. The example word here has $4$ letters. As we have seen in Section~\ref{sec:backwards}, not all words correspond to valid integer-valued sources, but if the resulting source is an integer, then all of the intermediate steps are integers (Remark~\ref{rem:admissible}). \subsubsection{Number of steps}\label{sec:outline-steps} Given a word $w = (a_1, \cdots, a_d)$, we define its \emph{degree} to be \[\deg(w) := a_1 + \cdots + a_d.\] We also denote by $|w|$ the \emph{length} of the word, which is $d$. The constructed source then takes $|w|$ accelerated steps to reach the target $t$, and $|w| + \deg(w)$ ordinary steps (Section~\ref{sec:words}). \subsubsection{Weight} A backward step dictated by the letter $a$ causes the value to be multiplied by approximately $\frac{2^a}{3}$. As a result, if we go backwards through the whole word $w$, then the value will be multiplied by approximately $3^{-|w|} 2^{\deg(w)}$. For the example in Section~\ref{sec:word}, we verify that $11 \approx 3^{-4} 2^{4+3+2+1} \approx 12.642$. In fact this will always be an overestimate. We now define the \emph{weight} of a word $w$ to be \[\wt(w) := 3^{|w|} 2^{-\deg(w)},\] which is the reciprocal of the previous value, so that the source is approximately the target divided by $\wt(w)$. We always have \[\wt(w) \le \frac{t}{s}\] where $t$ is the target and $s$ is the source. \subsubsection{Window and reduction}\label{sec:outline-reduction} To obtain the bound in the main theorem, we consider the window $[X, 32X)$ and try to construct many sources that land in the window. If $t$ is not part of a cycle, then two different words cannot produce the same source (Lemma~\ref{lem_distinct_sources}), so the problem reduces to a count of words. We record this constraint as an explicit hypothesis: \begin{equation}\label{hyp:not-cycle} \text{$t$ is not part of a cycle.} \tag{H2} \end{equation} Given the target $t$ and a valid word $w$ with source $s \in [X, 32X)$, we have $\wt(w) \le \frac{t}{s} \le \frac{t}{X}$, which implies \[\frac{X}{t} \wt(w) \le 1.\] Summing this over all valid words whose source lands in $[X, 32X)$, we obtain that the count of such words is at least $X/t$ times the total weight $\beta_X(t)$ of these words, which is \eqref{eq:charge}. Therefore, the main theorem reduces to obtaining an (explicit) constant lower bound of $\beta_X(t)$, with control over the lengths and degrees of the words, in view of Section~\ref{sec:outline-steps}. \subsection{A mixing lemma} In this section we explain an important lemma that relates to the stability of the set of valid words across different lengths. \subsubsection{Residue and offset} Consider words of length $3$, with target $t$. Say the word is $(a_1, a_2, a_3)$. This word is valid iff the source is an integer, where we recall the source is given by \[\frac{2^{a_3} \frac{2^{a_2} \frac{2^{a_1} t - 1}{3} - 1}{3} - 1}{3} = \frac{2^{a_1+a_2+a_3} t - 2^{a_2+a_3} - 2^{a_3} \cdot 3 - 9}{27}.\] Noting that $2$ is invertible modulo any power of $3$, we conclude that this is an integer iff \[t \equiv 2^{-a_1} + 2^{-a_1-a_2} \cdot 3 + 2^{-a_1-a_2-a_3} \cdot 9 \pmod{27}.\] Generalizing this, we can define the offset $\off(w)$ of a word $w = (a_1, \cdots, a_d)$ to be \[\off(w) := 2^{-a_1} + 2^{-a_1-a_2} \cdot 3 + \cdots + 2^{-a_1-\cdots-a_d} 3^{d-1}\] so that $w$ is valid iff $t \equiv \off(w) \pmod{3^{|w|}}$, which is Remark~\ref{rem:admissible}. Furthermore, given any $q \in \N$, we denote by $\off_q(w)$ the residue of $\off(w)$ in $\Z/3^q\Z$. \subsubsection{Residue density} Recall our probabilistic model where each letter is modeled by a random variable $A$ with $\Prob(A=a) = 2^{-a}$. We form random words $W$ by combining independent letters. The probability of a particular word being chosen is $\Prob(W=w) = 2^{-\deg(w)}$, so $\wt(w) = 3^{|w|} \Prob(W=w)$. Consider the distribution of $\off_d(W) \in \Z/3^d\Z$, i.e. the residue of the offset of a random word. Define the \emph{residue density} $\rho_d(y) := 3^d \Prob(\off_d(W) = y)$ for $y \in \Z/3^d\Z$. This value coincides with the total weight of length-$d$ words that are valid for $t$ (see \eqref{eq:rho-meaning}): \[\sum_{w} \wt(w) \cdot 1_{\off_d(w)=t} = \sum_w 3^d \Prob(W=w) \cdot 1_{\off_d(w)=t} = 3^d \Prob(\off_d(W)=t) = \rho_d(t).\] \subsubsection{Mixing} The residue density $\rho_d$ depends on $d$ and could differ wildly across different $d$. However, we have a \emph{fine-scale mixing} lemma, in the sense of Tao \cite{Tao}, which states that for large enough $d$, the residue density $\rho_d$ is, on average over residues, well approximated by $\rho_m$ for much smaller $m$. More precisely, \[3^{-d} \sum_{y \in \Z/3^d\Z} |\rho_d(y) - \rho_m(y \bmod 3^m)| \le 2^{96} m^{-1.45}\log m\] for any $d \ge m \ge 2^{80}$, and the same average is also at most $2^{365} m^{-1.8693}\log m$. The first bound has the smaller constant and is used for the propagation estimate below, and the second has the larger exponent and is used for the census inequality. They come from two Fourier bounds with different parameters. This is Proposition~\ref{prop:mix}, proved in Section~\ref{sec:mix}. \subsection{Constructing a large family of words} Recall we need a constant lower bound of the total weight $\beta_X(t)$ of words whose source lands in $[X, 32X)$, so we need a controlled way to construct many such words to satisfy this constraint. \subsubsection{Growing the family generation by generation} We construct a family $L_j$ of words generation by generation (Section~\ref{sec:physical}). $L_0$ consists of only the empty word. At generation $j$, we take every word in the previous generation, and extend it by every element of a yet to be constructed set $\FC(\delta_j, R_j)$. We then keep the words $w$ that are valid for the target $t$ and that additionally satisfy an unspecified filter that among other things has the effect of forcing the inequality $0 \le \off(w) \le \frac34+2^{-8}$, whenever $j \ge 29$. We choose $R_j = 29 + \floor{j/56}$ explicitly, but leave $\delta_j$ undefined here except that $\delta_0=16544$ and it behaves like $16544 \cdot 1.01^j$. We now describe $\FC(\delta, R)$, the set of \emph{first crossings} with average length $\delta$ and allowed overshoot $R$. For any word $w = (a_1, \cdots, a_d)$, draw the word-graph $(i, \deg_i(w))$ where $\deg_i(w) := a_1 + \cdots + a_i$ is the partial degree. Then draw a straight line passing through $(\delta, 2\delta)$ with slope $\log_2(3) \approx 1.585$. Chop each word off at the \emph{first crossing} of the line, and keep the words with length in $(\delta - \lfloor 3\delta/5 \rfloor, \delta + \lfloor 3\delta/5 \rfloor]$ and overshoot $\le R$. Note that by the first crossing construction, these words are prefix-disjoint, meaning no word is a prefix of any other word. Recall that the average value of a letter is $2$, so almost all words eventually cross the line, and the expected place of crossing is $(\delta, 2\delta)$, so these words have expected length approximately $\delta$ and expected degree approximately $2\delta$. \subsubsection{Weighted density} We define the \emph{weighted density} $Z_j(t)$ at generation $j$ (Section~\ref{sec:physical}) to be \[Z_j(t) := \sum_{w \in L_j} \wt(w) \rho_{\lfloor \frac14 \delta_j \rfloor}(s_w)\] where $s_w$ is the source of the word $w$ from target $t$. Recall the residue density $\rho$ represents how well words can continue from $s_w$. \subsubsection{Terminal extension} We now construct a family $L_{j,X}$ of words that will finally have sources landing near $X$: take every word in $L_j$ and add every extension in $\FC^\term_X(w, \delta_j, R_j)$ so that the resulting word is valid, where $\FC^\term$ is a slight modification of $\FC$ that among other things forces the sources to be $\ge X$. We will use a notion of $X$ being \emph{reachable} from $j$, which we do not define here (see Section~\ref{sec:physical}), but it roughly means that $X$ is not far away from a typical source of words in $L_j$. \subsubsection{Terminal weighted density} We then define the \emph{terminal weighted density} $Z^\term_{j,X}(t)$ to be \[Z^{\term}_{j,X}(t) := \sum_{w \in L_{j,X}} \wt(w) \rho_{\lfloor \frac14 \delta_j \rfloor}(s_w),\] with a similar interpretation as the weighted density. \subsection{Key estimates and the final proof} We now state several key estimates for the quantities above that are proved in this paper (Section~\ref{sec:census}), and explain how they lead to a proof of the main theorem. \subsubsection{Key estimates} The weighted density enjoys a propagation error bound from one generation to the next. Precisely, for any $j \ge 9853$, Proposition~\ref{prop:central-propagation} and Corollary~\ref{cor:geometric-propagation} state that \begin{equation}\label{eqn:propagation-error} |Z_{j+1}(t) - Z_j(t)| \le 0.007584\cdot0.990945^{j-9853}+2^{-90}\cdot0.995^{j-9853}. \end{equation} As a consequence, the sum of all these errors from generation $9853$ onwards is less than $6/7$ (Lemma~\ref{lem_Nstar_tail}), so it suffices that the main term at that generation exceeds $6/7$ by a margin. We indeed have a large enough main term. Precisely, let $j_0 := 9853$ and $d_0 := 5\cdot2^{160}$. This $d_0$ is enough to dominate the subscript of every $\rho$ that appears in the definition of $Z_{j_0}$, so that $Z_{j_0}$ is periodic with period $3^{d_0}$. Because of the filter, the words of $L_{j_0}$ concentrate in one residue class modulo $3^8$, so we average over that class. The estimate we need is that the average value of $Z_{j_0}(t)$ across the residues $t \equiv 6275 \pmod{3^8}$ is greater than $\frac{13}{15}$, which is supplied by Proposition~\ref{prop:average}: \begin{equation}\label{eqn:average-bound} \frac{1}{3^{d_0-8}} \sum_{\substack{t \in \Z/3^{d_0}\Z\\ t\equiv6275 \pmod{3^8}}} Z_{j_0}(t) > \frac{13}{15}. \end{equation} Now we bring $X$ into the picture, and seek a large enough bound for $X$ such that it is reachable from some $j$ that is large enough for the estimates below. Proposition~\ref{prop:coverage} then tells us the following: \begin{equation}\label{eqn:reachable} \text{ Let $t \ge 2^{66176}$. Then every $X \ge 2^{2^{352}} t$ is reachable from some $j \ge 23000$. } \end{equation} This requires another hypothesis on $t$: \begin{equation}\label{hyp:bound} t \ge 2^{66176}. \tag{H3} \end{equation} We now provide an estimate to connect the weighted density to the terminal weighted density. Precisely, for $j \ge 23000$ and $X$ reachable from $j$, according to Proposition~\ref{prop:terminal-errors}, \begin{equation}\label{eqn:terminal-error} |Z^\term_{j,X}(t) - Z_j(t)| \le 2^{169}\cdot0.993^{j}. \end{equation} And finally an inequality to connect the terminal weighted density to the total weight: for any $j$ and any $X$ reachable from $j$, \eqref{eq:census-short} provides us with the bound \begin{equation}\label{eqn:terminal-total-ineq} Z^\term_{j,X}(t) \le 2^{177} t^{14/11} \beta_X(t) + 2^{-32}. \end{equation} \subsubsection{Final proof}\label{sec:outline-final-fake} We now combine the five estimates above. Firstly from the estimate on the average weighted density \eqref{eqn:average-bound}, we know that there is some residue $y_0 \in \Z/3^{d_0}\Z$ with \[Z_{j_0}(y_0) > \frac{13}{15},\] which leads to our final hypothesis on $t$: \begin{equation}\label{hyp:residue} t \equiv y_0 \pmod{3^{d_0}} \tag{H4} \end{equation} Now following the reachability estimate \eqref{eqn:reachable}, we let $X \ge 2^{2^{352}} t$, with $j \ge 23000$ so that $X$ is reachable from $j$. This lets us use the estimate on propagation error \eqref{eqn:propagation-error}, which tells us that the errors from generation $j_0$ onwards (Lemma~\ref{lem_Nstar_tail}) sum to less than $\frac67$, so that we can obtain \[Z_j(t) > 2^{-28},\] at which point the estimate on terminal weighted density \eqref{eqn:terminal-error} gives us \[Z^\term_{j,X}(t) > 2^{-29}.\] Now the inequality linking terminal weighted density with total weight \eqref{eqn:terminal-total-ineq} gives us \[\beta_X(t) > 2^{-207} t^{-14/11},\] which we can substitute back into the reduction in Section~\ref{sec:outline-reduction} to obtain the count we desired, namely that \[\#\{s \in [X, 32X) ~\text{maps to}~t\} > 2^{-207} t^{-25/11} X,\] subject to the hypotheses \eqref{hyp:odd}, \eqref{hyp:not-cycle}, \eqref{hyp:bound}, \eqref{hyp:residue}. This is Proposition~\ref{prop:core}. \subsubsection{Discharging the hypotheses: choosing a seed} \label{sec:outline-seed} Recall the hypotheses require that $t \ge 2^{66176}$ is odd, $t$ is not part of a cycle, and $t$ has a specific residue modulo $3^{d_0}$. We now describe the process of removing those hypotheses, which mirrors Proposition~\ref{prop:seed}. Starting with an arbitrary $t$ with $3 \nmid t$, we will obtain a seed $t_1$ that satisfies the hypotheses above, with some constraints between the seed $t_1$ and the original target $t$. The seed $t_1$ will be chosen from $\frac{2^a t - 1}{3}$, so that $t_1$ will reach $t$ with only one odd step at the beginning, and the rest of the steps will be the even step where the value is divided by $2$. This discharges $t_1$ being odd (Hypothesis~\eqref{hyp:odd}). If $t$ is odd, then $t_1$ will reach $t$ in one Syracuse step; otherwise $t_1$ will still reach the odd part of $t$ in one Syracuse step. Valid choices of $a$ that make $t_1$ an integer will always be either all the even numbers or all the odd numbers. By modular arithmetic, these choices of $t_1$ meet every residue class modulo any power of $3$ (Lemma~\ref{lem_repunit_residues}). This discharges the residue requirement (Hypothesis~\eqref{hyp:residue}). The bound requirement (Hypothesis~\eqref{hyp:bound}) is discharged by simply choosing a larger $a$, which leaves us with the requirement that $t_1$ cannot be part of a cycle (Hypothesis~\eqref{hyp:not-cycle}), which is discharged by choosing \emph{two} potential candidates for $t_1$. They both map to (the odd part of) $t$ in one step under the Syracuse map, so they cannot both be part of a cycle. The resulting seed $t_1$ can be bounded in terms of $t$ using Proposition~\ref{prop:seed}, which says that \[t_1 \le D_A t.\] \subsubsection{Final proof for general $t$} Using Section~\ref{sec:outline-final-fake} for the seed $t_1$, we deduce that for $X \ge 2^{2^{352}} t_1$, we have \[\#\{s \in [X, 32X) ~\text{maps to}~ t_1\} > 2^{-207} t_1^{-25/11} X.\] Translating this back to $t$, using the bound $t_1 \le D_A t$, gives us that for $X \ge D_A t$, we have \[\#\{s \in [X, 32X) ~\text{maps to}~ t\} \ge t^{-25/11} D_A^{-1} X.\] The exact version of this bound is Proposition~\ref{prop:internal}. Note that there is some abuse of notation here considering that $D_A$ is a triple exponential and hence absorbs many smaller operations. This also covers replacing $X$ with $\frac1{32}X$ to align with the main theorem counting numbers $< X$. For $X < D_A t$ the count $\floor{t^{-25/11} D_A^{-1} X}$ in the main theorem is $0$, so no lower bound on $X$ is needed. \subsection{The bound for the number of steps} What remains is control on the length of the words involved, as well as their degrees (Section~\ref{sec:steps}). This follows from the construction since at each generation we pick the words at their first crossing with the line, which puts constraints on their expected lengths and degrees. Recall that the heuristic number of steps is $3.476 \log \frac{n}{t}$ accelerated steps and $10.428 \log \frac{n}{t}$ ordinary steps. The extra slack in the main theorem allows the bounds on step count to hold. We also use the fact that the seed $t_1$ is chosen to reach (the odd part of) the target $t$ in one accelerated step, which provides a simple bound for also the number of ordinary steps for this part. \section{Words and residue densities}\label{sec:words} This section makes the objects of Section~\ref{sec:outline} precise: valid words, their weights and offsets, the reduction to a lower bound for the total weight, and the residue density with its branch transfers. A \emph{word} $w=(a_1,\ldots,a_d)$ is a finite sequence of positive integers, of length $|w|=d$. It describes a walk backwards along the Syracuse map $S$: each letter $a$ picks the preimage $(2^an-1)/3$ of $n$ under $S$, as in Section~\ref{sec:backwards}. Starting from a positive odd $n$, the \emph{inverse trajectory} of $w$ is \[ x_0=n,\qquad x_i=\frac{2^{a_i}x_{i-1}-1}{3}\quad(1\le i\le|w|). \] The word is \emph{valid at $n$} if all $x_i$ are positive odd integers. Then $3x_i+1=2^{a_i}x_{i-1}$ with $x_{i-1}$ odd, so $S(x_i)=x_{i-1}$: the Collatz map $T$ takes $x_i$ to $x_{i-1}$ in one step $x\mapsto3x+1$ followed by $a_i$ halvings. Hence the \emph{source} $\src(w,n)=x_{|w|}$ reaches $n$ in $|w|$ accelerated steps and $|w|+\deg(w)$ ordinary steps, where \begin{gather*} \deg_i(w)=a_1+\cdots+a_i,\qquad \deg(w)=\deg_{|w|}(w),\\ \wt(w)=3^{|w|}2^{-\deg(w)},\qquad\off(w)=\sum_{i=1}^{|w|}3^{i-1}2^{-\deg_i(w)} \end{gather*} are the \emph{partial degrees}, the \emph{degree}, the \emph{weight} and the \emph{offset} of $w$. Iterating $x_{i-1}=(3x_i+1)/2^{a_i}$ gives the basic identity \begin{equation}\label{eq:affine} n=\wt(w)\src(w,n)+\off(w), \end{equation} which defines $\src(w,n)=(n-\off(w))/\wt(w)$ for every word. For a concatenation $vw$, \begin{equation}\label{eq:concat} \wt(vw)=\wt(v)\wt(w),\qquad \off(vw)=\off(v)+\wt(v)\off(w). \end{equation} For example, $w=(3,2)$ at $n=5$ gives $x_1=13$ and $x_2=17$, and indeed $\frac9{32}\cdot17+\frac7{32}=5$. \begin{remark}[Validity is a congruence; cf.~{\cite[Section~2]{Mazur}, \cite[Lemma~2.1]{Tao}}]\label{rem:admissible} A word $w$ is valid at a positive odd $n$ if and only if $n\equiv\off(w)\pmod{3^{|w|}}$. Indeed $2^{\deg(w)}\off(w)$ is an integer, so validity and \eqref{eq:affine} give the congruence. Conversely, if it holds then $x_{|w|}$ is an integer; the forward relations put every $x_i$ in $\Z[1/2]$ and the backward relations put it in $\Z[1/3]$, so every $x_i$ is an integer, odd because $2^{a_i}x_{i-1}-1$ is odd, and positive. \end{remark} \subsection{Distinct sources and the reduction} To count sources through the weights of their words, distinct words must have distinct sources; this holds unless the target lies on a cycle. A positive odd integer $y$ is \emph{$S$-periodic} if $S^{\circ j}(y)=y$ for some $j\ge1$ (that is, $y$ lies on a cycle of $S$), where $f^{\circ k}$ denotes the $k$-fold iterate of a map $f$. \begin{lemma}[Periodic points]\label{lem_syr_periodic_fiber}\label{lem_orbit_hits_seed_once} Let $y,y'$ be positive odd integers. \begin{enumerate} \item If $y$ and $y'$ are $S$-periodic and $S(y)=S(y')$, then $y=y'$. \item If $y$ is not $S$-periodic, then for every positive odd $n$ there is at most one $r\in\N$ with $S^{\circ r}(n)=y$. \end{enumerate} \end{lemma} \begin{proof} For (1), let $S^{\circ j}(y)=y$ and $S^{\circ j'}(y')=y'$ with $j,j'\ge1$; then $r=jj'$ satisfies $S^{\circ r}(y)=y$ and $S^{\circ r}(y')=y'$, so $y=S^{\circ(r-1)}(S(y))=S^{\circ(r-1)}(S(y'))=y'$. For (2), if $S^{\circ r}(n)=y=S^{\circ r'}(n)$ with $r0$ and a positive odd $n$, let $\beta_X(n)$ be the total weight of the words valid at $n$ whose source lies in $[X,32X)$. If $n$ is not $S$-periodic, these sources are distinct by Lemma~\ref{lem_distinct_sources}, and each such word has $\wt(w)\le n/\src(w,n)\le n/X$ by \eqref{eq:affine}, since $\off(w)\ge0$. Hence \begin{equation}\label{eq:charge} \#\{\src(w,n):w\text{ valid at }n,\ \src(w,n)\in[X,32X)\}\ge\frac Xn\,\beta_X(n). \end{equation} \subsection{The random model and the residue density} By Remark~\ref{rem:admissible}, the total weight of the words of length $d$ valid at $n$ depends only on $n$ modulo $3^d$; the random model computes it as a function on residues. Write $G_d=\Z/3^d\Z$, call $d$ its \emph{level}, and write $[x]_d\in G_d$ for the reduction of $x\in\Z[1/2]$; a function on $G_d$ is evaluated at such $x$ through $[x]_d$. Take independent letters with $\Prob(a_i=a)=2^{-a}$ for $a\ge1$, and call $W$ the resulting random word; a word $w$ occurs as a prefix of $W$ with probability $2^{-\deg(w)}$. Let the \emph{offset law} $\mu_d$ be the probability mass function on $G_d$ of the offset residue $[\off(W_{\le d})]_d$ of the first $d$ letters, and put the \emph{residue density} \begin{equation}\label{eq:rho} \rho_d(y)=3^d\mu_d(y). \end{equation} Write $\av df=3^{-d}\sum_{y\in G_d}f(y)$ for $f:G_d\to\C$, and $\pr_{d,m}:G_d\to G_m$ ($m\le d$) for reduction; then $\av d{f\circ\pr_{d,m}}=\av mf$ and $\av d{\rho_d}=1$. Reduction modulo $3^m$ sends $\mu_d$ to $\mu_m$ (\emph{projectivity}). For $d\ge1$ the law lives on units, since $\off(W_{\le d})\equiv2^{-a_1}\pmod3$. By Remark~\ref{rem:admissible}, \begin{equation}\label{eq:rho-meaning} \sum_{|w|=d}\wt(w)\,\mathbf 1[w\text{ valid at }n]=\rho_d(n), \end{equation} where $\mathbf 1[E]$ is $1$ if the statement $E$ holds and $0$ otherwise. To average quantities such as $\rho_k(\src(w,n))$ over the residue of $n$, we transport functions along words as in \cite[Section~2]{Mazur}. For a word $w$, the map $\sigma_w:G_k\to G_{k+|w|}$, $\sigma_w(y)=\wt(w)y+\off(w)$, is well-defined and injective, since its linear coefficient is $3^{|w|}$ times a unit. For $f$ on $G_k$, the \emph{branch transfer} $\mathcal T_wf$ on $G_{k+|w|}$ equals $\wt(w)f(y)$ at $\sigma_w(y)$ and zero off the image. By \cite[Lemma~2.1]{Mazur}, \begin{equation}\label{eq:transfer-mean} \av{k+|w|}{\mathcal T_wf}=2^{-\deg(w)}\av kf,\qquad \av{k+|w|}{|\mathcal T_wf|}=2^{-\deg(w)}\av k{|f|}. \end{equation} For positive odd $n$, Remark~\ref{rem:admissible} and injectivity of $\sigma_w$ give \begin{equation}\label{eq:fiber-source} (\mathcal T_wf)(n)=\begin{cases}\wt(w)f(\src(w,n)),&w\text{ valid at }n,\\0,&\text{otherwise}.\end{cases} \end{equation} By \eqref{eq:concat}, $\mathcal T_w\rho_k$ is $3^{k+|w|}$ times the law of the offset residue of $W_{\le k+|w|}$ restricted to the event that $W$ begins with $w$. \section{Mixing}\label{sec:mix} This section proves the mixing lemma of Section~\ref{sec:outline} (Proposition~\ref{prop:mix}) from the Fourier bound \eqref{eq:fourier}, and derives the transfer estimate used by propagation and by the terminal error (Lemma~\ref{lem:finite-transfer}). Here $n$ denotes a level. The Fourier bound is proved for two parameter sets, indexed by $\iota\in\{\mathrm o,\mathrm b\}$ (Table~\ref{tab:fourier-params}): the original set $\mathrm o$, whose larger exponent serves the terminal error and the census, and the bootstrap set $\mathrm b$, whose much smaller threshold serves propagation. Put \begin{equation}\label{eq:exponents} A_{\mathrm o}=\frac{21193}{10000},\qquad A_{\mathrm b}=\frac{17}{10},\qquad a_\iota=A_\iota-\frac14,\qquad n_0=2^{80}, \end{equation} so $a_{\mathrm o}=\frac{18693}{10000}$ and $a_{\mathrm b}=\frac{29}{20}$. Theorem~\ref{lem_ch_primitive_decay}, an explicit form of \cite[Proposition~1.17]{Tao} proved in Sections~\ref{sec:fb-black}--\ref{sec:fb-conclusion}, gives for each $\iota$, every $n\ge1$ and every frequency $\xi\in G_n$ prime to $3$ the \emph{Fourier bound} \begin{equation}\label{eq:fourier} |\widehat\mu_n(\xi)|\le\Bigl(\frac{D_F(\iota)}n\Bigr)^{A_\iota},\qquad \widehat\mu_n(\xi)=\sum_{y\in G_n}\mu_n(y)e^{-2\pi\mathrm i\xi y/3^n}, \end{equation} with $D_F(\iota)$ and $B_F(\iota)$ as in Definition~\ref{def_Dstar}; by Lemma~\ref{lem_s02_Dstar_eq}(3), $\log_2B_F(\mathrm o)<325.7939550288$ and $\log_2B_F(\mathrm b)<88.1188851177$. Mixing is proved first between levels whose ratio is at most $\frac{27}{25}$ (Lemma~\ref{lem:shell-joint}) and then along a geometric chain of levels in ratio $c_{\mathrm{ch}}=\frac{1079}{1000}$. The chain is summed exactly by the \emph{mixing profile} \begin{equation}\label{eq:mix-profile} \mathfrak M_\iota(x)=18B_F(\iota)x^{-a_\iota}(\mathfrak c_\iota\log x+\mathfrak d_\iota)+\mathfrak sx^{-2}\qquad(x\ge n_0), \end{equation} where, with $\mathfrak z_\iota=c_{\mathrm{ch}}^{a_\iota}$, \[ \mathfrak c_\iota=\frac1{\mathfrak z_\iota-1},\qquad\mathfrak d_\iota=\frac{\mathfrak z_\iota\log c_{\mathrm{ch}}}{(\mathfrak z_\iota-1)^2},\qquad\mathfrak s=\frac{15}{c_{\mathrm{ch}}^2-1}=\frac{15000000}{164241}. \] \begin{proposition}[Fine-scale mixing]\label{prop:mix} Let $\iota\in\{\mathrm o,\mathrm b\}$. For integers $n_0\le m\le d$, \begin{equation}\label{eq:mix} \av d{|\rho_d-\rho_m\circ\pr_{d,m}|}\le\mathfrak M_\iota(m). \end{equation} The profile $\mathfrak M_\iota$ is nonincreasing on $[n_0,\infty)$, and for real $x\ge n_0$ \begin{equation}\label{eq:mix-power} \mathfrak M_{\mathrm o}(x)\le126B_F(\mathrm o)x^{-a_{\mathrm o}}\log x+105x^{-2}\le2^{365}x^{-a_{\mathrm o}}\log x,\qquad\mathfrak M_{\mathrm b}(x)\le2^{96}x^{-a_{\mathrm b}}\log x. \end{equation} \end{proposition} \subsection{Tail estimates}\label{sec:first-crossing} Mixing discards the random words whose partial degrees or offsets are atypical; two tail bounds control them. The first is a Chernoff bound for partial degrees. \begin{lemma}[Geometric tail]\label{lem:geometric-tail} For real $\mathfrak t<\log2$ put $\mathsf M_{\mathrm{geo}}(\mathfrak t)=\E e^{\mathfrak t(a_1-2)}=e^{-\mathfrak t}/(2-e^{\mathfrak t})$. Then $0\le\log\mathsf M_{\mathrm{geo}}(\mathfrak t)\le8\mathfrak t^2$ for $|\mathfrak t|\le1/4$, and $\log\mathsf M_{\mathrm{geo}}(\mathfrak t)\le9\mathfrak t^2/8$ for $|\mathfrak t|\le1/32$. For integers $d\ge1$ and real $x\ge0$, \begin{equation}\label{eq:geometric-tail} \Prob(|\deg_d(W)-2d|\ge x)\le2\exp\left(-\min\{x^2/(32d),x/8\}\right). \end{equation} \end{lemma} \begin{proof} The formula for $\mathsf M_{\mathrm{geo}}$ is a geometric series. Its logarithm has value and derivative zero at $0$, and its second derivative $2e^{\mathfrak t}/(2-e^{\mathfrak t})^2$ is nonnegative and increasing, at most $6$ on $|\mathfrak t|\le1/4$ (as $e^{1/4}\le4/3$) and at most $\frac{496}{225}<\frac94$ on $|\mathfrak t|\le1/32$ (as $e^{1/32}\le32/31$); Taylor's formula gives the bounds. Since $\E e^{\mathfrak t(\deg_d(W)-2d)}=\mathsf M_{\mathrm{geo}}(\mathfrak t)^d$, the Cram\'er--Chernoff method \cite[Section~2.2]{BLM} for $\pm(\deg_d(W)-2d)$ with $\mathfrak t=\min(x/(16d),1/4)$ gives \eqref{eq:geometric-tail} (cf.~\cite[Section~3.1]{Mazur}). \end{proof} The second bounds the offset, which has a $1/x$ tail. \begin{lemma}[Offset tail]\label{lem_mx_offset_tail} For every $n\in\N$ and real $x\ge0$, $\Prob(\off(W_{\le n})\ge x)\le7/(x+2)$. \end{lemma} \begin{proof} First, for real $x\ge5$, \begin{equation}\label{eq:tail-step} 3\sum_{a\ge1}\frac{2^{-a}}{2^ax+5}\le\frac1{x+2}. \end{equation} Indeed $\frac{3\cdot2^{-a}}{2^ax+5}=\frac{3\cdot4^{-a}}x-\frac{15\cdot4^{-a}}{x(2^ax+5)}$; summing with $\sum_a4^{-a}=\frac13$ and keeping the terms $a=1,2$ of the subtracted series, it suffices that $\frac2{x+2}\le\frac{15(18x+25)}{16(2x+5)(4x+5)}$, that is $15(18x+25)(x+2)-32(2x+5)(4x+5)=14x^2-45x-50\ge0$, which holds for $x\ge5$. Now induct on $n$. For $n=0$ the offset is $0$, and $1\le7/2$. For $x<5$ the bound exceeds $1$. For $x\ge5$, write $W_{\le n}=(a)v$; then $\off(W_{\le n})=2^{-a}(1+3\off(v))$, so the event is $\off(v)\ge x_a=(2^ax-1)/3\ge0$, where $v$ is a random word of length $n-1$ independent of $a$. By the induction hypothesis and \eqref{eq:tail-step}, the probability is at most $\sum_a2^{-a}\frac7{x_a+2}=21\sum_a\frac{2^{-a}}{2^ax+5}\le\frac7{x+2}$. \end{proof} \subsection{From the Fourier bound to mixing}\label{sec:fourier-to-mixing} For $m\le n$, let $\operatorname{Av}_{n,m}$ average a function on each fiber of $\pr_{n,m}$, and put $\Osc_{n,m}(f)=\sum_y|f(y)-\operatorname{Av}_{n,m}f(y)|$. A frequency $\xi\in G_n$ \emph{factors through} $G_m$ if $3^{n-m}\mid\xi$. By projectivity, $\operatorname{Av}_{n,m}\mu_n=3^{-n}\rho_m\circ\pr_{n,m}$, so $\Osc_{n,m}(\mu_n)=\av n{|\rho_n-\rho_m\circ\pr_{n,m}|}$. For $m\le r\le n$, $\operatorname{Av}_{n,m}=\operatorname{Av}_{n,m}\operatorname{Av}_{n,r}$ and projectivity identifies $\Osc_{n,m}(\operatorname{Av}_{n,r}\mu_n)$ with $\Osc_{r,m}(\mu_r)$, so the triangle inequality gives \begin{equation}\label{eq:osc-telescope} \Osc_{n,m}(\mu_n)\le\Osc_{n,r}(\mu_n)+\Osc_{r,m}(\mu_r). \end{equation} For functions on $G_n$, $\|\cdot\|_1$ and $\|\cdot\|_\infty$ are the unnormalized $\ell^1$ and supremum norms, and $*$ is convolution in counting measure. \begin{lemma}[Convolution oscillation]\label{lem:oscillation} Let $0\le m\le n$ be integers and $\Lambda\ge0$. Suppose $f,\psi$ are complex-valued functions on $G_n$ and $|\widehat\psi(\xi)|\le\Lambda$ for all frequencies that do not factor through $G_m$. Then \[ \Osc_{n,m}(f*\psi)^2\le\Lambda^23^n\sum_y|f(y)|^2. \] \end{lemma} \begin{proof} This is the computation of \cite[(6.10)--(6.11)]{Tao}. Fiber averaging keeps exactly the Fourier coefficients at frequencies factoring through $G_m$, so Cauchy--Schwarz and Parseval give \[ \|f*\psi-\operatorname{Av}_{n,m}(f*\psi)\|_1^2\le\sum_{\xi\text{ not factoring through }G_m}|\widehat f(\xi)\widehat\psi(\xi)|^2\le\Lambda^23^n\sum_y|f(y)|^2. \] \end{proof} \subsection{A fixed binary clock}\label{sec:adapted-cut} Following \cite[Section~6]{Tao}, we cut a random word of length $n$ where its partial degree first exceeds a height $N$ with $2^{N+1}$ just above $3^n$. The part before the cut, the \emph{head}, has offset determined up to few collisions, and the part after it is a fresh random word, whose offset law inherits the Fourier bound. Throughout this subsection $n\ge n_0$ and \begin{equation}\label{eq:shell-cut} N=\ceil{n\log_23}-1,\quad h=\ceil{\sqrt{128n\log n}},\quad k_-=\floor{\tfrac{N+1}2-h},\quad k_+=\ceil{\tfrac{N+1}2+h},\quad\mathfrak j=\ceil{2\log_2n}. \end{equation} From $1.58<\log_23<1.585$, $\log n\ge80\log2>55$ and the monotonicity of $(\log n)/n$ on $[n_0,\infty)$ one gets \begin{equation}\label{eq:shell-window} 64\log n\le h\le\frac n{21600},\qquad0\frac{2n}{15}$, so \eqref{eq:fourier} bounds it by $(15D_F(\iota)/(2n))^{A_\iota}=B_F(\iota)n^{-A_\iota}$. Lemmas~\ref{lem:oscillation} and~\ref{lem:head-packing} give \[ \Osc_{n,m}(\Gamma_{d,j}*\mathcal L_d)\le B_F(\iota)n^{-A_\iota}\sqrt{(|I_j|+2)p_{d,j}}. \] For $k_-\le d\le k_+-1$, $N\ge\frac{3n}2$ and $|2d-N|\le2h+4$, so Lemma~\ref{lem:subset-tail}(2) with $x=2^{j-1}\le2n^2$ gives $p_{d,j}\le p_dq_j$ with $q_0=1$ and $q_j=\min(1,2^{4-j})$. The values $\sqrt{(|I_j|+2)q_j}$ for $j\le4$ are $\sqrt3,\sqrt3,2,\sqrt6,\sqrt{10}$, with sum below $12$, and for $j\ge5$ they are at most $3$; as $\mathfrak j\ge4$, their sum over $j\le\mathfrak j$ is below $3\mathfrak j$. With the weights $\varpi_d=1+4(d-N/2)^2/N$, whose mean under the binomial law is $2$, and $\sum_{d\in\Z}\varpi_d^{-1}\le2+\frac\pi2\sqrt N$ (comparison with the integral), Cauchy--Schwarz gives $(\sum_d\sqrt{p_d})^2\le4+\pi\sqrt N<4\sqrt n$. Summing over the slices, the retained part of $\mu_n$ has oscillation at most \[ B_F(\iota)n^{-A_\iota}\cdot2n^{1/4}\cdot3\mathfrak j<18B_F(\iota)n^{-a_\iota}\log n, \] by \eqref{eq:shell-window}. Fiber averaging is an $\ell^1$ contraction, so the rest adds at most twice its probability, $8n^{-16}+14n^{-2}\le15n^{-2}$, by \eqref{eq:shell-complement}. \end{proof} \begin{proof}[Proof of Proposition~\ref{prop:mix}] Fix $\iota$ and write $a=a_\iota$, $c=c_{\mathrm{ch}}$, $\mathfrak z=\mathfrak z_\iota$, $\mathfrak c=\mathfrak c_\iota$, $\mathfrak d=\mathfrak d_\iota$, $\mathfrak M=\mathfrak M_\iota$ and $\mathfrak M^{\mathrm{loc}}=\mathfrak M^{\mathrm{loc}}_\iota$. As $1\le a\le2$, $1<\mathfrak z\le c^2<2$, so $\mathfrak c\ge1$, $\mathfrak d>0$ and $\mathfrak s\ge15$; hence $\mathfrak M^{\mathrm{loc}}\le\mathfrak M$ on $[1,\infty)$. For $x\ge n_0$, $a\log x\ge1$, and then $x^{-a}\log x$ is nonincreasing (its logarithmic derivative is $(1-a\log x)/x$); so $\mathfrak M$ and $\mathfrak M^{\mathrm{loc}}$ are nonincreasing on $[n_0,\infty)$. Since $(cx)^{-a}=x^{-a}/\mathfrak z$, $\log(cx)=\log x+\log c$, $(\mathfrak c+1)/\mathfrak z=\mathfrak c$, $((\mathfrak c+1)\log c+\mathfrak d)/\mathfrak z=\mathfrak d$ and $(\mathfrak s+15)/c^2=\mathfrak s$, the profile satisfies the exact identity \[ \mathfrak M(cx)+\mathfrak M^{\mathrm{loc}}(cx)=\mathfrak M(x)\qquad(x>0). \] We prove $\Osc_{n,m}(\mu_n)\le\mathfrak M(m)$ for $n_0\le m\le n$ by induction on $n-m$; this is \eqref{eq:mix}. Let $q=\floor{27m/25}$; as $m\ge1000$, $q\ge cm>m$. If $n\le q$, Lemma~\ref{lem:shell-joint} gives $\Osc_{n,m}(\mu_n)\le\mathfrak M^{\mathrm{loc}}(n)\le\mathfrak M^{\mathrm{loc}}(m)\le\mathfrak M(m)$. Otherwise \eqref{eq:osc-telescope} with $r=q$, the induction hypothesis for $(n,q)$, Lemma~\ref{lem:shell-joint} for $(q,m)$ and monotonicity give \[ \Osc_{n,m}(\mu_n)\le\mathfrak M(q)+\mathfrak M^{\mathrm{loc}}(q)\le\mathfrak M(cm)+\mathfrak M^{\mathrm{loc}}(cm)=\mathfrak M(m). \] For \eqref{eq:mix-power} let $x\ge n_0$, so $\log x\ge80\log2>\frac{160}3$. For $\iota=\mathrm o$: the series $\log\frac{1+y}{1-y}=2\sum_{k\ge0}y^{2k+1}/(2k+1)$ at $y=\frac{79}{2079}$ and $\log(1+y)\le y$ give $\frac{158}{2079}\le\log c\le\frac{79}{1000}$, so $a_{\mathrm o}\log c\ge\frac{71}{500}$ and $\mathfrak z_{\mathrm o}\ge1+\frac{71}{500}+\frac12(\frac{71}{500})^2>\frac{23}{20}$. Hence $\mathfrak c_{\mathrm o}\le\frac{20}3$, and since $\mathfrak z/(\mathfrak z-1)^2$ decreases for $\mathfrak z>1$, $\mathfrak d_{\mathrm o}\le\frac{79}{1000}\cdot\frac{460}9=\frac{1817}{450}$. So \[ 18(\mathfrak c_{\mathrm o}\log x+\mathfrak d_{\mathrm o})\le18\Bigl(\frac{20}3+\frac3{160}\cdot\frac{1817}{450}\Bigr)\log x=\Bigl(120+\frac{49059}{36000}\Bigr)\log x<126\log x, \] and $\mathfrak s\le105$ as $15\cdot10^6\le105\cdot164241$. Then $x^{-2}\le x^{-a_{\mathrm o}}\le x^{-a_{\mathrm o}}\log x$ and $126B_F(\mathrm o)+105<2^{333}\le2^{365}$. For $\iota=\mathrm b$: the same series and the partial sum of order $8$ of the exponential series give $0.076034686275<\log c<0.076034686276$ and $\mathfrak z_{\mathrm b}>1.116557504$, hence $\mathfrak c_{\mathrm b}<8.5794562$ and $\mathfrak d_{\mathrm b}<6.24902664$; so $\mathfrak c_{\mathrm b}\log x+\mathfrak d_{\mathrm b}\le(\mathfrak c_{\mathrm b}+\frac3{160}\mathfrak d_{\mathrm b})\log x<8.7\log x$. With $B_F(\mathrm b)<2^{88.12}<1.09\cdot2^{88}$ and $\mathfrak s<92$, $\mathfrak M_{\mathrm b}(x)\le(18\cdot8.7\cdot1.09\cdot2^{88}+92)x^{-a_{\mathrm b}}\log x<2^{96}x^{-a_{\mathrm b}}\log x$. \end{proof} \subsection{Transfer through a prefix-disjoint family} Each generation of Section~\ref{sec:physical} appends one word from a family and then continues randomly; if the family captures almost all of the probability, the residue density after the appended word is close to the residue density of the unconditioned random word. For a finite family $\mathcal V$ of words write $\mass(\mathcal V)=\sum_{w\in\mathcal V}2^{-\deg(w)}$ for its \emph{mass} and call $1-\mass(\mathcal V)$ its \emph{deficit}. The family is \emph{prefix-disjoint} if no word is a proper prefix of another; then the events that $W$ begins with $w$ ($w\in\mathcal V$) are disjoint and $\mass(\mathcal V)\le1$. For $k\in\N$ and $Q\ge k+|w|$, write $\mathcal T_{w,Q}\rho_k=\mathcal T_w(\rho_k\circ\pr_{Q-|w|,k})$. \begin{lemma}[Finite transfer]\label{lem:finite-transfer} Let $\iota\in\{\mathrm o,\mathrm b\}$ and $d,k,m\in\N$, put $Q=d+k$, and suppose $k\ge n_0$ and $n_0\le m\le Q$. If $\mathcal V$ is a finite prefix-disjoint family whose words have length at most $d$, then \[ \av Q{\Bigl|\sum_{w\in\mathcal V}\mathcal T_{w,Q}\rho_k-\rho_m\circ\pr_{Q,m}\Bigr|}\le\mathfrak M_\iota(k)+\mathfrak M_\iota(m)+1-\mass(\mathcal V). \] \end{lemma} \begin{proof} This is \cite[(3.7)]{Mazur} in our normalization. Put $A^*=\sum_{w\in\mathcal V}\mathcal T_w\rho_{Q-|w|}$. Since $Q-|w|\ge k$, \eqref{eq:mix} bounds $\av{Q-|w|}{|\rho_k\circ\pr_{Q-|w|,k}-\rho_{Q-|w|}|}$ by $\mathfrak M_\iota(k)$, and \eqref{eq:transfer-mean} multiplies it by $2^{-\deg(w)}$; summing, the first sum differs from $A^*$ by at most $\mass(\mathcal V)\mathfrak M_\iota(k)\le\mathfrak M_\iota(k)$ in mean. By \eqref{eq:concat} and the disjointness of the events, $A^*$ is $3^Q$ times the restriction of $\mu_Q$ to the event that $W$ begins with a word of $\mathcal V$, so $0\le A^*\le\rho_Q$ and $\av Q{\rho_Q-A^*}=1-\mass(\mathcal V)$. Finally \eqref{eq:mix} bounds $\av Q{|\rho_Q-\rho_m\circ\pr_{Q,m}|}$ by $\mathfrak M_\iota(m)$. \end{proof} \section{The family of words}\label{sec:physical} This section constructs the families $L_j$ and $L_{j,X}$ of Section~\ref{sec:outline} and the weighted densities $Z_j$ and $Z^\term_{j,X}$. The estimates on scales, first-crossing families and the histogram are proved in Sections~\ref{sec:est-families}--\ref{sec:est-histogram}. \subsection{Scales and first crossings} Generation $j$ appends to each word a \emph{block}, a word of length about the \emph{scale} $\delta_j$ whose overshoot (defined below) is at most the \emph{cap} $R_j$. With $e_\delta=\ceil{\delta/100}$, the scales are $\delta_0=16544$ and $\delta_{j+1}=\delta_j+e_{\delta_j}$, and the caps are \[ R_j=29+\floor{j/56}. \] The first scale is large enough that the first block family is nearly complete (Lemma~\ref{lem_fc_first_deficit}); the increments make the sources of generation $j$ exceed $16^{\delta_j}$ (Lemma~\ref{lem_endpoint_large}); and the caps grow so that the losses $2^{-(R_j+1)}$ decay geometrically \eqref{eq:cap-rate}. Put $g=101/100$; the scales grow geometrically and linearly (Lemma~\ref{lem_scales_growth}(1)). The integer comparisons $101^{70}>2\cdot100^{70}$ and $101^{69}<2\cdot100^{69}$ give $1/70<\log_2g<1/69$. The \emph{levels} are $k_j=\floor{\delta_j/4}$. Put $R_\Sigma=\sum_{i2^{19}$), $\ell_\delta\le3\delta/5$ and $e_\delta\ge\delta/100$, $r_\delta\le\frac5{12}\cdot\frac{3\delta}5-\frac\delta{50}=\frac{23\delta}{100}$. Also $B_0(\ell_\delta)<\ell_\delta\log_23+1$, $2-\log_23>\frac{83}{200}$ (Lemma~\ref{lem_s03_log3_bounds}(1)), $\ell_\delta\ge3\delta/5-1$ and $e_\delta<\delta/100+1$ give \[ r_\delta>\frac{83}{200}\Bigl(\frac{3\delta}5-1\Bigr)-1-\frac\delta{50}-2=\frac{229}{1000}\delta-\frac{683}{200}. \] \end{proof} A word $w$ belongs to the \emph{first-crossing family} $\FC_u(\delta,R)$, where $R\in\N$, if $d^{\mathrm{lo}}_\delta<|w|\le d^{\mathrm{hi}}_\delta$, its partial degrees stay strictly below the line at lengths $d^{\mathrm{lo}}_\delta,\ldots,|w|-1$ (so $|w|$ is the \emph{first crossing}), and $H_{\delta,u}(|w|)\le\deg(w)\le H_{\delta,u}(|w|)+R$. Its \emph{overshoot} is $\deg(w)-H_{\delta,u}(|w|)\in[0,R]$. Such a family is finite and prefix-disjoint (Lemma~\ref{lem_first_crossing_prefix_disjoint}). The \emph{block family} $\FC(\delta,R)$, from which the blocks are drawn, is the subfamily of the first crossings of Section~\ref{sec:outline}, that is of $\FC_{r_\delta}(\delta,R)$, with length in $[\delta-\ell^{\mathrm c}_\delta,\delta+\ell^{\mathrm c}_\delta]$ (the \emph{length restriction}), where \[ \ell^{\mathrm c}_\delta=\min\left(\ceil{\sqrt{32\delta\ceil{\log_2\delta}}},\ell_\delta-1\right); \] it narrows the length spread for the histogram estimate \eqref{eq:histogram} and the step bounds at a deficit of order $\delta^{-3/2}$ (Lemma~\ref{lem_deficit_central}). For $\delta\ge2^{40}$, \begin{equation}\label{eq:width-late} 20000\,\ell^{\mathrm c}_\delta\le\delta. \end{equation} Indeed, with $k=\floor{\log_2\delta}\ge40$, $\ceil{\log_2\delta}\le k+1$, $2^k\le\delta$ and $(k+1)/2^k$ nonincreasing, \[ \frac{\ell^{\mathrm c}_\delta}\delta<\sqrt{\frac{32(k+1)}{2^k}}+\frac1\delta\le\sqrt{\frac{1312}{2^{40}}}+\frac1{2^{40}}\le\frac1{20000}, \] the last being the rational comparison $1312/2^{40}\le(1/20000-2^{-40})^2$. \begin{lemma}[Weight, offset and source of a first-crossing word]\label{lem_s05_block_weight} Let $\delta\ge256$, $u$ and $R\ge0$ be integers, and let $w\in\FC_u(\delta,R)$. Then \begin{enumerate} \item $2^{-R-1+r_\delta-u}(3/4)^\delta<\wt(w)<2^{1+r_\delta-u}(3/4)^\delta$; \item $0<\off(w)<2^\delta$; \item if $u=r_\delta$, then $16^{e_\delta}\wt(w)<\frac12$; \item for every odd $n\ge16^\delta$, \begin{equation}\label{eq:word-source} 2^{u-r_\delta-2}(4/3)^\delta n<\src(w,n)<2^{R+1+u-r_\delta}(4/3)^\delta n. \end{equation} \end{enumerate} \end{lemma} \begin{proof} For (1), $\wt(w)=3^{|w|}2^{-\deg(w)}$ and $H_{\delta,u}(|w|)\le\deg(w)\le H_{\delta,u}(|w|)+R$; insert \eqref{eq:hist-barrier}. For (2), as in \cite[proof of Proposition~3.1]{Mazur}: every summand of $\off(w)$ is positive and, since the letters are at least $1$, the $i$th summand is at most $3^{i-1}2^{-i}$; as $|w|\le d^{\mathrm{hi}}_\delta\le8\delta/5$ and $(3/2)^8<2^5$, $0<\off(w)<(3/2)^{|w|}<2^\delta$. For (3), $e_\delta\ge3$ and $\delta>100(e_\delta-1)$; the integer inequality $4^{100}>4096\cdot3^{100}$ says $(4/3)^{100}>16^3$, so $(4/3)^\delta>16^{3(e_\delta-1)}\ge4\cdot16^{e_\delta}$, and with (1), $16^{e_\delta}\wt(w)<\frac14(4/3)^\delta\cdot2(3/4)^\delta=\frac12$. For (4), which is \cite[(3.5)]{Mazur} for general $u$, (2) gives $0<\off(w)<2^\delta\le n/2$, so $\wt(w)\src(w,n)=n-\off(w)\in(n/2,n)$; insert (1). \end{proof} \subsection{The selector and the family \texorpdfstring{$L_j$}{Lj}} Consider the words $w=v_0\cdots v_{j-1}$ with $v_i\in\FC(\delta_i,R_i)$. Since each $\FC(\delta_i,R_i)$ is prefix-disjoint, such a word determines its \emph{blocks} $v_i$: if $v_0\cdots v_{j-1}w=v'_0\cdots v'_{j-1}w'$ with $v_i,v'_i\in\FC(\delta_i,R_i)$, then one of $v_0,v'_0$ is a prefix of the other, so $v_0=v'_0$, and cancelling and inducting gives $v_i=v'_i$ and $w=w'$. For $i\le j$ write $w_{\frac{s_{w_{16^{e_{\delta_i}}s_{w_{0$ be real. For an integer scale $\delta\ge256$ and a real $n>0$, set, as in \cite[Section~5]{Mazur}, \[ X^{\mathrm{lo}}_\delta(n)=\frac{(4/3)^\delta n}{4\cdot2^{r_\delta}},\qquad X^{\mathrm{hi}}_\delta(n)=2^{2r_\delta}X^{\mathrm{lo}}_\delta(n). \] By \eqref{eq:word-source}, every $v\in\FC_u(\delta,R)$ and every odd $n\ge16^\delta$ satisfy $2^uX^{\mathrm{lo}}_\delta(n)<\src(v,n)<2^{R+3+u}X^{\mathrm{lo}}_\delta(n)$. The real $X$ is \emph{reachable} at generation $j$ if $X^{\mathrm{lo}}_{\delta_j}(s_w)0.009950330853168$, this is at most $e^{-9097/10^6}<0.990945$. Evaluating $E^{\mathrm{mx}}_{j_0}$ with $\log_2B_F(\mathrm b)<88.1188851177$, $\mathfrak c_{\mathrm b}<8.5794562$, $\mathfrak d_{\mathrm b}<6.24902664$ (proof of Proposition~\ref{prop:mix}) and rational enclosures of $\log2$, $\log g$ and $e^x$ from partial sums of their series gives $E^{\mathrm{mx}}_{j_0}<0.007583$. For the second part the ratio is $(1+\frac1j)^{5/2}\frac{100}{101}\le0.990945$, by the integer comparison $(j_0+1)^5\cdot10^{16}\le j_0^5\cdot100085445^2$; and $2^8j_0^{5/2}g^{-j_0}<2^{8+34-140}<10^{-6}$, by $j_0^5<2^{68}$ and $g^{j_0}>2^{140}$. For the third part the ratio is $(1+\frac1j)^{5/2}\mathfrak y\le\frac{199}{200}$, by the comparison of $56$th powers $(j_0+1)^{140}\cdot101^{28}\cdot200^{56}\le2\cdot j_0^{140}\cdot100^{28}\cdot199^{56}$. As $\mathfrak y<1$, $\mathfrak y^{56}=g^{28}/2$ and $j_0\ge56\cdot175$, $\mathfrak y^{j_0}\le(g^{28}/2)^{175}\le2^{-104}$, by $101^{4900}\cdot2^{104}\le2^{175}\cdot100^{4900}$; so $2^{-20}j_0^{5/2}\mathfrak y^{j_0}<2^{-20+34-104}=2^{-90}$. Adding the three geometric bounds gives \eqref{eq:geometric-propagation}. \end{proof} \begin{lemma}[Propagation tail]\label{lem_Nstar_tail} $\sum_{j\ge j_0}E_j<\frac{7584}{9055}+2^{-82}<0.8376<\frac67$. Consequently, if $Z_{j_0}(t)>\frac67+2^{-28}$, then $Z_j(t)>2^{-28}$ for every $j\ge j_0$. \end{lemma} \begin{proof} Sum the two geometric series of \eqref{eq:geometric-propagation}: $0.007584/(1-0.990945)=\frac{7584}{9055}$ and $2^{-90}\cdot200<2^{-82}$. The consequence follows by summing \eqref{eq:variation} from $j_0$ to $j-1$. \end{proof} \subsection{Average at generation \texorpdfstring{$j_0$}{j0}} At generation $j_0$ the words are short enough that $Z_{j_0}(t)$ depends only on $t$ modulo $3^{d_0}$, where \begin{equation}\label{eq:endpoint} d_0=5\cdot2^{160}\ge1668728\,g^{j_0}, \end{equation} by the integer comparison $1668728\cdot101^{j_0}\le5\cdot2^{160}\cdot100^{j_0}$. So $2^{162}2^{55}>200\cdot\frac85\cdot101\cdot2^{40}$ and $k_{j_0}\le\delta_{j_0}/4$, the length plus $k_{j_0}$ is less than \[ \Bigl(\frac14+100\cdot\frac{20001}{20000}+\frac1{200}\Bigr)\delta_{j_0}=\frac{20052}{200}\delta_{j_0}<\frac{20052}{200}\cdot16644\,g^{j_0}\le1668728\,g^{j_0}\le d_0. \] For $w\in\bar L_{j_0}$, \eqref{eq:fiber-source} shows that the term of $w$ in the displayed sum, at a positive odd $t$, is $\wt(w)\rho_{k_{j_0}}(s_w)$ if $w$ is valid at $t$ and zero otherwise, so the sum is $Z_{j_0}(t)$. \end{proof} For integers $D\ge q\ge0$, $r\in G_q$ and real $x$, the \emph{joint law} of the offset and the offset residue of the first $q$ letters is \begin{equation}\label{eq:joint-law} F_{D,q}(r,x)=\Prob\bigl(\off(W_{\le D})\le x,\ [\off(W_{\le q})]_q=r\bigr). \end{equation} \begin{lemma}[Joint law]\label{lem_s05_joint_cert_exists} For every $D\ge8$, $F_{D,8}([6275]_8,\frac34)\ge617014680840434\cdot2^{-62}$. \end{lemma} \begin{proof} Conditioning on the first letter $a$ and writing $W=(a)W'$, \eqref{eq:concat} gives $\off(W_{\le D})=2^{-a}(1+3\off(W'_{\le D-1}))$, and for $q\ge1$, $[\off(W_{\le q})]_q=r$ holds if and only if $3\mid2^a\tilde r-1$ and $[\off(W'_{\le q-1})]_{q-1}$ is the residue of $(2^a\tilde r-1)/3$, where $\tilde r$ is any integer representing $r$. Hence \[ F_{D,q}(r,x)=\sum_{a\ge1,\ 3\mid2^a\tilde r-1}2^{-a}F_{D-1,q-1}\Bigl(\Bigl[\frac{2^a\tilde r-1}3\Bigr]_{q-1},\frac{2^ax-1}3\Bigr), \] and the level $q=0$ satisfies the same recursion without the residue condition and $F_{D,0}(0,x)\ge\max(0,1-7/(x+2))$ by Lemma~\ref{lem_mx_offset_tail}. Lemma~\ref{lem:joint-tables} gives tables of integers, read as nonnegative step functions of the offset on a finite grid, times $2^{-62}$: a nondecreasing one at level $0$, at most the maximum of $1-7/(x+2)$ and the right side of the recursion evaluated on it, and ones at levels $1\le q\le8$, at most the right side of the recursion evaluated on the tables of level $q-1$. Induction on $D$, using the monotonicity of $F_{D,q}$ in $x$, shows that the tables are below the joint laws for every $D$; the entry of the level-$8$ table at $([6275]_8,\frac34)$ is $617014680840434$. \end{proof} \begin{lemma}[Selected mass in a residue class]\label{lem_s05_tuple_mass}\label{lem_survival_product} For every $j\ge29$, the mass of the words of $\bar L_j$ whose first eight letters have offset residue $[6275]_8$ exceeds \[ \mathfrak m_8=\Bigl(\frac{617014680840434}{2^{62}}-\frac1{20000000}\Bigr)\Bigl(\frac{199}{200}-2^{-592}\Bigr). \] \end{lemma} \begin{proof} Every block of scale $\delta_0$ has length greater than $d^{\mathrm{lo}}_{16544}=6618\ge8$, so the offset residue of the first eight letters is that of $v_0$. The degree is additive under concatenation and the conditions of \eqref{eq:selector} concern separate blocks, so the mass in question is $m'_0\prod_{0\frac{617014680840434}{2^{62}}-\frac1{20000000}. \] Likewise Lemma~\ref{lem_mx_offset_tail} gives $m_i\ge \bar m_i-c_i$ with $\bar m_i=\mass(\FC(\delta_i,R_i))$, $c_i=7/(2^{600}+2)$ for $0\frac{199}{200}$ by Lemma~\ref{lem_fc_late_survival}. \end{proof} \begin{proposition}[Average at generation $j_0$]\label{prop:average} The mean of $Z_{j_0}$ over the residues $y\in G_{d_0}$ with $y\equiv6275\pmod{3^8}$ is at least $6561\mathfrak m_8>\frac{13}{15}+2^{-28}$. In particular some $y_0\in G_{d_0}$ has $Z_{j_0}(y_0)>\frac{13}{15}$. \end{proposition} \begin{proof} Let $w\in\bar L_{j_0}$, so $|w|\ge8$. By \eqref{eq:concat}, $\wt(w)\equiv0$ and $\off(w)\equiv\off(w_{\le8})\pmod{3^8}$ in $\Z[1/2]$, so the image of $\sigma_w$ lies in the residue class of $\off(w_{\le8})$ modulo $3^8$, and $\mathcal T_{w,d_0}\rho_{k_{j_0}}$ vanishes off it. By \eqref{eq:transfer-mean} and $\av k{\rho_k}=1$, its sum over $G_{d_0}$ is $3^{d_0}2^{-\deg(w)}$. By Lemma~\ref{lem_ph_conductor}, the sum of $Z_{j_0}$ over the class of $6275$ is therefore $3^{d_0}$ times the mass in Lemma~\ref{lem_s05_tuple_mass}, which exceeds $3^{d_0}\mathfrak m_8$ as $j_0\ge29$. The class has $3^{d_0-8}$ elements, and $6561\mathfrak m_8-\frac{13}{15}-2^{-28}>0.0064$ by Lemma~\ref{lem:joint-tables}. \end{proof} \subsection{Reachability} The \emph{generation-$j$ ranges} $(X^{\mathrm{lo}}_{\delta_j}(s_w),X^{\mathrm{hi}}_{\delta_j}(s_w)]$, $w\in L_j$, with \emph{lower ends} $X^{\mathrm{lo}}_{\delta_j}(s_w)$ and \emph{upper ends} $X^{\mathrm{hi}}_{\delta_j}(s_w)$, intersect in the set of $X$ reachable at $j$; consecutive intersections overlap and move to infinity. The overlap holds because the sources of $L_j$ differ by a factor at most $2^{R_\Sigma}$ (Lemma~\ref{lem_endpoint_ratio}), which \eqref{eq:Rsum} bounds. \begin{lemma}[Consecutive generations overlap]\label{lem_overlap} Let $t\ge16^{16544}$ be odd and $j\ge J_{\mathrm c}$. For all $w'\in L_j$ and $w\in L_{j+1}$, $X^{\mathrm{lo}}_{\delta_{j+1}}(s_w)2$, $\delta_j\ge16544\cdot2^k\ge16544\binom k3\ge148896k^2$, as $(k-1)(k-2)\ge54k$; and $j<71k$, so $\frac{37}{1000}\delta_j\ge5041k^2>j^2$. Also $\delta_j\le\delta_{j+1}\le\frac{101}{100}\delta_j+1$. Lemmas~\ref{lem_endpoint_large} and~\ref{lem_endpoint_ratio} give $s_w\le2^{R_j+1}(4/3)^{\delta_j}s_{w_{\frac{37}{1000}$, it suffices that $R_j+R_\Sigma+10<\frac{37}{1000}\delta_j$, and indeed, by \eqref{eq:Rsum}, $R_j+R_\Sigma+10<38+\frac j{56}+\frac{j^2}{82}\le j^2$. \end{proof} \begin{proposition}[Reachability]\label{prop:coverage} Let $t\ge16^{16544}$ be odd. Every real $X\ge2^{2^{352}}t$ is reachable at some generation $j\ge J_{\mathrm c}$. \end{proposition} \begin{proof} We follow \cite[Lemma~6.2]{Mazur} in the effective form of \cite[Section~8.5]{Mazur}. Put $\operatorname{gr}(\delta)=2\delta-\floor{19\delta/12}$, $\mathfrak l_0=0$ and $\mathfrak l_{j+1}=\mathfrak l_j+R_j+1+\operatorname{gr}(\delta_j)$ (cf.~\cite[Section~8.2]{Mazur}). The inequality $2^{19}\le3^{12}$ gives $(4/3)^\delta\le2^{\operatorname{gr}(\delta)}$, so Lemma~\ref{lem_endpoint_large} and induction give $s_w\le2^{\mathfrak l_j}t$ for $w\in L_j$. By Lemma~\ref{lem_rb_bounds} and $\operatorname{gr}(\delta)<\frac{5\delta}{12}+1$, $X^{\mathrm{hi}}_\delta(n)=2^{r_\delta}(4/3)^\delta n/4\le2^{r_\delta+\operatorname{gr}(\delta)-2}n$ with $r_\delta+\operatorname{gr}(\delta)-2<\frac{97\delta}{150}-1<\floor{2\delta/3}$. Hence every upper end at generation $J_{\mathrm c}$ is at most $2^Bt$, where $B=\mathfrak l_{J_{\mathrm c}}+\floor{2\delta_{J_{\mathrm c}}/3}$. Using $R_j+1\le30+j/56$, Lemma~\ref{lem_scales_growth}(1) and $\sum_{j0$. Then the terminal shifts $u_w$, $w\in L_j$, take fewer than $j^2/82$ values. \end{lemma} \begin{proof} We follow \cite[proof of Proposition~5.2]{Mazur}. Assume $L_j\ne\emptyset$ and let $w_{\min}\in L_j$ have the least source. Since $X^{\mathrm{lo}}_{\delta_j}(n)$ is positive and linear in $n$, $u_w$ is nonincreasing in $s_w$, so $u_w\le u_{w_{\min}}$. By Lemma~\ref{lem_endpoint_ratio}, $s_w\le2^{R_\Sigma}s_{w_{\min}}$, so $2^{u_w+R_\Sigma}X^{\mathrm{lo}}_{\delta_j}(s_{w_{\min}})\ge X$ and $u_{w_{\min}}\le u_w+R_\Sigma$. Thus all shifts lie in a set of at most $R_\Sigma+10$ real. There is $\underline\rho_m:G_m\to\R$ with \[ 0\le \underline\rho_m\le\rho_m,\qquad \underline\rho_m\le\frac B2,\qquad\av m{\rho_m-\underline\rho_m}\le2n^{-8}+\frac{2^{13}\sqrt{n\log n}}B. \] \end{lemma} \begin{proof} Put $\ell_{\mathrm{cl}}=\ceil{\sqrt{256m\log n}}+\ceil{64\log n}$, $l_{\mathrm{cl}}=\ceil{\log_2(8\cdot3^m/B)}$ and $x_{\mathrm{cl}}=B/(4(2\ell_{\mathrm{cl}}+1))$, and let $\mathcal V$ be the set of words $u$ of length $m$ with $|\deg(u)-2m|\le\ell_{\mathrm{cl}}$, $\deg(u)\ge l_{\mathrm{cl}}$ and $\off(u)\le x_{\mathrm{cl}}$. Let $\underline\rho_m(y)=3^m\Prob(W_{\le m}\in\mathcal V,\ [\off(W_{\le m})]_m=y)$, so $0\le \underline\rho_m\le\rho_m$. Fix $y$ and a degree $l\ge l_{\mathrm{cl}}$. The integers $2^l\off(u)$, for the words $u\in\mathcal V$ of degree $l$ with offset residue $y$, are distinct, since offsets determine words of a fixed length \cite[Lemma~6.2]{Tao}, lie in $[0,2^lx_{\mathrm{cl}}]$ and are congruent modulo $3^m$; so there are at most $2^lx_{\mathrm{cl}}3^{-m}+1$ of them, each of probability $2^{-l}$. Summing over the at most $2\ell_{\mathrm{cl}}+1$ degrees $l\ge l_{\mathrm{cl}}$, \[ \underline\rho_m(y)\le(2\ell_{\mathrm{cl}}+1)x_{\mathrm{cl}}+3^m\sum_{l\ge l_{\mathrm{cl}}}2^{-l}=\frac B4+2\cdot3^m2^{-l_{\mathrm{cl}}}\le\frac B2. \] The mean $\av m{\rho_m-\underline\rho_m}$ is the probability that $W_{\le m}\notin\mathcal V$. By \eqref{eq:geometric-tail}, whose exponent is at least $8\log n$ at $x=\ell_{\mathrm{cl}}$, $\Prob(|\deg_m(W)-2m|>\ell_{\mathrm{cl}})\le2n^{-8}$. Next $\Prob(\deg_m(W)x_{\mathrm{cl}})<7/x_{\mathrm{cl}}=28(2\ell_{\mathrm{cl}}+1)/B$, and $2\ell_{\mathrm{cl}}+1<32\sqrt{n\log n}+128\log n+5\le165\sqrt{n\log n}$, as $\log n\ge1$ and $\log n\le\sqrt{n\log n}$. Finally $8+28\cdot165<2^{13}$. \end{proof} Let $t\ge16^{16544}$ be odd and not $S$-periodic, let $X$ be reachable at $j$, and let $w\in L_j$. A word $v\in\FC^\term_X(w,\delta_j,R_j)$ with overshoot $o$ gives, after subtracting $2i$ from its last letter, $i=\floor{o/2}$, a word $v'\in\FC^\term_X(w,\delta_j,1)$ with the same length, the same earlier letters and the mask, and with $\src(v,s_w)=\lift_i(\src(v',s_w))$ and $\wt(v)=4^{-i}\wt(v')$, since adding $2$ to the last letter turns a source $s'$ into $4s'+1$ \cite[proof of Proposition~5.3]{Mazur}; and $(v',i)$ determines $v$. So $Z^\term_{j,X}(t)$ is at most the left side of \eqref{eq:census-unfold} for $\mathfrak w=\rho_{k_j}$, $\mathcal S=\Src_{j,X}(t)$ and the weights $\upsilon_s=\wt(wv')\le t/X$ of the sources $s=\src(v',s_w)$, whose total is $\beta^\term_{j,X}(t)$. If $L_j$ is empty, $Z^\term_{j,X}(t)=0$ and \eqref{eq:census} below is trivial; otherwise reachability, $s_w\ge16^{\delta_j}$ and $r_{\delta_j}\le3\delta_j/10$ give $X>16^{\delta_j}/(4\cdot3^{\delta_j})>3^{k_j}$. Let $n\ge n_0$ be an integer and $B>0$, and put $m=\min(k_j,n)$. Apply Proposition~\ref{prop:census} with $q=k_j$, $\underline{\mathfrak w}=\underline\rho_m$ of Lemma~\ref{lem:clipping}, $U=B/2$ and $\Phi=(\rho_m-\underline\rho_m)\circ\pr_{k_j,m}+|\rho_{k_j}-\rho_m\circ\pr_{k_j,m}|$, which is nonnegative with $\rho_{k_j}\le \underline\rho_m\circ\pr_{k_j,m}+\Phi$. The second term of $\Phi$ vanishes if $k_j\le n$, and otherwise has mean at most $\mathfrak M_{\mathrm o}(n)\le2^{365}n^{-a_{\mathrm o}}\log n$ by \eqref{eq:mix} and \eqref{eq:mix-power}. Hence, for every integer $n\ge n_0$ and real $B>0$, \begin{equation}\label{eq:census} Z^\term_{j,X}(t)\le\frac23B\beta^\term_{j,X}(t)+44t\Bigl(2n^{-8}+\frac{2^{13}\sqrt{n\log n}}B+2^{365}n^{-a_{\mathrm o}}\log n\Bigr). \end{equation} With $n$ and $B$ chosen from $t$, the error term becomes negligible: \begin{equation}\label{eq:census-short} Z^\term_{j,X}(t)\le2^{177}t^{14/11}\beta^\term_{j,X}(t)+2^{-32}. \end{equation} Indeed, write $a=a_{\mathrm o}$ and $\mathfrak f=1+\log t$, and take $n=\ceil{x_t}$ with $x_t=(2^{420}t\mathfrak f)^{1/a}\ge2^{420/a}>n_0$, and $B=2^{52}t\sqrt{n\log n}$. Then $n<2x_t$ and $\log n\le\log2+\frac1a(420\log2+\log t+\log\mathfrak f)\le256\mathfrak f$, using $\log\mathfrak f\le\log t$ and $1+\frac{420}a<256$. So $2^{365}n^{-a}\log n\le2^{365+8-420}/t$, $2n^{-8}\le2/x_t^8\le2^{-419}/t$ and $2^{13}\sqrt{n\log n}/B=2^{-39}/t$; and $44(2^{-47}+2^{-419}+2^{-39})<2^{-32}$. Moreover \[ \sqrt{n\log n}\le2^{\frac92+\frac{210}a}t^{\frac1{2a}}\mathfrak f^{\frac12+\frac1{2a}}<2^{117}t^{\frac{5000}{18693}}\mathfrak f^{\frac{28693}{37386}}, \] and, as $t^{1079/205623}\ge1+\frac{1079}{205623}\log t$, $\mathfrak f^{28693/37386}\le\mathfrak f\le\frac{205623}{1079}t^{1079/205623}<2^8t^{1079/205623}$. Since $1+\frac{5000}{18693}+\frac{1079}{205623}=\frac{14}{11}$, $B<2^{52+117+8}t^{14/11}$, and \eqref{eq:census} gives \eqref{eq:census-short}. Since $\beta^\term_{j,X}(t)\le\beta_X(t)$, the same bound holds with $\beta_X(t)$. \section{Proof of the main theorem}\label{sec:finish} This section combines the key estimates into a count for a target $t$ satisfying the hypotheses of Section~\ref{sec:outline} (Proposition~\ref{prop:core}), chooses a seed that satisfies them (Proposition~\ref{prop:seed}), and deduces Theorem~\ref{thm:main}, using the step bounds of Section~\ref{sec:steps}. \subsection{The count under the hypotheses} \begin{proposition}[Count under the hypotheses]\label{prop:core}\label{prop:unmarked} Let $t\ge16^{16544}$ be odd and not $S$-periodic, with $Z_{j_0}(t)>\frac67+2^{-28}$. Then every real $X\ge2^{2^{352}}t$ is reachable at some generation $j\ge J_{\mathrm c}$, and at every such $j$ \begin{equation}\label{eq:unmarked} \beta^\term_{j,X}(t)>2^{-207}t^{-14/11},\qquad\#\Src_{j,X}(t)>2^{-207}t^{-25/11}X. \end{equation} \end{proposition} \begin{proof} Proposition~\ref{prop:coverage} gives $j$. As $j\ge J_{\mathrm c}>j_0$, Lemma~\ref{lem_Nstar_tail} gives $Z_j(t)>2^{-28}$, and \eqref{eq:terminal-small} gives $Z^\term_{j,X}(t)>2^{-28}-2^{-29}=2^{-29}$. By \eqref{eq:census-short}, \[ \beta^\term_{j,X}(t)>(2^{-29}-2^{-32})2^{-177}t^{-14/11}=7\cdot2^{-209}t^{-14/11}>2^{-207}t^{-14/11}, \] and the second bound follows by \eqref{eq:charge-term}. \end{proof} These hypotheses follow from \eqref{hyp:odd}--\eqref{hyp:residue}: \eqref{hyp:bound} is $t\ge2^{66176}=16^{16544}$, not being $S$-periodic is \eqref{hyp:not-cycle}, and \eqref{hyp:residue} gives $Z_{j_0}(t)=Z_{j_0}(y_0)>\frac{13}{15}>\frac67+2^{-28}$ by Lemma~\ref{lem_ph_conductor}, as $\frac{13}{15}-\frac67=\frac1{105}$. \subsection{Choosing a seed} A general target need not satisfy the hypotheses of Proposition~\ref{prop:core}, so we apply it to a \emph{seed} $t_1$ that does, chosen among the integers that reach the target in one odd step. Let $t$ be a positive integer with $3\nmid t$. As $2^{66178}=4^{33089}\equiv1\pmod3$, exactly one $a^\circ\in\{66178,66179\}$ has $2^{a^\circ}t\equiv1\pmod3$, and the \emph{candidate seeds} are the integers $(2^at-1)/3$ with $a\equiv a^\circ\pmod2$ and $a\ge a^\circ$. They increase with $a$, and $3\cdot(2^at-1)/3+1=2^at$, so a candidate reaches $t$ after one odd step and $a$ halvings. \begin{lemma}[Candidate residues]\label{lem_repunit_residues} Let $t'$ be an integer with $t'\equiv1\pmod3$, and let $q,i_0\in\N$. Then the integers $(4^it'-1)/3$, $i_0\le i2^{4+\frac{317}{200}d_0}>16\cdot3^{d_0}. \end{equation} \begin{proposition}[The seed]\label{prop:seed} Let $t$ be a positive integer with $3\nmid t$. There is a candidate seed $t_1=(2^at-1)/3$ with $a<66180+4\cdot3^{d_0}$ that is odd, not $S$-periodic, satisfies \[ 2^{66176}t\frac{13}{15}, \] and reaches $t$ in $1+a$ ordinary steps; $S(t_1)$ is the odd part of $t$. \end{proposition} \begin{proof} By Proposition~\ref{prop:average} there is $y_0\in G_{d_0}$ with $Z_{j_0}(y_0)>\frac{13}{15}$. Apply Lemma~\ref{lem_repunit_residues} with $t'=2^{a^\circ}t$ and $q=d_0$, once with $i_0=0$ and once with $i_0=3^{d_0}$: this gives two candidate seeds $(4^it'-1)/3$, $i<2\cdot3^{d_0}$, congruent to $y_0$ modulo $3^{d_0}$, with $a=a^\circ+2i\le66177+4\cdot3^{d_0}$. Each is odd, as $2^at-1$ is odd, satisfies $Z_{j_0}=Z_{j_0}(y_0)$ by Lemma~\ref{lem_ph_conductor}, and lies between $(2^{66178}t-1)/3>2^{66176}t$ and $2^at/3<2^{5\cdot3^{d_0}}t2^{2^{352}}t_1$. The seed $t_1$ is odd, not $S$-periodic, at least $2^{66176}=16^{16544}$, and has $Z_{j_0}(t_1)>\frac{13}{15}>\frac67+2^{-28}$, so Proposition~\ref{prop:core} applies to it at $X/32$: at some $j\ge J_{\mathrm c}$ with $X/32$ reachable, \[ \#\Src_{j,X/32}(t_1)>2^{-212}t_1^{-25/11}X>2^{-212-\frac{125}{11}3^{d_0}}t^{-25/11}X\ge\frac X{t^{25/11}D_A}. \] Every source in $\Src_{j,X/32}(t_1)$ is odd, lies in $[X/32,X)$, and satisfies both step bounds by Proposition~\ref{prop:clocks}. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] Let $c(t)$ be as in Section~\ref{sec:intro} and $X>0$. If $X\ge D_At$, Proposition~\ref{prop:internal} gives at least $c(t)X\ge\floor{c(t)X}$ odd $n2^{66176}t$ are used. For a generation $j$ define, suppressing $j$, \[ \delta_\Sigma=\sum_{i\le j}\delta_i,\qquad\ell^{\mathrm c}_\Sigma=\sum_{i2$, $\delta_j\ge16544\cdot2^k\ge2^{14+k}$, and $2^{k-26}\ge70(k+1)>j$ by induction on $k\ge328$; so $\delta_j\ge2^{40}j$ and $2^{22}(j+1)\le2^{23}j\le\delta_j\le\delta_\Sigma$. For (2), $e_\delta<\delta/100+1$, so \[ \delta_j=16544+\sum_{i16^{16544}$). \begin{lemma}[Inverse trajectory of a counted source]\label{lem_orbit_large} In this notation, (1) every value of the inverse trajectory of $wv$ is at least $4096$; (2) $\deg(wv)\log2\le\log s-\log t_1+|wv|\,c_{\mathrm{step}}$; and (3) $\deg(wv)\ge2|wv|-(2-\log_23)\ell^{\mathrm c}_\Sigma-j-\delta_j/8$. \end{lemma} \begin{proof} For (1), we follow \cite[Section~7]{Mazur}. The first value is $t_1>2^{66176}$. Let $y$ be the value after $k$ letters, where either $|w_{4096$. For (2), write $wv=(a_1,\ldots,a_{|wv|})$. If $y$ and $y'$ are the values after $k$ and $k-1$ letters, then $3y+1=2^{a_k}y'$, so $a_k\log2=\log y-\log y'+\log(3+1/y)$. Summing over $k$, the first two terms telescope to $\log s-\log t_1$, and by (1) each last term is at most $c_{\mathrm{step}}$; this is \cite[(7.4)]{Mazur}. For (3), which is \cite[(7.3)]{Mazur} with $\ell^{\mathrm c}_\delta$ in place of his width, let $i2|v_i|-(2-\log_23)(|v_i|-\delta_i)-1$, and $|v_i|-\delta_i\le\ell^{\mathrm c}_{\delta_i}$ by the length restriction. As $2-\log_23>0$, $\deg(v_i)\ge2|v_i|-(2-\log_23)\ell^{\mathrm c}_{\delta_i}-1$. For $v$, the first crossing and the mask \eqref{eq:mask} give $\deg(v)\ge H_{\delta_j,u_w}(|v|)\ge2|v|-\delta_j/8$. Summing proves (3). \end{proof} \begin{lemma}[Size of a counted source]\label{lem_log_source_lower} Every $s\in\Src_{j,X}(t_1)$ satisfies $\log(s/t)\ge c_{\mathrm{src}}\delta_\Sigma$. \end{lemma} \begin{proof} This is \cite[(7.2)]{Mazur} with this paper's scales. Apply \eqref{eq:word-source} to $v_i$ at $s_{w_{66176\log2>\frac{24816}5\log2$ and $j+1\le\delta_\Sigma/2^{22}$ by Lemma~\ref{lem_width_sum}(1), \[ \log(s/t)\ge\delta_\Sigma\Bigl(\log\frac43-\log2\Bigl(\frac3{1000}+\frac{26}{10\cdot2^{22}}\Bigr)\Bigr), \] and by \eqref{eq:stop-logs} the bracket exceeds $\frac{287682}{10^6}-\frac{347}{500}\bigl(\frac3{1000}+\frac{26}{10\cdot2^{22}}\bigr)=\frac{598945709}{2097152000}=c_{\mathrm{src}}+\frac{501733}{52428800000}$. \end{proof} \begin{proposition}[Step bounds]\label{prop:clocks} Let $t_{\mathrm{odd}}$ be the odd part of $t$. Each $s\in\Src_{j,X}(t_1)$ reaches $t$ within $\floor{\frac{523}{50}\log(s/t)}$ ordinary steps and $t_{\mathrm{odd}}$ within $\floor{\frac{34881}{10000}\log(s/t)}$ accelerated steps. \end{proposition} \begin{proof} As $j\ge J_{\mathrm c}$, Lemmas~\ref{lem_width_sum} and~\ref{lem_log_source_lower} apply. For the accelerated steps we follow the proof of \cite[Lemma~7.2]{Mazur}. Put $c_{\mathrm{gain}}=2\log2-c_{\mathrm{step}}$; by \eqref{eq:stop-logs}, $\log(4/3)-1/12288\log(4/3)-1/12288$ and $\log(4/3)>287682/10^6$, the right side minus the left side exceeds the rational residual \begin{equation}\label{eq:accres} \Bigl(c_{\mathrm{src}}c_{\mathrm{acc}}-\frac1{9000}\Bigr)\frac{287682}{10^6}-\frac{c_{\mathrm{src}}c_{\mathrm{acc}}}{12288}-c_{\mathrm{src}}-\frac{219}{250000}=\frac{25365007801}{192000000000000000}>0. \end{equation} Hence $|wv|+1\le c_{\mathrm{acc}}\log(s/t)$. Since $s$ reaches $t_1$ in $|wv|$ accelerated steps and $S(t_1)=t_{\mathrm{odd}}$, $s$ reaches $t_{\mathrm{odd}}$ within $|wv|+1$ accelerated steps. For the ordinary steps we follow the proof of \cite[Lemma~7.3]{Mazur}. By Section~\ref{sec:words}, $s$ reaches $t_1$ in $|wv|+\deg(wv)$ ordinary steps, and $t_1$ reaches $t$ in $1+a$ more, where $3t_1+1=2^at$; so $s$ reaches $t$ within $N_{\mathrm{ord}}=|wv|+1+\deg(wv)+a$ ordinary steps. As $t_1>4096$, $a\log2=\log(3t_1+1)-\log t\le\log t_1+c_{\mathrm{step}}-\log t$, and adding Lemma~\ref{lem_orbit_large}(2) gives $(\deg(wv)+a)\log2\le\log(s/t)+(|wv|+1)c_{\mathrm{step}}$. With $|wv|+1\le c_{\mathrm{acc}}\log(s/t)$, \[ N_{\mathrm{ord}}\log2\le(|wv|+1)(\log2+c_{\mathrm{step}})+\log(s/t)\le\bigl(c_{\mathrm{acc}}(\log2+c_{\mathrm{step}})+1\bigr)\log(s/t). \] It remains to prove the inequality \cite[(7.9)]{Mazur}, \begin{equation}\label{eq:ordres} c_{\mathrm{acc}}(\log2+c_{\mathrm{step}})+1\le\frac{523}{50}\log2. \end{equation} By \eqref{eq:stop-logs} and Lemma~\ref{lem_s03_log3_bounds}(1), $c_{\mathrm{step}}<(317/200)\log2+1/12288$, so it suffices that \[ \Bigl(\frac{523}{50}-\frac{517}{200}c_{\mathrm{acc}}\Bigr)\log2\ge\frac{c_{\mathrm{acc}}}{12288}+1. \] The bracket is $2886523/2000000>0$, and by $\log2>693147180/10^9$ (Lemma~\ref{lem_s03_log3_bounds}(3)) the difference of the two sides exceeds \[ \frac{693147180}{10^9}\cdot\frac{2886523}{2000000}-\frac{c_{\mathrm{acc}}}{12288}-1=\frac{43510569153}{400000000000000}>0. \] Both step counts are integers, so both bounds may be floored. \end{proof} \section{The Fourier bound: black points and triangles}\label{sec:fb-black} This section and the next five prove the Fourier bound \eqref{eq:fourier} for both indices $\iota\in\{\mathrm o,\mathrm b\}$ at once, following Tao's argument \cite[Section 7]{Tao} with explicit constants; the index enters only through the parameters of Table~\ref{tab:fourier-params}. Section~\ref{sec:fb-charsum} bounds $|\widehat\mu_n(\xi)|$ by the expected penalty of a random walk, which gains a factor below $1$ at the white points of Definition~\ref{def_bk_points}, and reduces its decay to a descent step proved in three cases in Sections~\ref{sec:fb-trace}--\ref{sec:fb-cases}; Section~\ref{sec:fb-renewal} supplies the laws of the walk. Here we describe the geometry of the points at which the character sum gains no cancellation: these \emph{black} points form disjoint triangles, every point bordering a triangle is \emph{white}, and the angles of the points just above a triangle are close to odd dyadic fractions. In Sections~\ref{sec:fb-black}--\ref{sec:fb-conclusion} the letter $j$ denotes the first coordinate of a point and $J$ is as in Definition~\ref{lem_bk_eps_star_range}, and from Section~\ref{sec:fb-renewal} on $b$ (also $b^k$) denotes a hold word and $\mathbf b$ a list of hold words; the generations, scales and families of Sections~\ref{sec:physical}--\ref{sec:finish} do not occur there. \begin{definition}[Standing conventions]\label{lem_bk_eps_star_range} From now on, $n\ge1$, $J=\floor{n/2}$, $\xi\in G_n$ is a frequency prime to $3$, and $\varepsilon=37037/10^6$ is the constant of Definition~\ref{def_eps_star}. The objects defined below depend on $n$ and $\xi$; this dependence is suppressed from the notation. \end{definition} The arguments of this section use only $0<\varepsilon<1/27$, which holds as $27\varepsilon=999999/10^6$. \subsection{Points, angles, white and black points} In the character sum, the cancellation contributed by the $j$th pair $(a_{2j-1},a_{2j})$ of letters of the random word $W$ is governed by the angle, defined next, of the point $(j,\deg_{2j}(W))$ (see Lemma~\ref{lem_ch_front_pascal}). \begin{definition}[Points and angles]\label{def_bk_points}\label{def_bk_signed_frac}\label{def_bk_theta_residue}\label{def_bk_theta}\label{def_bk_black}\label{def_bk_white} A \emph{point} is an element $p=(j,l)$ of $\mathcal P=\Z_{\ge1}\times\Z$; we write $j(p)=j$ and $l(p)=l$, the \emph{raw length} and \emph{height} of $p$, and add points coordinatewise. Points $p\ne v$ are \emph{cardinal neighbours} if $|j(p)-j(v)|+|l(p)-l(v)|=1$. For $y\in G_n$, let $\tilde y\in\Z$ be the representative of $y$ with $|\tilde y|<3^n/2$ (it is unique, as $3^n$ is odd) and put $\operatorname{sfr}(y)=\tilde y/3^n$, the \emph{signed fractional part}. The \emph{angle} of $p=(j,l)$ is \[ \vartheta(p)=\operatorname{sfr}\bigl(\operatorname{res}(p)\bigr),\qquad \operatorname{res}(p)=\bigl[3^{2(j-1)}2^{1-l}\bigr]_n\,\xi . \] A point $p$ is \emph{white} if $j(p)\le J$ and $|\vartheta(p)|>\varepsilon$, and \emph{black} if $j(p)\le J$ and $|\vartheta(p)|\le\varepsilon$. Points with $j(p)>J$ are neither. \end{definition} Since the numerator of $\operatorname{sfr}(y)$ is the representative of least modulus, \begin{equation}\label{eq:fb-sfr} y'\in\Z,\ y'\equiv y,\ |y'|<3^n/2\ \Longrightarrow\ \operatorname{sfr}(y)=\frac{y'}{3^n}; \qquad |\operatorname{sfr}(ky)|\le k|\operatorname{sfr}(y)|\quad(k\in\N), \end{equation} the second because $k\cdot3^n\operatorname{sfr}(y)$ represents $ky$. Moving a point one step right multiplies its residue by $9$, and one step down by $2$; the southeast distance measures the resulting growth of the angle (Lemma~\ref{lem_bk_se_bound}). \begin{definition}[Southeast distance and the constant $\lambda$]\label{def_bk_se_weight}\label{def_bk_slope}\label{def_bk_drift}\label{lem_bk_alpha_bounds} For points $u,v$ with $j(u)\le j(v)$ and $l(v)\le l(u)$ put the \emph{southeast distance} \[ \operatorname{se}(u,v)=(j(v)-j(u))\log9+(l(u)-l(v))\log2, \] so that $e^{\operatorname{se}(u,v)}=9^{j(v)-j(u)}2^{l(u)-l(v)}$ is a positive integer. Let $\lambda=\log2/\log9$, the slope of the hypotenuse of a triangle (Definition~\ref{def_bk_triangle}). \end{definition} \begin{lemma}[Southeast transport]\label{lem_bk_se_bound}\label{lem_bk_se_exact}\label{lem_bk_residue_shift} Let $u,v\in\mathcal P$ with $j(u)\le j(v)$ and $l(v)\le l(u)$, and put $k=e^{\operatorname{se}(u,v)}$. Then $\operatorname{res}(v)=k\,\operatorname{res}(u)$ and $|\vartheta(v)|\le k|\vartheta(u)|$. If moreover $k|\vartheta(u)|<1/2$, then $\vartheta(v)=k\vartheta(u)$. \end{lemma} \begin{proof} As in \cite[(7.12)]{Tao}, $3^{2(j(v)-1)}2^{1-l(v)}=k\cdot3^{2(j(u)-1)}2^{1-l(u)}$ in $\Z[1/2]$; apply $[\cdot]_n$ and multiply by $\xi$. The bound follows from the second part of \eqref{eq:fb-sfr}, and the equality, as in \cite[(7.18)]{Tao}, from its first part with $y'=k\cdot3^n\vartheta(u)$. \end{proof} \begin{lemma}[Angles are bounded below]\label{lem_bk_strip} If $j(p)\le J$, then $3^{\,n+1-2j(p)}|\vartheta(p)|\ge1/3$; in particular $\vartheta(p)\ne0$. \end{lemma} \begin{proof} This is the proof of \cite[(7.16)]{Tao} with $\varepsilon$ replaced by $|\vartheta(p)|$: for $p=(j,l)$ and $k=n+1-2j\ge1$, $3^k\operatorname{res}(p)=3^{n-1}[2^{1-l}]_n\xi$ is represented by $\pm3^{n-1}$, so $1/3=|\operatorname{sfr}(3^k\operatorname{res}(p))|\le3^k|\vartheta(p)|$ by \eqref{eq:fb-sfr}. \end{proof} \subsection{Angles of neighbouring points} The proof of \cite[Lemma 7.4]{Tao} assumes $0<\varepsilon<1/100$; our $\varepsilon$ is larger, which is why we reprove its ingredients with explicit thresholds. The next lemma is a quantitative form of the claims (ii) and (iii) of that proof, which concern points with $|\vartheta|\le1/100$: it recovers the angle of a point exactly from the angles of two cardinal neighbours. \begin{lemma}[Quantitative claims (ii) and (iii)]\label{lem_bk_claim_ii}\label{lem_bk_claim_iii} Let $p=(j,l)\in\mathcal P$ and let $\bar\vartheta_1,\bar\vartheta_2$ be real numbers with $|\vartheta(j,l-1)|\le \bar\vartheta_2$. Each of the following implies $2\vartheta(p)=\vartheta(j,l-1)$: \begin{enumerate} \item[(ii)] $|\vartheta(j+1,l)|\le \bar\vartheta_1$ and $2\bar\vartheta_1+9\bar\vartheta_2<1$; \item[(iii)] $j\ge2$, $|\vartheta(j-1,l)|\le \bar\vartheta_1$ and $18\bar\vartheta_1+\bar\vartheta_2<1$. \end{enumerate} \end{lemma} \begin{proof} Write $y_2=3^n\vartheta(j,l-1)$; by Lemma~\ref{lem_bk_se_bound} it represents $2\operatorname{res}(p)$. In each case $\bar\vartheta_1\ge0$, so $\bar\vartheta_2<1$. (ii) Let $y_1=3^n\vartheta(j+1,l)$, which represents $9\operatorname{res}(p)$. Then $2y_1-9y_2\equiv18\operatorname{res}(p)-18\operatorname{res}(p)=0$ and $|2y_1-9y_2|<3^n$, so $2y_1=9y_2$. The integer $y_1-4y_2$ represents $9\operatorname{res}(p)-8\operatorname{res}(p)=\operatorname{res}(p)$ and equals $y_2/2$, of modulus at most $\bar\vartheta_2\,3^n/2<3^n/2$. By \eqref{eq:fb-sfr}, $\vartheta(p)=y_2/(2\cdot3^n)$. (iii) Let $y_3=3^n\vartheta(j-1,l)$, which represents $\operatorname{res}(j-1,l)$; then $\operatorname{res}(p)=9\operatorname{res}(j-1,l)$ and $y_2$ represents $18\operatorname{res}(j-1,l)$. As before $|18y_3-y_2|<3^n$ forces $y_2=18y_3$, and $9y_3=y_2/2$ represents $\operatorname{res}(p)$ with modulus less than $3^n/2$, so $\vartheta(p)=y_2/(2\cdot3^n)$. \end{proof} \begin{corollary}[Small angles along a row or column]\label{lem_bk_prop_left}\label{lem_bk_prop_right}\label{lem_bk_prop_up} Let $(j,l)\in\mathcal P$ and $m\in\N$. \begin{enumerate} \item[(a)] If $|\vartheta(j+m,l)|\le\varepsilon$ and $|\vartheta(j+k,l-1)|\le\varepsilon$ for $0\le k\varepsilon$, contradicting blackness of $p$. As every point $v$ with $j(v)\le J$ is either black or white, the following objects are well defined. \begin{definition}[Column top, gap, row start]\label{def_bk_col_top}\label{def_bk_row_start}\label{lem_bk_coltop_spec}\label{lem_bk_rowstart_spec}\label{lem_bk_column_ends} Let $p=(j,l)$ be black. Its \emph{column top} $l_*(p)$ is the unique $l''\ge l$ such that $(j,l')$ is black for $l\le l'\le l''$ and $(j,l''+1)$ is white. Its \emph{gap} is $\operatorname{gap}(p)=l_*(p)-l(p)\in\N$. Its \emph{row start} $j_*(p)$ is the unique $j'\in[1,j]$ such that $(i,l_*(p))$ is black for $j'\le i\le j$ and either $j'=1$ or $(j'-1,l_*(p))$ is white. \end{definition} \begin{definition}[Triangles and the canonical family]\label{def_bk_triangle}\label{def_bk_canon_triangle}\label{def_bk_family} A \emph{triangle} is a triple $\Delta=(j_\Delta,l_\Delta,S_\Delta)\in \Z_{\ge1}\times\Z\times\R$, with \emph{corner} $p_\Delta=(j_\Delta,l_\Delta)$ and \emph{size} $S_\Delta$. A point $v$ \emph{lies in} $\Delta$, written $v\in\Delta$, if \[ j(v)\ge j_\Delta,\qquad l(v)\le l_\Delta,\qquad \operatorname{se}(p_\Delta,v)\le S_\Delta . \] The \emph{top edge} of $\Delta$ is the row $l=l_\Delta$, and its \emph{left edge} is the column $j=j_\Delta$. For a black point $p$, the \emph{canonical triangle} is \[ \Delta(p)=\Bigl(j_*(p),\ l_*(p),\ \log\frac{\varepsilon}{|\vartheta(j_*(p),l_*(p))|}\Bigr), \] and the \emph{canonical family} is $\mathfrak T=\{\Delta(p):p\text{ black}\}$. \end{definition} Thus $v\in\Delta$ means that $v$ lies weakly southeast of the corner and weakly left of the hypotenuse $j-j_\Delta=\lambda(l-l_\Delta)+S_\Delta/\log9$. Membership is \emph{closed to the northwest}: if $v\in\Delta$ and $j_\Delta\le j(v')\le j(v)$, $l(v)\le l(v')\le l_\Delta$, then $v'\in\Delta$, since $\operatorname{se}(p_\Delta,\cdot)$ decreases. Also every $v\in\Delta$ satisfies $j(v)\le j_\Delta+S_\Delta/\log9$. \begin{lemma}[Canonical triangles]\label{lem_bk_corner_value}\label{lem_bk_canon_edge}\label{lem_bk_size_nonneg}\label{lem_bk_black_on}\label{lem_bk_right_edge} Let $p$ be black and $\Delta=\Delta(p)$. Then \begin{enumerate} \item[(a)] $p_\Delta$ is black, $|\vartheta(p_\Delta)|=\varepsilon e^{-S_\Delta}$ and $S_\Delta\ge0$; \item[(b)] (the \emph{right-end bound}) \begin{equation}\label{eq:fb-right-edge} j_\Delta+S_\Delta/\log9\le n/2+1-\log(1/\varepsilon)/\log9\log27=\frac32\log9$, and the third from $J=\floor{n/2}$. (c) By Lemma~\ref{lem_bk_se_bound} and (a), $|\vartheta(v)|\le e^{\operatorname{se}(p_\Delta,v)}\varepsilon e^{-S_\Delta}\le\varepsilon$. By (b), $j(v)\le j_\Delta+S_\Delta/\log9\varepsilon$. \emph{Case 2:} $j(v)\ge j_\Delta$, $l(v)>l_\Delta$. Then $v=x+(0,1)$ and $l(x)=l_\Delta$; suppose $v$ is black. If $j(v)j(p)$, the points $(j(p)+k,l_\Delta)$, $0\le km}\mathfrak q(c)=(m+1)2^{-m}$ for $m\in\N$. \item $\mathsf R(0,l)=\mathbf 1[l=0]$; for $k\ge1$, $\mathsf R(k,l)=\binom{l-1}{2k-1}2^{-l}$ if $l\ge1$ and $\mathsf R(k,l)=0$ if $l\le0$. \item $\sum_{k\ge1}\mathsf R(k,l)=\frac14$ for every integer $l\ge2$. \item For $l,k\in\N$, $\Prob(\deg_{2k}\le l<\deg_{2k+2})=\binom{l+1}{2k+1}2^{-l}$. \end{enumerate} \end{lemma} \begin{proof} The raw letters are almost surely finite, so $\sum_c\mathfrak q(c)=1$, and $c_1>m$ means $|\mathcal A\cap[1,m]|\le1$, of probability $(1+m)2^{-m}$. Part (2) is the negative binomial law \cite[Section~VI.8]{Feller}: for $k,l\ge1$, $\deg_{2k}=l$ means $l\in\mathcal A$ and $|\mathcal A\cap[1,l-1]|=2k-1$. Summing over $k\ge1$, $\sum_k\mathsf R(k,l)$ is the probability that $l\in\mathcal A$ and $|\mathcal A\cap[1,l-1]|$ is odd, which is $\frac12\cdot\frac12$ when $l-1\ge1$. Finally $\deg_{2k}\le l<\deg_{2k+2}$ means $|\mathcal A\cap[1,l]|\in\{2k,2k+1\}$, of probability $(\binom l{2k}+\binom l{2k+1})2^{-l}=\binom{l+1}{2k+1}2^{-l}$. \end{proof} We split the sequence of raw letters after each closing letter; the possible pieces are the hold words below. \begin{definition}[Hold words]\label{def_rn_hold_words}\label{def_rn_hold} \label{def_rn_geom4}\label{def_rn_hold_list}\label{def_ch_block_weight} \label{def_ch_block_point}\label{def_ch_block_path}\label{def_ch_raw} For $(j,l)\in\mathcal P$, let $\mathfrak B_{j,l}$ be the set of \emph{hold words} $b=(\mathbf c_1,\ldots,\mathbf c_j)\in\Z^j$ with all $\mathbf c_i\ge2$, with $\mathbf c_i\notin\{4,5\}$ for $i\omega$. Since every $l(\mathsf h_i)\ge4$, it exists and $N_{\omega}\le\floor{\omega/4}+1$. The \emph{first-passage law} is $\mathsf F_{\omega}(x)=\Prob(\mathsf W_{N_{\omega}}=x)$ for $x\in\Z\times\Z$, where, as for points, $j(x)$ and $l(x)$ denote the coordinates of $x$. Equivalently, call $\mathbf y\in\mathcal P^K$ a \emph{first-passage list over height $\omega$} if $l(y_1)+\cdots+l(y_k)\le \omega$ for $k\omega$; then $\mathsf F_{\omega}(x)$ is the sum of $\eta^{\otimes K}(\mathbf y)$ over $K\ge1$ and the first-passage lists $\mathbf y$ with $y_1+\cdots+y_K=x$. \end{definition} The \emph{first-passage overshoot} over height $\omega$ is $l(\mathsf W_{N_{\omega}})-\omega\ge1$. The \emph{horizontal first-passage coordinate} over height $\omega$ is $j(\mathsf W_{N_{\omega}})$, and its law $r\mapsto\sum_{x:\ j(x)=r}\mathsf F_{\omega}(x)$ is the \emph{horizontal first-passage law}. \begin{lemma}[First-passage law]\label{lem_rn_fp_mass} \label{lem_rn_fp_support} \label{lem_rn_fp_finite}\label{lem_rn_fp_raw} Let $\omega\in\N$. \begin{enumerate} \item $\mathsf F_{\omega}$ is a probability on $\Z\times\Z$, and $\mathsf F_{\omega}(x)\ne0$ implies $x\in\mathcal P$ (that is, $j(x)\ge1$) and $l(x)>\omega$. \item $\mathsf W_{N_{\omega}}=(i,\deg_{2i})$ for the least index $i$ with $c_i$ closing and $\deg_{2i}>\omega$. \end{enumerate} \end{lemma} \begin{proof} Part (1) holds since $N_{\omega}$ is finite, $j(\mathsf W_{N_{\omega}})\ge N_{\omega}\ge1$, and $l(\mathsf W_{N_{\omega}})>\omega$. Part (2) follows from Lemma~\ref{lem_rn_hold_mass}(4): the points $\mathsf W_N$, $N\ge1$, are the points $(i,\deg_{2i})$ at the closing indices $i$, in increasing order. \end{proof} \subsection{Exponential moments} Chernoff bounds for sums of hold points need the exponential moments of one hold point. \begin{definition}\label{def_rn_mgf}\label{def_rn_vpgf}\label{def_rn_joint_pgf} For real $\mathfrak t$ and real $X,y>0$ put \[ \mathsf M_{45}(\mathfrak t)=\sum_{r\ge1}\nu_{45}(r)e^{\mathfrak t r}=\E e^{\mathfrak t j(\mathsf h_1)},\qquad \mathsf G(X,y)=\sum_{(j,l)\in\mathcal P}\eta(j,l)X^jy^l=\E X^{j(\mathsf h_1)}y^{l(\mathsf h_1)}, \] with values in $[0,\infty]$, and $\mathsf V(y)=\mathsf G(1,y)=\E y^{l(\mathsf h_1)}$. \end{definition} \begin{lemma}[Moments of one hold point]\label{lem_rn_mgf_bound} \label{lem_rn_mgf_summable}\label{lem_rn_mgf_finite} \label{lem_rn_mgf_sixteenth}\label{lem_rn_hold_vpgf}\label{lem_rn_joint_pgf_value} \label{lem_rn_vpgf_tilt} \begin{enumerate} \item If $11e^{\mathfrak t}<16$, then $\mathsf M_{45}(\mathfrak t)=5e^{\mathfrak t}/(16-11e^{\mathfrak t})<\infty$. \item If $0\le \mathfrak t\le1/1024$, then $\mathsf M_{45}(\mathfrak t)\le e^{13\mathfrak t/4}$. \item $\mathsf M_{45}(1/16)\le5/4$. \item Let $X>0$ and $00$, so $\mathsf M_{45}(\mathfrak t)=5/(16e^{-\mathfrak t}-11)$, and it suffices that $5-16\mathfrak t\ge5e^{-13\mathfrak t/4}$. Since $e^{-13\mathfrak t/4}\le1-\frac{13}4\mathfrak t+\frac12(\frac{13}4\mathfrak t)^2$ for $\mathfrak t\ge0$, the right side is at most $5-\frac{65}4\mathfrak t+\frac{845}{32}\mathfrak t^2$, which is at most $5-16\mathfrak t$ because $\mathfrak t\le1/1024<8/845$. For (3), $e^{1/16}\le16/15$ by $e^{-1/16}\ge15/16$, and by (1) $\mathsf M_{45}(\mathfrak t)=5e^{\mathfrak t}/(16-11e^{\mathfrak t})$ increases with $e^{\mathfrak t}$ on $(0,16/11)$, with value $5/4$ at $e^{\mathfrak t}=16/15$. For (4), $X^jy^l=\prod_{i=1}^jXy^{\mathbf c_i}$ for $b=(\mathbf c_1,\ldots,\mathbf c_j)\in\mathfrak B_{j,l}$, so the factorization in the proof of Lemma~\ref{lem_rn_hold_mass} gives $\mathsf G(X,y)=\sum_{j\ge1}(X\mathsf V_{\mathrm{nc}}(y))^{j-1}X(\frac3{16}y^4+\frac18y^5)$. Here $\sum_c\mathfrak q(c)y^c=\sum_{c\ge2}(c-1)(y/2)^c=y^2/(2-y)^2$, so $\mathsf V_{\mathrm{nc}}(y)$ is the sum of $\mathfrak q(c)y^c$ over $c\notin\{4,5\}$, a nonnegative number. Sum the geometric series. For (5), exact evaluation gives $\mathsf V_{\mathrm{nc}}(27/25)=77640184719/82656250000<1$ and, by (4) with $X=1$, $\mathsf V(27/25)=36266065281/5016065281<8$. \end{proof} \begin{lemma}[Sums of hold points]\label{lem_rn_list_hor_tail} \label{lem_rn_list_hor_mgf}\label{lem_rn_list_tilt_split}\label{lem_rn_fp_mgf}\label{lem_rn_fp_mgf_summable} Let $N\in\N$. \begin{enumerate} \item For real $\mathfrak t$, $\E e^{\mathfrak t(j(\mathsf h_1)+\cdots+j(\mathsf h_N))}=\mathsf M_{45}(\mathfrak t)^N$ in $[0,\infty]$. \item For real $X,y>0$, an integer $0\le u\le N$ and an event $E$ determined by $\mathsf h_1,\ldots,\mathsf h_u$, \[ \E\bigl[\mathbf 1_EX^{j(\mathsf W_N)}y^{l(\mathsf W_N)}\bigr]=\mathsf G(X,y)^{N-u}\,\E\bigl[\mathbf 1_EX^{j(\mathsf W_u)}y^{l(\mathsf W_u)}\bigr] \] in $[0,\infty]$, with $\mathsf W_0=(0,0)$ and $0\cdot\infty=0$. \item For real $\mathsf m$, $\displaystyle\Prob\Bigl(\mathsf m\le10\sum_{i\le N}j(\mathsf h_i)\Bigr)\le\exp\left(\frac N2-\frac{\mathsf m}{160}\right)$. \item For $\omega\in\N$ and real $\mathfrak t\ge0$ with $11e^{\mathfrak t}<16$, $\sum_{x\in\mathcal P}\mathsf F_{\omega}(x)e^{\mathfrak t j(x)}\le \mathsf M_{45}(\mathfrak t)^{\omega+1}<\infty$. \end{enumerate} \end{lemma} \begin{proof} Parts (1) and (2) are independence (Lemma~\ref{lem_rn_hold_mass}(1)): $\mathsf W_N=\mathsf W_u+\mathsf h_{u+1}+\cdots+\mathsf h_N$, with $\mathsf h_{u+1},\ldots,\mathsf h_N$ independent of $\mathsf h_1,\ldots,\mathsf h_u$. Part (3) is the exponential Markov inequality: the probability is at most $e^{-\mathsf m/160}\mathsf M_{45}(1/16)^N$; apply Lemma~\ref{lem_rn_mgf_bound}(3) and $5/4<1+\frac12+\frac18\le e^{1/2}$. In (4) the sum is $\E e^{\mathfrak t j(\mathsf W_{N_{\omega}})}$; since $N_{\omega}\le \omega+1$ and $\mathfrak t\ge0$, $\mathfrak t j(\mathsf W_{N_{\omega}})\le \mathfrak t\sum_{i\le \omega+1}j(\mathsf h_i)$, so (1) and Lemma~\ref{lem_rn_mgf_bound}(1) apply. \end{proof} \subsection{First-passage overshoot} The first passage over a height does not overshoot it by much. \begin{lemma}[First-passage overshoot tail]\label{lem_rn_overshoot_tail} \label{def_rn_occupation}\label{lem_rn_occupation_value}\label{def_rn_green}\label{lem_rn_green_formula}\label{lem_rn_terminal_split} For integers $\omega\ge64$ and $\mathsf k\ge1$, \[ \sum_{x:\ l(x)\ge \omega+\mathsf k}\mathsf F_{\omega}(x) <9\left(\frac{25}{27}\right)^{\mathsf k}. \] \end{lemma} \begin{proof} Put $\mathsf W_0=(0,0)$ and, for $m\in\Z$, let $\mathsf u(m)=\sum_{N\ge0}\Prob(l(\mathsf W_N)=m)$ be the expected number of $N\ge0$ with $l(\mathsf W_N)=m$. By Lemma~\ref{lem_rn_hold_mass}(4), the heights $l(\mathsf W_N)$, $N\ge1$, are the $\deg_{2i}$ at the closing indices $i$. Since $c_{k+1}$ is independent of $\deg_{2k}$, \[ \mathsf u(m)=\mathbf 1[m=0]+\sum_{k\ge0}\bigl(\mathfrak q(4)\mathsf R(k,m-4) +\mathfrak q(5)\mathsf R(k,m-5)\bigr). \] By Lemma~\ref{lem_rn_raw_mass_formula}(2),(3), $\sum_{k\ge0}\mathsf R(k,l)$ is $1$ at $l=0$, is $1/4$ for $l\ge2$, and vanishes otherwise. With $\mathfrak q(4)=3/16$ and $\mathfrak q(5)=1/8$, for $m\in\N$, \[ \mathsf u(m)=\mathbf 1[m=0]+\tfrac3{16}\mathbf 1[m=4]+\tfrac18\mathbf 1[m=5] +\tfrac3{64}\mathbf 1[m\ge6]+\tfrac1{32}\mathbf 1[m\ge7], \] so $\mathsf u(m)\le\frac5{64}+\mathbf 1[m=0]+\frac3{16}\mathbf 1[m=4]+\frac18\mathbf 1[m=5]$. The left side of the claim is $\Prob(l(\mathsf W_{N_{\omega}})\ge \omega+\mathsf k)$. On this event, $N=N_{\omega}-1$ is the unique $N\ge0$ with $l(\mathsf W_N)\le \omega$ and $l(\mathsf h_{N+1})\ge \omega+\mathsf k-l(\mathsf W_N)$; conversely, any such $N$ equals $N_{\omega}-1$. Since $\mathsf h_{N+1}$ is independent of $\mathsf W_N$, with $y=27/25$, \[ \Prob(l(\mathsf W_{N_{\omega}})\ge \omega+\mathsf k) =\sum_{m=0}^{\omega}\mathsf u(m)\Prob(l(\mathsf h_1)\ge \omega+\mathsf k-m) \le\mathsf V(y)y^{-\mathsf k}\sum_{m=0}^{\omega}\mathsf u(m)y^{m-\omega}, \] and \[ \sum_{m=0}^{\omega}\mathsf u(m)y^{m-\omega} \le\frac5{64}\sum_{i\ge0}y^{-i} +y^{-\omega}\left(1+\frac3{16}y^4+\frac18y^5\right) \le\frac{135}{128}+\frac9{128}=\frac98. \] The last step uses the exact rational comparison $(25/27)^{64}\cdot224805889/156250000<9/128$ (the left side is $0.0104\ldots$), where $224805889/156250000=1+\frac3{16}y^4+\frac18y^5$. Lemma~\ref{lem_rn_mgf_bound}(5) gives $\mathsf V(y)<8$. \end{proof} \subsection{The horizontal first-passage law} The horizontal first-passage law is a mixture of two binomial rows (Lemma~\ref{lem_rn_cross_law}), whose tails give the horizontal tail of the first passage (Lemma~\ref{lem_rn_hor_tail}). We first bound binomial rows. \begin{lemma}[Binomial bounds]\label{lem_rn_binom_row} \label{lem_rn_binom_central}\label{lem_rn_hoeffding} For $N\in\N$ and $k\in\Z$, $(\binom Nk2^{-N})^2\le2/(3N+2)$; in particular $\mathsf R(k,l)\le(2(3l-1))^{-1/2}$ for all $k\in\N$ and integers $l\ge1$. For $N\ge1$ and real $u\ge0$, \[ \sum_{|k-N/2|\ge u}\binom Nk2^{-N}\le2e^{-2u^2/N}. \] \end{lemma} \begin{proof} We have $(3m+1)\bigl(\binom{2m}m4^{-m}\bigr)^2\le1$ by induction on $m$: it holds at $m=0$, and $\binom{2m+2}{m+1}4^{-m-1}=\binom{2m}m4^{-m}(2m+1)/(2m+2)$ with $(3m+4)(2m+1)^2=12m^3+28m^2+19m+4\le(3m+1)(2m+2)^2$. The largest coefficient of row $N$ is the middle one. For $N=2m$ this gives the claim; for $N=2m+1$, $\binom{2m+1}m2^{-N}=\binom{2m+2}{m+1}4^{-m-1}$, whose square is at most $1/(3m+4)=2/(3N+5)$. By Lemma~\ref{lem_rn_raw_mass_formula}(2), $\mathsf R(k,l)$ is $0$ or $\frac12\binom{l-1}{2k-1}2^{-(l-1)}\le\frac12(2/(3l-1))^{1/2}$. The last bound is Hoeffding's inequality \cite[Theorem~2]{Hoeffding} for a sum of $N$ independent fair Bernoulli variables, applied to each of the two tails. \end{proof} \begin{definition}[Binomial masses]\label{def_rn_cross_p}\label{def_rn_cross_e} For $l\in\N$ and $i\in\Z$ put \[ \mathsf p_l(i)=\binom{l+1}{2i+1}2^{-l},\qquad \mathsf p^{\mathrm{cl}}_l(i)=\frac18\binom{l-1}{2i-1}2^{-l}\quad(l,i\ge1), \] and $\mathsf p^{\mathrm{cl}}_l(i)=0$ otherwise. \end{definition} By Lemma~\ref{lem_rn_raw_mass_formula}, $\mathsf p_l(i)$ is the probability that $\deg_{2i}\le l<\deg_{2i+2}$, and for $l\ge2$, $\mathsf p^{\mathrm{cl}}_l(i)=\mathfrak q(5)\mathsf R(i,l)$ is the probability that $\deg_{2i}=l$ and $c_{i+1}=5$. Odd-index sums of binomial rows give $\sum_i\mathsf p_l(i)=1$ and, for $l\ge2$, $\sum_i\mathsf p^{\mathrm{cl}}_l(i)=1/32$. \begin{lemma}[Exact horizontal first-passage law]\label{lem_rn_cross_law} Let $\omega\ge6$ and $r\ge1$ be integers, and $l=\omega-4$. Then \[ \sum_{x:\ j(x)=r}\mathsf F_{\omega}(x)=\mathsf p^{\mathrm{cl}}_l(r-1) +\sum_{k=0}^{r-2}\bigl(\mathsf p_l(k)-\mathsf p^{\mathrm{cl}}_l(k)\bigr)\nu_{45}(r-1-k). \] \end{lemma} \begin{proof} By Lemma~\ref{lem_rn_fp_mass}(2), the left side is $\Prob(i_1=r)$, where $i_1=j(\mathsf W_{N_{\omega}})$. Let $i_0$ be the largest $i\ge0$ with $\deg_{2i}\le l$; then $i_0\omega$; so $i_1$ is the first closing index after $i_0+1$. Therefore $\{i_1=r\}$ is the disjoint union of $\{\deg_{2r-2}=l,\ c_r=5\}$, of probability $\mathsf p^{\mathrm{cl}}_l(r-1)$ (zero for $r=1$, since $l\ne0$), and, for $0\le k\le r-2$, of the events \[ \bigl(\{\deg_{2k}\le l<\deg_{2k+2}\}\setminus\{\deg_{2k}=l,\ c_{k+1}=5\}\bigr) \ \cap\ \{c_{k+2},\ldots,c_{r-1}\text{ not closing},\ c_r\text{ closing}\}. \] The two parts are independent, with probabilities $\mathsf p_l(k)-\mathsf p^{\mathrm{cl}}_l(k)$ and $\nu_{45}(r-1-k)$. \end{proof} \begin{lemma}[Horizontal tail of the first passage]\label{lem_rn_hor_tail}\label{lem_rn_hor_tail_sharp} For $\omega\in\N$ and real $u\ge2$, \[ \sum_{x:\ |j(x)-\omega/4|\ge u}\mathsf F_{\omega}(x) \le\begin{cases} 4e^{-u/256}&\text{if }\omega\le5,\\[2pt] 4\exp\Bigl(-\dfrac{u^2}{2(\omega-4)}\Bigr)+2e^{-u/256}&\text{if }\omega\ge6. \end{cases} \] \end{lemma} \begin{proof} \emph{Case 1.} Suppose $\omega\le5$. A nonzero term has $j(x)\ge1$, so $j(x)-\omega/4\ge-\frac14>-u$; hence $j(x)-\omega/4\ge u$ and $j(x)\ge u$. Markov's inequality, Lemma~\ref{lem_rn_fp_mgf}(4) with exponent $1/16$ and Lemma~\ref{lem_rn_mgf_bound}(3) bound the left side by $(5/4)^{\omega+1}e^{-u/16}\le(5/4)^6e^{-u/16}\le4e^{-u/256}$, as $(5/4)^6=15625/4096$. \emph{Case 2.} Suppose $\omega\ge6$. Put $l=\omega-4\ge2$; then $r-\omega/4=(r-1)-l/4$ for $r=j(x)$. Let $\mathcal J=\{i\ge0:|i-l/4|\ge u/2\}$. By Pascal's rule $\mathsf p_l(i)=(\binom l{2i}+\binom l{2i+1})2^{-l}\ge\mathsf p^{\mathrm{cl}}_l(i)$. For $i\in\mathcal J$ and $i'\in\{2i,2i+1\}$ we have $|i'-l/2|\ge2|i-l/4|-1\ge u-1\ge u/2$, so Lemma~\ref{lem_rn_hoeffding} gives $\sum_{i\in\mathcal J}\mathsf p_l(i)\le2e^{-u^2/(2l)}$. Sum Lemma~\ref{lem_rn_cross_law} over the $r$ with $|(r-1)-l/4|\ge u$. The $\mathsf p^{\mathrm{cl}}_l$-part is at most $\sum_{i\in\mathcal J}\mathsf p_l(i)$. In the remaining part, with $k=r-1-i\ge1$, $|i+k-l/4|\ge u$ forces $i\in\mathcal J$ or $k\ge u/2$, so it is at most \[ \sum_{i\in\mathcal J}\mathsf p_l(i)+\sum_{k\ge u/2}\nu_{45}(k) \le2e^{-u^2/(2l)}+\left(\frac{11}{16}\right)^{u/2-1} \le2e^{-u^2/(2l)}+2e^{-u/256}, \] using $\log(16/11)\ge5/16$. The total is at most $4e^{-u^2/(2l)}+2e^{-u/256}$. \end{proof} \section{The character sum and the weighted maxima}\label{sec:fb-charsum} This section bounds $|\widehat\mu_n(\xi)|$ by the expectation $\sum_y\eta(y)\mathsf Q(y)$ of the expected penalty $\mathsf Q$ (Proposition~\ref{lem_ch_front_end}, used in Theorem~\ref{lem_ch_primitive_decay}), following \cite[\S\S7.1, 7.3]{Tao}, but with cancellation at every raw letter up to $16$ (Lemma~\ref{lem_ch_white_cancel} and the paid rewards of Definition~\ref{def_ch_paid_reward}). It then introduces the weighted maxima $\mathsf Q_m$, whose descent step $\mathsf Q_m\le\mathsf Q_{m-1}$ is proved in Sections~\ref{sec:fb-trace}--\ref{sec:fb-conclusion}. The constants $z=\frac{133}{3125}$ and $\kappa=\frac{3187}{20000}$ are those of Definition~\ref{def_eps_star}; $\kappa z=\frac{423871}{62500000}$. Every series below is indexed by a countable set and has nonnegative terms or converges absolutely, so it may be rearranged and regrouped freely. For $p\in\mathcal P$ and $k\in\Z$ write $p-(0,k)=(j(p),l(p)-k)$. \subsection{Pairing}\label{sec:fb-characters} Grouping the letters in pairs, as in \cite[\S7.1]{Tao}, bounds $|\widehat\mu_n(\xi)|$ by an average of products of the following factors, one for each raw letter $\mathbf c_i$ at its point $(i,\mathbf c_1+\cdots+\mathbf c_i)$. For an integer $t\ge1$ and real $\theta$, and for $p\in\mathcal P$ and an integer $c$, put \begin{equation}\label{eq:fbc-pair-factor} \Phi_t(\theta)=\frac1t\Bigl|\sum_{a=0}^{t-1}e^{2\pi\mathrm i(2^a-1)\theta}\Bigr|,\qquad \varphi_c(p)=\Phi_{c-1}\bigl(\vartheta(p)\bigr)\quad(c\ge2), \end{equation} and $\varphi_c(p)=1$ for $c\le1$. By the triangle inequality, $0\le\varphi_c(p)\le1$. \begin{lemma}[Pairing]\label{lem_ch_front_pascal}\label{lem_fx_character_sum}\label{lem_fx_offset_law}\label{lem_ch_fp_formula} \begin{equation}\label{eq:fbc-pascal} |\widehat\mu_n(\xi)|\le\sum_{\mathbf c\in\Z^J}\ \prod_{i=1}^J \mathfrak q(\mathbf c_i)\,\varphi_{\mathbf c_i}\bigl(i,\,\mathbf c_1+\cdots+\mathbf c_i\bigr). \end{equation} \end{lemma} \begin{proof} Let $\mathbf e(y)=e^{-2\pi\mathrm i\xi y/3^n}$ for $y\in G_n$, evaluated at elements of $\Z[1/2]$ after reduction (Section~\ref{sec:words}). Then $\widehat\mu_n(\xi)=\E\mathbf e(\off(W_{\le n}))$ is the sum of \cite[(7.2)]{Tao} for the character $\mathbf e$, since the expression in \cite[(1.29)]{Tao} is $\off(W_{\le n})$ letter for letter. Tao's pair sums $a_{2i-1}+a_{2i}$ are the raw letters, with law $\mathfrak q$ (Definition~\ref{def_rn_pascal}), and given $a_{2i-1}+a_{2i}=c$ the letter $a_{2i}$ is uniform on $\{1,\ldots,c-1\}$. So, with $p_i=(i,\mathbf c_1+\cdots+\mathbf c_i)$ and $x_i=3^{2(i-1)}2^{-l(p_i)}$, \cite[(7.4)--(7.5)]{Tao} read \[ |\widehat\mu_n(\xi)|\le\sum_{\mathbf c\in\Z^J}\ \prod_{i=1}^J\mathfrak q(\mathbf c_i)\, |f(x_i,\mathbf c_i)|,\qquad f(x,c)=\frac1{c-1}\sum_{k=1}^{c-1}\mathbf e\bigl((2^k+3)x\bigr), \] where the terms with some $\mathbf c_i\le1$ vanish. Since $2^k+3=5+2(2^{k-1}-1)$ and $\mathbf e(2x_i)=e^{-2\pi\mathrm i\vartheta(p_i)}$ (Definition~\ref{def_bk_points}), we have $\mathbf e((2^k+3)x_i)=\mathbf e(5x_i)\,e^{-2\pi\mathrm i(2^{k-1}-1)\vartheta(p_i)}$. The sum over $k$ of the last factors is the complex conjugate of the sum in \eqref{eq:fbc-pair-factor} with $t=\mathbf c_i-1$ and $a=k-1$, so $|f(x_i,\mathbf c_i)|=\varphi_{\mathbf c_i}(p_i)$. \end{proof} \subsection{Cancellation at white points} At a white point the factors $\varphi_3$, $\varphi_4$, $\varphi_5$ are bounded away from $1$. \begin{lemma}[White cancellation]\label{lem_ch_white_cancel} \label{lem_ch_white_cancel_four}\label{lem_ch_white_cancel_five}\label{lem_ch_raw3_numeric}\label{lem_ch_fiber4_numeric}\label{lem_ch_fiber5_numeric}\label{def_ch_v0}\label{def_ch_u0}\label{lem_ch_v0_lower} If $p\in\mathcal P$ is white, then \[ \varphi_3(p)3.1415$, \[ 0\sin x_\circ\ge x_\circ-x_\circ^3/6>0$, so $\mathfrak u>\mathfrak u_\circ=(x_\circ-x_\circ^3/6)^2$. If $\mathfrak u\le\frac14$, then $\mathfrak h$ is nondecreasing on $[0,\frac14]$ (as $\mathfrak h'(y)\ge14-56y$), so $\mathfrak h(\mathfrak u)\ge \mathfrak h(\mathfrak u_\circ)$. If $\mathfrak u>\frac14$, then $\mathfrak h(\mathfrak u)-\frac74\mathfrak u=16\mathfrak u(\mathfrak u-\frac78)^2\ge0$ gives $\mathfrak h(\mathfrak u)>\frac7{16}$. Exact rational arithmetic gives $\mathfrak u_\circ<\frac14$, $\frac{18362}{100000}<\mathfrak h(\mathfrak u_\circ)<\frac7{16}$ and \[ 9-4\cdot\frac{18362}{100000}<9\Bigl(1-2z+2z^2-\frac43z^3\Bigr)\le9e^{-2z} \] (decimal values $8.26552$ and $8.26559\ldots$; the last step is the Taylor bound at $y=2z$). In both cases $\mathfrak h(\mathfrak u)>\frac{18362}{100000}$, hence $9\varphi_4(p)^2=9-4\mathfrak h(\mathfrak u)<9e^{-2z}$. \emph{The raw letter $5$.} By the triangle inequality and $|1+e^{2\mathrm iy}|=2|\cos y|$, \[ \varphi_5(p)=\tfrac14|1+\mathfrak a+\mathfrak a^3+\mathfrak a^7|\le\tfrac14\bigl(|1+\mathfrak a|+|1+\mathfrak a^4|\bigr) =\tfrac12\bigl(|\cos x|+|\cos4x|\bigr). \] If $x\le\frac\pi8$, then $4x_\circ<4x\le\frac\pi2$, so $0\le\cos4x<\cos4x_\circ$, and $\varphi_5(p)< 1-(4x_\circ)^2/4+(4x_\circ)^4/48$, which is less than $0.947$. If $\frac\pi8\frac14$, $\cos(2\pi\phi)=-\cos(2\pi(\frac12-\alpha))$ is bounded in the same way; here $10^{-9}$ exceeds $2(8/5)^{16}/16!+\frac12|\pi-\pi_0|$, a bound for the Lagrange remainder of Taylor's formula plus the error from $\pi_0$, since $2\pi_0\alpha\le8/5$ and $|\pi-\pi_0|<5\cdot10^{-10}$. These upper bounds, rounded up to multiples of $2^{-64}$, give an upper bound for $g_t$ at the point. A segment $[\theta_0,\theta_1]$ is accepted if the larger of the bounds at its ends plus $L_t(\theta_1-\theta_0)/2$ is less than $t^2U_{s,t}^2$, which bounds $g_t$ on the segment; otherwise it is split at $\floor{(N_0+N_1)/2}/Q$, where $\theta_i=N_i/Q$ and $Q=3\cdot2^{s+20}$, and each part is treated in the same way. Starting from the cells and splitting at most $20$ times, every segment is accepted, for each of the $20$ pairs; at most $831$ segments are tested per pair. \end{proof} \subsection{Paid rewards and the penalty} The descent step needs the cancellation of every raw letter, not only of the raw letters $3$, $4$, $5$ at white points. The paid reward $R_c(p)$ below records it: $e^{-zR_c(p)}$ bounds $\varphi_c(p)$, with the bounds of Lemmas~\ref{lem_ch_white_cancel} and~\ref{lem_ch_packet_bound} as a floor and the actual value of $\varphi_c(p)$, capped at $2^{-16}$, for $3\le c\le16$. \begin{definition}[Paid rewards]\label{def_ch_paid_reward}\label{def:paid-reward}\label{def_ch_packets}\label{def_ch_packet_coverage}\label{def_ch_old_reward}\label{def_ch_residual_reward} Let $c$ be an integer and $p\in\mathcal P$. A pair $(k,t)\in\N\times\{3,4\}$ with $k+t\le c-1$ is \emph{admissible} if $p-(0,k)$ is white, and the \emph{coverage} $M_c(p)$ is the largest value of $\sum_{(k,t)\in S}t$ over the sets $S$ of admissible pairs with pairwise disjoint packets (with $M_c(p)=0$ for $S=\emptyset$). The \emph{baseline reward} is \[ R^{\mathrm{old}}_c(p)=\begin{cases} \kappa\,\mathbf 1[p\text{ white}],& c=3,\\ \mathbf 1[p\text{ white}],& c=4,\\ \mathbf 1[p\text{ white}]+\frac{18351}{25000}\,\mathbf 1[p\text{ not white},\ p-(0,1)\text{ white}],& c=5,\\ \frac{M_c(p)}{c-1}\bigl(1-\frac z2\bigr),& 6\le c\le16,\\ 0&\text{otherwise}. \end{cases} \] The \emph{paid reward} is $R_c(p)=\max\bigl\{R^{\mathrm{old}}_c(p),-z^{-1}\log\max(\varphi_c(p),2^{-16})\bigr\}$ if $3\le c\le16$ and $j(p)\le J$, and $R_c(p)=R^{\mathrm{old}}_c(p)$ otherwise. The \emph{residual reward} is $R^{\mathrm{res}}_c(p)=R_c(p)-\mathbf 1[c\in\{4,5\}]\,\mathbf 1[p\text{ white}]$. \end{definition} Here $\frac{18351}{25000}=\frac34(1-\frac z2)$. \begin{lemma}[Paid rewards]\label{lem_ch_paid_reward_bound}\label{lem_ch_reward_beyond}\label{lem_ch_paid_reward_ge_old}\label{lem_ch_paid_reward_nonneg}\label{lem_ch_residual_nonneg}\label{lem_ch_old_reward_bound}\label{lem_ch_paid_reward_cap} Let $c$ be an integer and $p\in\mathcal P$. \begin{enumerate} \item $R_c(p)\ge R^{\mathrm{old}}_c(p)\ge0$ and $R^{\mathrm{res}}_c(p)\ge0$; if $j(p)>J$, then $R_c(p)=0$. \item $\varphi_c(p)\le e^{-zR^{\mathrm{old}}_c(p)}$ and $\varphi_c(p)\le e^{-zR_c(p)}$. \item If $3\le c\le16$ and $j(p)\le J$, then $e^{-zR_c(p)}\le\max(\varphi_c(p),2^{-16})$. \end{enumerate} \end{lemma} \begin{proof} (1) The first inequality holds by definition, and each case of $R^{\mathrm{old}}_c$ is nonnegative. If $c\in\{4,5\}$ and $p$ is white, then $R^{\mathrm{old}}_c(p)=1$, so $R^{\mathrm{res}}_c(p)\ge0$; otherwise $R^{\mathrm{res}}_c(p)=R_c(p)$. If $j(p)>J$, no point $p-(0,k)$ is white, so $M_c(p)=0$ and $R_c(p)=R^{\mathrm{old}}_c(p)=0$. (2) The second bound follows from the first, since also $\varphi_c(p)\le\max(\varphi_c(p),2^{-16})$ and $y\mapsto e^{-zy}$ decreases. For the first we may assume $R^{\mathrm{old}}_c(p)>0$, as $\varphi_c\le1$. If $c\in\{3,4,5\}$ and $p$ is white, apply Lemma~\ref{lem_ch_white_cancel}. If $c=5$, $p$ is not white and $p-(0,1)$ is white, Lemma~\ref{lem_ch_packet_bound} with $S=\{(1,3)\}$ and Lemma~\ref{lem_ch_white_cancel} give $\varphi_5(p)\le\frac14(1+3e^{-z})\le1-\frac34z(1-\frac z2)\le e^{-zR^{\mathrm{old}}_5(p)}$, using $e^{-z}\le1-z+z^2/2$ and $1-y\le e^{-y}$. If $6\le c\le16$, take $S$ attaining $M=M_c(p)$; as $t+1\in\{4,5\}$ for $(k,t)\in S$, Lemmas~\ref{lem_ch_packet_bound} and~\ref{lem_ch_white_cancel} give \[ \varphi_c(p)\le1-\frac M{c-1}\bigl(1-e^{-z}\bigr)\le1-z\frac M{c-1}\Bigl(1-\frac z2\Bigr)\le e^{-zR^{\mathrm{old}}_c(p)}. \] (3) By definition $R_c(p)\ge-z^{-1}\log\max(\varphi_c(p),2^{-16})$. \end{proof} \begin{definition}[White factor and penalty]\label{def_ch_white_factor}\label{def_ch_penalty} For $p\in\mathcal P$ the \emph{white factor} is $\mathsf w(p)=e^{-z}$ if $p$ is white, and $\mathsf w(p)=1$ otherwise. For a word of raw letters $\mathbf c=(\mathbf c_1,\ldots,\mathbf c_j)\in\Z^j$, the \emph{penalty} is \[ \operatorname{Pen}(\mathbf c)=\prod_{i=1}^je^{-zR_{\mathbf c_i}(i,\,\mathbf c_1+\cdots+\mathbf c_i)}\in(0,1]. \] \end{definition} \subsection{Splitting the penalty into holds} Splitting the raw letters into holds turns the penalty into a product along the hold walk: the white factors $\mathsf w$ at the hold points carry the reward $\mathbf 1[\text{white}]$ of the closing letters, and the internal factor carries the residual rewards of all letters of a hold (Lemma~\ref{lem_ch_raw_penalty}). \begin{definition}[Internal factors]\label{def_ch_internal_weight} For $x\in\N\times\Z$ and a hold $b=(\mathbf c_1,\ldots,\mathbf c_{|b|})$ (Definition~\ref{def_rn_hold_words}), the \emph{internal factor} is \[ \mathsf I(x;b)=\prod_{i=1}^{|b|}e^{-zR^{\mathrm{res}}_{\mathbf c_i}(x+(i,\,\mathbf c_1+\cdots+\mathbf c_i))}\in(0,1]. \] \end{definition} \begin{lemma}[Penalty along holds]\label{lem_ch_raw_penalty}\label{lem_ch_block_reward}\label{lem_ch_internal_range}\label{lem_ch_factor_penalty} Let $K\ge J$, let $\mathbf b\in\mathfrak B^K$, and let $\mathbf c$ be the first $J$ raw letters of its raw word. Then \[ \operatorname{Pen}(\mathbf c)=\prod_{k=1}^K\mathsf w\bigl(\operatorname{pt}_k(\mathbf b)\bigr) \prod_{k=1}^K\mathsf I\bigl(\operatorname{pt}_{k-1}(\mathbf b);b^k\bigr). \] \end{lemma} \begin{proof} For a hold $b=(\mathbf c_1,\ldots,\mathbf c_r)$ and $x\in\N\times\Z$, the letters $\mathbf c_i$, $iJ$, then $\mathsf Q(p)=1$. \item $\displaystyle\mathsf Q(p)=\mathsf w(p)\sum_{b\in\mathfrak B} \mathfrak q(b)\,\mathsf I(p;b)\,\mathsf Q\bigl(p+\operatorname{pt}(b)\bigr)$. \item $\displaystyle\mathsf Q(p)\le\mathsf w(p)\sum_{y\in\mathcal P}\eta(y)\,\mathsf Q(p+y)$. \end{enumerate} \end{lemma} \begin{proof} Part (2) is the analogue of \cite[(7.35)]{Tao}, with internal factors and truncated sums. All factors in Definition~\ref{def_ch_Qfinite} lie in $(0,1]$ and the lists have total mass $1$ (Lemma~\ref{lem_rn_hold_mass}(5)), so $0\le\mathsf U_K\le1$. Writing a list in $\mathfrak B^{K+1}$ as $(b,\mathbf b')$ with $\operatorname{pt}_i(b,\mathbf b')=\operatorname{pt}(b) +\operatorname{pt}_{i-1}(\mathbf b')$ for $i\ge1$ gives the one-step identity \begin{equation}\label{eq:fbc-step} \mathsf U_{K+1}(p)=\mathsf w(p)\sum_{b\in\mathfrak B}\mathfrak q(b)\, \mathsf I(p;b)\,\mathsf U_K\bigl(p+\operatorname{pt}(b)\bigr). \end{equation} Splitting off the last hold instead shows that $\mathsf U_{K+1}(p)=\mathsf U_K(p)$ when $j(p)+K\ge J$: the new factors $\mathsf w(p+\operatorname{pt}_{K+1}(\mathbf b))$ and $\mathsf I(p+\operatorname{pt}_K(\mathbf b);b^{K+1})$ are evaluated at points of raw length at least $j(p)+K+1>J$, which are not white and where the rewards vanish, so they equal $1$, and the last hold then sums to mass $1$. By induction, $\mathsf U_K(p)$ does not depend on $K$ once $j(p)+K\ge J$; as $K=J$ qualifies, the common value is $\mathsf Q(p)$. If $j(p)>J$, the same reasoning makes every factor equal to $1$, and $\mathsf Q(p)=1$. This proves (1). For (2), apply \eqref{eq:fbc-step} with $K=J$, noting $\mathsf U_{J+1}(p)=\mathsf Q(p)$ by (1). For (3), drop $\mathsf I\le1$ in (2) and group the holds by their point using \eqref{eq:fbc-eta}. \end{proof} \begin{proposition}[Character sum and expected penalty]\label{lem_ch_front_end} \begin{equation}\label{eq:fbc-front} |\widehat\mu_n(\xi)|\le\sum_{y\in\mathcal P}\eta(y)\,\mathsf Q(y). \end{equation} \end{proposition} \begin{proof} If $J=0$, then $\mathsf Q(y)=1$ for every $y\in\mathcal P$ (Lemma~\ref{lem_ch_Q_range}(1)), so the right side is $1$, while $|\widehat\mu_n(\xi)|\le\sum_x\mu_n(x)=1$. Let $J\ge1$. By Lemma~\ref{lem_ch_paid_reward_bound}(2), $\varphi_c(p)\le e^{-zR_c(p)}$ for every integer $c$ and every $p\in\mathcal P$, so \eqref{eq:fbc-pascal} gives \[ |\widehat\mu_n(\xi)|\le\sum_{\mathbf c\in\Z^J}\ \prod_{i=1}^J\mathfrak q(\mathbf c_i)\, \operatorname{Pen}(\mathbf c). \] By \eqref{eq:fbc-raw-law} with $m=K=J$, the mass $\prod_i\mathfrak q(\mathbf c_i)$ is the total mass of the lists $\mathbf b\in\mathfrak B^J$ whose raw word begins with $\mathbf c$. Summing over $\mathbf c$ first and applying Lemma~\ref{lem_ch_raw_penalty}, the right side becomes \[ \sum_{\mathbf b\in\mathfrak B^J}\mathfrak q(\mathbf b) \prod_{k=1}^J\mathsf w\bigl(\operatorname{pt}_k(\mathbf b)\bigr) \prod_{k=1}^J\mathsf I\bigl(\operatorname{pt}_{k-1}(\mathbf b);b^k\bigr). \] Write $\mathbf b=(b^1,\mathbf b')$ and $y=\operatorname{pt}(b^1)$, so that $\operatorname{pt}_k(\mathbf b)=y+\operatorname{pt}_{k-1}(\mathbf b')$ for $k\ge1$. Summing over $\mathbf b'\in\mathfrak B^{J-1}$ turns the summand into $\mathfrak q(b^1)\,\mathsf I((0,0);b^1)\,\mathsf U_{J-1}(y)$, by Definition~\ref{def_ch_Qfinite}. Since $j(y)\ge1$, Lemma~\ref{lem_ch_Q_range}(1) gives $\mathsf U_{J-1}(y)=\mathsf Q(y)$. Finally drop $\mathsf I\le1$ and group the holds $b^1$ by their point, using \eqref{eq:fbc-eta}. \end{proof} \subsection{Weighted maxima near the horizon} To show that $\mathsf Q(p)$ decays like a power of the distance to the horizon $j=J$, we follow \cite[(7.38)--(7.41)]{Tao} and track the largest weighted value $d_J^{A}\mathsf Q$ within distance $m$ of the horizon; a bound on it that does not grow with $m$ is the decay we need. \begin{definition}[Weighted maxima]\label{def_ch_Qm}\label{def_ch_dist} For $p\in\mathcal P$ let $d_J(p)=\max(J-j(p),1)$, the \emph{distance to the horizon} $j=J$. For an integer $m\ge1$, a \emph{boundary point} for $m$ is a $p\in\mathcal P$ with $j(p)+m=J$. For a real exponent $A\ge0$, suppressed from the notation, and an integer $m\ge0$, the \emph{weighted maxima} are \[ \mathsf Q_m=\sup\bigl\{d_J(p)^{A}\,\mathsf Q(p):\ p\in\mathcal P,\ j(p)\ge J-m\bigr\}. \] \end{definition} \begin{lemma}[Basic properties of the weighted maxima]\label{lem_ch_Qm_bounded} \label{lem_ch_Qm_nonempty}\label{lem_ch_Qm_set_bound}\label{lem_ch_Qm_le_pow} \label{lem_ch_Qm_dominate} Let $A\ge0$ and let $m\ge0$ be an integer. \begin{enumerate} \item $0\le\mathsf Q_m\le\max(m,1)^{A}$. \item If $j(p)\ge J-m$, then $d_J(p)^{A}\,\mathsf Q(p)\le\mathsf Q_m$. \end{enumerate} \end{lemma} \begin{proof} As in \cite[(7.39)]{Tao}: if $j(p)\ge J-m$, then $1\le d_J(p)\le\max(m,1)$ and $0\le\mathsf Q(p)\le1$ (Lemma~\ref{lem_ch_Q_range}(1)), and the set in Definition~\ref{def_ch_Qm} contains the point $(J+1,0)$. \end{proof} \begin{lemma}[Boundary reduction]\label{lem_ch_boundary_suffices} \label{lem_ch_boundary_step} Let $A\ge0$ and let $m\ge1$ be an integer. \begin{enumerate} \item If $r\ge1$ and $j(p)+m=J+r$, then $\mathsf Q(p)\le\max(m-r,1)^{-A}\mathsf Q_{m-1}$. \item If $\mathsf Q(p)\le m^{-A}\mathsf Q_{m-1}$ for every boundary point $p$ for $m$, then $\mathsf Q_m\le\mathsf Q_{m-1}$. \end{enumerate} \end{lemma} \begin{proof} As in \cite[\S7.4]{Tao} (the bound opening Case~1, and the reduction of (7.40) to (7.41)), by Lemma~\ref{lem_ch_Qm_bounded}(2): in (1), $j(p)\ge J-(m-1)$ and $d_J(p)=\max(m-r,1)$; in (2), a point with $j(p)\ge J-m$ either has $j(p)\ge J-(m-1)$ or is a boundary point for $m$, where $d_J(p)=m$. \end{proof} For the index $\iota$ take $A=A_\iota$. By Lemma~\ref{lem_ch_boundary_suffices}(2), the descent step $\mathsf Q_m\le\mathsf Q_{m-1}$ (Proposition~\ref{lem_mo_monotonicity}) reduces to the bound $\mathsf Q(p)\le m^{-A_\iota}\mathsf Q_{m-1}$ at every boundary point $p$ for $m$, which is white or black as $j(p)\mathsf s_\iota m$. Case~1 needs one hold (Section~\ref{sec:fb-cases}); Cases~2 and~3 follow the hold walk through the trace of Section~\ref{sec:fb-trace}, and are completed in Sections~\ref{sec:fb-cases} and~\ref{sec:fb-case3}. \section{The trace}\label{sec:fb-trace} This section proves the explicit form of \cite[Lemma~7.9]{Tao} used in Case~3 (Section~\ref{sec:fb-case3}): from any starting point, the average of the discounted reward $e^{-z\operatorname{Rw}}$ at the $(k+1)$st trace time is at most $(\frac{77}{100})^k$ (Lemma~\ref{lem_tr_lemma79}). It rests on the bound $\frac{77}{100}$ for one step of the entry kernel (Proposition~\ref{lem_tr_kernel_two}). At most gaps this bound comes from the reward collected at the first raw crossing of the top edge of a triangle, whose angle is an odd dyadic fraction (Lemma~\ref{lem:odd-dyadic-exit}); at six gaps it comes from finite trees of raw prefixes. The same crossing bounds give the bound $1-d_{\mathrm{pass}}$ for one passage at every gap, used in Case~2 (Lemma~\ref{lem_mo_case2}). The discount rate of the trace is the cancellation $z$ at a white point (Lemma~\ref{lem_ch_white_cancel}). All sums below have nonnegative terms and values in $[0,\infty]$ unless stated otherwise, and are rearranged freely. \subsection{Paths and rewards} A path follows the hold walk for a fixed number of holds. Its reward adds the paid raw rewards $R_c$ of Definition~\ref{def:paid-reward}, which can be positive at black as well as white points; each white closing point contributes at least $1$. \begin{definition}[Paths and rewards] \label{def_tr_list_weight}\label{def_tr_path}\label{def_tr_reward}\label{def_tr_count} For a list $\mathbf b=(b^1,\ldots,b^L)\in\mathfrak B^L$, $L\in\N$, write $|\mathbf b|=L$, $\mathbf b_{[i,i']}=(b^i,\ldots,b^{i'})$, and $\mathbf w\mathbf w'$ for the concatenation of lists. The \emph{path} of $\mathbf b$ from $\bar o\in\mathcal P$ is $\mathsf y_u(\bar o,\mathbf b)=\bar o+\operatorname{pt}_{\min(u,L)}(\mathbf b)$, $u\in\N$. The \emph{reward} of a hold $b=(\mathbf c_1,\ldots,\mathbf c_{|b|})$ at a point $x$ is \[ \operatorname{rw}(x,b)=\sum_{i=1}^{|b|}R_{\mathbf c_i}\bigl(x+(i,\mathbf c_1+\cdots+\mathbf c_i)\bigr), \] and the \emph{accumulated reward} is $\operatorname{Rw}(\bar o,\mathbf b;u)=\sum_{i=1}^{\min(u,L)}\operatorname{rw}(\mathsf y_{i-1}(\bar o,\mathbf b),b^i)$. The \emph{raw word} of $\mathbf b$ is the concatenation of its holds, of length $M=j(\operatorname{pt}_L(\mathbf b))$; $\sigma_i(\mathbf b)$, $0\le i\le M$, denotes the sum of its first $i$ raw letters. \end{definition} The raw letters of a hold other than its closing letter lie outside $\{4,5\}$, so Definitions~\ref{def_ch_white_factor} and~\ref{def_ch_internal_weight} give \begin{equation}\label{eq:tr-wI} \mathsf w(x+\operatorname{pt}(b))\,\mathsf I(x;b)=e^{-z\operatorname{rw}(x,b)}. \end{equation} \begin{lemma}[Elementary properties]\label{lem_tr_concat} Let $\bar o\in\mathcal P$, $\mathbf w\in\mathfrak B^{L_1}$, $\mathbf w'\in\mathfrak B^{L_2}$ and $\mathbf b\in\mathfrak B^L$. \begin{enumerate} \item For $\Psi\ge0$ on $\mathfrak B^{L_1}\times\mathfrak B^{L_2}$, \[ \sum_{\mathbf b\in\mathfrak B^{L_1+L_2}}\mathfrak q(\mathbf b)\Psi(\mathbf b_{[1,L_1]},\mathbf b_{[L_1+1,L_1+L_2]})=\sum_{\mathbf w,\mathbf w'}\mathfrak q(\mathbf w)\mathfrak q(\mathbf w')\Psi(\mathbf w,\mathbf w'). \] \item $\mathsf y_u(\bar o,\mathbf w\mathbf w')=\mathsf y_u(\bar o,\mathbf w)$ for $u\le L_1$, $\mathsf y_{L_1+u}(\bar o,\mathbf w\mathbf w')=\mathsf y_u(\mathsf y_{L_1}(\bar o,\mathbf w),\mathbf w')$ and $\operatorname{Rw}(\bar o,\mathbf w\mathbf w';L_1+u)=\operatorname{Rw}(\bar o,\mathbf w;L_1)+\operatorname{Rw}(\mathsf y_{L_1}(\bar o,\mathbf w),\mathbf w';u)$ for $u\in\N$. \item For $u\le u'$, with $\mathsf y_u=\mathsf y_u(\bar o,\mathbf b)$ and $k=\min(u',L)-\min(u,L)$, we have $j(\mathsf y_{u'})-j(\mathsf y_u)\ge k$, and $l(\mathsf y_{u'})-l(\mathsf y_u)\ge4k$ if $\mathfrak q(\mathbf b)\ne0$. \item For $L'\in\N$, the masses of the lists in a prefix-disjoint set of lists of length at most $L'$ sum to at most $1$. \item For $u\le L$, $\operatorname{Rw}(\bar o,\mathbf b;u)\ge\#\{1\le i\le u:\mathsf y_i(\bar o,\mathbf b)\text{ white}\}$, and $u\mapsto\operatorname{Rw}(\bar o,\mathbf b;u)$ is nondecreasing. \item With $\mathbf c$ the raw word of $\mathbf b$ and $M$ its length, $\operatorname{Rw}(\bar o,\mathbf b;L)=\sum_{i=1}^MR_{\mathbf c_i}(\bar o+(i,\sigma_i(\mathbf b)))$. \end{enumerate} \end{lemma} \begin{proof} (1) Concatenation is a bijection $\mathfrak B^{L_1}\times\mathfrak B^{L_2}\to\mathfrak B^{L_1+L_2}$ and the mass is multiplicative. (2) follows from $\operatorname{pt}_{L_1+u}(\mathbf w\mathbf w')=\operatorname{pt}_{L_1}(\mathbf w)+\operatorname{pt}_u(\mathbf w')$. (3) Every hold point $(j,l)$ has $j\ge1$, and $l\ge4$ if the hold has positive mass (Lemma~\ref{lem_rn_hold_mass}(3)). (4) Extend every list $\mathbf w$ of the set by all lists of length $L'-|\mathbf w|$; by (1) the extensions of $\mathbf w$ carry mass $\mathfrak q(\mathbf w)$, and the extensions of distinct lists are disjoint subsets of $\mathfrak B^{L'}$, which has mass $1$ (Lemma~\ref{lem_rn_hold_mass}(5)). (5) Rewards are nonnegative, and the closing letter of the $i$th hold sits at $\mathsf y_i$ and has reward at least $1$ there if $\mathsf y_i$ is white (Definition~\ref{def:paid-reward}). (6) The $i$th raw letter of the $k$th hold has index $q=j(\operatorname{pt}_{k-1}(\mathbf b))+i$ in the raw word, and the point attached to it in Definition~\ref{def_tr_reward} is $\bar o+(q,\sigma_q(\mathbf b))$. \end{proof} \subsection{Gaps and the trace times} The trace times mark the successive entries of a path into triangles. Each new entry lies above the top edge of the triangle entered before, so between two entries the path makes a full passage over that edge. A black point $p$ lies in $\Delta(p)$ and $l_{\Delta(p)}=l_*(p)$ (Lemma~\ref{lem_bk_source_mem} and Definition~\ref{def_bk_triangle}), so its gap $\operatorname{gap}(p)=l_*(p)-l(p)\ge0$ (Definition~\ref{def_bk_col_top}) is the distance from $p$ up to the top edge of $\Delta(p)$. Call the path $\mathsf y_u=\mathsf y_u(\bar o,\mathbf b)$ of $\mathbf b\in\mathfrak B^L$ \emph{complete} if $j(\bar o)+L>J$. If $\mathsf y_u$ is black on a complete path, then $uJ$ by Lemma~\ref{lem_tr_concat}(3). A time $u$ is a \emph{hit} if $\mathsf y_u$ is black. \begin{definition}[Trace times]\label{def_tr_trace} The \emph{trace times} $u_1u_i$ with $l(\mathsf y_u)>l_*(\mathsf y_{u_i})$, if there is one. Since hits are less than $L$, the sequence is finite. \end{definition} For $p\in\mathcal P$ and a list $\mathbf w$ write $p_{\mathbf w}=\mathsf y_{|\mathbf w|}(p,\mathbf w)$, and $p_b=p+\operatorname{pt}(b)$ for a hold $b$. For $\bar o\in\mathcal P$ let $\mathcal U(\bar o)$, the \emph{bridge lists}, be the set of lists $\mathbf w$ of positive mass such that $\bar o_{\mathbf w}$ is black and $\mathsf y_u(\bar o,\mathbf w)$ is not black for $u<|\mathbf w|$. For a black $v$ let $\mathcal E(v)$, the \emph{entry lists}, be the set of nonempty lists $\mathbf w$ of positive mass such that $v_{\mathbf w}$ is black with $l(v_{\mathbf w})>l_*(v)$, and no $\mathsf y_u(v,\mathbf w)$ with $1\le u<|\mathbf w|$ has these two properties. Both sets are prefix-disjoint, and their lists $\mathbf w$ satisfy $j(\bar o)+|\mathbf w|\le j(\bar o_{\mathbf w})\le J$. The path of a list agrees with the path of each of its prefixes up to the prefix's length. So, for the complete path of a list $\mathbf b\in\mathfrak B^L$ of positive mass from $\bar o$, $u_1$ exists and equals $\tilde u$ if and only if $\tilde u\le L$ and $\mathbf b_{[1,\tilde u]}\in\mathcal U(\bar o)$; and if $\bar o=v$ is black, then $u_1=0$, and $u_2$ exists and equals $\tilde u$ if and only if $1\le\tilde u\le L$ and $\mathbf b_{[1,\tilde u]}\in\mathcal E(v)$. \begin{lemma}[Restart at a trace time] \label{lem_tr_restart}\label{lem_tr_first_stop_prefix}\label{lem_tr_entry_prefix} Let $\mathsf y_u=\mathsf y_u(\bar o,\mathbf b)$ be the complete path of $\mathbf b\in\mathfrak B^L$ from $\bar o$. Suppose $u_i=\tilde u$ exists, and let $\mathsf y'_u=\mathsf y_u(\mathsf y_{\tilde u},\mathbf b_{[\tilde u+1,L]})$. Then $j(\mathsf y_{\tilde u})+(L-\tilde u)>J$, and for every $k\ge1$, $u_{i-1+k}$ exists if and only if the $k$th trace time $u'_k$ of $\mathsf y'$ does, and then $u_{i-1+k}=\tilde u+u'_k$. \end{lemma} \begin{proof} By Lemma~\ref{lem_tr_concat}(3),(2), $j(\mathsf y_{\tilde u})\ge j(\bar o)+\tilde u$ and $\mathsf y'_u=\mathsf y_{\tilde u+u}$. Since $\mathsf y'_0=\mathsf y_{\tilde u}$ is black, $u'_1=0$, matching $u_i=\tilde u$, and both sequences are continued by the same rule applied to the same points. \end{proof} \subsection{One passage} Between two trace times the path climbs from a black point $v$ above its column top. For $\omega\in\N$ let $\Pi_\omega$ be the set of nonempty lists $\mathbf f$ of positive mass with $l(\operatorname{pt}_i(\mathbf f))\le\omega$ for $i<|\mathbf f|$ and $l(\operatorname{pt}_{|\mathbf f|}(\mathbf f))>\omega$, that is, the lists whose hold points form a first-passage list over height $\omega$ (Definition~\ref{def_rn_fp_word}). Grouping lists by their hold points and using \eqref{eq:fbc-eta} gives, for $\Psi\ge0$, \begin{equation}\label{eq:tr-passage-law} \sum_{\mathbf f\in\Pi_\omega}\mathfrak q(\mathbf f)\,\Psi(\operatorname{pt}_{|\mathbf f|}(\mathbf f))=\sum_{x\in\mathcal P}\mathsf F_\omega(x)\Psi(x). \end{equation} In particular $\sum_{\mathbf f\in\Pi_\omega}\mathfrak q(\mathbf f)=1$. The reward of a passage is bounded below at the place where its raw word first exceeds $\omega$. \begin{lemma}[First raw crossings]\label{lem_tr_passage_raw3}\label{lem_c3_crossing_partition} Let $\omega\in\N$. For integers $c\ge2$, $1\le o\le c$ and $r\ge1$ let $\mathcal X_\omega(c,o,r)$ be the set of $\mathbf f\in\Pi_\omega$ whose raw word has length at least $r$, $r$th raw letter $c$, and $\sigma_r(\mathbf f)=\omega+o$. \begin{enumerate} \item The sets $\mathcal X_\omega(c,o,r)$ partition $\Pi_\omega$; for $\mathbf f\in\mathcal X_\omega(c,o,r)$, $r$ is the least index with $\sigma_r(\mathbf f)>\omega$, and the position $r$ lies in the last hold of $\mathbf f$. \item For $\Psi\ge0$ on finite words, \[ \sum_{\mathbf f\in\mathcal X_\omega(c,o,r)}\mathfrak q(\mathbf f)\Psi(\mathbf c(\mathbf f))=\mathfrak q(c)\sum_{\mathbf a}\sum_{\mathbf s}\mathfrak q(\mathbf a)\mathfrak q(\mathbf s)\Psi(\mathbf a\,c\,\mathbf s), \] where $\mathbf c(\mathbf f)$ is the raw word, $\mathbf a$ runs over the words of $r-1$ raw letters with sum $\omega+o-c$, and $\mathbf s$ is empty if $c\in\{4,5\}$ and runs over the hold words if $c\notin\{4,5\}$. In particular the mass of $\mathcal X_\omega(c,o,r)$ is $\mathfrak q(c)\mathsf R(r-1,\omega+o-c)$, and if $c\notin\{4,5\}$ and $H\in\N$, the lists of $\mathcal X_\omega(c,o,r)$ whose raw word has length greater than $r+H$ have mass $\mathfrak q(c)\mathsf R(r-1,\omega+o-c)(\frac{11}{16})^H$. \item For $v\in\mathcal P$ and $\mathbf f\in\mathcal X_\omega(c,o,r)$, $\operatorname{Rw}(v,\mathbf f;|\mathbf f|)\ge R_c(v+(r,\omega+o))$. \end{enumerate} \end{lemma} \begin{proof} Raw letters of lists of positive mass are at least $2$, so $i\mapsto\sigma_i(\mathbf f)$ increases strictly, from $0$ to $l(\operatorname{pt}_{|\mathbf f|}(\mathbf f))>\omega$. If $\mathbf f\in\mathcal X_\omega(c,o,r)$, then $\sigma_{r-1}(\mathbf f)=\omega+o-c\le\omega<\sigma_r(\mathbf f)$, so $r$ is the least index with $\sigma_r>\omega$; conversely that index $r$, its letter $c$ and $o=\sigma_r-\omega\in[1,c]$ define a class containing $\mathbf f$. Every hold but the last ends at height at most $\omega$, and the hold containing position $r$ ends above $\omega$, so it is the last one. This proves (1). For (2), a word of raw letters whose last letter is closing is the raw word of exactly one list of positive mass (cut after each closing letter), with mass the product of the letter masses. By (1), the raw words of $\mathcal X_\omega(c,o,r)$ are exactly the words $\mathbf a\,c\,\mathbf s$ described: if $c$ is closing the word ends at $r$, and otherwise the letters after $r$ up to the next closing letter form a hold word. Summing over $\mathbf a$ gives $\mathsf R(r-1,\omega+o-c)$ (Definition~\ref{def_rn_raw_mass}), and the hold words have total mass $1$ and those with more than $H$ raw letters, i.e.\ at least $H$ nonclosing ones, have mass $\sum_{N\ge H}(\frac{11}{16})^N\frac5{16}=(\frac{11}{16})^H$. (3) follows from Lemma~\ref{lem_tr_concat}(6), since rewards are nonnegative. \end{proof} The angle at a crossing point within the exit width $f_\omega=\floor{(5\omega+16)/16}$ is an odd dyadic fraction, perturbed by at most $9^r\varepsilon2^{-\omega}$ (Lemma~\ref{lem:odd-dyadic-exit}), and the raw-letter factor there is bounded by disjoint packets of the sum \eqref{eq:fbc-pair-factor}, as in the proof of Lemma~\ref{lem:odd-packets}. For a raw letter $c\ge3$ write the factor as $\Phi_{c-1}$, so that $\varphi_c(p)=\Phi_{c-1}(\vartheta(p))$, and put \[ \Phi^{\mathrm{cap}}_c(\theta)=\max\{\Phi_{c-1}(\theta),2^{-16}\}\quad(3\le c\le16),\qquad\Phi^{\mathrm{cap}}_c=1\text{ otherwise}. \] By Definition~\ref{def:paid-reward}, $e^{-zR_c(p)}\le\Phi^{\mathrm{cap}}_c(\vartheta(p))$ for every $p$ with $j(p)\le J$. The function $\Phi^{\mathrm{cap}}_c$ is even and has period $1$, as the frequencies $2^a-1$ are integers. \begin{definition}[Packet gains]\label{def_tr_packet_value}\label{def_tr_packet_deficit} An \emph{envelope table} is a finite set $T$ of pairs $(s,t)$ of integers $s\ge1$, $t\ge2$ with numbers $V_{s,t}\in[0,1]$. For $3\le c\le16$ and $1\le o\le c$, a \emph{packet family} for $(c,o)$ is a set of pairs $(i,t)$ with $i\ge0$, $i+t\le c-1$ and $(o-i,t)\in T$, whose index sets $\{i,\ldots,i+t-1\}$ are pairwise disjoint, and \[ a_{c,o}[V]=\max\sum_{(i,t)}t\,(1-V_{o-i,t}) \] over the packet families (computed by the downward recursion $F(c-1)=0$, $F(i)=\max(\{F(i+1)\}\cup\{t(1-V_{o-i,t})+F(i+t)\})$, $a_{c,o}[V]=F(0)$). The \emph{packet gains} are $\delta_{c,o}=a_{c,o}[U]/(c-1)$, with the table $U$ of Lemma~\ref{lem:odd-packets}. \end{definition} \begin{lemma}[Packet families]\label{lem_tr_packet_bound}\label{lem_tr_packet_range} Let $V$ be an envelope table with $\Phi_t((m+\beta)/2^s)\le V_{s,t}$ for every $(s,t)$ in it, every odd $m$ and every real $|\beta|\le\bar\beta$. Let $3\le c\le16$, $1\le o\le c$, $m$ odd, $|\beta|\le\bar\beta$ and $\theta\equiv(m+\beta)/2^o\pmod1$. Then $\Phi_{c-1}(\theta)\le1-a_{c,o}[V]/(c-1)$. Moreover $0\le\delta_{c,o}\le\frac12$; in particular $\delta_{3,1}=\frac12$ and $\delta_{4,1}=\frac{41}{100}$. \end{lemma} \begin{proof} Apply Lemma~\ref{lem_ch_packet_bound} to an optimal packet family, with $\Phi_t(2^i\theta)\le V_{o-i,t}$ as $2^i\theta\equiv(m+\beta)/2^{o-i}$. The entries of $U$ lie in $[\frac12,1]$, so each packet contributes at most $t/2$ and $\delta_{c,o}\le\frac12$; the two values are exact evaluations. \end{proof} \begin{lemma}[Reward at an exit point]\label{lem_tr_exit_reward} Let $v$ be black, $\omega=\operatorname{gap}(v)$, $1\le r\le f_\omega$, $3\le c\le16$ and $1\le o\le c$, and put $y=v+(r,\omega+o)$. Then $j(y)\le J$, $\vartheta(y)\equiv(m+\beta)/2^o$ with $m$ odd and $|\beta|\le9^r\varepsilon2^{-\omega}<\frac13$, and \[ e^{-zR_c(y)}\le\Phi^{\mathrm{cap}}_c(\vartheta(y))\le1-\delta_{c,o}. \] \end{lemma} \begin{proof} Here $y=(j(v)+r,l_{\Delta(v)}+o)$, and Lemma~\ref{lem:odd-dyadic-exit}(a),(b) give $j(y)\le J$ and the localization. Lemma~\ref{lem_tr_packet_bound} with $V=U$ and $\bar\beta=\frac13$ (Lemma~\ref{lem:odd-packets}), and $2^{-16}<\frac12\le1-\delta_{c,o}$, finish the proof. \end{proof} At a few gaps we need sharper bounds for single factors, obtained on finitely many cells. \begin{lemma}[Capped factors on cells]\label{lem_tr_cap_lipschitz}\label{lem_tr_cap_upper}\label{lem_tr_gap_one_cells}\label{lem_tr_phi2_small} \leavevmode \begin{enumerate} \item With $a_j=2^j-1$ and $\ell_c=\frac{44}{7(c-1)}\sum_{j=0}^{c-2}|a_j-a_{\floor{(c-2)/2}}|$ for $3\le c\le16$ ($\ell_c=0$ otherwise), $|\Phi^{\mathrm{cap}}_c(\theta)-\Phi^{\mathrm{cap}}_c(\theta')|\le\ell_c|\theta-\theta'|$. \item For rational $\theta$ let $\overline U_c(\theta)$ be the least $k/10^8$, $k\in\N$, with $(k/10^8)^2\ge(c-1)^{-2}\bigl(c-1+2\sum_{id_{\mathrm{pass}}$. Each $\mathsf D(\omega)$ is an explicit rational, as $\mathsf R(k,l)=\binom{l-1}{2k-1}2^{-l}$ for $k,l\ge1$ (Lemma~\ref{lem_rn_raw_mass_formula}). Exact evaluation gives $\mathsf D(0)=\frac{59987721}{1638400000}\ge d_{\mathrm{pass}}$, $\mathsf D(1)=\frac{832326661}{6553600000}$, $\mathsf D(6)=\frac{108692439667}{524288000000}$, $\mathsf D(9)=\frac{911532121133}{4194304000000}$, $\mathsf D(13)=\frac{7713203895523}{33554432000000}$, $\mathsf D(16)=\frac{195010696398427}{858993459200000}$, and, over the other $505$ integers $2\le\omega\le511$, the minimum $\mathsf D(15)=\frac{61817834604121}{268435456000000}$. For $\omega\ge512$: first, for $2\le l\le\omega$, $\sum_{r=1}^{f_\omega}\mathsf R(r-1,l)\ge\frac14-\frac{25}{2\omega}\ge\frac{231}{1024}$. Indeed the full row sums to $\frac14$ (Lemma~\ref{lem_rn_raw_mass_formula}), and the omitted part is at most $\frac12\Prob(X\ge2f_\omega-1)$ for $X$ binomial with parameters $l-1,\frac12$, whose threshold exceeds the mean by at least $\frac{\omega-3}8\ge\frac\omega{10}$, while $\operatorname{Var}X\le\frac\omega4$; apply Chebyshev's inequality. Second, writing $\omega=16k+s$, $0\le s<16$, $k\ge32$, we have $f_\omega=5k+1+\floor{5s/16}$ and $9^{\floor{5s/16}}\le2^s$, so $9^{f_\omega}2^{-\omega}\le9(9^5/2^{16})^{32}$ and $\varsigma_\omega<\frac1{50}$ by exact comparison. Hence \[ \mathsf D(\omega)\ge\frac{231}{1024}\Bigl(\sum_{c=3}^{16}\mathfrak q(c)\sum_{o=1}^c\delta_{c,o}+\frac14\Bigl(\frac{49}{50}-\frac12\Bigr)\Bigr)=\frac{231}{1024}\Bigl(\frac{15036545331}{16384000000}+\frac{3}{25}\Bigr)=\frac{3927606451461}{16777216000000}, \] which exceeds $d_{\mathrm{pass}}$. \end{proof} \begin{lemma}[Entry lists split]\label{lem_tr_entry_split} Let $v$ be black and $\omega=\operatorname{gap}(v)$. The map $(\mathbf f,\mathbf w)\mapsto\mathbf f\mathbf w$ is a bijection from the pairs with $\mathbf f\in\Pi_\omega$ and $\mathbf w\in\mathcal U(v_{\mathbf f})$ onto $\mathcal E(v)$. \end{lemma} \begin{proof} For a list $\mathbf b$, $l(\mathsf y_u(v,\mathbf b))>l_*(v)$ if and only if $l(\operatorname{pt}_u(\mathbf b))>\omega$. Given $\mathbf b\in\mathcal E(v)$, let $k$ be the least index with $l(\operatorname{pt}_k(\mathbf b))>\omega$. Then $\mathbf f=\mathbf b_{[1,k]}$ is the only prefix of $\mathbf b$ in $\Pi_\omega$, every $\mathsf y_u(v,\mathbf b)$ with $u\ge k$ lies above $l_*(v)$ (Lemma~\ref{lem_tr_concat}(3)), and the conditions defining $\mathcal E(v)$ say that $\mathbf b_{[k+1,|\mathbf b|]}\in\mathcal U(\mathsf y_k(v,\mathbf b))$. The same facts show that each $\mathbf f\mathbf w$ lies in $\mathcal E(v)$. \end{proof} \subsection{The entry kernel} For $p\in\mathcal P$ and a list $\mathbf w$ write $\mathfrak q^p(\mathbf w)=\mathfrak q(\mathbf w)e^{-z\operatorname{Rw}(p,\mathbf w;|\mathbf w|)}$. The \emph{entry kernel} acts on nonnegative functions on black points by \[ \mathsf K\Psi(v)=\sum_{\mathbf w\in\mathcal E(v)}\mathfrak q^v(\mathbf w)\,\Psi(v_{\mathbf w}); \] it is positive and homogeneous. The \emph{bridge mass} of $p\in\mathcal P$ is $\operatorname{Br}(p)=\sum_{\mathbf w\in\mathcal U(p)}\mathfrak q^p(\mathbf w)\le1$, by Lemma~\ref{lem_tr_concat}(4). By Lemma~\ref{lem_tr_entry_split} and Lemma~\ref{lem_tr_concat}(1),(2), \begin{equation}\label{eq:tr-bridge} \mathsf K\mathbf 1(v)=\sum_{\mathbf f\in\Pi_{\operatorname{gap}(v)}}\mathfrak q^v(\mathbf f)\operatorname{Br}(v_{\mathbf f})\le S(v), \end{equation} with $S(v)$ as in Lemma~\ref{lem_tr_passage_bound}. Hence $\mathsf K\mathbf1(v)\le1-\mathsf D(\operatorname{gap}(v))<\frac{77}{100}$ unless $\operatorname{gap}(v)\in\{0,1,6,9,13,16\}$ (for $\operatorname{gap}(v)=3$ use $\frac{37}{160}>\frac{23}{100}$). At these six gaps a single crossing is not enough, and we follow the raw word further: as long as a raw letter cannot end the entry, the path is continued, and each factor read off along the way is paid. \begin{definition}[Entry trees]\label{def_tr_entry_trees}\label{def_tr_tree_policy}\label{def_tr_tree_datum}\label{def_tr_tree_factor}\label{def_tr_tree_cost}\label{def_tr_tree_leaves}\label{def_tr_tree_lip}\label{def_tr_white_policy}\label{def_tr_tail_gain}\label{def_tr_tree_valid} A \emph{policy} is a set $W$ of triples $(r,h,c)$ of integers with $c\ge2$ and $h+c$ bounded; the triple $(r,h,c)$ means that the raw letter $c$ at depth $r$ and height $h$ is \emph{continued}. A \emph{tree datum of height $H$} is a pair $(\mathrm{cut},W)$ of a function $\mathrm{cut}:\N\to\N$ and a policy such that $c\le\mathrm{cut}(h)$ for $(r,h,c)\in W$, $\mathrm{cut}(0)\le\min(16,H)$, and $\mathrm{cut}(h+c)\le16$, $h+c+\mathrm{cut}(h+c)\le H$ for $(r,h,c)\in W$. For real $X$ put $\psi_{r,h,c}(X)=\Phi^{\mathrm{cap}}_c(9^rX/2^{h+c})$ if $2\le c\le\mathrm{cut}(h)$ and $\psi_{r,h,c}=1$ otherwise, and define the \emph{tree cost} by downward recursion on $h$: \[ F_{r,h}(X)=1-\sum_{c=2}^{\mathrm{cut}(h)}\mathfrak q(c)\bigl[1-\psi_{r,h,c}(X)G_{r,h,c}(X)\bigr], \] with $G_{r,h,c}=F_{r+1,h+c}$ if $(r,h,c)\in W$ and $G_{r,h,c}=1$ otherwise, and its \emph{Lipschitz constant} $L_{r,h}=9^r2^{-h}\sum_{c=3}^{\mathrm{cut}(h)}\mathfrak q(c)\ell_c2^{-c}+\sum_{(r,h,c)\in W}\mathfrak q(c)L_{r+1,h+c}$. For $\omega\in\N$, integers $C,H',m$ and reals $a\le b$, the \emph{white-test policy} $W^{\omega,C,H'}_{m,a,b}$ consists of the triples with $2\le c\le C$, $h+c\le H'$ and either $c\notin\{4,5\}$, or $h+c\le\omega$, or \[ \operatorname{dist}\Bigl(\frac{9^r(2^\omega m+\frac{a+b}2)}{2^{h+c}},\Z\Bigr)-\frac{9^r(b-a)}{2^{h+c+1}}>\varepsilon. \] A policy is \emph{valid} at a black point $v$ if, for every $(r,h,c)\in W$ with $c\in\{4,5\}$, the point $v+(r+1,h+c)$ is white or $l(v)+h+c\le l_*(v)$. The \emph{root correction} is $T_{\omega,k}=\sum_{c=\max(k,\omega,2)+1}^{16}\mathfrak q(c)\delta_{c,c-\omega}$. \end{definition} \begin{lemma}[Tree costs]\label{lem_tr_tree_angle}\label{lem_tr_white_policy_valid}\label{lem_tr_tree_cylinder_bound}\label{lem_tr_tree_cost_range}\label{lem_tr_tree_cost_lipschitz}\label{lem_tr_zero_reflect} Let $v$ be black, $\omega=\operatorname{gap}(v)$ and $B\ge1$. \begin{enumerate} \item There are an odd $m$ with $0\varepsilon$ and the point is white. (3) Let $\mathbf w\in\mathcal E(v)$ with raw word $\mathbf c$. Follow $\mathbf c$ from the root: the edge $(i-1,\mathbf c_1+\cdots+\mathbf c_{i-1},\mathbf c_i)$ is either in $W$ or not. It cannot be in $W$ at the last position of $\mathbf c$: a nonclosing letter does not end a hold, and by validity a continued closing letter ends at a white point or at height at most $l_*(v)$, so not at the end of an entry. Hence $\mathbf c$ begins with exactly one \emph{leaf} $\mathbf l$, a word whose edges are continued except the last. Along $\mathbf l$, $\operatorname{Rw}(v,\mathbf w;|\mathbf w|)$ is at least the sum of the rewards at the points $v+(i,\mathbf l_1+\cdots+\mathbf l_i)$ (Lemma~\ref{lem_tr_concat}(6)); these points have $j\le J$ since the entry ends at a black point further right, and their heights are at most $H$, so by (1) and Definition~\ref{def:paid-reward} their factors are at most $\psi_{i-1,\mathbf l_1+\cdots+\mathbf l_{i-1},\mathbf l_i}(2^\omega m+\alpha)$. The entry lists beginning with $\mathbf l$ have mass at most $\prod_i\mathfrak q(\mathbf l_i)$ (extend them to raw length $J$ and use \eqref{eq:fbc-raw-law}), and, by induction on $h$, $F_{0,0}$ is the sum over leaves of $\prod_i\mathfrak q(\mathbf l_i)\psi_i$. Finally, for $c>\max(\mathrm{cut}(0),\omega,2)$ the one-letter leaf $(c)$ has factor $1$ in $F_{0,0}$, while Lemma~\ref{lem_tr_exit_reward} with $r=1$, $o=c-\omega$ bounds its factor by $1-\delta_{c,c-\omega}$; this gives the correction $T_{\omega,\mathrm{cut}(0)}$. (4) By downward induction on $h$, using $\psi\in[0,1]$, $\sum_c\mathfrak q(c)=1$, $|pg-p'g'|\le|p-p'|+|g-g'|$ for numbers in $[0,1]$, and (Lemma~\ref{lem_tr_cap_lipschitz}(1)) the constant $\ell_c9^r2^{-h-c}$ of $\psi_{r,h,c}$. (5) All retained heights satisfy $h+c\le17$, so $9^r(2^{17}-X)/2^{h+c}\equiv-9^rX/2^{h+c}$; the capped factors are even and $1$-periodic, and $\operatorname{dist}(\cdot,\Z)$ is even, so the policies and the costs coincide. \end{proof} \begin{lemma}[The six special gaps]\label{lem_tr_tree_certificate}\label{lem_tr_zero_gap_tree}\label{lem_tr_direct_certificate}\label{lem_tr_direct_positive} If $v$ is black and $\operatorname{gap}(v)\in\{0,1,6,9,13,16\}$, then $\mathsf K\mathbf 1(v)<\frac{77}{100}$. \end{lemma} \begin{proof} For a tree datum and a cell $[a,b]$ we bound $F_{0,0}$ by \emph{node values}: if $f_c\ge\psi_{r,h,c}$ and $g_c\ge G_{r,h,c}$ (with $g_c\ge1$ unless the edge is continued), then $F_{r,h}\le1-\sum_c\mathfrak q(c)(1-f_cg_c)$, because $\psi,G\in[0,1]$ (Lemma~\ref{lem_tr_tree_angle}(4)). \emph{Gap $0$.} Lemma~\ref{lem_tr_tree_angle}(1) with $B=17$ gives an odd $m<2^{17}$ and $|\alpha|\le9\varepsilon<\frac13$. Take $\mathrm{cut}^0(h)=\min\{12,17-h\}$ for $h\le17$ and $W=W^{0,12,14}_{m,a,b}$; every triple of $W$ has $c\le12$ and $h+c\le14$, so $(\mathrm{cut}^0,W)$ is a tree datum of height $17$, valid at $v$ by Lemma~\ref{lem_tr_tree_angle}(2). By Lemma~\ref{lem_tr_tree_angle}(3), it suffices to find $a\le\alpha\le b$ in $[-\frac13,\frac13]$ with $F_{0,0}(m+\alpha)<\frac{77}{100}+T_{0,12}$, where $T_{0,12}=\sum_{c=13}^{16}\mathfrak q(c)\delta_{c,c}=\frac{1197}{13107200}$. By Lemma~\ref{lem_tr_tree_angle}(5) we may assume $m<2^{16}$ (replace $(m,\alpha)$ by $(2^{17}-m,-\alpha)$). This is a finite computation. The odd integers are split into $84$ residue classes $m_0+2^k\Z$, $k\le17$, obtained from $1+2\Z$ by repeated halving; four of them contain no $m<2^{16}$. The cells are the dyadic subintervals $[\frac{p-1}{3\cdot2^d},\frac{p+1}{3\cdot2^d}]$ of $[-\frac13,\frac13]$. For a class, a cell and every triple with $h+c\le k$, the white test of Definition~\ref{def_tr_entry_trees} and the factor $\psi_{r,h,c}(m+\beta)$, up to the Lipschitz term $\ell_c9^r2^{-h-c}$ times the half-width (Lemma~\ref{lem_tr_cap_lipschitz}(1)), depend only on the class and the cell. Bound each factor by its value at the midpoint, computed from rigorous enclosures of the units $e^{2\pi\mathrm i2^jq}$ (a degree-$17$ Taylor polynomial at a rational multiple of $\pi$, followed by repeated squaring, all with error bounds on the scale $2^{-60}$), plus the Lipschitz term; treat edges with $h+c>k$ or a failed white test as not continued; and compute the node values from depth $8$ down to the root, rounding upward. A cell is accepted if the root value is below $\frac{77}{100}+T_{0,12}$, and otherwise replaced by its two halves. The computation, in exact integer arithmetic, accepts $211$ cells of depth at most $6$ for the $80$ classes, covering $[-\frac13,\frac13]$ for each class, with least margin greater than $2.26\cdot10^{-4}$. \emph{Gaps $1,6,9,13,16$.} Let $p=4$ for $\omega\in\{1,6,9\}$ and $p=1$ for $\omega\in\{13,16\}$. Lemma~\ref{lem_tr_tree_angle}(1) with $B=p+8$ gives $m<2^{p+8}$ and $\alpha$. Take the constant cutoff $8$ and $W=W^{\omega,8,\omega+p}_{m,a,b}$, a tree datum of height $\omega+p+8$, valid at $v$. The root corrections are $T_{1,8}=\frac{4595457}{1310720000}$, $T_{6,8}=\frac{13575489}{1638400000}$, $T_{9,8}=\frac{800801}{204800000}$, $T_{13,8}=\frac{697807}{3276800000}$ and $T_{16,8}=0$. For each odd $m<2^{p+8}$, start from $[-\frac13,\frac13]$ (from its halves if $\omega\in\{6,9\}$, from its quarters if $\omega\in\{13,16\}$); on a cell with half-width $\delta$ and midpoint $u$, bound $F_{0,0}(2^\omega m+u)$ by node values with the factors computed from the cosine formula of Lemma~\ref{lem_tr_cap_lipschitz}(2) (a degree-$14$ Taylor polynomial at $2\pi\cdot\frac{3141592654}{10^9}$, error at most $10^{-9}$), and add $\Lambda\delta$, where $\Lambda$ bounds $L_{0,0}$ for the policy of all triples with $c\le8$, $h+c\le\omega+p$, which contains $W$ (Lemma~\ref{lem_tr_tree_angle}(4)). Accept the cell if the result is below $\frac{77}{100}+T_{\omega,8}$, and otherwise halve it. The computation accepts $2204$, $4096$, $4112$, $1024$ and $1054$ pairs of a value of $m$ and a cell for $\omega=1,6,9,13,16$, with least margin greater than $1.39\cdot10^{-5}$ (at $\omega=16$). \end{proof} \begin{proposition}[The entry kernel]\label{lem_tr_kernel_two}\label{lem_tr_kernel_one}\label{lem_tr_kernel_powers} For every black point $v$ and every $k\in\N$, $\mathsf K\mathbf 1(v)\le\frac{77}{100}$ and $\mathsf K^k\mathbf 1(v)\le(\frac{77}{100})^k$. \end{proposition} \begin{proof} The first bound is Lemma~\ref{lem_tr_tree_certificate} at the six special gaps, and \eqref{eq:tr-bridge} with Lemma~\ref{lem_tr_passage_bound} elsewhere: $\frac{37}{160}$, $\frac{61817834604121}{268435456000000}$ and $\frac{3927606451461}{16777216000000}$ all exceed $\frac{23}{100}$. The powers follow by induction, as $\mathsf K$ is positive and homogeneous. \end{proof} \subsection{Accumulated rewards at the trace times} For $\mathbf b\in\mathfrak B^L$ whose path from $\bar o$ is complete and $k\in\N$, put $\mathcal Z_{k+1}(\bar o,\mathbf b)=e^{-z\operatorname{Rw}(\bar o,\mathbf b;u_{k+1})}$ if $u_{k+1}$ exists, and $\mathcal Z_{k+1}(\bar o,\mathbf b)=0$ otherwise. \begin{lemma}[Explicit form of Tao's Lemma 7.9]\label{lem_tr_lemma79}\label{lem_tr_moment_black} Let $\bar o\in\mathcal P$ and $L\in\N$ with $j(\bar o)+L>J$. Then \begin{enumerate} \item if $\bar o=v$ is black, then $\sum_{\mathbf b\in\mathfrak B^L}\mathfrak q(\mathbf b)\mathcal Z_{k+1}(v,\mathbf b)=\mathsf K^k\mathbf 1(v)$ for every $k\in\N$; \item for every $k\in\N$, $\sum_{\mathbf b\in\mathfrak B^L}\mathfrak q(\mathbf b)\mathcal Z_{k+1}(\bar o,\mathbf b)\le(\frac{77}{100})^k$. \end{enumerate} \end{lemma} \begin{proof} (1) We induct on $k$, for all black $v$ and all $L$ with $j(v)+L>J$ at once. For $k=0$, $u_1=0$, $\mathcal Z_1=1$ and the total mass is $1$. For the step, the description of $u_2$, Lemma~\ref{lem_tr_restart} with $i=2$ and Lemma~\ref{lem_tr_concat}(2) give, for $\mathbf b$ of positive mass, \[ \mathcal Z_{k+2}(v,\mathbf b)=\sum_{u=1}^L\mathbf 1[\mathbf b_{[1,u]}\in\mathcal E(v)]\,e^{-z\operatorname{Rw}(v,\mathbf b_{[1,u]};u)}\,\mathcal Z_{k+1}(\mathsf y_u(v,\mathbf b),\mathbf b_{[u+1,L]}), \] with at most one nonzero term. Split $\mathbf b$ at $u$ by Lemma~\ref{lem_tr_concat}(1). For $\mathbf w\in\mathcal E(v)$, $v_{\mathbf w}$ is black, $j(v_{\mathbf w})+L-|\mathbf w|>J$ and $|\mathbf w|\le J-j(v)\mathsf s_\iota m$ below the top edge of its triangle (Lemma~\ref{lem_c3_case3}). Following Tao \cite[Case~3 of Proposition~7.8 and Lemma~7.10]{Tao}, we continue the hold walk after its first passage above the top edge, keeping the reward paid during that passage. Outside rare events, a low reward forces many trace times on a fixed schedule (Lemma~\ref{lem_tr_survival_time}), which Lemma~\ref{lem_tr_lemma79} makes unlikely; the main rare event, a visit to a large triangle, is bounded by a packing estimate (Lemma~\ref{lem_c3_outside_mass}). The paid first passage has mass less than $\mathsf q_{\mathrm{mass}}=\frac{38177}{125000}$ (Lemma~\ref{lem_c3_initial_mass}), and for $\iota=\mathrm b$ the last trace factors are replaced by stopped stages (Lemma~\ref{lem_c3_timed_stages}). Throughout, $\iota$ is fixed and $\mathsf Q$, $\mathsf Q_m$ are formed with the exponent $A_\iota$; we put $\lambda_0=\lambda-\frac14$; then $\frac5{16}\le\lambda<\frac8{25}$ and $\frac1\lambda<\frac{158497}{50000}<\frac{127}{40}$ (exact comparisons $9^5\le2^{16}$, $2^{25}<9^8$, $9^{50000}<2^{158497}$). The schedule constants $T_\iota$, $r_\iota$, $p_0(\iota)$, $\alpha_\iota$, $H_\iota$ are those of Table~\ref{tab:fourier-params}, the size factors $K_i(\iota)$ are those of Definition~\ref{def_eps_star}, and $p_i$, $S_i$, $P_\iota$, $V_\iota$ are those of Definition~\ref{def_s02_schedule}; we drop the index $\iota$ from $K_i$, $p_i$ and $S_i$. For $u\in\N$ let $i(u)$ be the least $i\le r_\iota$ with $u\le p_i$ ($i(u)=r_\iota$ if $u>p_{r_\iota}$), and put \[ \beta_\iota(u)=S_{i(u)},\qquad h_\iota(u)=\ceil{\alpha_\iota\beta_\iota(u)}+H_\iota,\qquad\mathfrak g_\iota(u)=u+h_\iota(u)+T_\iota+1. \] Since $K_{i+1}\ge268$ and $268\alpha_\iota\ge1$, $S_i\le S_{i+1}$; so $\beta_\iota$, $h_\iota$ and $\mathfrak g_\iota$ are nondecreasing, $\beta_\iota(u)=S_i$ for $p_{i-1}l_*(y_q)$. \item If $a\notin\mathrm{Clr}$, $0\le k\le r_\iota$ and $a$ has no oversize hit at a time $u\le p_{k-1}$, then the fresh path has at least $k+1$ trace times and $u_i\le p_{i-1}$ for $1\le i\le k+1$. \end{enumerate} \end{lemma} \begin{proof} (1) As $a\notin\mathrm{Bad}^p_m$, $j(y_{P_\iota})\frac9{13}$, so $\operatorname{gap}(y_q)<\frac{13}9\beta_\iota(q)$. As $a\notin\mathrm{Clr}$ and $q+h_\iota(q)\le P_\iota-1\le J$, $l(y_{q+h_\iota(q)})-l(y_q)>\frac{13}9\beta_\iota(q)$, so $l(y_u)>l_*(y_q)$ for $u\ge q+h_\iota(q)$ (Lemma~\ref{lem_tr_concat}(3)). By (1) the run $[q+h_\iota(q)+1,\mathfrak g_\iota(q)]$ contains a hit. (3) By induction on $i$: (1) gives $u_1\le p_0$, and if $u_i\le p_{i-1}$ with $i\le k$, then $\mathfrak g_\iota(u_i)\le\mathfrak g_\iota(p_{i-1})=p_i\le P_\iota-1$ and there is no oversize hit at $u_i$, so (2) gives $u_{i+1}\le p_i$. \end{proof} \begin{lemma}[Discounted mass at the trace times]\label{lem_tr_discounted_trace}\label{lem_tr_trace_event} Let $p\in\mathcal P$, $k\in\N$, $\phi\ge0$ on $\mathcal P$, $D\subseteq\mathcal P$, and let $\mathcal S$ be a set of atoms $(x,\mathbf b)$ with $x\in D$ whose fresh path has at least $k+1$ trace times, with $u_{k+1}\le P_\iota-1$. Then \[ \sum_{(x,\mathbf b)\in\mathcal S}\phi(x)\mathfrak q(\mathbf b)e^{-z\operatorname{Rw}^p_{P_\iota-1}(x,\mathbf b)}\le\Bigl(\frac{77}{100}\Bigr)^k\sum_{x\in D}\phi(x). \] \end{lemma} \begin{proof} As the accumulated reward is nondecreasing, $e^{-z\operatorname{Rw}^p_{P_\iota-1}}\le\mathcal Z_{k+1}(p+x,\mathbf b)$. Enlarge $\mathcal S$ to all atoms with $x\in D$ and apply Lemma~\ref{lem_tr_lemma79}(2) with $L=J$. \end{proof} \begin{lemma}[Slow clearing is rare]\label{lem_tr_clear_mass}\label{lem_tr_vpgf_clear}\label{lem_tr_ver_low_clear} Let $p\in\mathcal P$, $\omega\in\N$ and $P_\iota\le J$. Then $\Prob_{p,\omega}(\mathrm{Clr})\le E^{\mathrm{cl}}_\iota$, with $E^{\mathrm{cl}}_\iota$ as in Definition~\ref{def_c3_error}. \end{lemma} \begin{proof} Put $y=y^{\mathrm{cl}}_\iota$, $v=v^{\mathrm{cl}}_\iota$ (Definition~\ref{def_c3_allowances}). Fix $u$ with $u+h\le P_\iota-1$, $h=h_\iota(u)$, $Y=\frac{13}9\beta_\iota(u)$. By \eqref{eq:c3-marginal} the atoms with $\sum_{i=u+1}^{u+h}l(\operatorname{pt}(b^i))\le Y$ have mass at most $\sum_{\mathbf h\in\mathcal P^h}\eta^{\otimes h}(\mathbf h)\mathbf 1[\sum l(\mathbf h_i)\le Y]\le y^{-Y}\mathsf V(y)^h\le y^{vh-Y}$, by Lemma~\ref{lem_c3_gates}(3). If $p_{i-1}0$, and $\log y\le-(1-y)$ gives $y^{vh-Y}\le e^{-t_i}\le1/P_{80}(t_i)$ (Lemma~\ref{lem_s03_log3_bounds}(4)). The admissible $u$ in the block $(p_{i-1},p_i]$ ($[0,p_0]$ for $i=0$) are those with $u\le P_\iota-1-h_\iota(p_i)$, and their number is $n^{\mathrm{cl}}_i(\iota)$. Sum over the blocks. \end{proof} \subsection{Row geometry of triangles} For a triangle $\Delta$ and $l\in\Z$ put $\tip_\Delta=l_\Delta-S_\Delta/\log2$ and $\row_\Delta(l)=j_\Delta+\lambda(l-\tip_\Delta)$, the height at which the hypotenuse meets the left edge and the right end of row $l$. After a first passage over height $\omega$ the fresh path lies a little above the top edge of $\Delta$, about $\omega/4$ to the right, while the rows of $\Delta$ widen by $\lambda\omega$ over that height. Making explicit the geometric steps of the proof of \cite[Lemma~7.10]{Tao}, we show that large triangles met there have tips at or above $l_\Delta$ and corners in well-separated columns. \begin{lemma}[Rows of a triangle]\label{lem_c3_row_mem}\label{lem_c3_row_bound} Let $\Delta$ be a triangle and $(j,l)\in\mathcal P$ with $l\le l_\Delta$. Then $(j,l)\in\Delta$ if and only if $j_\Delta\le j\le\row_\Delta(l)$. Every $(j,l)\in\Delta$ satisfies $l\ge\tip_\Delta$ and $(j-j_\Delta)\log9\le(l-\tip_\Delta)\log2$. \end{lemma} \begin{proof} Since $S_\Delta-(l_\Delta-l)\log2=(l-\tip_\Delta)\log2$, the third membership condition reads, as in \cite[(7.65)]{Tao}, $(j-j_\Delta)\log9\le(l-\tip_\Delta)\log2$, that is, $j\le\row_\Delta(l)$. With $j\ge j_\Delta$ it forces $l\ge\tip_\Delta$. \end{proof} \begin{lemma}[Tips of nearby triangles]\label{lem_c3_close}\label{lem_c3_bridge} Let $\Delta\ne\Delta'$ be members of $\mathfrak T$, $p\in\Delta$ and $\omega=\operatorname{gap}(p)$. Let $(j,l)\in\Delta'$ with $l_\Delta\le l\le l_\Delta+W$ and $|j-(j(p)+\omega/4)|\le Y$, where $W,Y\ge0$ and $Y+\lambda W+1\le\omega\lambda_0$. Then $\tip_{\Delta'}\ge l_\Delta$. \end{lemma} \begin{proof} Suppose $\tip_{\Delta'}j_{\Delta'}$. By Lemma~\ref{lem_c3_row_mem}, $j\le\row_{\Delta'}(l)\le\bar\jmath+\lambda W$. Let $j'=\min(j,\floor{\bar\jmath})$; then $j_{\Delta'}\le j'\le\bar\jmath$, $0\le j-j'\le\lambda W+1$, and $(j',l_\Delta)\in\Delta'$ as $l_\Delta\le l\le l_{\Delta'}$. On the other hand $\lambda_0\le\frac14$, so $Y+\lambda W+1\le\omega/4$; hence $j'\ge j(p)\ge j_\Delta$ and $j'\le j(p)+(\frac14+\lambda_0)\omega=j(p)+\lambda\omega$. Multiplying by $\log9$ and using the membership of $p$, $(j'-j_\Delta)\log9\le(j(p)-j_\Delta)\log9+\omega\log2\le S_\Delta$, so $(j',l_\Delta)\in\Delta$ as well. \end{proof} For $\Delta\in\mathfrak T$ and reals $\mathsf S$ and $W\ge0$, the \emph{anchor set} $\operatorname{Anc}(\Delta,\mathsf S,W)\subseteq\Z$ consists of the $j_{\Delta'}$ of the $\Delta'\in\mathfrak T$ with $S_{\Delta'}\ge\mathsf S$ and $l_\Delta\le\tip_{\Delta'}\le l_\Delta+W$. \begin{lemma}[Anchors are separated]\label{lem_c3_anchor_sep} Let $\Delta\in\mathfrak T$, and let $W\ge0$ and $\mathsf S>0$ be reals with $\mathsf A=b_{\mathrm{an}}\mathsf S-W-1>0$. Distinct elements $\zeta<\zeta'$ of $\operatorname{Anc}(\Delta,\mathsf S,W)$ satisfy $\zeta'-\zeta>\lambda\mathsf A$. \end{lemma} \begin{proof} Let $\Delta',\Delta''$ define $\zeta$ and $\zeta'$; they are distinct. As in the proof of \cite[Lemma~7.10]{Tao}, we compare their rows at the height $\hat l=l_\Delta+\floor{\mathsf S/\log2}$. Since $b_{\mathrm{an}}<1/\log2$ (Lemma~\ref{lem_c3_gates}(4)), $\floor{\mathsf S/\log2}>\mathsf S/\log2-1>W$, so $\tip_{\Delta'},\tip_{\Delta''}\le l_\Delta+W<\hat l$ and $l_{\Delta'}=\tip_{\Delta'}+S_{\Delta'}/\log2\ge\hat l$, and likewise for $\Delta''$. By Lemma~\ref{lem_c3_row_mem}, $(\zeta',\hat l)\in\Delta''$; if $\zeta'\le\row_{\Delta'}(\hat l)$, then $(\zeta',\hat l)\in\Delta'$ as well, contradicting Proposition~\ref{lem_bk_cover}. Hence $\zeta'-\zeta>\lambda(\hat l-\tip_{\Delta'})\ge\lambda(\mathsf S/\log2-1-W)>\lambda\mathsf A$. \end{proof} \subsection{The paid first passage}\label{sec:c3-paid} In Tao's argument the reward of the first passage above the top edge is discarded. We keep it: the first passage then has total mass less than $\mathsf q_{\mathrm{mass}}$ at large gaps (Lemma~\ref{lem_c3_initial_mass}), which pays for most of the budget. For $v\in\mathcal P$ put $\mathsf H(v)=\mathsf Q(v)/\mathsf w(v)$, and for a black point $e$ with $\omega=\operatorname{gap}(e)$ define the \emph{paid first passage} \[ \widetilde{\mathsf F}_e(x)=\sum_{\mathbf f\in\Pi_\omega:\ \operatorname{pt}_{|\mathbf f|}(\mathbf f)=x}\mathfrak q(\mathbf f)e^{-z\operatorname{Rw}(e,\mathbf f;|\mathbf f|)},\qquad\widetilde\Prob_e(x,\mathbf b)=\widetilde{\mathsf F}_e(x)\mathfrak q(\mathbf b). \] As rewards are nonnegative, $0\le\widetilde{\mathsf F}_e\le\mathsf F_\omega$ by \eqref{eq:tr-passage-law}, so $\widetilde\Prob_e\le\Prob_{e,\omega}$. \begin{lemma}[Paid continuation]\label{lem_c3_continuation}\label{lem_ch_Q_continuation}\label{lem_c3_paid_passage} Let $e$ be black and $1\le L\le J$. Then \[ \mathsf Q(e)\le\sum_a\widetilde\Prob_e(a)\,e^{-z\operatorname{Rw}^e_{L-1}(a)}\,\mathsf Q(y^e_L(a)). \] \end{lemma} \begin{proof} By Lemma~\ref{lem_ch_Q_range}(2) and \eqref{eq:tr-wI}, $\mathsf H(v)=\sum_b\mathfrak q(b)e^{-z\operatorname{rw}(v,b)}\mathsf H(v+\operatorname{pt}(b))$ for every $v\in\mathcal P$, and iterating, $\mathsf H(v)=\sum_{\mathbf b\in\mathfrak B^K}\mathfrak q(\mathbf b)e^{-z\operatorname{Rw}(v,\mathbf b;K)}\mathsf H(v_{\mathbf b})$ (Lemma~\ref{lem_tr_concat}(1),(2)). Apply the one-step identity at $e$ and expand only the lists whose holds all end at height at most $l(e)+\omega$; after $\floor{\omega/4}+1$ steps none remain (Lemma~\ref{lem_tr_concat}(3)), and the expanded terms are exactly the lists of $\Pi_\omega$. As $e$ is black, $\mathsf w(e)=1$, so $\mathsf Q(e)=\sum_x\widetilde{\mathsf F}_e(x)\mathsf H(e+x)$. For $o=e+x$, the iterated identity with $K=L$ and \eqref{eq:tr-wI} for the last hold give $\mathsf H(o)\le\sum_{\mathbf b\in\mathfrak B^L}\mathfrak q(\mathbf b)e^{-z\operatorname{Rw}(o,\mathbf b;L-1)}\mathsf Q(o_{\mathbf b})$, as $\mathsf I\le1$. Extending $\mathbf b$ to $J$ holds changes neither factor (Lemma~\ref{lem_tr_concat}(1),(2)). \end{proof} \subsection{The paid mass of a long first passage} A first passage over a long gap $\omega$ first crosses height $\omega$ at a raw letter $c$, raw index $r$ and overshoot $o$ (Lemma~\ref{lem_tr_passage_raw3}). For $r\le\floor{9\omega/32}$ the angles at the crossing point and at the following raw positions of the same hold, up to height $17$ above the top edge, are determined by seventeen bits of the column-top residue up to a perturbation below $10^{-6}$; the paid factors there are bounded by cost tables which are periodic in $r$, and averaging them against the rows of raw-prefix masses gives the bound $\mathsf q_{\mathrm{mass}}$. \begin{lemma}[Narrow envelopes]\label{lem_c3_narrow_cells}\label{def_c3_narrow_table} Let $U'$ be the envelope table with $U'_{1,2}=2^{-16}$ and the other entries \[ \begin{array}{c|rrrrrr} s\backslash t&2&3&4&5&6&7\\\hline 1&&.333340&.500010&&&\\ 2&.707108&.333337&.353560&&&\\ 3&.923880&.577352&.461943&&&\\ 4&.980786&.883638&.604555&&&\\ 5&.995185&.970239&.867542&&&\\ 6&.998796&.992518&.965743&.864601&&\\ 7&&&&&.868067&\\ 8&&&&&&.874299 \end{array} \] Then $\Phi_t((b+\beta)/2^s)\le U'_{s,t}$ for every $(s,t)$ in $U'$, every odd $b$ and every real $|\beta|\le10^{-6}$. Put $\delta'_{c,o}=\min\{a_{c,o}[U']/(c-1),1-2^{-16}\}$; then $\Phi^{\mathrm{cap}}_c((b+\beta)/2^o)\le1-\delta'_{c,o}$ for $3\le c\le16$, $1\le o\le c$. \end{lemma} \begin{proof} For $(1,2)$, $\Phi_2((b+\beta)/2)=|\sin(\pi\beta/2)|\le\frac{11}7\cdot10^{-6}<2^{-16}$. For the other pairs let $f=\Phi_t^2$; then $|f'|\le\frac{4\pi}{t^2}\sum_{i\floor{9\omega/32}}\mathsf R_l(r)\le e^{-2\omega/289}$, which is at most $37/\omega$ for $\omega\ge1129$. \item $9^{2^{14}}\equiv1\pmod{2^{17}}$, and every odd $M$ is $\equiv9^as\pmod{2^{17}}$ for some $0\le a<2^{14}$ and $s\in\{1,3,5,7\}$, $s\equiv M\pmod 8$. \item For $L=2^{14}$ and $\mathsf f:\N\to[0,1]$ of period $L$, $\sum_r\mathsf R_l(r)\mathsf f(r)\ge\frac1{4L}\sum_{a0$, is an interval of integers, and $\mathsf R_l=\sum_i(\mathsf v_i-\mathsf v_{i-1})\mathbf 1_{I_i}$ over the distinct values $0=\mathsf v_0<\mathsf v_1<\cdots$; here $\sum_i(\mathsf v_i-\mathsf v_{i-1})|I_i|=\frac14$ and $\sum_i(\mathsf v_i-\mathsf v_{i-1})=\max\mathsf R_l\le(2(3l-1))^{-1/2}$ (Lemma~\ref{lem_rn_binom_row}). Apply the interval bound on each $I_i$. For the second inequality, an interval of $k$ integers meets at most $1+(k+N-2)/\mathsf d$ of the blocks of $\mathcal V$, and each intersection carries at most $\mu N+D$. \end{proof} For the cost tables, the retained factors along the final hold are bounded as follows. For $h\ge1$ and real $X$ define, by downward recursion, the \emph{future cost} $\mathrm{cf}_h(X)=1$ for $h\ge15$ and, for $h\le14$, \[ \mathrm{cf}_h(X)=1-\sum_{d=2}^{17-h}\mathfrak q(d)\Bigl[1-\Phi^{\mathrm{cap}}_d\Bigl(\frac X{2^{h+d}}\Bigr)\cdot\begin{cases}\mathrm{cf}_{h+d}(9X)&d\notin\{4,5\},\ h+d\le15,\\1&\text{otherwise,}\end{cases}\Bigr], \] with Lipschitz constant $\mathsf L_h=2^{-h}\sum_{d=3}^{17-h}\mathfrak q(d)\ell_d2^{-d}+9\sum_{d\notin\{4,5\},\,d\le15-h}\mathfrak q(d)\mathsf L_{h+d}$ ($\mathsf L_h=0$ for $h\ge15$); put $\mathrm{xc}_{c,o}(X)=\Phi^{\mathrm{cap}}_c(X/2^o)$ for $c\in\{4,5\}$ and $\mathrm{xc}_{c,o}(X)=\Phi^{\mathrm{cap}}_c(X/2^o)\mathrm{cf}_o(9X)$ otherwise. Let $\mathrm{cf}^+_h(X)$ be defined by the same recursion for integers $X$ with $\Phi^{\mathrm{cap}}$ replaced by $\overline U$ (Lemma~\ref{lem_tr_cap_lipschitz}(2), cosine bounds rounded up on the mesh $10^{-18}$) and each value rounded up on the mesh $10^{-8}$. For $2\le c\le16$, $1\le o\le c$ and odd $m$, the \emph{cost table} $\mathrm{ct}_{c,o}(m)$ is the least of: $1$; if $c\ge3$, $1-\delta'_{c,o}$ and $\overline U_c(m/2^o)+\ceil{10^8\cdot10^{-6}\ell_c2^{-o}}10^{-8}$; and, if $c\notin\{4,5\}$, $\ceil{10^8\overline U_c(m/2^o)\mathrm{cf}^+_o(9m)}10^{-8}+\ceil{10^2(\ell_c2^{-o}+9\mathsf L_o)}10^{-8}$. All arguments of $\overline U$ are multiples of $2^{-17}$, so $\mathrm{ct}_{c,o}(m)$ depends only on $m\bmod2^{17}$. For $s\in\{1,3,5,7\}$ let $\mu_{c,o,s}$ and $\mathrm{rg}_{c,o,s}$ be the mean and the range, in the sense of Lemma~\ref{lem_c3_row_tail_exp}(4), of the sequence $k\mapsto\mathrm{ct}_{c,o}(9^ks)$ of period $2^{14}$, and put \[ \mathsf S^{\mathrm h}_s=\sum_{c=2}^{16}\mathfrak q(c)\sum_{o=1}^c(1-\mu_{c,o,s}),\qquad\mathsf D^{\mathrm h}_s=\sum_{c=2}^{16}\mathfrak q(c)\sum_{o=1}^c\mathrm{rg}_{c,o,s}. \] \begin{lemma}[Cost of an early crossing]\label{lem_c3_h17_angle}\label{lem_c3_h17_crossing_cost}\label{lem_c3_h17_table_bound}\label{lem_c3_h17_row_cost}\label{lem_c3_h17_values} \leavevmode \begin{enumerate} \item Let $e$ be black with $\omega=\operatorname{gap}(e)\ge224$, let $\hat e=(j(e),l_*(e))$ and $N=3^n\vartheta(\hat e)$, and let $M_0$ be odd with $2^{17}\mid3^nM_0+N$. For $2\le c\le16$, $1\le o\le c$ and $1\le r\le\floor{9\omega/32}$, \[ \sum_{\mathbf f\in\mathcal X_\omega(c,o,r)}\mathfrak q(\mathbf f)e^{-z\operatorname{Rw}(e,\mathbf f;|\mathbf f|)}\le\mathfrak q(c)\mathsf R(r-1,\omega+o-c)\,\mathrm{ct}_{c,o}(9^rM_0). \] \item The aggregates are \[ (\mathsf S^{\mathrm h}_s,\mathsf D^{\mathrm h}_s)=\begin{cases}\bigl(\frac{149160843578876007}{53687091200000000},\frac{90751350494755481}{21474836480000000}\bigr),&s\in\{1,7\},\\[3pt]\bigl(\frac{319022353342658719}{107374182400000000},\frac{258514465939645767}{53687091200000000}\bigr),&s\in\{3,5\}.\end{cases} \] \end{enumerate} \end{lemma} \begin{proof} (1) By Lemma~\ref{lem:odd-dyadic-exit}(c), $N$ is odd and $|\vartheta(\hat e)|\le\varepsilon2^{-\omega}$. Residue transport as in Lemma~\ref{lem_tr_tree_angle}(1) gives $\vartheta(j(e)+s',l_*(e)+h)\equiv9^{s'}(M_0+\vartheta(\hat e))/2^h$ for $s'\ge0$, $0\le h\le17$. Put $x=9^r(M_0+\vartheta(\hat e))$; then $|9^r\vartheta(\hat e)|\le2^{16r/5}\varepsilon2^{-\omega}<2^{-\omega/10}<10^{-6}$. By Lemma~\ref{lem_tr_passage_raw3}(2), a list of $\mathcal X_\omega(c,o,r)$ has raw word $\mathbf a\,c\,\mathbf s$. The crossing point $e+(r,\omega+o)$ and the points of the next raw letters $\mathbf s_1,\mathbf s_2,\ldots$ up to height $15$ above $l_*(e)$ (at most seven of them, as raw letters are at least $2$) lie within raw index $\floor{9\omega/32}+7\le f_\omega$ of $e$, hence have $j\le J$ (Lemma~\ref{lem:odd-dyadic-exit}). Their factors are therefore at most $\Phi^{\mathrm{cap}}_c(x/2^o)$, $\Phi^{\mathrm{cap}}_{\mathbf s_1}(9x/2^{o+\mathbf s_1})$, \ldots, the last retained one being at height at most $17$. Discarding the other rewards and summing over $\mathbf s$ with the hold-word masses gives, by induction on the height, at most $\mathfrak q(c)\mathsf R(r-1,\omega+o-c)\mathrm{xc}_{c,o}(x)$. It remains to show $\mathrm{xc}_{c,o}(m+\beta)\le\mathrm{ct}_{c,o}(m)$ for $m=9^rM_0$ and $|\beta|\le10^{-6}$. The value $1$ and the packet value hold by Lemma~\ref{lem_c3_narrow_cells}; the direct value by Lemma~\ref{lem_tr_cap_lipschitz}(1),(2); and the joint value because $\mathrm{xc}_{c,o}$ is a product of two $[0,1]$-valued factors with Lipschitz constants $\ell_c2^{-o}$ and $9\mathsf L_o$ (by induction, as in Lemma~\ref{lem_tr_tree_angle}(4)), and $\mathrm{cf}_h\le\mathrm{cf}^+_h$ (by induction). (2) This is a finite computation in exact rational arithmetic. The cosine bounds are needed only at the $2^{16}+1$ turns $j/2^{17}$, $0\le j\le2^{16}$; the arrays $\mathrm{cf}^+_h$, $14\ge h\ge1$, on the $2^{16}$ odd residues modulo $2^{17}$ are computed in decreasing order of $h$; then the $135$ tables $\mathrm{ct}_{c,o}$ on the odd residues ($131050$ distinct direct values and $8126464$ distinct joint values), and the $540$ orbit sequences $\mathrm{ct}_{c,o}(9^ks\bmod2^{17})$, $k<2^{14}$, which give $\mu_{c,o,s}$, $\mathrm{rg}_{c,o,s}$ and the four pairs displayed. \end{proof} \begin{lemma}[Paid mass of a long first passage]\label{lem_c3_initial_mass}\label{lem_c3_future_mass} Let $e$ be black and $\omega=\operatorname{gap}(e)$. If $\omega\ge2^{34}$, then $\sum_x\widetilde{\mathsf F}_e(x)<\mathsf q_{\mathrm{mass}}=\frac{38177}{125000}$. If $\omega\ge4096$, then $\sum_x\widetilde{\mathsf F}_e(x)2^{40}$; the right side is $0.33250\ldots$ for $s\in\{1,7\}$ and $0.28808\ldots$ for $s\in\{3,5\}$, both below $b_*$. \end{proof} \subsection{Deviations, the initial filter and the packing estimate} Outside a small deviation event the first passage and the next holds stay close to their typical displacements, so a visit to a large triangle pins the column of the first passage near an anchor (Lemma~\ref{lem_c3_near}), and the anchors are sparse. The allowances below are affine in the number $v$ of holds; their slopes are chosen so that the generating functions of Lemma~\ref{lem_c3_gates}(3) control the deviations along the whole schedule at once. \begin{definition}[Case~3 allowances]\label{def_c3_allowances}\label{def_s02_Xo}\label{def_s02_Xl}\label{def_s02_Xd}\label{def_s02_Wtot} For each index the allowances are $X^{\mathrm o}_\iota$, $X^{\mathrm l}_\iota(v)=X^{\mathrm l}_\iota(0)+s^{\mathrm v}_\iota v$, $X^{\mathrm d}_\iota(v)=X^{\mathrm d}_\iota(0)+s^{\mathrm d}_\iota v/4$ and $W_\iota(v)=X^{\mathrm o}_\iota+X^{\mathrm l}_\iota(v)$, with the following constants: \[ \begin{array}{c|cccccc} \iota&X^{\mathrm o}_\iota&X^{\mathrm l}_\iota(0)&s^{\mathrm v}_\iota&y^{\mathrm v}_\iota&X^{\mathrm d}_\iota(0)&s^{\mathrm d}_\iota\\\hline \mathrm o&194&1503&\frac{6579}{500}&\frac{169}{168}&131&\frac{257}{2000}\\[2pt] \mathrm b&182&1174&\frac{1653}{125}&\frac{144}{143}&102&\frac{383}{2500} \end{array} \] \[ \begin{array}{c|cccc} \iota&b^{\mathrm d}_\iota&H^{\mathrm{pk}}_\iota&y^{\mathrm{cl}}_\iota&v^{\mathrm{cl}}_\iota\\\hline \mathrm o&\frac{51}{50}&35&\frac{8191}{8192}&\frac{1279}{100}\\[2pt] \mathrm b&\frac{43}{42}&33&\frac{255}{256}&\frac{25}2 \end{array} \] The common constants are $b_{\mathrm{an}}=\frac{12500000000}{8664339757}$, $\mathsf q_{\mathrm{pack}}=\frac{1527079}{5000000}$ and $\Gamma_{\mathrm{pk}}=\frac{2113}{500}$. For $0\le i0$ and $\mathsf B_i+H^{\mathrm{pk}}_\iota\le\frac5{16}\mathsf A_i$. \item $\mathsf V(y^{\mathrm{cl}}_\iota)<(y^{\mathrm{cl}}_\iota)^{v^{\mathrm{cl}}_\iota}$, $\mathsf G(1,y^{\mathrm v}_\iota)<(y^{\mathrm v}_\iota)^{s^{\mathrm v}_\iota}$, and $\mathsf G((b^{\mathrm d}_\iota)^{4\varsigma},(b^{\mathrm d}_\iota)^{-\varsigma})<(b^{\mathrm d}_\iota)^{s^{\mathrm d}_\iota}$ for $\varsigma=\pm1$; and $v^{\mathrm{cl}}_\iota\alpha_\iota>\frac{13}9$. \item $b_{\mathrm{an}}<1/\log2$. \end{enumerate} \end{lemma} \begin{proof} (1) The allowances increase with $v$, $\lambda<\frac8{25}$ and $\lambda_0\ge\frac1{16}$, so the left side is at most $\frac\omega{32}+8V_\iota\le\frac{3\omega}{64}$ provided $X^{\mathrm d}_\iota(V)+\frac14X^{\mathrm l}_\iota(V)+\frac8{25}W_\iota(V)+1\le8V$ at $V=V_\iota$; this affine inequality holds as $V_\iota\ge2^{18}$, and $\Omega_\iota\ge512V_\iota$ (Lemma~\ref{lem:schedule}); so the left side is at most $\frac\omega{16}\le\omega\lambda_0$. (2) is an exact evaluation at the $r_\iota$ schedule positions. (3) By Lemma~\ref{lem_rn_mgf_bound}(4) these generating functions are explicit rationals: $\mathsf V(\frac{8191}{8192})=\frac{6187886789300271379243896831}{6197558195857188412641546239}$, $\mathsf V(\frac{255}{256})=\frac{178454632614069375}{187461831868810367}$, $\mathsf G(1,\frac{169}{168})=\frac{9577713826824949}{8858255458075381}$, $\mathsf G(1,\frac{144}{143})=\frac{97132784504832}{88581797925983}$, and $\mathsf G$ at the four drift-free points is $\frac{106892500}{106627249}$, $\frac{393435063}{392435263}$ ($\iota=\mathrm o$), $\frac{45463572}{45304601}$, $\frac{164732957}{164140421}$ ($\iota=\mathrm b$). Raising to the denominators of the exponents turns each claim into an exact integer comparison. Finally $\frac{1279}{100}\cdot\frac{113}{1000}-\frac{13}9=\frac{743}{900000}$ and $\frac{25}2\cdot\frac3{25}-\frac{13}9=\frac1{18}$. (4) $\sum_{j\le25}x^j/j!>2$ at $x=1/b_{\mathrm{an}}$, so $e^{1/b_{\mathrm{an}}}>2$. \end{proof} For $\omega\in\N$ and $v\le J$, the \emph{deviation event} $\mathrm{Dev}_{\omega,v}$ is the set of atoms $(x,\mathbf b)$ with $l(x)-\omega\ge X^{\mathrm o}_\iota$, or $|j(x)-\omega/4|\ge\omega/32$, or $\sum_{k\le v}l(\operatorname{pt}(b^k))\ge X^{\mathrm l}_\iota(v)$, or $\max_{1\le u\le v}|\sum_{k\le u}(4j-l)(\operatorname{pt}(b^k))|\ge4X^{\mathrm d}_\iota(v)$. The \emph{fresh deviation event} $\mathrm{Dev}^{\mathrm{fr}}$ is the set of atoms for which some $1\le u\le\min(V_\iota-1,J)$ has $\sum_{k\le u}l(\operatorname{pt}(b^k))\ge X^{\mathrm l}_\iota(u)$ or $|\sum_{k\le u}(4j-l)(\operatorname{pt}(b^k))|\ge4X^{\mathrm d}_\iota(u)$. For $p\in\mathcal P$ and real $\mathsf S$, the \emph{large-triangle event} $\mathrm{Big}^p_{v,\mathsf S}$ is the set of atoms with $y^p_u(a)\in\Delta$ for some $u\le v$ and $\Delta\in\mathfrak T$ with $S_\Delta\ge\mathsf S$. \begin{lemma}[Mass of the deviation events]\label{lem_c3_eprime_mass}\label{lem_c3_fresh_dev_mass}\label{lem_c3_affine_barrier} Let $p\in\mathcal P$ and $\omega\in\N$. If $\omega\ge2^{32}$, the atoms with $l(x)-\omega\ge X^{\mathrm o}_\iota$ or $|j(x)-\omega/4|\ge\omega/32$ have $\Prob_{p,\omega}$-mass at most $9(\frac{25}{27})^{X^{\mathrm o}_\iota}+(2\omega)^{-1/2}$. For every $\omega$, $\Prob_{p,\omega}(\mathrm{Dev}^{\mathrm{fr}})\le(y^{\mathrm v}_\iota)^{-X^{\mathrm l}_\iota(0)}+2(b^{\mathrm d}_\iota)^{-4X^{\mathrm d}_\iota(0)}$. \end{lemma} \begin{proof} The first-passage overshoot tail (Lemma~\ref{lem_rn_overshoot_tail}, valid for $\omega\ge64$) bounds the first condition by $9(\frac{25}{27})^{X^{\mathrm o}_\iota}$. The horizontal tail of the first passage (Lemma~\ref{lem_rn_hor_tail}, with $u=\omega/32\ge2$) bounds the second by $4e^{-(\omega/32)^2/(2(\omega-4))}+2e^{-\omega/8192}\le6e^{-\omega/8192}$, and with $x=\omega/8192\ge2^{19}$, $e^{2x}\ge2x^2\ge2^{20}x>72\cdot8192x$, that is, $36e^{-2x}<(2\omega)^{-1}$. For the second claim we use an \emph{affine barrier}: for reals $X,y>0$, $T>0$, $\Lambda\ge\mathsf G(X,y)$ and $N\in\N$, the $\eta^{\otimes N}$-mass of the $\mathbf h\in\mathcal P^N$ with $X^{j(\mathbf h_1+\cdots+\mathbf h_u)}y^{l(\mathbf h_1+\cdots+\mathbf h_u)}\ge T\Lambda^u$ for some $u\le N$ is at most $1/T$. Indeed, split by the least such $u$; on that event the weight $X^jy^l/(T\mathsf G^u)$ of the first $u$ points is at least $1$, and the tilted measures $\eta^{\otimes u}(\mathbf h)X^{j}y^{l}/\mathsf G(X,y)^u$ of these disjoint events, extended to $N$ points, sum to at most $1$. By \eqref{eq:c3-marginal} the event depends only on the first $\min(V_\iota-1,J)$ hold points. For the vertical part, $l\ge X^{\mathrm l}_\iota(u)$ if and only if $(y^{\mathrm v})^l\ge(y^{\mathrm v})^{X^{\mathrm l}(0)}((y^{\mathrm v})^{s^{\mathrm v}})^u$; apply the barrier with $X=1$, $T=(y^{\mathrm v})^{X^{\mathrm l}(0)}$ and Lemma~\ref{lem_c3_gates}(3). For the drift-free part, $\varsigma(4j-l)\ge4X^{\mathrm d}_\iota(u)$ if and only if $((b^{\mathrm d})^{4\varsigma})^j((b^{\mathrm d})^{-\varsigma})^l\ge(b^{\mathrm d})^{4X^{\mathrm d}(0)}((b^{\mathrm d})^{s^{\mathrm d}})^u$; apply the barrier for $\varsigma=\pm1$. \end{proof} For $p\in\Delta\in\mathfrak T$, $v\in\N$ and real $\mathsf S$, the \emph{anchor columns} are \[ \mathcal K_{v,\mathsf S}=\bigl\{\zeta-j(p)+i:\ \zeta\in\operatorname{Anc}(\Delta,\mathsf S,W_\iota(v)),\ -X^{\mathrm d}_\iota(v)-\tfrac14X^{\mathrm l}_\iota(v)-X^{\mathrm d}(v)-\frac14X^{\mathrm l}(v)$ and $i<\lambda X^{\mathrm o}+\lambda_0X^{\mathrm l}(v)+X^{\mathrm d}(v)$, as $\lambda=\frac14+\lambda_0$. \end{proof} Packing needs a filter on the first passage: its crossing letter is at most $128$, its crossing index at most $\floor{9\omega/32}$, and its final hold has at most $H^{\mathrm{pk}}_\iota$ raw letters after the crossing. Let $\mathcal B^{\mathrm{in}}_\omega$ be the set of $\mathbf f\in\Pi_\omega$ violating this, and for a black $e$ let $\mathsf F^{\mathrm{gd}}_e$ be $\widetilde{\mathsf F}_e$ with the sum restricted to $\Pi_\omega\setminus\mathcal B^{\mathrm{in}}_\omega$. \begin{lemma}[The filtered first passage]\label{lem_c3_init_exception_mass}\label{lem_c3_affine_envelope}\label{lem_c3_filtered_packing} Let $\omega\ge12500000$. \begin{enumerate} \item The lists of $\mathcal B^{\mathrm{in}}_\omega$ have total mass at most $(\frac{11}{16})^{H^{\mathrm{pk}}_\iota}+\frac{2161}{2^{127}}+\frac{148}\omega$. \item Let $e$ be black with $\operatorname{gap}(e)=\omega\ge2^{34}$, $\mathsf n\in\N$, $\mathsf B>\mathsf n$ and $\mathsf d\ge\mathsf B+H^{\mathrm{pk}}_\iota$ real, $Z\subseteq\Z$ with pairwise distances at least $\mathsf d$, and $\mathcal U=\{\zeta+i:\zeta\in Z,0\le i<\mathsf n\}$. Then, with $H=H^{\mathrm{pk}}_\iota$, \[ \sum_{r\in\mathcal U}\sum_\ell\mathsf F^{\mathrm{gd}}_e(r,\ell)\le\frac{\mathsf q_{\mathrm{pack}}(\mathsf B+H)+\Gamma_{\mathrm{pk}}/4}{\mathsf d}+\frac{49}{120}\cdot\frac{(4\mathsf q_{\mathrm{pack}}(\mathsf B+H)+\Gamma_{\mathrm{pk}})(1+(\mathsf B+H)/\mathsf d)}{\sqrt\omega}. \] \end{enumerate} \end{lemma} \begin{proof} (1) By Lemma~\ref{lem_tr_passage_raw3}(2), the long final holds have mass at most $(\frac{11}{16})^H$. For $c>128$, $\sum_{o\le c}\sum_r\mathsf R(r-1,\omega+o-c)\le1+\frac c4$, and $\sum_{c>128}\mathfrak q(c)(1+\frac c4)=\frac{128^2+7\cdot128+8}{4\cdot2^{128}}=\frac{2161}{2^{127}}$, by the closed forms $\sum_{c>k}\mathfrak q(c)=(k+1)2^{-k}$ and $\sum_{c>k}c\,\mathfrak q(c)=(k^2+3k+4)2^{-k}$. For $c\le128$ the rows lie in $[\omega-127,\omega]$, and Lemma~\ref{lem_c3_row_tail_exp}(1) and $\sum_cc\,\mathfrak q(c)=4$ give $148/\omega$. (2) We may assume $\mathsf n\ge1$. A list counted on the left lies in a class $\mathcal X_\omega(c,o,r)$ with $c\le128$, $r\le\floor{9\omega/32}$ and raw length in $[r,r+H]$; its raw length is its column, so $r$ lies in $\mathcal V=\{\zeta'+i:\zeta'\in Z-H,0\le i0$ and $\mathsf D^{\mathrm h}_s-(H+1)(\mathsf S^{\mathrm h}_s-4+4\mathsf q_{\mathrm{pack}})<\Gamma_{\mathrm{pk}}$ for both values of $H$ (exact comparisons), so for $N\ge H+1$, $(4-\mathsf S^{\mathrm h}_s)N+\mathsf D^{\mathrm h}_s\le4\mathsf q_{\mathrm{pack}}N+\Gamma_{\mathrm{pk}}\le4\mathsf q_{\mathrm{pack}}(\mathsf B+H)+\Gamma_{\mathrm{pk}}$. Expanding $\varrho$ gives the claim. \end{proof} \begin{lemma}[Filtered mass of the anchor columns]\label{lem_c3_outside_mass}\label{lem_c3_lemma710} Let $p\in\Delta\in\mathfrak T$ be black with $\omega=\operatorname{gap}(p)\ge2^{34}$, $0\le i0$ by Lemma~\ref{lem_c3_gates}(2)). As $\lambda\ge\frac5{16}$, $\mathsf B+H\le\mathsf B_i+H\le\frac5{16}\mathsf A_i\le \mathsf d$. Apply Lemma~\ref{lem_c3_init_exception_mass}(2), and use $(\mathsf B+H)/\lambda\le\mathsf C_i+\frac{127}{40}H$ and $(\mathsf B+H)/(\lambda\mathsf A_i)\le\mathsf r_i$, as $1/\lambda<\frac{127}{40}$. \end{proof} \subsection{Stopped stages for the bootstrap index} For $\iota=\mathrm b$ the trace factors of the last two schedule intervals are replaced by the mass of \emph{stopped stages}. From a black point, a stage follows complete entries until either one departure from a point of gap at least $4096$ has completed its entry, or $5$ departures from smaller gaps have. An entry from a gap of at least $4096$ has paid mass less than $b_*$ (Lemma~\ref{lem_c3_initial_mass}, via \eqref{eq:tr-bridge}), every entry has paid mass at most $\frac{77}{100}$, and $(\frac{77}{100})^5\nu$ and $\mathrm{se}_{k,t}(i)=\mathrm{se}_{\mathrm{nx}(k,t;\operatorname{gap}(\mathsf y_{u_i}))}(i+1)$ otherwise; and put $\mathcal Z^{\mathrm{st}}_k(\bar o,\mathbf b)=e^{-z\operatorname{Rw}(\bar o,\mathbf b;u_{\mathrm{se}_{k,5}(1)})}$ if $\mathrm{se}_{k,5}(1)\le\nu$, and $0$ otherwise. \end{definition} \begin{lemma}[Mass of stopped stages]\label{lem_c3_stage_mass_bound}\label{lem_c3_stage_moment_black}\label{lem_c3_stage_trace}\label{lem_c3_stage_discount}\label{lem_c3_entry_large}\label{lem_c3_stage_rate}\label{lem_c3_stage_shift} \leavevmode \begin{enumerate} \item For black $v$ and $k\in\N$, $\mathcal M_{k,5}(v)\le b_*^k$. \item For $\bar o\in\mathcal P$ and $L$ with $j(\bar o)+L>J$, $\sum_{\mathbf b\in\mathfrak B^L}\mathfrak q(\mathbf b)\mathcal Z^{\mathrm{st}}_k(\bar o,\mathbf b)\le b_*^k$. \item In the setting of Lemma~\ref{lem_tr_discounted_trace}, if every atom of $\mathcal S$ satisfies $\mathrm{se}_{k,5}(1)\le\nu$ and $u_{\mathrm{se}_{k,5}(1)}\le P_\iota-1$ for its fresh path, the factor $(\frac{77}{100})^k$ may be replaced by $b_*^k$. \end{enumerate} \end{lemma} \begin{proof} (1) We show $\mathcal M_{k,t}\le\max(b_*,(\frac{77}{100})^t)b_*^{k-1}$ for $k\ge1$. If $\operatorname{gap}(v)\ge4096$, then $\mathsf K\mathbf1(v)\le S(v)=\sum_x\widetilde{\mathsf F}_v(x)0$ and $n^{\mathrm{cl}}_i=\max(0,\min(p_i,P_\iota-1-h_\iota(p_i))-p_{i-1})$ ($p_{-1}=-1$). The \emph{Case~3 error} is \[ \mathcal E_\iota=\Pi^{\mathrm{ad}}_\iota+\mathsf q_{\mathrm{mass}}\mathfrak e_{r_\iota}+E^{\mathrm{sq}}_\iota+E^{\mathrm{in}}_\iota+\mathsf q_{\mathrm{mass}}(E^{\mathrm{dv}}_\iota+E^{\mathrm{cl}}_\iota). \] \end{definition} \begin{lemma}[Case~3 low-reward bound]\label{lem_tr_survival_export}\label{lem_c3_estar_mass} Let $p\in\Delta\in\mathfrak T$, $\omega=\operatorname{gap}(p)>\mathsf s_\iota m$, $m\ge D_{\mathrm{sc}}(\iota)$, $j(p)+m=J$ and $P_\iota\le J$. Then \[ \sum_{a\in\mathrm{Low}^p\setminus\mathrm{Bad}^p_m}\widetilde\Prob_p(a)e^{-z\operatorname{Rw}^p_{P_\iota-1}(a)}\le\mathcal E_\iota. \] \end{lemma} \begin{proof} By Lemma~\ref{lem_s02_Dstar_eq}(2), $\mathsf s_\iota m\ge\Omega_\iota$, so $\omega\ge\Omega_\iota\ge\max(2^{34},512V_\iota)$ (Lemma~\ref{lem:schedule}). Rewards are nonnegative, so all discounts lie in $(0,1]$. Write $X$ for the left side. \emph{Filter.} The part of $X$ carried by $\widetilde{\mathsf F}_p-\mathsf F^{\mathrm{gd}}_p$ is at most $(\frac{11}{16})^H+\frac{2161}{2^{127}}+\frac{148}{\Omega_\iota}$ (Lemma~\ref{lem_c3_init_exception_mass}(1)). For the rest, $\sum_x\mathsf F^{\mathrm{gd}}_p(x)<\mathsf q_{\mathrm{mass}}$ (Lemma~\ref{lem_c3_initial_mass}) and $\mathsf F^{\mathrm{gd}}_p\le\mathsf F_\omega$. \emph{Deviations.} The atoms with $l(x)-\omega\ge X^{\mathrm o}$ or $|j(x)-\omega/4|\ge\omega/32$ contribute at most $9(\frac{25}{27})^{X^{\mathrm o}}+(2\omega)^{-1/2}$ (Lemma~\ref{lem_c3_eprime_mass}). Membership in $\mathrm{Dev}^{\mathrm{fr}}\cup\mathrm{Clr}$ depends only on $\mathbf b$, so these atoms contribute at most $\mathsf q_{\mathrm{mass}}(E^{\mathrm{dv}}_\iota+E^{\mathrm{cl}}_\iota)$ (Lemmas~\ref{lem_c3_eprime_mass} and~\ref{lem_tr_clear_mass}). \emph{The remaining atoms.} Let $\mathcal L'$ be the remaining atoms of positive mass. Split them into $\mathcal L'_{\mathrm A}$, those with no oversize hit at a time $u\le p_{r_\iota-1}$, and, for $i2$, and Lemma~\ref{lem_rn_hor_tail} bounds its mass by $4e^{-u^2/(2(\omega-4))}+2e^{-u/256}\le6e^{-m/2^{36}}$ (or by $4e^{-u/256}$ if $\omega\le5$), because $25600000<2^{36}$ and $2(\omega-4)\cdot10^{10}<63398800000m\le2^{36}m$. On the second, Lemma~\ref{lem_rn_list_hor_tail}(3), applied through \eqref{eq:c3-marginal} with threshold $10\ceil{m/200000}$, gives $e^{P_\iota/2-m/3200000}$. Now $m\ge D_{\mathrm{bad}}(\iota)=2^{21}(P_\iota+64)$, so $P_\iota/2\le m/2^{22}-32$, and $m\ge2^{43}$ by Lemma~\ref{lem_s02_Dstar_eq}(1). With $x=m/2^{43}\ge1$, $\log m<43+x-1$, so $A_\iota\log m\le\frac52\log m<105+\frac52x\le128x-13=m/2^{36}-13$; hence $m^{A_\iota}6e^{-m/2^{36}}<6e^{-13}2e^9>16000$ (Lemma~\ref{lem_s03_log3_bounds}(4)), so the sum is less than $2e^{-10}<\frac1{8000}$. \end{proof} \begin{lemma}[Case~3 of the descent step]\label{lem_c3_case3}\label{def_s02_budget} Let $m$ be an integer with $D_*(\iota)\le m\le J$, let $p\in\mathcal P$ with $j(p)+m=J$, and suppose $p\in\Delta\in\mathfrak T$ with $\operatorname{gap}(p)>\mathsf s_\iota m$. Then $\mathsf Q(p)\le m^{-A_\iota}\mathsf Q_{m-1}$. \end{lemma} \begin{proof} We follow \cite[(7.52)--(7.56)]{Tao}, with $\frac{317}{400}m$ in place of $0.9m$ and an explicit error budget. Write $A=A_\iota$ and $\omega=\operatorname{gap}(p)$. By Lemma~\ref{lem_s02_Dstar_eq}(2), $P_\iota\le m\le J$. The right-end bound \eqref{eq:fb-right-edge} and the membership of $p$ give $\omega\log2\le S_\Delta-(j(p)-j_\Delta)\log9<(J-j(p))\log9=m\log9$. Lemma~\ref{lem_c3_continuation} with $L=P_\iota$ gives $\mathsf Q(p)\le\sum_a\widetilde\Prob_p(a)e^{-z\operatorname{Rw}^p_{P_\iota-1}(a)}\mathsf Q(y^p_{P_\iota}(a))$. For an atom of positive mass, $\operatorname{Adv}(a)=j(y^p_{P_\iota}(a))-j(p)\ge1$ and $j(y^p_{P_\iota}(a))+m=J+\operatorname{Adv}(a)$, so the boundary reduction (Lemma~\ref{lem_ch_boundary_suffices}(1)) gives $\mathsf Q(y^p_{P_\iota}(a))\le\max(m-\operatorname{Adv}(a),1)^{-A}\mathsf Q_{m-1}$. This factor is at most $m^{A}\cdot m^{-A}$; outside $\mathrm{Bad}^p_m$, $m-\operatorname{Adv}(a)>\frac{83}{400}m$, so it is less than $(400/83)^Am^{-A}m$, then $\max(m-r,1)^{-A}\le1=m^{-A}e^{A\log m}$ and $A\log m\le\mathsf t_mr$. If $m\ge2^{40}$, then $\log m\le\sqrt m$ gives $\mathsf t_m\le8A/\sqrt m\le\chi/32$, because $(256A/\chi)^2\le(256\cdot\frac52\cdot\frac{2500}{63})^2<2^{30}$; and $\chi/32<1/1024$. Summing \eqref{eq:F4-envelope} against $\nu_{45}$ gives the first inequality of \eqref{eq:F4-invpow}, and Lemma~\ref{lem_rn_mgf_bound}(2) gives $\mathsf M_{45}(\mathsf t_m)\le e^{13\mathsf t_m/4}\le e^{\chi/2}$. \end{proof} \subsection{The white case} At a white boundary point the closing letter at $p$ carries the factor $e^{-z}$, which outweighs the cost $e^{\chi/2}$ of averaging the envelope factor over one hold. \begin{lemma}[White boundary points]\label{lem_mo_case1}\label{lem_mo_hold_average} Let $0\le A\le\frac52$, let $m\ge2^{40}$ be an integer, and let $p\in\mathcal P$ be white with $j(p)+m=J$. Then \[ \mathsf Q(p)\le e^{-z+\chi/2}m^{-A}\mathsf Q_{m-1}\le m^{-A}\mathsf Q_{m-1}. \] \end{lemma} \begin{proof} We follow \cite[(7.43)]{Tao}. The second inequality holds as $\chi/2=\frac{63}{5000}\omega/4+u\}$ by $4e^{-u/256}$ if $\omega\le5$ and by $4e^{-u^2/(2(\omega-4))}+2e^{-u/256}$ otherwise; as $2(\omega-4)\le4m$, both are at most $6e^{-m/2^{26}}$. The mass of $\{U>u\}$ is $(\frac{11}{16})^{\floor u}\le\frac{16}{11}e^{-5u/16}<2e^{-m/2^{26}}$. As $\widetilde\Prob_p\le\Prob_{p,\omega}$ and $\theta^A\le m^3$ ($A_\iota<3$), the contribution of the complement of $\mathcal G$ to $Z$ is less than $8m^3e^{-m/2^{26}}$. With $x=m/2^{42}\ge1$, $e^{m/2^{26}}=e^{2^{15}x}e^{2^{15}x}\ge2^{32768}\cdot\frac{(2^{15}x)^3}6$, so this is less than $6\cdot2^{129-45-32768}<2^{-100}$. \emph{Large gaps.} On $\mathcal G$, $R+U\le\omega/4+m/2048\le(\frac{\mathsf s_\iota}4+\frac1{2048})m$, so $\theta(a)\le2048/(2047-512\mathsf s_\iota)$. If $\omega\ge2^{34}$, the total mass of $\widetilde\Prob_p$ is $\sum_x\widetilde{\mathsf F}_p(x)<\mathsf q_{\mathrm{mass}}=\frac{38177}{125000}$ (Lemma~\ref{lem_c3_initial_mass}), and the contribution of $\mathcal G$ is less than $\frac{999}{1000}$ by Lemma~\ref{lem_mo_rate_tiny}, since $A\le A_\iota$ and $\theta\ge1$. \emph{Small gaps.} If $\omega<2^{34}$, then $\omega/4<2^{32}\le m/1024$, so on $\mathcal G$, $R+U<\frac{3m}{2048}$ and $\theta(a)<\frac{2048}{2045}$. The total mass of $\widetilde\Prob_p$ is at most $1-d_{\mathrm{pass}}=\frac{96338641}{10^8}$ (Lemma~\ref{lem_tr_passage_bound}), and the contribution of $\mathcal G$ is less than $\frac{97}{100}$ by Lemma~\ref{lem_mo_rate_tiny}. In both cases $Z<\frac{999}{1000}+2^{-100}<\frac{1999}{2000}$, and $\mathsf Q_{m-1}\ge0$. \end{proof} \subsection{The descent step and the Fourier bound} \begin{proposition}[Descent]\label{lem_mo_monotonicity} Let $\iota\in\{\mathrm o,\mathrm b\}$ and form $\mathsf Q_m$ with $A=A_\iota$. For every integer $m$ with $D_*(\iota)\le m\le J$, $\mathsf Q_m\le\mathsf Q_{m-1}$. \end{proposition} \begin{proof} By Definition~\ref{def_Dstar}, $m\ge D_{\mathrm{sc}}(\iota)$ and $m\ge D_{\mathrm{bad}}(\iota)$, which is at least $2^{43}$ by Lemma~\ref{lem_s02_Dstar_eq}(1). By Lemma~\ref{lem_ch_boundary_suffices}(2) it suffices to prove $\mathsf Q(p)\le m^{-A_\iota}\mathsf Q_{m-1}$ for every $p\in\mathcal P$ with $j(p)+m=J$. Fix such a point. \emph{Case~1.} $p$ is white. Apply Lemma~\ref{lem_mo_case1}. Otherwise $p$ is black, because $j(p)\le J$, so it lies in some $\Delta\in\mathfrak T$ by Proposition~\ref{lem_bk_cover}. \emph{Case~2.} $\operatorname{gap}(p)\le\mathsf s_\iota m$. Apply Lemma~\ref{lem_mo_case2} with $A=A_\iota$. \emph{Case~3.} $\operatorname{gap}(p)>\mathsf s_\iota m$. Apply Lemma~\ref{lem_c3_case3}. \end{proof} \begin{lemma}[An inverse moment of the first hold]\label{lem_mo_ser_inverse_moment} For $1J/32$ are at most $(\frac{11}{16})^{\floor{J/32}}\le e^{-J/256}$, and $J^3e^{-J/256}<\frac1{8J}$ for $J\ge2^{24}$, as $\log J\le\sqrt J$. Since $\frac72-\frac{104}{31}=\frac9{62}$ and $\frac{9A}{62}>\frac18$, $e^{104A/(31J)}+\frac1{8J}D_F$, so $J\ge(n-1)/2>D_*+\frac52$ and $J\ge D_*+3$. Form $\mathsf Q$ and $\mathsf Q_m$ for $(n,\xi)$ with the exponent $A$. Then $\mathsf Q_m\le(D_*-1)^A$ for $0\le m\le J$, by induction on $m$: for $m\le D_*-1$ by Lemma~\ref{lem_ch_Qm_bounded}(1), and for $m\ge D_*$ by Proposition~\ref{lem_mo_monotonicity}. So Lemma~\ref{lem_ch_Qm_bounded}(2) with $m=J$ gives $\mathsf Q(y)\le(D_*-1)^Ad_J(y)^{-A}$ for every $y\in\mathcal P$, where $d_J(y)=\max(J-j(y),1)$. By Proposition~\ref{lem_ch_front_end}, grouping by $r=j(y)$ with \eqref{eq:hold-law}, and Lemma~\ref{lem_mo_ser_inverse_moment}, \[ |\widehat\mu_n(\xi)|\le\sum_y\eta(y)\mathsf Q(y)\le(D_*-1)^A\sum_{r\ge1}\nu_{45}(r)\max(J-r,1)^{-A}\le\Bigl(\frac{D_*-1}{J-7/2}\Bigr)^A. \] Finally $n\le2J+1$ gives $D_F(J-\frac72)-n(D_*-1)\ge(2D_*+6)(J-\frac72)-(2J+1)(D_*-1)=8(J-D_*)-20\ge4$, so $\frac{D_*-1}{J-7/2}<\frac{D_F}n$. \end{proof} \section{Estimates for the first-crossing families}\label{sec:est-families} This section proves the facts about scales and first-crossing families used in Sections~\ref{sec:physical}--\ref{sec:steps}: the growth of scales and levels (Lemma~\ref{lem_scales_growth}), prefix-disjointness (Lemma~\ref{lem_first_crossing_prefix_disjoint}), the deficit of the first block family (Lemma~\ref{lem_fc_first_deficit}), the deficits of the first-crossing families at every shift and their mask failure (Lemma~\ref{lem_deficit_family}), and the decay and the products of the deficits of the block families (Lemmas~\ref{lem_central_deficit_decay} and~\ref{lem_fc_late_survival}). \subsection{Scales and levels} The deficit bounds need linear and geometric growth of the scales, the selector needs $\delta_{29}$, and propagation needs the levels $k_j=\floor{\delta_j/4}$ to reach the mixing gate $n_0=2^{80}$ of Proposition~\ref{prop:mix}. \begin{lemma}[Scales and levels]\label{lem_scales_growth}\label{lem_level_late_lower} \leavevmode \begin{enumerate} \item For all $i,j\in\N$, $g^j\delta_i\le\delta_{i+j}$, $\delta_j\ge16544+166j$ and $16544g^j\le\delta_j<16644g^j$. Moreover $\delta_{29}=22095$. \item For every $j\in\N$, $k_j\ge2^{12}g^j$; for $j\ge9853$, $k_j\ge\max(n_0,2^{12}g^j)$. \end{enumerate} \end{lemma} \begin{proof} For (1), $e_\delta=\ceil{\delta/100}$ satisfies $\delta/100\le e_\delta\le(\delta+99)/100$, and $e_\delta\ge166$ for $\delta\ge16544$. Hence $\delta_{m+1}\ge g\delta_m$ and $\delta_{m+1}\ge\delta_m+166$ for every $m$, and induction gives the first two bounds and, with $\delta_0=16544$, the lower bound $16544g^j$. For the upper bound, $\delta_j+100\le16644g^j$ by induction: it is an equality at $j=0$, and $\delta_{j+1}+100\le\delta_j+(\delta_j+99)/100+100\delta_j/4-1\ge4136g^j-1\ge2^{12}g^j$ as $g^j\ge1$. The integer comparison $101^{70}>2\cdot100^{70}$ gives $g^{70}>2$, so for $j\ge9853\ge70\cdot140$, $2^{12}g^j\ge2^{12}g^{9800}>2^{152}>n_0$. \end{proof} \subsection{The line and the families} The transfer of Section~\ref{sec:mix} needs finite prefix-disjoint families; the first lemma shows that the first-crossing families are such. \begin{lemma}[Structure of the families]\label{lem_first_crossing_prefix_disjoint}\label{lem_s03_barrier_mono} Let $\delta\ge256$, $u$ and $R\ge0$ be integers. The line is nondecreasing: $H_{\delta,u}(d)\le H_{\delta,u}(d+1)$ for integers $d\ge0$. The family $\FC_u(\delta,R)$ is finite and prefix-disjoint, hence so is each of its subfamilies, in particular $\FC(\delta,R)\subseteq\FC_{r_\delta}(\delta,R)$. \end{lemma} \begin{proof} The line is nondecreasing since $B_0$ and $(d-\delta)_+$ are nondecreasing and $(\delta-d)_+$ is nonincreasing in $d$. Words of $\FC_u(\delta,R)$ have length at most $d^{\mathrm{hi}}_\delta$ and letters at most $\max_{d\le d^{\mathrm{hi}}_\delta}H_{\delta,u}(d)+R$, so the family is finite. Suppose $w\in\FC_u(\delta,R)$ of length $d$ is a proper prefix of $w'\in\FC_u(\delta,R)$. Since $d^{\mathrm{lo}}_\deltaH_{\delta,u}(\hat d)+R$. Fix $d^{\mathrm{lo}}_\delta0$ real. \begin{enumerate} \item If $4x/(9d)\le1/32$, then \[ \Prob\Bigl(\max_{1\le i\le d}(\deg_i(W)-2i)\ge x\Bigr)\le e^{-2x^2/(9d)},\qquad\Prob(\deg_d(W)-2d\le-x)\le e^{-2x^2/(9d)}. \] \item If $0<\theta<1$, then \[ \Prob\Bigl(\max_{1\le i\le d}(\deg_i(W)-2i)\ge x\Bigr)\le\frac{(1+\theta)^{-x}}{(1-\theta^2)^d},\qquad\Prob(\deg_d(W)-2d\le-x)\le\frac{(1-\theta)^x}{(1-\theta^2)^d}. \] \end{enumerate} \end{lemma} \begin{proof} For $0(2-\log_23)(\delta-i)-1>\tfrac{83}{200}y-1\ge x, \] by $B_0(n)\frac{83}{200}$ (Lemma~\ref{lem_s03_log3_bounds}(1)) and $(\frac{83}{200}-\frac{207}{500})y=y/1000\ge1$. If $\deg_{\delta+y}(W)\delta/8\ge y_{\mathrm{lin}}$, $y\le\ell^{\mathrm c}_\delta$, so $\FC(\delta,R)=\mathcal V_{\ell^{\mathrm c}_\delta}\supseteq\mathcal V_y$ in the notation of Lemma~\ref{lem_deficit_window}. Also $y_{\mathrm{lin}}\ge2068$ and $y_{\mathrm{sq}}^2\ge32\cdot16544\cdot15>1000^2$, so $1000\le y\le\delta/8$, and Lemma~\ref{lem_deficit_window} gives $1-\mass(\FC(\delta,R))\le2e^{-\mathsf x}+2^{-(R+1)}$ with $\mathsf x=c_{\mathrm w}y^2/(\delta+y)$ and $c_{\mathrm w}=2(207/500)^2/9=4761/125000$. \emph{Case $y_{\mathrm{lin}}\le y_{\mathrm{sq}}$.} Then $y=y_{\mathrm{lin}}\ge(\delta-7)/8$. As $\mathsf x$ increases with $y>0$, \[ \mathsf x\ge c_{\mathrm w}\frac{(\delta-7)^2}{8(9\delta-7)}\ge\frac{c_{\mathrm w}}{72}(\delta-14)=\frac{529}{10^6}(\delta-14), \] since $9(\delta-7)^2-(\delta-14)(9\delta-7)=7\delta+343>0$. \emph{Case $y_{\mathrm{sq}}\frac32\cdot\frac{347}{500}>\frac32\log2$ (Lemma~\ref{lem_s03_log3_bounds}(3)). Hence $2e^{-\mathsf x}\le2\delta^{-3/2}$. \end{proof} \begin{lemma}[First-crossing families and the mask]\label{lem_deficit_family} Let $\delta\ge256$, $R\ge0$ and $0\le u\le2r_\delta$ be integers. Then \begin{gather*} 1-\mass(\FC_u(\delta,R))\le2^{116}\delta^{-6}+2^{-(R+1)},\\ \mass(\{w\in\FC_u(\delta,R):2|w|>H_{\delta,u}(|w|)+\floor{\delta/8}\})\le2^{113}\delta^{-6}; \end{gather*} the words of the second set are those failing the mask \eqref{eq:mask} at scale $\delta$ and shift $u$. \end{lemma} \begin{proof} We follow \cite[proofs of Proposition 5.2 and Lemma 5.1]{Mazur}, with smaller constants. Apply Lemma~\ref{lem_overshoot} with $d'=d^{\mathrm{lo}}_\delta+1$, $d''=d^{\mathrm{hi}}_\delta$. From $\delta-d^{\mathrm{lo}}_\delta=d^{\mathrm{hi}}_\delta-\delta=\ell_\delta$, the definition of $r_\delta$ and $0\le u\le2r_\delta$, \[ H_{\delta,u}(d^{\mathrm{lo}}_\delta)\ge2d^{\mathrm{lo}}_\delta+2e_\delta,\qquad H_{\delta,u}(d^{\mathrm{hi}}_\delta)\le2d^{\mathrm{hi}}_\delta-2e_\delta. \] So both events of Lemma~\ref{lem_overshoot} lie in $\{|\deg_i(W)-2i|\ge2e_\delta\}$ for $i=d^{\mathrm{lo}}_\delta$ and $i=d^{\mathrm{hi}}_\delta$, respectively. As $e_\delta\ge\delta/100$ and $i\le2\delta$, the exponent in \eqref{eq:geometric-tail} is at least $\delta/160000$. The bound $e^{-\delta/160000}\le6!\,(\delta/160000)^{-6}$ then gives $1-\mass(\FC_u(\delta,R))\le4\cdot6!\cdot160000^6\delta^{-6}+2^{-(R+1)}$, with $4\cdot6!\cdot160000^6<2^{116}$. For the mask, let $\mathcal V$ be the set of failing words; it is prefix-disjoint. If $w\in\mathcal V$ has length $d$, its prefix of length $d-1\ge d^{\mathrm{lo}}_\delta$ has degree at most $H_{\delta,u}(d-1)-1\le H_{\delta,u}(d)-1\le2d-\floor{\delta/8}-2$, so $\deg_{d-1}(W)-2(d-1)\le-\floor{\delta/8}\le-\delta/16$ if $W$ begins with $w$. Hence $\mass(\mathcal V)\le\sum_{i=d^{\mathrm{lo}}_\delta}^{d^{\mathrm{hi}}_\delta-1}\Prob(|\deg_i(W)-2i|\ge\delta/16)$. There are at most $2\delta$ terms, each at most $2e^{-\delta/16384}$ by \eqref{eq:geometric-tail}, and $e^{-\delta/16384}\le7!\,(\delta/16384)^{-7}$ gives $\mass(\mathcal V)\le4\cdot7!\cdot16384^7\delta^{-6}<2^{113}\delta^{-6}$. \end{proof} The average at generation $j_0$ (Section~\ref{sec:census}) needs the first block family far more precisely than Lemma~\ref{lem_deficit_central} gives; the exact tilts of Lemma~\ref{lem_fc_maximal}(2) provide it. \begin{lemma}[The first block family]\label{lem_fc_first_deficit} $1-\mass(\FC(\delta_0,R_0))<1/20000000$. \end{lemma} \begin{proof} Here $\delta=\delta_0=16544$ and $R_0=29$, so $\ell_\delta=9926$, $d^{\mathrm{lo}}_\delta=6618$ and $\ceil{\log_2\delta}=15$; as $2817^2<32\cdot16544\cdot15\le2818^2$, $\ell^{\mathrm c}_\delta=2818$, and $\FC(\delta,29)$ consists of the words of $\FC_{r_\delta}(\delta,29)$ with length in $[13726,19362]$. Apply Lemma~\ref{lem_overshoot} with $d'=13726$ and $d''=19362$; the shift cancels as in the proof of Lemma~\ref{lem_deficit_window}. If $6618\le i<13726$ and $\deg_i(W)\ge H_{\delta,r_\delta}(i)$, then $m=\delta-i\ge2819$ and $\deg_i(W)-2i\ge2m-B_0(m)>\frac{83}{200}m-1>1168$, so the integer $\deg_i(W)-2i$ is at least $1169$. Lemma~\ref{lem_fc_maximal}(2) with $d=13725$ and $\theta=\frac1{24}$, and $1+s\le e^s$, bound the first event of Lemma~\ref{lem_overshoot} by \[ \Bigl(\frac{24}{25}\Bigr)^{1169}\Bigl(\frac{576}{575}\Bigr)^{13725}\le\exp\Bigl(-\frac{1169}{25}+\frac{13725}{575}\Bigr)=e^{-13162/575}3\cdot10^9$ and $e^{35/2}>39\cdot10^6$, and $\frac1{3\cdot10^9}+\frac1{39\cdot10^6}+2^{-30}=\frac{2200586851}{81788928000000000}<\frac1{20000000}$. \end{proof} \subsection{Deficits along the scale sequence} At the scales $\delta_j$, Lemma~\ref{lem_deficit_central} gives the decay of the block deficits used for propagation and the lower bound on products of block masses used in Lemma~\ref{lem_s05_tuple_mass}. The cap terms satisfy \begin{equation}\label{eq:cap-rate} 2^{-(R_j+1)}\le2^{-29}2^{-j/56}\qquad(j\in\N), \end{equation} since $R_j+1=30+\floor{j/56}\ge29+(j+1)/56$. \begin{lemma}[Decay of the block deficits]\label{lem_central_deficit_decay} For every $j\in\N$, $1-\mass(\FC(\delta_j,R_j))\le\frac12g^{-3j/2}+2^{-29}2^{-j/56}$. \end{lemma} \begin{proof} Put $c=529/10^6$. By Lemma~\ref{lem_scales_growth}, $\delta_j-14\ge16530+166j$, and $166c>\frac3{200}\ge\frac32\log g$ as $\log g<\frac1{100}$; with $e^{16530c}\ge1+16530c>8$ this gives $2e^{-c(\delta_j-14)}\le\frac14g^{-3j/2}$. Also $\delta_j\ge16544g^j$ gives $2\delta_j^{-3/2}\le2\cdot16544^{-3/2}g^{-3j/2}\le\frac14g^{-3j/2}$. Lemma~\ref{lem_deficit_central} and \eqref{eq:cap-rate} conclude. \end{proof} \begin{lemma}[Products of block masses]\label{lem_fc_late_survival} For all integers $0\le j_1\le j_2$, \[ \prod_{j_1\le j\frac{199}{200}. \] \end{lemma} \begin{proof} All factors lie in $[0,1]$ (Lemma~\ref{lem_first_crossing_prefix_disjoint}), so the product is at least $1-\sum_{j\ge0}(1-\mass(\FC(\delta_j,R_j)))$. We bound the three sums arising from Lemma~\ref{lem_deficit_central}. With $c=529/10^6$, $\delta_j-14\ge16530+166j$ gives $\sum_j2e^{-c(\delta_j-14)}\le2e^{-16530c}/(1-e^{-166c})$, where $1-e^{-166c}\ge166c-(166c)^2/2>\frac{83}{1000}$ and $e^{16530c}>6275$ (Lemma~\ref{lem_s03_log3_bounds}(4) with $k=40$). Next $\delta_j\ge16544g^j$, $16544^3\ge2127000^2$ and $1-g^{-3/2}\ge1-g^{-1}=\frac1{101}$ give $\sum_j2\delta_j^{-3/2}\le\frac{202}{2127000}$. Each value of $\floor{j/56}$ occurs $56$ times, so $\sum_j2^{-(R_j+1)}\le56\cdot2^{-29}$. Finally \[ \frac2{6275}\cdot\frac{1000}{83}+\frac{202}{2127000}+\frac{56}{2^{29}}<\frac1{200}.\qedhere \] \end{proof} \section{Sources and the histogram estimate}\label{sec:est-histogram} This section proves the spread of the sources (Lemma~\ref{lem_endpoint_ratio}), used in Lemmas~\ref{lem_shift_count} and~\ref{lem_overlap}, and the histogram estimate \eqref{eq:histogram} (Proposition~\ref{lem_histogram_bound}) used in Section~\ref{sec:census}. The arguments are those of \cite[proof of Proposition~3.1]{Mazur}, made explicit. \subsection{Sources} \begin{lemma}[Spread of the sources]\label{lem_endpoint_ratio} Let $t\ge16^{16544}$ be odd and $j\in\N$. For all $w,w'\in L_j$, \[ s_{w'}\le2^{R_\Sigma}s_w. \] \end{lemma} \begin{proof} Multiplying the bounds of Lemma~\ref{lem_endpoint_large} over $i2/401$, hence $\sum_{i287682/10^6$. \item For real $x\ge0$ and $k\in\N$, $\sum_{j=0}^kx^j/j!\le e^x$. In particular $e^9>8000$. \end{enumerate} \end{lemma} \begin{proof} Parts (1) and (3), and the numerical claim in (4), follow from the standard values $\log_23=1.58496\ldots$, $\log2=0.6931471805\ldots$, $\log(4/3)=0.2876820724\ldots$ and $e^9=8103.08\ldots$. Part (2) is the series $\log y=2\sum_{j\ge0}r^{2j+1}/(2j+1)$, valid as $0\le r<1$ and $(1+r)/(1-r)=y$; its tail after $N$ terms lies between $0$ and $\frac2{2N+1}\sum_{k\ge0}r^{2N+1+2k}=\frac{2r^{2N+1}}{(2N+1)(1-r^2)}$. Part (4) holds because the exponential series has nonnegative terms. \end{proof} \subsection{The Fourier parameters and the threshold \texorpdfstring{$D_*$}{D*}}\label{app:analytic} The Fourier bound \eqref{eq:fourier} is proved twice by one argument, for the original index $\mathrm o$ and the bootstrap index $\mathrm b$; the two parameter sets differ in the constants of Table~\ref{tab:fourier-params}. This subsection defines them, the trace schedule built from them and the threshold $D_*(\iota)$ above which the descent step holds, and proves their numerical properties. \begin{definition}[Fourier parameters]\label{def_eps_star}% \label{def_s02_kappa}\label{def_s02_z}\label{def_s02_chi}\label{def_s02_Aexp}% \label{def_Tstar}\label{def_s02_pinit}\label{def_Rstar}\label{def_s02_H}\label{def_s02_K}% \label{def_s02_alpha}\label{def_s02_eta}\label{def_s02_split}\label{def_s02_ROmega}\label{def_s02_Omega_far} The constants common to both indices are \[ \varepsilon=\frac{37037}{10^6},\quad z=\frac{133}{3125},\quad\kappa=\frac{3187}{20000},\quad\chi=\frac{63}{2500},\quad b_*=\frac{333407}{10^6},\quad\ell_{\mathrm{cont}}=\frac{157263}{100000}. \] The constants depending on $\iota$ are listed in Table~\ref{tab:fourier-params}, where $V_\iota$ is defined in Definition~\ref{def_s02_schedule}. The size factors are \[ (K_0(\iota),\ldots,K_{r_\iota}(\iota))=\begin{cases}(4638,1622,1253,971,754,587,458,359,292,2^{30},2^{30}),&\iota=\mathrm o,\\(718,268,1024,2^{30}),&\iota=\mathrm b.\end{cases} \] \end{definition} \begin{table}[ht] \centering \caption{The constants of the two Fourier parameter sets.}\label{tab:fourier-params} \begin{tabular}{lll} quantity&$\iota=\mathrm o$&$\iota=\mathrm b$\\\hline exponent $A_\iota$; $a_\iota=A_\iota-\frac14$&$\frac{21193}{10000}$; $\frac{18693}{10000}$&$\frac{17}{10}$; $\frac{29}{20}$\\ Case-2 split $\mathsf s_\iota$&$\frac32$&$2$\\ reward bound $T_\iota$; first position $p_0(\iota)=T_\iota+1$&$192$; $193$&$168$; $169$\\ schedule length $r_\iota$&$10$&$3$\\ window height $H_\iota$; slope $\alpha_\iota$&$10100$; $\frac{113}{1000}$&$500$; $\frac3{25}$\\ event coefficients $\mathfrak e_i(\iota)$, $0\le i\le r_\iota$&$(\frac{77}{100})^i$&$1,\frac{77}{100},b_*,b_*^2$\\ far-gap scale $R_\Omega(\iota)$&$\ceil{1231V_{\mathrm o}/4}$&$45V_{\mathrm b}$\\ far-gap threshold $\Omega_\iota$&$R_\Omega(\mathrm o)^2$&$R_\Omega(\mathrm b)^2$\\ continuation factor $c_{\mathrm{cont}}(\iota)$&$\frac{14009206687631}{500000000000}$&$\frac{7245014059}{500000000}$\\ prefactor bound: $\log_2B_F(\iota)<$&$325.7939550288$&$88.1188851177$ \end{tabular} \end{table} \begin{definition}[Trace schedule]\label{def_s02_schedule}\label{def_Pstar}\label{def_s02_B}\label{def_s02_S} The \emph{schedule positions} are $p_0=p_0(\iota)$ and \[ p_{i+1}=p_i+\ceil{\alpha_\iota S_i}+H_\iota+T_\iota+1,\qquad S_i=K_i(\iota)(p_i+1)\qquad(0\le i\mathsf s_\iota m\ge\Omega_\iota$ (Section~\ref{sec:fb-case3}); the near-top case needs $m\ge2^{42}$. \begin{lemma}[The thresholds]\label{lem_s02_Dstar_eq}\label{lem_s02_far_B}\label{lem_s02_far_S}% \label{lem_s02_DF_head}\label{lem_s02_log2Bstar} \leavevmode \begin{enumerate} \item $D_*(\iota)=D_{\mathrm{sc}}(\iota)\ge2^{47}$ and $D_{\mathrm{bad}}(\iota)\ge2^{43}$, with $D_{\mathrm{bad}}(\mathrm o)<2^{116}$, $D_{\mathrm{bad}}(\mathrm b)=133592900435968$ and \[ D_{\mathrm{sc}}(\mathrm o)=1260064847115131240228229351654462380561780602,\qquad D_{\mathrm{sc}}(\mathrm b)=267725467120047. \] Hence \[ D_F(\mathrm o)=2520129694230262480456458703308924761123561210,\qquad D_F(\mathrm b)=535450934240100. \] \item Every real $m\ge D_{\mathrm{sc}}(\iota)$ satisfies $P_\iota\le m$ and $\mathsf s_\iota m\ge\Omega_\iota$. \item The prefactors satisfy \[ 325.7939550287<\log_2B_F(\mathrm o)<325.7939550288,\quad88.1188851176<\log_2B_F(\mathrm b)<88.1188851177. \] In particular $B_F(\mathrm o)<2^{349}$. \end{enumerate} \end{lemma} \begin{proof} For (1), $\Omega_\iota/\mathsf s_\iota$ is an integer, so $D_{\mathrm{sc}}(\iota)=2+P_\iota+2\Omega_\iota/3$ for $\mathrm o$ and $2+P_\iota+\Omega_\iota/2$ for $\mathrm b$; the values and the comparisons are integer computations from Lemma~\ref{lem:schedule}, and $D_{\mathrm{bad}}(\iota)\ge2^{21}P_\iota\ge2^{43}$. Part (2) follows from $D_{\mathrm{sc}}(\iota)\ge P_\iota$ and $D_{\mathrm{sc}}(\iota)\ge\Omega_\iota/\mathsf s_\iota$. For (3), write $\frac{15}2D_F(\iota)=2^eu$ with $e\in\N$ and $1\le u<2$ ($e=153$ for $\mathrm o$, $e=51$ for $\mathrm b$). Then $\log_2B_F(\iota)=A_\iota(e\log2+\log u)/\log2$, and \eqref{eq:logcert} with $N=80$ for $\log2$ and $\log u$, the lower bounds in the numerator and the upper bound for $\log2$ in the denominator (and conversely), gives rational enclosures of width below $10^{-20}$ that lie in the stated intervals. \end{proof} The near-top case (Section~\ref{sec:fb-cases}) bounds the paid mass of a first passage over the top edge, times an inverse power of the remaining distance to the horizon; it closes by four integer comparisons. \begin{lemma}[Numerical facts for Case~2]\label{lem_mo_rate_tiny}\label{lem:paid-gates} The following integer comparisons hold: \begin{gather*} (38177\cdot1000)^{10000}2048^{21193}<(125000\cdot999)^{10000}1279^{21193},\\ 96338641^{10000}2048^{21193}<(97\cdot10^6)^{10000}2045^{21193},\\ (38177\cdot1000)^{10}2048^{17}<(125000\cdot999)^{10}1023^{17},\qquad96338641^{10}2048^{17}<(97\cdot10^6)^{10}2045^{17}. \end{gather*} Equivalently, with $f_\iota=(2047-512\mathsf s_\iota)/2048$, that is $f_{\mathrm o}=\frac{1279}{2048}$ and $f_{\mathrm b}=\frac{1023}{2048}$, and $b_s=\frac{2045}{2048}$, \[ \frac{38177}{125000}f_\iota^{-A_\iota}<\frac{999}{1000},\qquad\frac{96338641}{10^8}b_s^{-A_\iota}<\frac{97}{100}. \] \end{lemma} \begin{proof} Raise the second set of inequalities to the power $10000$ (for $\mathrm o$) or $10$ (for $\mathrm b$) and clear denominators. \end{proof} \subsection{The error budget}\label{app:budget} This subsection defines the error budget \eqref{eq:budget} of Case~3 and shows that it is less than $1$ for both indices. It bounds the Case~3 error $\mathcal E_\iota$ of Definition~\ref{def_c3_error} after rounding each of its pieces upward. \begin{definition}[Error budget]\label{def_s02_cont}\label{def_s02_lc}\label{def_s02_PW}% \label{def_s02_Pi_ad_plus}\label{def_s02_Uo}\label{def_s02_Uv}\label{def_s02_Ud} Put $x_W(\iota)=zT_\iota-A_\iota\ell_{\mathrm{cont}}$ and $P_W(\iota)=\sum_{j=0}^{20}x_W(\iota)^j/j!$. With the notation of Definition~\ref{def_c3_error}, let $\Pi^+_\iota$ be $\Pi^{\mathrm{ad}}_\iota$ with each of its $r_\iota$ terms rounded up to a multiple of $10^{-16}$, let $E^{\mathrm{cl},+}_\iota$ be $E^{\mathrm{cl}}_\iota$ with each of its terms rounded up to a multiple of $10^{-24}$, and let $U^{\mathrm o}_\iota$, $U^{\mathrm v}_\iota$, $U^{\mathrm d}_\iota$ be $9(\frac{25}{27})^{X^{\mathrm o}_\iota}$, $(y^{\mathrm v}_\iota)^{-X^{\mathrm l}_\iota(0)}$ and $2(b^{\mathrm d}_\iota)^{-4X^{\mathrm d}_\iota(0)}$ rounded up to multiples of $10^{-20}$. The \emph{error budget} is \begin{equation}\label{eq:budget} \mathcal B_\iota=\frac1{8000}+\frac{\mathsf q_{\mathrm{mass}}}{P_W(\iota)}+\Bigl(c_{\mathrm{cont}}(\iota)-\frac1{P_W(\iota)}\Bigr)\mathcal E^+_\iota, \end{equation} where \[ \mathcal E^+_\iota=\Pi^+_\iota+\mathsf q_{\mathrm{mass}}\mathfrak e_{r_\iota}(\iota)+E^{\mathrm{sq}}_\iota+U^{\mathrm o}_\iota+\Bigl(\frac{11}{16}\Bigr)^{H^{\mathrm{pk}}_\iota}+\frac{2161}{2^{127}}+\frac{148}{\Omega_\iota}+\mathsf q_{\mathrm{mass}}\bigl(U^{\mathrm v}_\iota+U^{\mathrm d}_\iota+E^{\mathrm{cl},+}_\iota\bigr)\ge\mathcal E_\iota. \] \end{definition} In order, the terms of $\mathcal B_\iota$ pay for the bad advance, the paid mass outside the low-reward event, and, through the continuation factor, the packing, the trace survival, the square-root deviations, the overshoot deviation, the common initial exception, and the vertical and drift-free deviations and the clearing of the paid mass. \begin{lemma}[The budget closes]\label{lem_s02_budget}\label{lem_s02_cont}\label{lem_s02_white_term}% \label{lem_s02_budget_le}\label{lem_s02_budget_plus}\label{lem_s02_Pi_ad}\label{lem_s02_Epiece_value}% \label{lem_s02_Uo}\label{lem_s02_Uv}\label{lem_s02_Ud}\label{lem_c3_exc_sum} For both indices: \begin{enumerate} \item $(400/83)^{A_\iota}400/83=4.819277\ldots$, so $(400/83)^{A_\iota}0$, $x_W(\mathrm b)=\frac{4476609}{10^6}>0$ give $1\xi_{6198}$, and $\floor{2^{-a}\mathsf T(\operatorname{ix}(y_{k,a}))}$ otherwise. For tables $Y_q(r,k)$, $1\le q\le8$, $r\in G_q$, $k\le6198$, and $1\le a\le60$ let $c^{\mathrm{jt}}_q(r,k,a)$ be $0$ unless $3\mid2^ar-1$ (with $0\le r<3^q$); otherwise it is $c_{Y_0}(k,a)$ if $q=1$, and for $q\ge2$ it is $\floor{2^{-a}Y_{q-1}(\frac{2^ar-1}3\bmod3^{q-1},\operatorname{ix}(y_{k,a}))}$ if $0\le y_{k,a}\le\xi_{6198}$ and $0$ otherwise. \begin{lemma}[The joint-law tables]\label{lem:joint-tables} There are integer tables $Y_0,\ldots,Y_8$ with \begin{gather*} Y_0(0)\le Y_0(1)\le\cdots\le Y_0(6198)\le\floor{2^{62}F^-(\xi_{6198})},\qquad Y_0(k)\le\max\Bigl(\floor{2^{62}F^-(\xi_k)},\sum_{a=1}^{60}c_{Y_0}(k,a)\Bigr),\\ Y_q(r,k)\le\sum_{a=1}^{60}c^{\mathrm{jt}}_q(r,k,a)\quad(1\le q\le8),\qquad Y_8(6275,384)=617014680840434. \end{gather*} Moreover, with $\mathfrak m_8$ as in Lemma~\ref{lem_s05_tuple_mass}, $6561\mathfrak m_8-\frac{13}{15}-2^{-28}>0.0064$. \end{lemma} \begin{proof} The table $Y_0$ is the stationary point, reached after $724$ sweeps, of the iteration \[ Y^{(0)}_0(k)=\floor{2^{62}F^-(\xi_k)},\qquad Y^{(s+1)}_0(k)=\max_{l\le k}\max\Bigl(Y^{(s)}_0(l),\sum_{a=1}^{60}c_{Y^{(s)}_0}(l,a)\Bigr); \] its entries include $Y_0(384)=997765252056324269$ and $Y_0(6198)=4611686018427359570$, which is $\floor{2^{62}F^-(\xi_{6198})}$. For $q\ge1$ the table $Y_q$ vanishes outside the reachable pairs: $\mathcal Y_8=\{(6275,384)\}$, and $\mathcal Y_{q-1}$ consists of the pairs $(\frac{2^ar-1}3\bmod3^{q-1},\operatorname{ix}(y_{k,a}))$ with $(r,k)\in\mathcal Y_q$, $a\le60$, $3\mid2^ar-1$ and $0\le y_{k,a}\le\xi_{6198}$. On $\mathcal Y_q$, $Y_q(r,k)$ is the sum in its defining inequality, computed for $q=1,\ldots,8$ in turn. The sets $\mathcal Y_8,\ldots,\mathcal Y_1$ have $1,26,243,1564,5830,9719,8465,4568$ elements, of which $1,16,145,907,3502,6076,5504,3043$ carry a nonzero value. All quantities are integers: with $p=2^an_k-512$, $y_{k,a}<0$ means $p<0$, $y_{k,a}>\xi_{6198}$ means $p>3n_{6198}$, $\operatorname{ix}(y_{k,a})$ is the largest $k'$ with $3n_{k'}\le p$, and $\floor{2^{62}F^-(x)}=\floor{2^{62}(n-2560)/(n+1024)}$ for $x=n/512\ge5$. The defining inequalities are checked entry by entry; how the tables are produced plays no role. The last claim is a rational comparison; the difference is $0.006438\ldots$. \end{proof} \subsection{Reproducing the finite checks}\label{app:pipeline} Every finite claim above is an integer or rational computation that a reader can repeat in any language with exact integers, in the following order. \begin{enumerate} \item \emph{Scales.} Iterate $\delta_{j+1}=\delta_j+\ceil{\delta_j/100}$ from $16544$; this gives $\delta_{29}$. \item \emph{Fourier schedules and thresholds.} For each index, iterate the schedule of Definition~\ref{def_s02_schedule} from the constants of Table~\ref{tab:fourier-params}, then form $R_\Omega(\iota)$, $\Omega_\iota$, $D_{\mathrm{bad}}(\iota)$, $D_{\mathrm{sc}}(\iota)$, $D_*(\iota)$ and $D_F(\iota)$; compare with Lemmas~\ref{lem:schedule} and~\ref{lem_s02_Dstar_eq}. \item \emph{Logarithms.} Evaluate the two sides of \eqref{eq:logcert} with $N=80$ as rationals for Lemma~\ref{lem_s02_Dstar_eq}(3), and bound exponentials below by the partial sums of Lemma~\ref{lem_s03_log3_bounds}(4). \item \emph{Budgets.} Evaluate Definition~\ref{def_c3_error} and \eqref{eq:budget} with the stated upward roundings at $10^{-16}$, $10^{-20}$ and $10^{-24}$, and compare $1-\mathcal B_\iota$ with the bounds of Lemma~\ref{lem_s02_budget}. \item \emph{Powers.} Check the integer comparisons of Lemmas~\ref{lem_mo_rate_tiny} and~\ref{lem_s02_budget}(1) directly; the largest involve integers of fewer than $600000$ bits. \item \emph{Tables.} Compute the grid, the stationary table $Y_0$ and the tables $Y_q$ on the reachable sets as described in the proof of Lemma~\ref{lem:joint-tables}, then check every defining inequality. \end{enumerate} \section{Extracting tower bounds from Mazur's constants}\label{app:mazur} This appendix proves \eqref{eq:mazur-bounds}: Mazur's theorem holds with $(X_0,c)=(D_M,D_M^{-1})$, where $D_M=2^{2^{2^{2^{2^{2^{2^{173}}}}}}}$. Mazur proves it with the density constant $c_{\mathrm M}$ and cutoff $X_{\mathrm M}$ defined in \cite[Section 8]{Mazur}; we show $1/c_{\mathrm M}50016$. Let $C_{\mathrm M}=2(640\cdot6409\cdot D_{*,\mathrm M})^{6409}+2+2^{481}$ be Mazur's mixing constant, where $D_{*,\mathrm M}$ is the maximum of his thresholds. By \eqref{eq:mazur-p}, $\log_2\mathfrak p_{\mathrm M}>3^{r_{\mathrm M}}>2^{4a_{\mathrm M}}$. His thresholds other than $D_{\mathrm{sc},\mathrm M}$ and $D_{\mathrm{exp},\mathrm M}$ are less than $2^{6a_{\mathrm M}+42}+2^{39}\mathfrak p_{\mathrm M}<\mathfrak p_{\mathrm M}^2$. The degree-nine term of $D_{\mathrm{sc},\mathrm M}$ is at most $2^{294921}\mathfrak p_{\mathrm M}^9$, so $\mathfrak p_{\mathrm M}^{10}\le D_{\mathrm{sc},\mathrm M}<\mathfrak p_{\mathrm M}^{10}+2^{294922}\mathfrak p_{\mathrm M}^9<\mathfrak p_{\mathrm M}^{11}$, and \[ \log_2 D_{\mathrm{exp},\mathrm M}=8192\cdot6409\,2^{3a_{\mathrm M}} <2^{3a_{\mathrm M}+26}<2^{r_{\mathrm M}}<3^{r_{\mathrm M}}<\log_2 \mathfrak p_{\mathrm M}. \] Hence $\mathfrak p_{\mathrm M}^{10}\le D_{*,\mathrm M}<\mathfrak p_{\mathrm M}^{11}$. As $640\cdot6409<2^{22}$ and $6409\cdot11<2^{17}$, it follows that $64090\log_2\mathfrak p_{\mathrm M}<\log_2C_{\mathrm M}<2+6409(22+11\log_2\mathfrak p_{\mathrm M}) <2^{17}\log_2\mathfrak p_{\mathrm M}$, and \eqref{eq:mazur-p} gives \begin{equation}\label{eq:mazur-L} 3^{r_{\mathrm M}}<\log_2C_{\mathrm M}<2^{20}a_{\mathrm M}\,3^{r_{\mathrm M}},\qquad \log_2C_{\mathrm M}>4\cdot2^{80}+1000. \end{equation} Put $b_{0,\mathrm M}=2^{80}$. The next parameters \cite[(8.1)--(8.2)]{Mazur} are \[ F_{\mathrm M}=2^{467}b_{0,\mathrm M}\cdot16^{b_{0,\mathrm M}}(C_{\mathrm M}+1),\quad N_{*,\mathrm M}=20000(\ceil{\log_2 F_{\mathrm M}}+64),\quad N_{\mathrm t,\mathrm M}=20000(\ceil{\log_2(21F_{\mathrm M})}+96). \] Since $\log_2 F_{\mathrm M}=547+4b_{0,\mathrm M}+\log_2(C_{\mathrm M}+1)$, \[ 20000\log_2C_{\mathrm M}\le N_{*,\mathrm M}<40000\log_2C_{\mathrm M},\qquad N_{\mathrm t,\mathrm M}<40000\log_2C_{\mathrm M}. \] The recurrence $b_{j+1,\mathrm M}=b_{j,\mathrm M}+\floor{b_{j,\mathrm M}/100}$ gives $b_{j,\mathrm M}\le2^{80+j}$. Unfolding the definition \cite[(8.3)--(8.4)]{Mazur} of $q_{*,\mathrm M}$ yields \[ q_{*,\mathrm M}=\floor{b_{N_{*,\mathrm M},\mathrm M}/4} +\sum_{i100$. Taking another logarithm and using \eqref{eq:mazur-L} gives \begin{equation}\label{eq:mazur-fifth} \log_2^{\circ5}(1/c_{\mathrm M})<\log_2^{\circ2}(C_{\mathrm M})+17100$. Hence $\log_2^{\circ4}(X_{\mathrm M})<100001\log_2C_{\mathrm M}$, and the same fifth-logarithm bound \eqref{eq:mazur-fifth} holds for $X_{\mathrm M}$. \subsection{Counting the iterated logarithms} It remains to count the logarithms. For either $Y=1/c_{\mathrm M}$ or $Y=X_{\mathrm M}$, the preceding bounds give \[ \log_2^{\circ5}(Y)<2r_{\mathrm M}+207<2^{4a_{\mathrm M}+17}. \] Indeed $2r_{\mathrm M}=128180\,2^{4a_{\mathrm M}}+49172\,2^{a_{\mathrm M}}$, and $49172\,2^{a_{\mathrm M}}+207<2892\,2^{4a_{\mathrm M}}$, where $128180+2892=2^{17}$. Therefore \[ \log_2^{\circ6}(Y)<4a_{\mathrm M}+17=2^{172}+17<2^{173},\qquad \log_2^{\circ7}(Y)<173. \] Since $Y>\calM_{\mathrm M}$ and $q_{*,\mathrm M}>100$, the iterated logarithms $\log_2^{\circ i}(Y)$ with $i\le6$ are positive, so exponentiating seven times gives $1/c_{\mathrm M}X_{\mathrm M}$ and the density constant $1/D_M