\chapter{The tail of the weighted trail sums}\label{s:tail} In this appendix, we prove \zcref{p:tail}, which gives the bound $K_{\mathfrak t}(1) \le 0.92320$ of \zcref{t:inputs} for both types, and we fix the enumerations $\varsigma_w$ of the first-visit steps that Hypothesis~(H3) leaves open. The trails of length at most $20$ are enumerated exactly and their weights are bounded using upward rounding. A longer trail is followed exactly for $20$ steps, and we dominate its continuation by a weighted walk on $\Z^2$ that remembers a phase, its last ten steps, and its position. We bound the total weight of the paths of this walk that end at $v$ by a supersolution, that is, a nonnegative function on the states of the walk that dominates its own image under one step of the walk plus the reward at $v$. Such a function is determined by finitely many numbers, and a program verifies the defining inequality with directed rounding. Since the walk keeps its position and must end at $v$, the bound retains the constraint that the trails close at $v$ (see \zcref{s:computer-H3}). \section{Reduction to two scalar sums}\label{s:tail-reduction} Throughout this appendix, we fix a type $\mathfrak t \in \{\tcoll, \tdiag\}$, and we write $c = (0, 0)$, $u = (-1, 0)$, and $v = v^{\mathfrak t}$, so that $(u, v)$ is a pair of type $\mathfrak t$ with center $c$. Recall from \zcref{s:contraction-sums} that $\mathcal T^{\mathfrak t}_n$ is the set of trails $w = (v_0, \dots, v_n)$ of $\Z^2$ that do not visit $c$, with $v_0 = u$, $v_n = v$, and $v_i \neq v$ for $0 \le i < n$, and that we use the arrival site $v_{-1} = c$. The thresholds $\cs, \ct \in (0, 1]$ appear through the numbers $1/\cs$ and $1/\ct$, and we use their values $(961/1000, 187/200)$ only in \zcref{s:tail-bound}. We use the notions of \zcref{s:walks-growth,s:contraction-sums} for trails of $\Z^2$: the steps $j \in \{1, \dots, n\}$ of a trail, the set $\FV(w)$ of first-visit steps, the number $\rev(w)$ of revisits, straight steps and turns, the pairs at a step, dead and live pairs, the weighted coefficient sum $\kappa(j)$ of \eqref{e:kappa}, and the numbers $\bar\rho_j \in \{1/\cs, 1/\ct\}$. These definitions apply verbatim to every trail $(v_0, \dots, v_k)$ of $\Z^2$ that does not visit $c$, with $v_0 = u$ and the arrival site $v_{-1} = c$, whether or not it ends at $v$. The type of step $j$ (revisit, straight first visit, or turning first visit) and the number $\kappa(j)$ are determined by $(v_0, \dots, v_j)$. For $w \in \mathcal T^{\mathfrak t}_n$, we let $\mathsf m(\{w\})$ denote the term of $w$ in \eqref{e:mT}, that is, \begin{equation}\label{e:tail-mw} \mathsf m(\{w\}) = 3^{-n} \Bigl( \frac35 \Bigr)^{\rev(w)} \sum_{k = 1}^{|\FV(w)|} \kappa(\varsigma_w(k)) \prod_{l = 1}^{k} \bar\rho_{\varsigma_w(l)} . \end{equation} By \eqref{e:kernel}, we have \begin{equation}\label{e:tail-K1} h_{\mathfrak t} K_{\mathfrak t}(1) = \sum_{n \ge 1} \mathsf m_{\mathfrak t}(n) . \end{equation} Since $d(u, v) = 2$ and $\Z^2$ is bipartite, every trail from $u$ to $v$ has even length, and $\mathsf m_{\mathfrak t}(n) = 0$ for odd $n$. The first step of a trail of $\mathcal T^{\mathfrak t}_n$ avoids $c = u + \sE$, so that its direction belongs to $\{\sN, \sW, \sS\}$. For $\mathsf e_0 \in \{\sN, \sW, \sS\}$, we let $\mathcal T^{\mathfrak t, \mathsf e_0}_n$ denote the set of trails of $\mathcal T^{\mathfrak t}_n$ whose first step is $\mathsf e_0$, and we set $a_0 = u + \mathsf e_0$. Then \begin{equation}\label{e:tail-split} \mathsf m_{\mathfrak t}(n) = \sum_{\mathsf e_0 \in \{\sN, \sW, \sS\}} \mathsf m(\mathcal T^{\mathfrak t, \mathsf e_0}_n) . \end{equation} By \eqref{e:tail-K1}, the bound \eqref{e:inputsH3} of \zcref{t:inputs} is equivalent to the two scalar inequalities \begin{equation}\label{e:tail-target} \sum_{n \ge 1} \mathsf m_\tcoll(n) \le 0.92320, \qquad \sum_{n \ge 1} \mathsf m_\tdiag(n) \le \frac54 \cdot 0.92320 . \end{equation} \section{The enumerations}\label{s:tail-enum} We now fix the enumerations $\varsigma_w$ in (H3). For trails of length at most $20$, we use an enumeration that minimizes \eqref{e:tail-mw}. This enumeration depends on the whole trail, so that a walk with a bounded memory cannot follow it. For longer trails, we list the straight first-visit steps before the turns, which a walk can follow with the four phases of \zcref{s:tail-phases}. \begin{definition}\label{d:enum} Let $w \in \mathcal T^{\mathfrak t}_n$. If $n \le 20$, we let $\varsigma_w$ list the steps $j \in \FV(w)$ in increasing order of the quotient $(\bar\rho_j - 1)/(\bar\rho_j \kappa(j))$, which we set equal to $+\infty$ if $\kappa(j) = 0$, with ties broken by increasing $j$. If $n > 20$, we let $\varsigma_w$ list the straight steps of $\FV(w)$ in increasing order, followed by the turning steps of $\FV(w)$ in increasing order. \end{definition} For fixed thresholds, each $\varsigma_w$ is determined by $w$. We now explain why, for $n \le 20$, the enumeration $\varsigma_w$ minimizes \eqref{e:tail-mw} over all enumerations of $\FV(w)$. Let $i$ and $j$ be consecutive in an enumeration, with $i$ before $j$, and let $\Pi$ be the product of $\bar\rho$ over the steps that precede them. Exchanging $i$ and $j$ changes the sum in \eqref{e:tail-mw} by \begin{equation}\label{e:tail-swap} \Pi \bigl[ \bar\rho_j \kappa(j) + \bar\rho_j \bar\rho_i \kappa(i) - \bar\rho_i \kappa(i) - \bar\rho_i \bar\rho_j \kappa(j) \bigr] = \Pi \bigl[ \bar\rho_i \kappa(i) (\bar\rho_j - 1) - \bar\rho_j \kappa(j) (\bar\rho_i - 1) \bigr] , \end{equation} since the terms of the other steps do not change. Observe that the right side is nonpositive when the quotient of $i$ is larger than that of $j$, and that it vanishes when the quotients are equal. Every enumeration can be brought into the order of \zcref{d:enum} by a finite sequence of exchanges of consecutive steps, each of which exchanges two steps whose quotients are in decreasing order, or equal quotients in the wrong order of indices. None of these exchanges increases \eqref{e:tail-mw}. \section{Kinds and phases}\label{s:tail-phases} We now write \eqref{e:tail-mw}, for $n > 20$, as a sum of products with one factor for each step. We define the \emph{kind} of a step of a trail to be $\mathrm s$ if it is a straight first visit, $\mathrm t$ if it is a turning first visit, and $\mathrm r$ if it is a revisit. (For a step $j \ge 2$ of a trail $(v_0, \dots, v_k)$, this is the kind of the admissible step $v_j - v_{j - 1}$ in the sense of \zcref{d:history}, from the history formed by the steps $1, \dots, j - 1$.) We use four \emph{phases}, denoted $\mathrm t^-$, $\mathrm t^+$, $\mathrm s^-$, and $\mathrm s^+$. Each term of \eqref{e:tail-mw} belongs to one step $j = \varsigma_w(k)$ of $\FV(w)$. Heuristically, the phases $\mathrm t^-$ and $\mathrm t^+$ are used for the steps before and after $j$ when $j$ is a turn, and the phases $\mathrm s^-$ and $\mathrm s^+$ when $j$ is straight. For a phase $\vartheta$ and a kind $\mathrm k$, we define the \emph{phase weight} $\varpi_\vartheta(\mathrm k)$ by the table \begin{equation}\label{e:phaseweights} \begin{array}{c|ccc} \vartheta & \varpi_\vartheta(\mathrm s) & \varpi_\vartheta(\mathrm t) & \varpi_\vartheta(\mathrm r) \\ \hline \mathrm t^- & 1/(3\cs) & 1/(3\ct) & 1/5 \\ \mathrm t^+ & 1/(3\cs) & 1/3 & 1/5 \\ \mathrm s^- & 1/(3\cs) & 1/3 & 1/5 \\ \mathrm s^+ & 1/3 & 1/3 & 1/5 \end{array} \end{equation} Since $\cs, \ct \le 1$, the smallest phase weight is $1/5$, and $\varpi_\vartheta(\mathrm s), \varpi_\vartheta(\mathrm t) \ge 1/3$ for every phase $\vartheta$. Let $w = (v_0, \dots, v_k)$ be a trail of $\Z^2$ that does not visit $c$, with $v_0 = u$, and let $\mathrm k_j$ denote the kind of its step $j$. For $1 \le j \le k$ and phases $\vartheta$, $\vartheta'$, we define the weight of step $j$ for the transition from $\vartheta$ to $\vartheta'$ by \begin{equation}\label{e:tail-transition} \varpi_j(\vartheta, \vartheta') = \begin{cases} \varpi_\vartheta(\mathrm k_j) & \text{if } \vartheta' = \vartheta, \\ \kappa(j)/(3\ct) & \text{if } (\vartheta, \vartheta') = (\mathrm t^-, \mathrm t^+) \text{ and } \mathrm k_j = \mathrm t, \\ \kappa(j)/(3\cs) & \text{if } (\vartheta, \vartheta') = (\mathrm s^-, \mathrm s^+) \text{ and } \mathrm k_j = \mathrm s, \\ 0 & \text{otherwise}. \end{cases} \end{equation} Note that $\varpi_j(\vartheta, \vartheta')$ is determined by $(v_0, \dots, v_j)$. A transition from $\mathrm t^-$ to $\mathrm t^+$, or from $\mathrm s^-$ to $\mathrm s^+$, marks the step $j$ of a term of \eqref{e:tail-mw}. \begin{lemma}\label{l:phases} Let $n > 20$ and $w \in \mathcal T^{\mathfrak t}_n$, and let $\varsigma_w$ be as in \zcref{d:enum}. Then \begin{equation}\label{e:tail-phasesum} \mathsf m(\{w\}) = \sum_{\vartheta_0 \in \{\mathrm t^-, \mathrm s^-\}} \ \sum_{\vartheta_1, \dots, \vartheta_{n - 1}} \ \sum_{\vartheta_n \in \{\mathrm t^+, \mathrm s^+\}} \ \prod_{j = 1}^{n} \varpi_j(\vartheta_{j - 1}, \vartheta_j) . \end{equation} \end{lemma} \begin{proof} By \eqref{e:tail-transition}, a sequence of phases can have positive weight in \eqref{e:tail-phasesum} only if it changes exactly once, at a step $j$, from $\mathrm t^-$ to $\mathrm t^+$ with $\mathrm k_j = \mathrm t$, or from $\mathrm s^-$ to $\mathrm s^+$ with $\mathrm k_j = \mathrm s$. Each step $j \in \FV(w)$ determines exactly one candidate sequence of this form, whose weight is zero when $\kappa(j)=0$. It therefore suffices to show that the product in \eqref{e:tail-phasesum} for the sequence determined by $j$ coincides with the term of $j$ in \eqref{e:tail-mw}, which is \begin{equation}\label{e:phases-term} 3^{-n} \Bigl( \frac35 \Bigr)^{\rev(w)} \kappa(j) \prod_{l = 1}^{k} \bar\rho_{\varsigma_w(l)} , \qquad j = \varsigma_w(k) . \end{equation} Note that $3^{-n} (3/5)^{\rev(w)}$ is the product, over the steps $i$ of $w$, of $1/5$ if $i$ is a revisit and $1/3$ if $i$ is a first visit. Suppose first that $j$ is a turn. By \zcref{d:enum}, the steps up to $j$ in the enumeration are all straight steps of $\FV(w)$ and the turning steps $i \in \FV(w)$ with $i \le j$. Therefore \eqref{e:phases-term} is the product over the steps $i$ of $w$ of the factors \begin{equation*} \begin{cases} 1/5 = \varpi_{\mathrm t^\mp}(\mathrm r) & \text{if } \mathrm k_i = \mathrm r, \\ 1/(3\cs) = \varpi_{\mathrm t^\mp}(\mathrm s) & \text{if } \mathrm k_i = \mathrm s, \\ 1/(3\ct) = \varpi_{\mathrm t^-}(\mathrm t) & \text{if } \mathrm k_i = \mathrm t \text{ and } i < j, \\ \kappa(j)/(3\ct) = \varpi_j(\mathrm t^-, \mathrm t^+) & \text{if } i = j, \\ 1/3 = \varpi_{\mathrm t^+}(\mathrm t) & \text{if } \mathrm k_i = \mathrm t \text{ and } i > j, \end{cases} \end{equation*} where we used \eqref{e:phaseweights}, and $\mathrm t^\mp$ stands for $\mathrm t^-$ if $i < j$ and for $\mathrm t^+$ if $i > j$. This is the product in \eqref{e:tail-phasesum} for the sequence with $\vartheta_i = \mathrm t^-$ for $i < j$ and $\vartheta_i = \mathrm t^+$ for $i \ge j$. Suppose next that $j$ is straight. Then the steps up to $j$ in the enumeration are the straight steps $i \in \FV(w)$ with $i \le j$. In the same way, \eqref{e:phases-term} is the product over the steps $i$ of $w$ of the factors \begin{equation*} \begin{cases} 1/5 = \varpi_{\mathrm s^\mp}(\mathrm r) & \text{if } \mathrm k_i = \mathrm r, \\ 1/3 = \varpi_{\mathrm s^\mp}(\mathrm t) & \text{if } \mathrm k_i = \mathrm t, \\ 1/(3\cs) = \varpi_{\mathrm s^-}(\mathrm s) & \text{if } \mathrm k_i = \mathrm s \text{ and } i < j, \\ \kappa(j)/(3\cs) = \varpi_j(\mathrm s^-, \mathrm s^+) & \text{if } i = j, \\ 1/3 = \varpi_{\mathrm s^+}(\mathrm s) & \text{if } \mathrm k_i = \mathrm s \text{ and } i > j, \end{cases} \end{equation*} with the analogous meaning of $\mathrm s^\mp$. Summing over $j$ proves \eqref{e:tail-phasesum}. \end{proof} \section{The stationary walk}\label{s:tail-walk} In this section and the next, we fix, in addition to $\mathfrak t$, a first direction $\mathsf e_0 \in \{\sN, \sW, \sS\}$, and we recall that $a_0 = u + \mathsf e_0$. We use the histories of memory $10$ of \zcref{d:history}, with their admissible steps, successors, and kinds. We have $|\Omega_{10}| = 60{,}092$. The walk below cannot determine which pairs are dead. Instead, it uses the following two upper bounds for $\kappa(j)$. Let $x \in \Z^2$, and let $\mathsf e'$ and $\mathsf e$ be unit vectors with $\mathsf e \neq -\mathsf e'$. Consider the three neighbors of $x$ other than $x - \mathsf e'$, and the three pairs that they form, with the coefficient $\bar\alpha$ for the pair that does not contain $x + \mathsf e$ and $\bar\beta$ for the two pairs that contain it. We define $\kappa^{\mathrm c}(x, \mathsf e', \mathsf e)$ to be the sum of the coefficient of $p$ times $h(p)$ over the pairs $p$ that do not contain $c$, and we define $\kappa^\circ(\mathsf e', \mathsf e)$ to be the same sum over all three pairs. A short computation gives \begin{equation}\label{e:tail-kappacirc} \kappa^\circ(\mathsf e', \mathsf e) = \begin{cases} \bar\alpha h_\tcoll + 2 \bar\beta h_\tdiag & \text{if } \mathsf e = \mathsf e', \\ \bar\beta h_\tcoll + (\bar\alpha + \bar\beta) h_\tdiag & \text{if } \mathsf e \neq \pm \mathsf e'. \end{cases} \end{equation} Indeed, for a straight step the pair that does not contain $x + \mathsf e$ is collinear and the other two pairs are diagonal. For a turn, the pair formed by $x + \mathsf e$ and $x - \mathsf e$ is collinear, and the other two pairs are diagonal. Now let $w$ be a trail as in \zcref{s:tail-phases}, and let $j \ge 2$ be a step of $\FV(w)$, with arrival direction $\mathsf e' = v_{j - 1} - v_{j - 2}$ and direction $\mathsf e = v_j - v_{j - 1}$. The pairs at step $j$ are the three pairs above for $x = v_{j - 1}$, with the same coefficients, and every live pair avoids $c$. Since all coefficients and type weights are nonnegative, we have \begin{equation}\label{e:tail-kappabounds} \kappa(j) \le \kappa^{\mathrm c}(v_{j - 1}, \mathsf e', \mathsf e) \le \kappa^\circ(\mathsf e', \mathsf e) . \end{equation} Further, $\kappa^{\mathrm c}(x, \mathsf e', \mathsf e) = \kappa^\circ(\mathsf e', \mathsf e)$ unless $c$ is a neighbor of $x$. \begin{definition}\label{d:statwalk} A \emph{state} is a triple $(\vartheta, \omega, x)$ of a phase $\vartheta$, a history $\omega \in \Omega_{10}$, and a site $x \in \Z^2$. We define the nonnegative matrix $\mathsf T = \mathsf T_{\mathfrak t, \mathsf e_0}$, indexed by pairs of states, as follows. Its entries vanish except for the entries $\mathsf T(\vartheta, \omega, x; \vartheta', \omega \mathsf e, x + \mathsf e)$, where $\mathsf e$ is an admissible step from $\omega$ and $\vartheta'$ is a phase. Let $\mathrm k$ denote the kind of $\mathsf e$ as a step from $\omega$, and let $\mathsf e_{10}$ denote the last entry of $\omega$. Then the entry $\mathsf T(\vartheta, \omega, x; \vartheta', \omega \mathsf e, x + \mathsf e)$ is given by the first of the following rules that applies. \begin{enumerate} \item[(a)] If $x \in \{c, v\}$ or $x + \mathsf e = c$, the entry is $0$. \item[(b)] If $x \in \{u, a_0\}$, the entry is $0$ if $\{x, x + \mathsf e\} = \{u, a_0\}$ or $\vartheta' \neq \vartheta$, and it is $1/5$ otherwise. \item[(c)] The entry is $\varpi_\vartheta(\mathrm k)$ if $\vartheta' = \vartheta$, it is $\kappa^{\mathrm c}(x, \mathsf e_{10}, \mathsf e)/(3\ct)$ if $(\vartheta, \vartheta') = (\mathrm t^-, \mathrm t^+)$ and $\mathrm k = \mathrm t$, it is $\kappa^{\mathrm c}(x, \mathsf e_{10}, \mathsf e)/(3\cs)$ if $(\vartheta, \vartheta') = (\mathrm s^-, \mathrm s^+)$ and $\mathrm k = \mathrm s$, and it is $0$ otherwise. \end{enumerate} For a nonnegative function $\mathsf F$ on the states, we define \begin{equation}\label{e:tail-TF} (\mathsf T \mathsf F)(\vartheta, \omega, x) = \sum_{\mathsf e} \sum_{\vartheta'} \mathsf T(\vartheta, \omega, x; \vartheta', \omega \mathsf e, x + \mathsf e) \, \mathsf F(\vartheta', \omega \mathsf e, x + \mathsf e) , \end{equation} where $\mathsf e$ runs over the admissible steps from $\omega$ and $\vartheta'$ over the phases. We define the \emph{reward} $\mathsf g$ by $\mathsf g(\vartheta, \omega, x) = 1$ if $x = v$ and $\vartheta \in \{\mathrm t^+, \mathrm s^+\}$, and $\mathsf g(\vartheta, \omega, x) = 0$ otherwise. Finally, we define the nonnegative matrix $\mathsf T^\circ$, indexed by pairs $(\vartheta, \omega)$, whose entry $\mathsf T^\circ(\vartheta, \omega; \vartheta', \omega \mathsf e)$ is given by rule (c) with $\kappa^\circ(\mathsf e_{10}, \mathsf e)$ in place of $\kappa^{\mathrm c}(x, \mathsf e_{10}, \mathsf e)$, and whose other entries vanish. It acts on nonnegative functions of $(\vartheta, \omega)$ as in \eqref{e:tail-TF}. \end{definition} The sum \eqref{e:tail-TF} has at most $12$ nonzero terms, so that $\mathsf T \mathsf F$ is finite whenever $\mathsf F$ is. The walk with the transition weights $\mathsf T$ remembers its last ten steps, its position, and the first bond $\{u, a_0\}$ of the trail. By rule (a), the walk stops at $v$, where it collects the reward $\mathsf g$. Its steps into $c$ have weight zero. Rule (b) concerns the sites $u$ and $a_0$. A trail of $\mathcal T^{\mathfrak t, \mathsf e_0}_n$ leaves them at the steps $1$ and $2$, so that every later step from these sites is a revisit, although the history of ten steps may not show it. The operator $\mathsf T^\circ$ is the one-step operator of the same walk without its position. At the sites $x$ with $|x|_\infty \ge 3$, rules (a) and (b) do not apply and $\kappa^{\mathrm c} = \kappa^\circ$, so that $\mathsf T(\vartheta, \omega, x; \vartheta', \omega \mathsf e, x + \mathsf e) = \mathsf T^\circ(\vartheta, \omega; \vartheta', \omega \mathsf e)$. The main step of this appendix is \zcref{l:memdom} below, which dominates the trails of length $n > 20$ by the walk. We next describe how such a trail starts. We let $\mathcal T_{\mathrm{pre}}$ denote the set of trails $w' = (v'_0, \dots, v'_{20})$ of $\Z^2$ that visit neither $c$ nor $v$, with $v'_0 = u$ and $v'_1 = a_0$. For $w' \in \mathcal T_{\mathrm{pre}}$, we let $\omega(w') \in \Omega_{10}$ denote the history formed by the last ten steps of $w'$, and for a phase $\vartheta$ we define \begin{equation}\label{e:tail-prefixweight} \mathsf P_\vartheta(w') = \sum_{\vartheta_0 \in \{\mathrm t^-, \mathrm s^-\}} \ \sum_{\vartheta_1, \dots, \vartheta_{19}} \ \prod_{j = 1}^{20} \varpi_j(\vartheta_{j - 1}, \vartheta_j) , \qquad \vartheta_{20} = \vartheta , \end{equation} where $\varpi_j$ is the weight \eqref{e:tail-transition} of step $j$ of $w'$. For $n > 20$ and $w \in \mathcal T^{\mathfrak t, \mathsf e_0}_n$, the prefix $w_{20} = (v_0, \dots, v_{20})$ belongs to $\mathcal T_{\mathrm{pre}}$, by the definition of $\mathcal T^{\mathfrak t, \mathsf e_0}_n$. \begin{lemma}\label{l:memdom} For all $n > 20$, \begin{equation}\label{e:memdom} \mathsf m(\mathcal T^{\mathfrak t, \mathsf e_0}_n) \le \sum_{w' \in \mathcal T_{\mathrm{pre}}} \sum_{\vartheta} \mathsf P_\vartheta(w') \, (\mathsf T^{n - 20} \mathsf g)(\vartheta, \omega(w'), v'_{20}) . \end{equation} \end{lemma} \begin{proof} We split each trail after its step $20$, and we then compare the later steps with the steps of the walk. \emph{Splitting after step 20.} Let $w = (v_0, \dots, v_n)$ be a trail of $\mathcal T^{\mathfrak t, \mathsf e_0}_n$, and let $w' = w_{20}$. The weights $\varpi_j$ of the steps $j \le 20$ of $w$ and of $w'$ coincide, since they are determined by $(v_0, \dots, v_{20})$. Splitting each product in \eqref{e:tail-phasesum} after step $20$, we obtain from \zcref{l:phases} that \begin{equation}\label{e:memdom-split} \mathsf m(\{w\}) = \sum_{\vartheta} \mathsf P_\vartheta(w') \sum_{\vartheta_{21}, \dots, \vartheta_{n - 1}} \ \sum_{\vartheta_n \in \{\mathrm t^+, \mathrm s^+\}} \ \prod_{j = 21}^{n} \varpi_j(\vartheta_{j - 1}, \vartheta_j) , \qquad \vartheta_{20} = \vartheta . \end{equation} \emph{Domination of one step.} For $10 \le j \le n$, let $\omega_j \in \Omega_{10}$ denote the history formed by the last ten steps of $w_j = (v_0, \dots, v_j)$, so that $\omega_{20} = \omega(w')$ and $\omega_j = \omega_{j - 1} \mathsf e$ with $\mathsf e = v_j - v_{j - 1}$. We claim that for $21 \le j \le n$ and all phases $\vartheta$ and $\vartheta'$, \begin{equation}\label{e:memdom-step} \varpi_j(\vartheta, \vartheta') \le \mathsf T(\vartheta, \omega_{j - 1}, v_{j - 1}; \vartheta', \omega_j, v_j) . \end{equation} The step $\mathsf e$ is admissible from $\omega_{j - 1}$, since the path of $\omega_{j - 1}$ is a translate of $(v_{j - 11}, \dots, v_{j - 1})$ and $w$ does not use a bond twice. Rule (a) does not apply, since $w$ does not visit $c$ and $v_{j - 1} \neq v$. Suppose first that $v_{j - 1} \in \{u, a_0\}$. Then step $j$ is a revisit, since $w$ left $u$ at step $1$ and $a_0$ at step $2$, and $\varpi_j(\vartheta, \vartheta')$ equals $1/5$ if $\vartheta' = \vartheta$ and $0$ otherwise. Moreover, $\{v_{j - 1}, v_j\} \neq \{u, a_0\}$, since $w$ used the bond $\{u, a_0\}$ at step $1$. By rule (b), the two sides of \eqref{e:memdom-step} are equal. Suppose next that $v_{j - 1} \notin \{u, a_0\}$, so that rule (c) applies, and let $\mathrm k$ be the kind of $\mathsf e$ as a step from $\omega_{j - 1}$. We distinguish three cases. If $\mathrm k = \mathrm r$, then $v_{j - 1} \in \{v_{j - 11}, \dots, v_{j - 2}\}$, and step $j$ is a revisit. If $\mathrm k \in \{\mathrm s, \mathrm t\}$ and step $j$ is a revisit, then $v_{j - 1} \in \{v_0, \dots, v_{j - 12}\}$. Otherwise, step $j$ is a first visit. Its arrival direction $v_{j - 1} - v_{j - 2}$ is the last entry of $\omega_{j - 1}$, so that its kind as a step of $w$ is $\mathrm k$. Writing $\mathsf T_j = \mathsf T(\vartheta, \omega_{j - 1}, v_{j - 1}; \vartheta', \omega_j, v_j)$, and using \eqref{e:tail-transition}, rule (c), and \eqref{e:tail-kappabounds}, we find in the three cases that \begin{equation*} \varpi_j(\vartheta, \vartheta') \; \begin{cases} = \mathsf T_j \in \{0, 1/5\} & \text{if } \mathrm k = \mathrm r, \\ = \1_{\vartheta' = \vartheta}/5 \le \varpi_\vartheta(\mathrm k) \1_{\vartheta' = \vartheta} \le \mathsf T_j & \text{if } \mathrm k \in \{\mathrm s, \mathrm t\} \text{ and step } j \text{ is a revisit}, \\ \le \mathsf T_j & \text{otherwise}. \end{cases} \end{equation*} In the second case, we used that $\varpi_\vartheta(\mathrm s), \varpi_\vartheta(\mathrm t) \ge 1/3$. In the third case, the two sides are equal for $\vartheta' = \vartheta$ and for the transitions with weight zero. For the transitions from $\mathrm t^-$ to $\mathrm t^+$ and from $\mathrm s^-$ to $\mathrm s^+$, the inequality follows from \eqref{e:tail-kappabounds}, which completes the proof of \eqref{e:memdom-step}. \emph{Summation.} Fix $w' \in \mathcal T_{\mathrm{pre}}$ and a phase $\vartheta$. We consider the map that sends a trail $w \in \mathcal T^{\mathfrak t, \mathsf e_0}_n$ with $w_{20} = w'$, together with phases $\vartheta_{21}, \dots, \vartheta_n$ such that $\vartheta_n \in \{\mathrm t^+, \mathrm s^+\}$, to the sequence of states $(\vartheta_j, \omega_j, v_j)$, $20 \le j \le n$, where $\vartheta_{20} = \vartheta$. This map is injective, since the states determine $v_{20}, \dots, v_n$ and the phases. Every sequence in its image starts at $(\vartheta, \omega(w'), v'_{20})$ and ends at a state with reward $1$. Therefore \eqref{e:memdom-step} implies that \begin{equation}\label{e:memdom-sum} \begin{aligned} &\sum_{\substack{w \in \mathcal T^{\mathfrak t, \mathsf e_0}_n \\ w_{20} = w'}} \ \sum_{\vartheta_{21}, \dots, \vartheta_{n - 1}} \ \sum_{\vartheta_n \in \{\mathrm t^+, \mathrm s^+\}} \ \prod_{j = 21}^{n} \varpi_j(\vartheta_{j - 1}, \vartheta_j) \\ &\qquad \le \sum_{(\vartheta'_j, \omega'_j, x_j)_{21 \le j \le n}} \ \prod_{j = 21}^{n} \mathsf T(\vartheta'_{j - 1}, \omega'_{j - 1}, x_{j - 1}; \vartheta'_j, \omega'_j, x_j) \, \mathsf g(\vartheta'_n, \omega'_n, x_n) \\ &\qquad = (\mathsf T^{n - 20} \mathsf g)(\vartheta, \omega(w'), v'_{20}) , \end{aligned} \end{equation} where the sum in the second line runs over all sequences of states, and $(\vartheta'_{20}, \omega'_{20}, x_{20}) = (\vartheta, \omega(w'), v'_{20})$. The equality in the third line follows from \eqref{e:tail-TF} by induction on $n - 20$. Summing \eqref{e:memdom-split} over the trails $w$ with $w_{20} = w'$, inserting \eqref{e:memdom-sum}, and summing over $w'$, we obtain \eqref{e:memdom}. \end{proof} \begin{lemma}\label{l:super} Let $\mathsf F$ be a nonnegative function on the states such that $\mathsf g + \mathsf T \mathsf F \le \mathsf F$. Then for all $K \ge 0$, \begin{equation}\label{e:super} \sum_{k = 0}^K \mathsf T^k \mathsf g \le \mathsf F . \end{equation} \end{lemma} \begin{proof} We argue by induction on $K$. For $K = 0$, \eqref{e:super} reads $\mathsf g \le \mathsf F$, which holds since $\mathsf T \mathsf F \ge 0$. Suppose that \eqref{e:super} holds for some $K \ge 0$. Since the entries of $\mathsf T$ are nonnegative, we obtain \begin{equation*} \sum_{k = 0}^{K + 1} \mathsf T^k \mathsf g = \mathsf g + \mathsf T \sum_{k = 0}^{K} \mathsf T^k \mathsf g \le \mathsf g + \mathsf T \mathsf F \le \mathsf F , \end{equation*} which completes the induction. \end{proof} \zcref[S]{l:super} is the standard comparison principle for supersolutions of a linear equation with a nonnegative matrix. The next lemma constructs a function as in \zcref{l:super} from its values at the sites of a box and from a function of the phase and the history. Recall that $\mathcal C_R = \{x \in \Z^2 : |x|_\infty \le R\}$. \begin{lemma}\label{l:box} Let $R \ge 1$. Let $\mathsf Z$ be a positive function of $(\vartheta, \omega)$ such that \begin{equation}\label{e:tail-slack} \mathsf D = \mathsf Z - \mathsf T^\circ \mathsf Z \end{equation} is positive. Let $\mathsf U$ be a nonnegative function on the states, and let $\epsilon_{\mathrm{out}} \ge 0$. Suppose that $\mathsf U(\vartheta, \omega, x) = 0$ if $x \notin \mathcal C_R$ or $x = c$, that $\mathsf U(\vartheta, \omega, v) = \mathsf g(\vartheta, \omega, v)$, and that for all phases $\vartheta$ and all $\omega \in \Omega_{10}$, \begin{equation}\label{e:boxcheck} \begin{aligned} (\mathsf T \mathsf U)(\vartheta, \omega, x) &\le \mathsf U(\vartheta, \omega, x) && \text{for } x \in \mathcal C_R \setminus \{c, v\}, \\ (\mathsf T \mathsf U)(\vartheta, \omega, x) &\le \epsilon_{\mathrm{out}} \mathsf D(\vartheta, \omega) && \text{for } x \notin \mathcal C_R . \end{aligned} \end{equation} Then the function $\mathsf F = \mathsf U + \epsilon_{\mathrm{out}} \mathsf Z$, where $\mathsf Z$ is regarded as a function of the states that does not depend on the site, satisfies $\mathsf g + \mathsf T \mathsf F \le \mathsf F$. \end{lemma} \begin{proof} We begin by comparing $\mathsf T$ with $\mathsf T^\circ$. We claim that for all states $(\vartheta, \omega, x)$, all admissible steps $\mathsf e$ from $\omega$, and all phases $\vartheta'$, \begin{equation}\label{e:box-entries} \mathsf T(\vartheta, \omega, x; \vartheta', \omega \mathsf e, x + \mathsf e) \le \mathsf T^\circ(\vartheta, \omega; \vartheta', \omega \mathsf e) . \end{equation} The entries of rule (a) vanish. Rule (b) gives the entry $1/5$ only for $\vartheta' = \vartheta$, and $1/5 \le \varpi_\vartheta(\mathrm k)$ for all kinds $\mathrm k$ by \eqref{e:phaseweights}. Rule (c) differs from the definition of $\mathsf T^\circ$ through the replacement of $\kappa^\circ$ by $\kappa^{\mathrm c} \le \kappa^\circ$. This proves \eqref{e:box-entries}, which implies that \begin{equation}\label{e:box-TZ} (\mathsf T \mathsf Z)(\vartheta, \omega, x) \le (\mathsf T^\circ \mathsf Z)(\vartheta, \omega) = \mathsf Z(\vartheta, \omega) - \mathsf D(\vartheta, \omega) \end{equation} for all states. Note also that $c, v \in \mathcal C_R$, since $R \ge 1$, and that $\mathsf g$ vanishes at the states with $x \neq v$. We now verify $\mathsf g + \mathsf T \mathsf F \le \mathsf F$ at a state $(\vartheta, \omega, x)$. Suppose first that $x \in \mathcal C_R \setminus \{c, v\}$. Then $\mathsf g(\vartheta, \omega, x) = 0$. Using \eqref{e:boxcheck} and \eqref{e:box-TZ}, we obtain \begin{equation*} (\mathsf T \mathsf F)(\vartheta, \omega, x) \le \mathsf U(\vartheta, \omega, x) + \epsilon_{\mathrm{out}} \bigl( \mathsf Z(\vartheta, \omega) - \mathsf D(\vartheta, \omega) \bigr) \le \mathsf F(\vartheta, \omega, x) . \end{equation*} Next, suppose that $x \notin \mathcal C_R$. Then $\mathsf g(\vartheta, \omega, x) = 0$ and $\mathsf U(\vartheta, \omega, x) = 0$, and we have \begin{equation*} (\mathsf T \mathsf F)(\vartheta, \omega, x) \le \epsilon_{\mathrm{out}} \mathsf D(\vartheta, \omega) + \epsilon_{\mathrm{out}} \bigl( \mathsf Z(\vartheta, \omega) - \mathsf D(\vartheta, \omega) \bigr) = \mathsf F(\vartheta, \omega, x) . \end{equation*} Finally, suppose that $x \in \{c, v\}$. Then $(\mathsf T \mathsf F)(\vartheta, \omega, x) = 0$ by rule (a). Since $\mathsf U = \mathsf g$ at $v$ and $\mathsf g = 0$ at $c$, we have \begin{equation*} \mathsf g(\vartheta, \omega, x) \le \mathsf U(\vartheta, \omega, x) \le \mathsf F(\vartheta, \omega, x) , \end{equation*} which completes the proof. \end{proof} The function $\mathsf T \mathsf U$ vanishes at the sites outside $\mathcal C_R$ that are not adjacent to $\mathcal C_R$, since $\mathsf U$ vanishes outside $\mathcal C_R$. The second condition in \eqref{e:boxcheck} therefore concerns only the sites adjacent to $\mathcal C_R$, and \eqref{e:boxcheck} is a finite set of inequalities. \section{The certified bound}\label{s:tail-bound} We now state the bound, with the numerical values of the parameters. \begin{proposition}\label{p:tail} Let $(\cs, \ct) = (961/1000, 187/200)$, $\bar\alpha = 1/6$, $\bar\beta = 9/25$, and $h = (1, 5/4)$, and let $\varsigma_w$ be the enumerations of \zcref{d:enum}. Then the entries of \zcref{tab:tail} are upper bounds for the quantities in its first column. In particular, \begin{equation}\label{e:tail-result} K_\tcoll(1) \le 0.923198 \qquad \text{and} \qquad K_\tdiag(1) \le 0.899348 , \end{equation} and $K_{\mathfrak t}(1) \le 0.92320$ for $\mathfrak t \in \{\tcoll, \tdiag\}$. \end{proposition} \begin{table}[ht] \centering \begin{tabular}{lcc} \toprule & $\mathfrak t = \tcoll$ & $\mathfrak t = \tdiag$ \\ \midrule $\sum_{n \le 20} \mathsf m_{\mathfrak t}(n)$ & $0.582353$ & $0.823644$ \\ $\sum_{n > 20} \mathsf m(\mathcal T^{\mathfrak t, \sN}_n)$ & $0.111332$ & $0.078222$ \\ $\sum_{n > 20} \mathsf m(\mathcal T^{\mathfrak t, \sW}_n)$ & $0.118181$ & $0.114607$ \\ $\sum_{n > 20} \mathsf m(\mathcal T^{\mathfrak t, \sS}_n)$ & $0.111332$ & $0.107712$ \\ \midrule $\sum_{n \ge 1} \mathsf m_{\mathfrak t}(n) = h_{\mathfrak t} K_{\mathfrak t}(1)$ & $0.923198$ & $1.124185$ \\ $K_{\mathfrak t}(1)$ & $0.923198$ & $0.899348$ \\ \bottomrule \end{tabular} \caption{Certified upper bounds at $(\cs, \ct) = (961/1000, 187/200)$, $\bar\alpha = 1/6$, $\bar\beta = 9/25$, and $h = (1, 5/4)$, with the enumerations of \zcref{d:enum}. The entries of the first four rows are rounded up in the last digit, and the last two rows are computed from the rounded entries. For the collinear type, the rows for the first directions $\sN$ and $\sS$ are equal by symmetry.}\label{tab:tail} \end{table} \begin{proof} We treat the trails of length at most $20$ and the longer trails separately. \emph{Trails of length at most 20.} The program \texttt{anc/h3/tailmem5.py} enumerates the trails of $\mathcal T^{\mathfrak t}_n$ for $n \le 20$ by depth-first search. It sorts the first-visit steps by binary64 approximations to the quotients of \zcref{d:enum}, and uses upward rounding to evaluate \eqref{e:tail-mw} in the resulting order. For each trail, the exact value in this order is at least the minimum attained by the order of \zcref{d:enum}. Thus the evaluation yields a valid upper bound even if rounding changes the order. Summing the bounds with upward rounding gives the first row of \zcref{tab:tail}. \emph{Longer trails.} We treat the five cases $(\tcoll, \sN)$, $(\tcoll, \sW)$, $(\tdiag, \sN)$, $(\tdiag, \sW)$, and $(\tdiag, \sS)$ for $(\mathfrak t, \mathsf e_0)$. In each recorded run, the Bellman program constructed a positive function $\mathsf Z$ of $(\vartheta, \omega)$ such that $\mathsf D > 0$, a function $\mathsf U$ on the states with the vanishing and boundary properties of \zcref{l:box} for $R = 70$, and a constant $\epsilon_{\mathrm{out}}$. It then verified the inequalities \eqref{e:boxcheck} as described in \zcref{s:tail-trust}. By \zcref{l:box}, the function $\mathsf F = \mathsf U + \epsilon_{\mathrm{out}} \mathsf Z$ satisfies $\mathsf g + \mathsf T \mathsf F \le \mathsf F$. Let $K \ge 1$. Summing \eqref{e:memdom} over $20 < n \le 20 + K$ and using \zcref{l:super}, we find that \begin{equation}\label{e:tail-bound} \begin{aligned} \sum_{n = 21}^{20 + K} \mathsf m(\mathcal T^{\mathfrak t, \mathsf e_0}_n) &\le \sum_{w' \in \mathcal T_{\mathrm{pre}}} \sum_{\vartheta} \mathsf P_\vartheta(w') \sum_{k = 1}^{K} (\mathsf T^k \mathsf g)(\vartheta, \omega(w'), v'_{20}) \\ &\le \sum_{w' \in \mathcal T_{\mathrm{pre}}} \sum_{\vartheta} \mathsf P_\vartheta(w') \, \mathsf F(\vartheta, \omega(w'), v'_{20}) . \end{aligned} \end{equation} Letting $K \to \infty$, we obtain the same bound for the sum over all $n > 20$. The recorded runs evaluated the right side of \eqref{e:tail-bound} with upward rounding. Rounding each reported bound up to six decimal places gives the corresponding entry of \zcref{tab:tail}. In the five runs, we had $\epsilon_{\mathrm{out}} \le 4.6 \cdot 10^{-6}$, and the term with $\epsilon_{\mathrm{out}} \mathsf Z$ contributed less than $9.2 \cdot 10^{-4}$ to the right side of \eqref{e:tail-bound}. \emph{Symmetry.} For $\mathfrak t = \tcoll$, the reflection $(x_1, x_2) \mapsto (x_1, -x_2)$ fixes $c$, $u$, and $v$. It maps $\mathcal T^{\tcoll, \sN}_n$ bijectively onto $\mathcal T^{\tcoll, \sS}_n$. Further, it preserves the arrival site $c$ of $u$, the kinds of the steps, the types of the pairs, and the dead pairs. It therefore preserves the coefficient sums $\kappa(j)$ and the enumerations of \zcref{d:enum}. Thus $\mathsf m(\mathcal T^{\tcoll, \sN}_n) = \mathsf m(\mathcal T^{\tcoll, \sS}_n)$ for all $n$, and the fourth row of the first column equals the second. \emph{Conclusion.} By \eqref{e:tail-split}, the fifth row is the sum of the first four. By \eqref{e:tail-K1}, the last row is the fifth divided by $h_{\mathfrak t}$, which gives \eqref{e:tail-result}. The two bounds in \eqref{e:tail-result} are smaller than $0.92320$. This completes the proof. \end{proof} \section{What is computed, and what must be trusted}\label{s:tail-trust} \paragraph{Programs.} The program \texttt{anc/h3/bellman.py} treats one case $(\mathfrak t, \mathsf e_0)$. It generates the histories of $\Omega_{10}$ and their admissible steps from \zcref{d:history}. It computes an approximation of $\sum_{k \ge 0} (\mathsf T^\circ)^k \mathbf 1$, which serves as $\mathsf Z$, and a lower bound for the slack $\mathsf D = \mathsf Z - \mathsf T^\circ \mathsf Z$. In all five recorded runs the minimum of this lower bound was $0.999 \ldots$. It enumerates the trails of $\mathcal T_{\mathrm{pre}}$ by depth-first search (between $2.3 \cdot 10^8$ and $3.6 \cdot 10^8$ of them in the recorded runs, depending on the case) and accumulates the weights $\mathsf P_\vartheta(w')$ by phase, history, and endpoint. It then initializes $\mathsf U$ with $\mathsf Z$ rounded up to binary32 at the states with position in $\mathcal C_{70} \setminus \{c, v\}$, with zero at $c$, and with $\mathsf g$ at $v$. It proposes smaller values by sweeping the states with position in $\mathcal C_{70} \setminus \{c, v\}$, taking the minimum of the currently stored value and the rounded value of $\mathsf T \mathsf U$ at each state. The current program uses atomic accesses to the shared entries of $\mathsf U$ during the parallel sweeps. The proof uses the final verification pass in one thread, which recomputes every row of the first inequality of \eqref{e:boxcheck} from the stored $\mathsf U$. For each state at a site just outside the box and adjacent to it, the program divides an upper bound for $\mathsf T \mathsf U$ by a positive lower bound for $\mathsf D$. It takes $\epsilon_{\mathrm{out}}$ to be the maximum of these upward-rounded quotients, which ensures the second inequality of \eqref{e:boxcheck}. Finally, it bounds the right side of \eqref{e:tail-bound} with upward rounding. The recorded runs took about ten minutes on four cores and used $1.3$ gigabytes of memory per case. The command lines are listed in \texttt{anc/h3/jobs.yaml}, and the historical outputs used for \zcref{tab:tail} are stored in \texttt{anc/h3/*.log}. In these files, the collinear type is labeled $\mathrm B$ and the diagonal type $\mathrm C$, the first directions $\sN$, $\sW$, $\sS$ are labeled $1$, $2$, $3$, and the phases $\mathrm t^-$, $\mathrm s^-$, $\mathrm t^+$, $\mathrm s^+$ are labeled $\mathrm A$, $\mathrm B$, $\mathrm C$, $\mathrm D$. A verification run must report zero violated rows and end with \texttt{PASS}. The program does not store $\mathsf U$ for each history. It merges the histories into $3{,}744$ classes, such that the histories of a class have the same last entry and the same admissible steps with the same kinds, and such that the successors by the same step of two histories of a class lie in the same class. By \zcref{d:statwalk}, the entries of $\mathsf T$ and $\mathsf T^\circ$ depend on the history only through these data. Hence a function of the class that satisfies the inequalities of \zcref{l:box} on classes satisfies them on histories. The program checks the defining property of the classes for every history. \paragraph{Arithmetic.} Upward rounding gives upper bounds for the sums and products of nonnegative numbers used for the prefix weights, the operator rows, and the final bound \cite{IEEE754,Tucker11}. To bound $\mathsf D$ from below, the Bellman program subtracts the upward-rounded value of $\mathsf T^\circ \mathsf Z$ from $\mathsf Z$ with downward rounding. In the two proof programs, \texttt{tailmem5.py} and \texttt{bellman.py}, the decimal inputs for $\cs$ and $\ct$ are moved down to the adjacent binary64 numbers after conversion, and those for $\bar\alpha$ and $\bar\beta$ are moved up. The coefficient inputs are $0.16666666666666667$ and $0.36$, so that the binary64 numbers used are at least $1/6$ and $9/25$. The type weights $1$ and $5/4$ are exact binary64 numbers. The optional comparison program \texttt{exact75.py} applies a relative margin to the converted thresholds and coefficients. The function $\mathsf U$ is stored in binary32. In the final pass, each row $\mathsf T \mathsf U$ is evaluated in binary64 with upward rounding and compared with the stored value of $\mathsf U$, so that an accepted row holds for the exact coefficients. The C library calls that set the rounding direction are checked for success. See \zcref{s:ancillary-H3} for the compiler settings and the assumptions about directed rounding. \paragraph{Checks.} We also made the following empirical comparisons. \begin{enumerate} \item We independently enumerated the short trails in \texttt{exact75.py}, starting from \eqref{e:mT}. For every length $n \le 20$ with a nonzero sum, the sums from \texttt{exact75.py} and \texttt{tailmem5.py} differ by at most $9 \cdot 10^{-13}$ in relative terms. \item For $n = 22$, the right side of \eqref{e:memdom}, evaluated by \texttt{anc/h3/bellman.py}, agrees to a relative error of at most $3 \cdot 10^{-6}$ with the value computed by a separately written dynamic program in \texttt{anc/h3/tailmem5.py}. This second walk runs on a periodic quotient of $\Z^2$ and discards steps from $u$ or $a_0$ when the history already records a visit to that site. \item The same quotient walk gives values for $22 \le n \le 108$ in the recorded runs. Over these lengths the quotient can count paths that reach a periodic translate of $v$. The sums of the recorded values in the five cases lie between $94.8\%$ and $95.1\%$ of the corresponding entries of \zcref{tab:tail}. The Bellman bound in \eqref{e:tail-bound} applies to the walk on $\Z^2$. \end{enumerate} \paragraph{What must be trusted.} Granting the lemmas of this appendix, the bounds rely on \texttt{anc/h3/tailmem5.py} enumerating every short trail and bounding its weight, on \texttt{anc/h3/bellman.py} implementing the prefix weights \eqref{e:tail-prefixweight} and the entries of $\mathsf T$ and $\mathsf T^\circ$ of \zcref{d:statwalk}, and on the compiler and floating-point environment implementing binary64 and binary32 arithmetic with the directed rounding specified in \cite{IEEE754}. The comparisons above provide empirical checks of the implementations.