The actual history list and error quantifiers

This appendix accompanies the main text, From actual search histories to current-group localization and far-band transfer to side arguments. Notation, the fixed version of H, and hypotheses are the same as in the main text. We express its list construction as finite rules that can be enumerated term by term and identify the tests that can be named before catalog insertion begins.

A. The data in a history name

H, p. 47 · H, p. 48 · H, p. 49 · The four history classes in the main text

On a fixed cell, a history name consists of the following finite data: the basic pattern, slot, base name, target mask context and pad, target rank, and ordered list of inner-history factors. A main base name can only be the fixed $B_e$ or $U_e$ in that slot of the selected pattern. A helper base name denotes a complete side state fixed at a later stage.

A factor is specified by four pieces of data: mask context, rank, individual pad, and the choice of a positive projection or its complement. There are two kinds of mask contexts: a cumulative split point $m$, or a historical-ball group $G$ together with the insertion index. A history word is an operator product acting from right to left. Equivalently, one may list its successive left multiplications from earliest to latest. The two conventions must not be mixed.

Only currently available columns enter a projection. Columns that may be inserted later are not in its current range. A name specifies how that projection is recomputed each time the catalog grows. Along the sequence of column insertions, the same name determines an increasing family of positive projections. Their complements are not increasing, but can be treated through the positive projection family. This is the monotonicity required by Lemma 6.7.

The target residual is not counted in the inner-history length. For ball targets, the inner histories in all four slots are the original cumulative search words. For transfer targets, the inner history is the remaining positive word exposed by the actual deletion order. A helper target has as its inner history the product of helper averages previously transferred to slot $a$.

B. Search rules and invariants

H, p. 49 · H, p. 50 · Return to binary search

Represent a node by

Here $v=\varnothing$ means that there is no lower retained slot. Initialize at $(1,L,u_0,\varnothing;1,1,1,1)$, choosing $u_0$ in advance from the basic $B$ slots. At each nonleaf node, choose the least nonretained slot $t$ and the midpoint $m=\lfloor(\ell+h)/2\rfloor$.

The two children are

All words not displayed remain unchanged. Thus the following invariants hold at each node.

1. The upper retained slot is either the unchanged initial basic $B$, in which case $h=L$, or has as its outermost factor the positive cumulative filter at split point $h$.
2. When $\ell>1$, the outermost factor in the lower retained slot is the complementary cumulative filter at split point $\ell-1$. When $\ell=1$, there is no lower retained slot.
3. The two retained slots are distinct. Every new left multiplication acts on a nonretained slot, so an outer factor in a slot still being retained remains unchanged.
4. Each split point occurs only once along a path. The rank names of all inserted positive factors are distinct, although their numerical values need not be monotone in insertion order.
5. The total number of cumulative factors in the four slots equals the path length and is at most $\lceil\log_2 L\rceil$.

These invariants follow by direct induction from the update formulas. At a leaf $\ell=h=j$, they imply the ranks $L-j+1,L-j+2$ and the pad-difference formula in the main text. Any other predetermined rule for choosing a nonretained slot gives the same invariants. We use the least-numbered slot here to make the choice completely specified.

C. The complete main-catalog list

H, p. 48 · H, p. 49 · H, p. 50 · H, p. 51

For every entry below, also enumerate all pads of its inner factors and its target. A target pad $t$ satisfies $1\le t\le P$. Identity endpoints are not new targets requiring detection.

C1. Old-source residuals

H, p. 48 · H, p. 49 · H, p. 50 · The first-ball identity

For each leaf $j>1$, write the lower retained argument as

Record the target $(v,L-j+2,U_{j-1,h(j-1)+t})$ with inner history $W_v^{\mathrm{in}}z_v$. Changes to the other slots during localization do not create new target bases: equation (13) of H already holds for two arbitrary $L^2$ observer arguments.

In the pure-source proof of the first-ball identity, old sources may occur on either side of the identity, but the same entry is used. In particular, a ball output on the right is only an observer argument. One cannot instead expand a higher-rank ball source to trigger the lower-rank test in the lower retained slot.

C2. Ball insertion

H, p. 47 · H, p. 49 · H, p. 50 · Four-ball localization

For every leaf and every actual group context $G$, fix the first ball's nonretained slot and then a fixed order of the other slots, denoted by $e_1,e_2,e_3,e_4$. For $j=1,2,3,4$, record

The first ball is triggered by pure sources from the upper retained slot, and the other three balls by pure sources from the first ball. All source labels are allowed original vertices. Their ranks are at most $L$ and $L+1$, respectively, and strictly below their corresponding target ranks.

C3. Successive removal of main filters

H, p. 50 · H, p. 51 · Filter deletion order

For each leaf and every role assignment in which $c,d$ both have basic inputs of type $B$, generate all expansions of complementary factors in these two slots. Each such factor contributes either the identity or minus the positive average, so every branch has a definite total sign. Retained positive factors keep their order, and the slot's existing ball average remains outermost.

In each positive-word branch, compare only the two current outermost ranks and remove the larger one. If the outgoing filter is in slot $c$ and is denoted by $Q_c$, write $V_c$ for the word after removal. For each individual projection $Q_{c,t}$ of that filter, record

Continue by comparing the two remaining outer factors. Both words are empty at the end. Before enumerating individual pad choices, the number of deletion positions in each positive-word branch is at most the number of factors before deletion.

Why does this include both endpoints of a high band? If the high-band index satisfies $q\le P$, its targets are $Q_{c,q-1}$ and $Q_{c,q}$. In the second far-band direction $q>p+2$, we have $q\ge4$, so both indices lie in $1,\ldots,P$. If $q=P+1$, only $Q_{c,P}$ is required. Thus the enumeration includes every test actually used and does not require a nonexistent catalog at pad $P+1$.

The main list can be generated before helper insertion: the inner words in C3 depend only on the main search and deletion order. A later helper band is an arbitrary observer allowed by the test and need not be included in the main history.

D. The helper list after fixing the side bases

H, p. 48 · H, p. 49 · H, p. 51 · H, p. 52 · The first far-band direction · Conditions on fixed complete side bases

Write the actual outgoing order of a positive-word branch as

Copy each outgoing filter's masks and pads unchanged to slot $a$, and replace all ranks by $R_*=L+5$. Denote the resulting positive averages by $\widehat Q^{(j)}$. Before transfer $j$, the side history is

The index $j$ denotes transfer order, not a new helper rank. Every helper projection has the same rank.

For outgoing mask $j$ and all $1\le t\le P$, record the helper residual target with inner history $D_a^{(j-1)}S_a$. Expand every average in this history into individual pad words. The first far-band direction $p>q+2$ requires pads $p-1,p$ or terminal pad $P$, all of which are listed.

Although all helper factors have the same rank, they generally arise from different masks and need not commute. Catalog termination requires only that the positive projection with a given name increase along the insertion sequence; different names need not give nested projections. A target residual may act on a history of the same rank without violating the requirement that its triggering pure source have lower rank. The actual triggering source always comes from the main slot $c$ and has rank at most $L+4<R_*$.

The vector of the complete side base $S_a$ is fixed before this stage, and its new private helper coordinates are zero. If the base could be reselected during helper insertion, the catalog increments could no longer be assigned to a fixed base, and the hypothesis of Lemma 6.7 would fail. The main and helper lists allow several fixed complete side bases, but not the introduction of infinitely many frequency components as new bases during the construction.

E. What the counting is used for

H, p. 48 · H, p. 49 · Restoring the averages

For a fixed leaf, the four slots have at most $m_*$ cumulative factors in total. Hence all complementary expansions in $c,d$ produce at most $2^{m_*}$ branches, and there are at most $m_*+2$ deletion positions. Each history factor and target has $P$ individual pad choices. Endpoints introduce at most an additional fixed factor of two. There are at most $4!$ role assignments and exactly four ball-insertion positions.

The a priori number of original context names is supplied by successful coloring and the historical-mask construction, independently of numerical graph distances. If it is bounded by $D^{C_{\mathrm{ctx}}}$, equation (10) in the main text is a generous upper bound for the product of all these choices. It does not assert that every listed name is nonzero on some cell, or combine groups from different spatial branches of the full tree into a count along one path.

When the list is used in Lemma 6.7, the number of individual pad histories enters the bound for the total number of insertions. After the catalog has been constructed, the analytic estimate uses averages of total weight one and does not multiply by the number of pad combinations in the list. These two counts have different purposes and must be kept distinct.

Every actual main-list entry consists of projections or complementary projections of main ranks acting on a fixed basic input. Every helper entry consists of positive helper projections acting on a fixed complete side base. The two arbitrary observer arguments require no enumeration; they are already included in the supremum defining the test norm.

F. Quantifiers for the four error types

H, p. 49 · H, p. 50 · H, p. 51 · H, p. 52 · The total far-band error

Fix a finite tree, a pattern, and a set of a priori bounds. The constants below are independent of tree depth, actual individual pads, particular triggering sources, and linear modulation.

1. Old-source and same-group ball residuals: for each target and individual history, apply equation (13) of H and cancel the $D\sqrt{n_{r-1}}$ coefficient sum of one lower-rank outer support. Only $\tau_3$ times the local norms of the fixed base and observers remains.
2. Mismatches between different groups: expand both the upper-source and first-ball supports. A fixed power of the a priori main-catalog bound is allowed. Distance greater than one between pure sources supplies $\tau_2$ by Lemma 6.1. This term does not depend on the old-source residual precision.
3. First far-band direction: the source is a main band and the target a helper residual. The main-band coefficient bound is at most $D\sqrt{n_{R_*-1}}$ and is canceled by the helper target's denominator. The observers are the other main history and the second side state.
4. Second far-band direction: the near source comes from the lower-rank main outer factor in the other slot, and the target is the outgoing main residual. The complete helper band is an observer. For far sources, expand the main source and helper support and apply $\tau_2$. Only this far-source part uses the helper coefficient bound.

For a given $C_3$, let $A_{\mathrm{tr}}(k)$ bound the number of transfer positions and positive-word branches. It is a fixed polynomial in $k$. We can therefore choose a fixed $C_\tau$ such that

Once the a priori $D_{\mathrm{tot}}$ is fixed, also require

Both inequalities can hold simultaneously with the localization requirements

Since the logarithms of all quantities have a priori bounds of order $k^{O(1)}$, we still have $\log(1/\tau_2)\le k^{O(1)}$, as required by Lemma 6.1.

Obtaining the a priori $D_{\mathrm{tot}}$ uses the input that the number of complete side bases is bounded by $\exp(k^{O(1)})$, not a particular frequency decomposition of those bases. The main-catalog error need not be multiplied by the number of future linearized modes. If a later estimate really requires exponentially many additional side bases, their a priori number and the parameter order must be checked again. They cannot simply be assumed to fall within this finite list.

G. Small-parameter boundary cases

H, p. 39 · H, p. 47 · H, p. 49 · H, p. 50 · H, p. 51 · The band identity and both endpoints

When $L=1$, there is no search split. The initial basic upper source has color one, and there is no lower retained slot. The four ball insertions and subsequent transfers still make sense. No actual split need use cumulative rank one; this does not affect a catalog bound for ranks at most a given value.

When $P=1$, a positive average is a single projection, but there are still two bands: $Q_1$ and $1-Q_1$. Equation (15) of H must still be summed through $P+1=2$. There are no far bands with $|p-q|>2$, and every nonzero difference term is retained as a near-band term.

An empty target mask has zero positive projection. If there is no current group for the first ball, the group sum is empty, and the old-source argument shows that the leaf contributes only a numerical error. If the low helper mask in a transfer is empty, its positive band is zero; no nonexistent neighbor needs to be found.

When two original vertices have the same curvature tag, their graph distance is zero, but their private column labels remain distinct. Cumulative and historical masks determine membership by tag conditions, whereas uniqueness of pure-source coefficients depends on the separate private coordinates. These two meanings of equality must not be confused.

H. Later theorems not supplied by this appendix

H, p. 48 · H, p. 50 · H, p. 51 · H, p. 52 · Scope of the main conclusion

We do not construct the complete side states of Sections 7–8 of H, prove their linear square-sum bounds, or prove a $P^{-1/2}$ gain from the near-band sums. We establish only that, given these fixed bases and their a priori number, every test actually used in this chapter belongs to the previously prescribed finite list, and far-band removal does not require the main catalog to change after helper insertion.