Graphs and labels

Edges have length one and may be traversed in either direction. Whenever a positive orientation is specified, reverse traversal carries the formal inverse label. A labeled graph is folded if, at each vertex, a prescribed oriented label occurs on at most one outgoing edge. A path is nonbacktracking when it never immediately reverses an edge; a closed path is cyclically nonbacktracking if this also holds across its chosen basepoint. Closed walks and their repeated traversals are allowed as presentation relators.

For a labeled group presentation we retain the formal Cayley edges: a positive generator and its initial vertex specify an edge even if different formal generators have the same group value. All degree and forest assertions are about this graph. This convention also specifies an unambiguous left action on oriented edges. Intrinsic distances and balls in an embedded copy are measured using its own graph edges.

All vertex Hilbert spaces use counting measure. A biregular incidence from a \(B\)-side of degree \(D'\) to an \(A\)-side of degree \(d\) is normalized by \((dD')^{-1/2}\). It maps the normalized constant vector on one side to the normalized constant vector on the other. When using probabilities to prove a bound for that operator, we pass explicitly to uniform probability on each side.

The growing parameter

Let \(\ell\) be a positive integer, eventually sufficiently large, and set \[ \begin{aligned} d&=2^{4\ell},& D&=d^2,& s&=10\ell,& r&=7\ell,\\ n_0&=1000,& H_i&=(2n_0+1)s+1+|i| \quad(i\in\mathbb Z). \end{aligned} \tag{8}\] Write \(H_0=(2n_0+1)s+1\), and put \[ L_i=\frac{100H_i}{\log_2d},\qquad g_i=\frac{H_i}{100\log_2d}. \tag{9}\] Inequalities comparing integer walk lengths with these real numbers have their usual literal meaning; a lower required length can equivalently be rounded upward. We may use the fixed bound \[ H_0\le h_*\log_2d,\qquad h_*=5003, \tag{10}\] valid for every \(\ell\ge1\).

Edges in the base tower change the layer by at most one. Consequently, for any fixed \(C<\infty\), \[ |j-i|\le \frac{CH_i}{\log_2d} \quad\Longrightarrow\quad \left|\frac{H_j}{H_i}-1\right| \le\frac{C}{\log_2d}. \tag{11}\] The convergence to one is uniform in \(i\). Constants such as \(C\) may be very large, but are fixed before \(\ell\) grows.

Unless stated otherwise, a term \(o(1)\) tends to zero as \(\ell\to\infty\), uniformly over all allowed layers, blocks, and choices already declared arbitrary. Fixed constants may depend on fixed accuracies and earlier parameters. They may not depend on \(\ell\) or a layer index. Later sections record the order of the remaining choices: geometric constants first, then nilpotence and mask scales, then operator accuracies and finite test constants, and finally a sufficiently large finite \(\ell\). We do not choose different values of \(\ell\) for different layers.

The order of choices

Table 1 records which choices are fixed before which others. It is a guide to the estimates proved below: each indicated section supplies the corresponding inequality. All choices use one final value of \(\ell\), uniformly over the infinitely many layers.

Stream lengths and slots

For \(h\geq0\), write \(h=2sq+t\), where \(q\geq0\) and \(0\leq t<2s\), and set \[ \begin{split} l_A(h)&=r+n_0s+qs+\max(t-s,0),\\ l_B(h)&=n_0s+qs+\min(t,s). \end{split} \tag{12}\] We also write \(l_A(i)=l_A(|i|)\) and \(l_B(i)=l_B(|i|)\). Thus \(l_A(h)+l_B(h)=r+2n_0s+h\). Increasing \(h\) by one increases exactly one of the two lengths by one: first the \(B\)-length for \(s\) consecutive steps, and then the \(A\)-length for \(s\) steps. Let \[\begin{split} A_i&=\mathbb F _2^{l_A(i)}\times \mathbb F _2^{r+1+l_B(i)},\\ B_i&=\mathbb F _2^{l_B(i)}\times \mathbb F _2^{s-r+1+l_A(i)}. \end{split}\] The two coordinates of either vertex are denoted \((u,v)\). Since \(2r-s=\log_2d\), their exact cardinalities are \[ |A_i|=d\,2^{H_i},\qquad |B_i|=2^{H_i}. \tag{13}\] All four active stream lengths at layer \(i\) are at most \(H_i\). For example, \(l_A(i)\leq r+n_0s+|i|<H_i\), and the other three bounds follow from the displayed definitions.

Partition every \(A\)-stream into a first block of length \(r\), called block \(0\), followed by blocks of length \(s\), called \(1,2,\ldots\). Every \(B\)-stream has blocks of length \(s\), also called \(1,2,\ldots\). Order the \(u\)-blocks from the two sides as \[ A,0;\ B,1;\ A,1;\ B,2;\ A,2;\ \ldots. \tag{14}\] For every \(|i-k|\leq1\), the active bits of \(u_A\) at \(A_i\) and \(u_B\) at \(B_k\) form an initial segment of this order, including possibly a proper initial part of its last block. Indeed this is true for equal absolute indices by (12); adjacent absolute indices differ by adding a single bit of the next available block, and choosing one of the two side lengths from each of these adjacent indices preserves the same property. Consequently the final cutoff has exactly one of the two descriptions \[ \begin{array}{ll} l_A(i)=r+ns,\quad l_B(k)=ns+t,&1\leq t\leq s,\\ l_B(k)=(n+1)s,\quad l_A(i)=r+ns+t,&1\leq t\leq s. \end{array} \tag{15}\] These descriptions include cutoffs at block ends by taking \(t=s\). The initial value of \(n_0\) ensures that the four blocks immediately before every such final block are full blocks of length \(s\).

For a pair \((i,k)\) with \(|i-k|\leq1\), put \[ \begin{aligned} \alpha&=1+l_B(i)-l_B(k),&p&=r+\alpha,\\ \beta&=1+l_A(k)-l_A(i),&p'&=s-r+\beta. \end{aligned} \tag{16}\] Here \(\alpha,\beta\in\{0,1,2\}\), and \(p>p'>0\) for large \(\ell\). There are \(d\) slots at each \(A_i\)-vertex for this pair, indexed by \(a=(k-i,j)\), \(1\leq j\leq d\). At a \(B_k\)-vertex the slots are \(c=(i-k,j,b)\), where \(b\in\mathbb F _2^{p-p'}\). Thus the desired degree on that side is \[ D_{ik}=d\,2^{p-p'}=D\,2^{|i|-|k|}, \qquad D/2\leq D_{ik}\leq2D. \tag{17}\] The identity follows from \(p-p'=2r-s+|i|-|k|\). In particular, \(d|A_i|=D_{ik}|B_k|\). After all three adjacent pairs are included, the degrees are \(3d\) on \(A_i\) and at most \(6D\) on \(B_i\).

Set \(K=32s\). The family of a pair is the tuple \[(k-i,\operatorname{sgn}(i),\operatorname{sgn}(k), |i|\bmod K,|k|\bmod K),\] where zero has its own sign. There are at most \(27K^2\) families. The quantities \(\alpha,\beta,p,p'\), the slot conventions, and the phase of the final block are determined by this tuple. For a family that occurs more than once, both indices have the same nonzero sign. Its consecutive occurrences increase both absolute indices by \(K\), and hence both side lengths by \(K/2=16s\). Their final blocks are therefore separated by \(32\) positions in (14). Families involving zero occur only once.

The linear slot evaluations

On each side and for each slot define a linear map \(\mathcal K\) on padded streams and its evaluation \[ Q=v+\mathcal K u. \tag{18}\] On a diagonal block of length \(h\in\{r,s\}\), \(\mathcal K\) is multiplication by a coefficient of \(\mathbb F _{2^h}\), after choosing a linear identification with \(\mathbb F _2^h\). Only \(A\)-block \(0\) uses \(h=r\). From each block it may also send a linear image into the first \(\alpha\) bits of the following block on side \(A\), or into the first \(\beta\) bits of the following block on side \(B\). There are no other off-diagonal terms. These images will be called spills. The same diagonal coefficient and spill matrix are used at every repeated block of length \(s\) for a given family and slot. The spill from \(A\)-block \(0\) may, and will, be zero.

Once the preceding input block is known, remove its spills from two slot evaluations on the current block; their difference then cancels the \(v\)-coordinate. If the diagonal coefficients differ, their difference is invertible and recovers the current \(u\)-block, followed by the \(v\)-block. This is the local operation behind recovery from a nonbacktracking path word.

We enforce this distinctness with finite global coefficient pools. On side \(A\), a slot name is \((\delta,j)\), with \(\delta\in\{-1,0,1\}\) and \(1\leq j\leq d\), so there are \(3d\) names. On side \(B\), include in the slot name the offset, serial number, bucket width and bucket value. The width belongs to \(\{\log_2d-1,\log_2d,\log_2d+1\}\), so there are at most \((21/2)D\) names. Choose separate injections of the two pools into \(\mathbb F _{2^s}\), and an injection of the \(A\)-pool into \(\mathbb F _{2^r}\). They exist because \(3d<2^r\) and \((21/2)D<2^s\) for large \(\ell\). Use the resulting coefficients independently of height and family. In particular, any two different incident slots at a vertex have different diagonal coefficients, for every applicable block size. Spills can additionally depend on the family. Finite fields introduce no group elements: they are used only for these maps of bit coordinates. Their existence follows, for example, by taking the roots of \(z^{2^h}-z\) in a splitting field over \(\mathbb F _2\); the roots form a field and, since the derivative is \(-1\), there are exactly \(2^h\) of them.

Expansion requires a second property: a uniform bound on the fraction of slots inducing the same input functional from a nonzero output functional, including on partial blocks. The following choice of injections and spills supplies the needed multiplicity bounds.

The output of \(\mathcal K\) fits in the active \(v\)-length at every pair. In fact those lengths equal \[ |v_A|=p+l_B(k),\qquad |v_B|=p'+l_A(i). \tag{19}\] In the first case of (15), the \(A\)-output ends by \(r+ns+\alpha\) and the \(B\)-output by \((n+1)s+\beta\). In the second case they end by \(r+(n+1)s+\alpha\) and \((n+1)s+\beta\), respectively. These are bounded by (19), including the cases \(\alpha=0\), \(\beta=0\), and \(t=s\).

One padded permutation rule for each family

A positive edge label is a triple consisting of a family, a serial number \(j\), and a vector \(x\in\mathbb F _2^p\). Write \(x=b\Vert x'\), where \(b\) has length \(p-p'\) and \(x'\) has length \(p'\). The reverse orientation has the formal inverse label. A family and \(x\) hence determine both slots, once their serial number is given.

We next define triangular transformations \(\mathcal F\) of \(B\)-blocks and \(\mathcal J\) of \(A\)-blocks. Their parameters include the family, \(j\), and \(x\). At each block the rule may also depend on all input \(u\)-blocks, on both sides, strictly earlier in (14). This is the complete list of keys. No transformation depends on input bits in its own block or a later block through its keys.

For each actual pair in the family, mark its last active block and its active prefix length \(t\). At this marked block choose, for each possible tuple of preceding keys, a permutation of \(\mathbb F _2^t\); apply it to the first \(t\) bits and leave the other bits of the block unchanged. In the universal rule, apply this permutation only when the four immediately preceding full \(s\)-blocks of input are not jointly zero. If they are jointly zero, use the identity. At unmarked blocks also use the identity. At a \(B\)-block the transformation contributes to \(\mathcal F\), and at an \(A\)-block to \(\mathcal J\).

The marked positions of one family are at least \(32\) blocks apart, so there is at most one rule at any position. Any finite prefix uses only finitely many tables. On inputs padded at the actual cutoff, every higher marked rule is inactive: the first higher one has four previous blocks past the cutoff, and its gate is closed; the same is then true at every later marked block. All these preceding inputs are zero. Thus the rule preserves the active input lengths. It is triangular and invertible, since its gate and permutation key are known before its current block is inverted. These statements also hold when one side’s entire stream is fixed and the other is solved successively.

The equations defining the endpoints of an edge are \[ Q_A=x\Vert\mathcal F(u_B),\qquad Q_B=x'\Vert\mathcal J(u_A). \tag{20}\] They are equations of padded streams. To solve them from a vertex \(A_i\) and its slot \(a\), compute \(Q_A\), read its first \(p\) bits as \(x\), and obtain \(c\) from its bucket. Invert \(\mathcal F\) successively to recover \(u_B\); the known \(u_A\) supplies its other keys. Then form \(Q_B\) by the second equation and set \(v_B=Q_B+\mathcal K_cu_B\). Conversely, from \(B_k,c\), the first \(p'\) bits of \(Q_B\) give \(x'\), and the bucket in \(c\) gives \(x\). Successively invert \(\mathcal J\), then compute \(v_A\) from the first equation. The support bounds above ensure that the resulting streams have the required lengths. In inversion beyond the cutoff, the unmarked blocks copy zeros until the next marked block; its preceding four blocks are zero, so its gate is closed, and induction continues. The two constructions are inverse: they solve the same triangular equations with the same keys.

Let \(Y^\#\) be the union of the blocks so defined. Every slot has exactly one incident edge, giving the degrees (17). Multiedges are allowed and are regarded as distinct slot incidences. The labeling is folded: at an \(A\)-vertex two distinct slots differ in offset or serial number; at a \(B\)-vertex they differ in these data or in bucket. In every case the labels differ. All outgoing labels at \(A\) are positive, and all outgoing labels at \(B\) are formal inverses, so no further coincidences are possible. With \(m_\ell\) denoting the positive alphabet size, we have \[ m_\ell\leq 27K^2 d\,2^{r+2} =O\bigl(d\,2^r(1+s)^2\bigr),\qquad \log_2(2m_\ell)=11\ell+O(\log\ell). \tag{21}\]

For the auxiliary graph \(Y^0\), in each actual pair use the same rule except that its own last-block permutation is applied unconditionally. All rules at lower marked positions retain their gates. Higher rules are inactive on its padded inputs. The slot inversion argument still applies, so the auxiliary block has the same degrees and label set, and is folded as well.

The coefficient maps are now fixed, but the permutation tables remain to be chosen. The next section proves that the current matchings can be chosen to give a uniform incidence gap, whatever lower-cutoff tables have already been fixed. That result will allow a successive choice in each family: later tables cannot alter an earlier auxiliary block, since their gates are inactive on its padded streams.

A conditional variance calculation.

The following elementary estimate specifies, in particular, the mean that is subtracted. Its last assertion is needed when the active input block ends partway through a full block.

Prefixes and causal dependence.

Let \(P_h^A\), \(h\geq0\), be conditional expectation onto the first \(r+sh\) bits of each of \(u_A,v_A\). Let \(P_j^B\), \(j\geq0\), be conditional expectation onto the first \(sj\) bits of each of \(u_B,v_B\). Only active bits are retained; the others are deterministic zeros. Thus these are finite increasing filtrations, eventually equal to the identity, and \(P_0^B\) is the projection onto constants. Denote the constant projection on either side by \(C_A,C_B\).

For a fixed \(A\)-slot and \(j\geq1\), the data needed to evaluate a function in \(\operatorname{ran}P_j^B\) are \[ u_A\big|_{[0,r+s(j-1))},\qquad Q_A\big|_{[0,p+sj)}. \tag{24}\] Indeed the first \(p\) evaluation bits supply \(x\), including its bucket, and inversion of \(\mathcal F\) supplies the first \(j\) blocks of \(u_B\). At the \(j\)th \(B\)-block the keys use only preceding interleaved blocks, ending with the \((j-1)\)st \(A\)-block. To determine \(v_B\) through length \(sj\), the equation for \(Q_B\) uses \(\mathcal J(u_A)\) through length at most \[sj-p'=r+s(j-1)-\beta\leq r+s(j-1).\] The diagonal and forward-spill rule for \(\mathcal K_B\) uses no \(u_B\) beyond its first \(j\) blocks to produce these \(v_B\) bits. This proves (24), including when a prefix extends into zero padding.

In the reverse direction, for an input in \(\operatorname{ran}P_h^A\) and a fixed \(B\)-slot, the needed data are \[ u_B\big|_{[0,sh)},\qquad Q_B\big|_{[0,p'+r+sh)}. \tag{25}\] Here \(x'\) is read first and the bucket is already part of the slot; inverting \(\mathcal J\) supplies \(u_A\) through \(r+sh\). Its keys end with the \(h\)th \(B\)-block. Computing \(v_A\) through \(r+sh\) then uses \(\mathcal F(u_B)\) through at most \(sh-\alpha\leq sh\) bits and the already recovered \(u_A\) blocks. These observations prove the reverse assertion also for \(h=0\).

To read a few bits of a diagonal evaluation block one may need its whole input block. Consequently (24) and (25) imply, for any fixed tables and also after taking their mean, \[ \operatorname{ran}(MP_j^B)\subseteq\operatorname{ran}P_{j+1}^A, \qquad \operatorname{ran}(M^*P_h^A)\subseteq\operatorname{ran}P_{h+2}^B. \tag{26}\] For example \(p+sj=r+sj+\alpha\) lies at most \(\alpha\leq2\) bits into the next \(A\)-block; \(p'+r+sh=(h+1)s+\beta\) is handled by the next \(B\)-block. This explains both shifts in (26), including \(\alpha=0\) or \(\beta=0\), when the stated bounds can simply be non-sharp.

We now apply Lemma 7 to these data. For (24), condition on \(P_{j-1}^A\) and put \(R=r+s(j-1)\). All still needed data from the \(A\)-state occur through its evaluation on \([R,R+s+\alpha)\). If its \(j\)th input block and this entire \(v_A\) interval are active, write that evaluation as \[Z_a=V+M_aU+o_a.\] Here \(U\) is the full \(j\)th \(A\) input block and \(V\) consists of the \(s+\alpha\) new \(v_A\) bits. The offset contains the known spill from the preceding block and any diagonal contribution from the next input block to the last \(\alpha\) output bits. Such next-block input bits are the auxiliary variable \(W\) of Lemma 7. They enter nowhere else: (24) uses direct \(u_A\) only before \(R\). Therefore the slot summand is a function \(f_a(C,Z_a)\) with no separate \(W\)-dependence. The \(A\) coefficient map does not depend on the bucket extracted from \(x\); that bucket may affect \(f_a\), but does not change \(M_a\). It follows that \[ \|(1-P_{j-1}^A)MP_j^B\|^2\leq10^{-3} \quad\text{whenever these full intervals are active.} \tag{27}\]

For completeness, the right-hand side of (23) is bounded by the squared norm of the original input function, rather than a larger slot-dependent norm. A uniform output vertex with an independent uniform incident slot gives a uniform input vertex, since every input has the same number of slots. Thus the average over slots and vertices of a deterministic neighbor value squared is exactly the input norm squared. When a summand averages random table choices, Jensen’s inequality bounds its square by the corresponding average of those squares. These are precisely the individual norms in (23), since \(V\) makes each \(Z_a\) uniform conditional on all other data.

The identical argument in (25), conditioning on \(P_h^B\), uses the \(B\) input block on \([sh,s(h+1))\) and its extended evaluation interval \([sh,s(h+1)+\beta)\). It gives \[ \|(1-P_h^B)M^*P_h^A\|^2\leq10^{-3} \quad\text{when that input block and extended $v_B$ interval are full.} \tag{28}\] The explanation of the conditioned mean is the same in both directions: the means of the slot functions under their uniform evaluation argument depend only on the retained prefix, so no uncontrolled contribution comes from the frozen next-block inputs.

Realizing the mean expansion by independent matchings.

We next choose the current tables so that the actual block has a uniform edge-isoperimetric constant. A tail estimate for each cut alone would introduce the number of vertices when summed over all subsets, and hence would not give the height-uniform bound needed here. Instead, we will use connected cuts and the local dependence of the matching variables to select the tables by the local lemma.

Give \(A\sqcup B\) the degree measure \(\mu(a)=d\), \(\mu(b)=D'\); write \(v(Z)=\sum_{z\in Z}\mu(z)\) and \(\mu(A\sqcup B)=2E\). The mean random walk on this Hilbert space is \[R=\begin{pmatrix}0&M\\M^*&0\end{pmatrix}.\] The constant-on-each-side subspace has eigenvalues \(1,-1\); its orthogonal complement is the sum of the two sidewise centered spaces. Lemma 8 bounds \(R\) above by \(0.8\) on that complement. On the orthogonal complement of the global constant, the remaining sidewise-constant vector has eigenvalue \(-1\), so the same upper bound \(0.8\) holds there. Hence, for \(0<v(Z)\leq E\), the expected number \(b(Z)\) of crossing edges obeys \[\begin{align*} \mathbb E b(Z) &=\langle(1-R)\mathbf1_Z,\mathbf1_Z\rangle_{\mu}\tag{34}\\ &\geq0.2\left(v(Z)-\frac{v(Z)^2}{2E}\right) \geq0.1v(Z). \tag{35}\end{align*}\]

Let \(\mathcal G\) be the finite simple graph of possible endpoints of edges in this block. Each cluster has at most \(2^s\) vertices on each side. A vertex has at most \(\max\{d,D'\}\) incident slots, so \[\Delta(\mathcal G)\leq\Delta:=2D\,2^s, \qquad Q:=1+\Delta.\] For every nonempty connected vertex set \(Z\) of \(\mathcal G\) with \(v(Z)\leq E\), introduce the bad event of Lemma 9. It is enough to avoid these events. Indeed every other set splits into its connected components in \(\mathcal G\); actual edges never join different components, so the crossing counts and volumes add, and each component still has volume at most \(E\).

Every matching variable is supported on one pair of clusters, with every edge between their two sides possible. Its support has \(\mathcal G\)-diameter at most two. An event for \(Z\) depends only on variables whose supports meet \(Z\). Thus two events at distance greater than two use disjoint sets of independent variables. Moreover an event is independent jointly of any collection of such distant events, since all their variables together are disjoint from its own. We may therefore join two events in a dependency graph whenever their vertex sets have distance at most two.

There are at most \(zQ^2\) vertices within distance two of a \(z\)-set. The number of connected \(m\)-sets containing a specified vertex is at most \(Q^{2(m-1)}\): fix orders of the vertices and their neighbors, choose for each such set its first spanning tree under that order, and traverse this rooted tree in depth-first order. The traversal is a walk of length \(2(m-1)\) visiting exactly that set, and the orders make the association a well-defined injection into such walks. It follows that a bad event for a \(z\)-set has at most \[ zQ^{2m}\quad\text{dependent events indexed by $m$-sets}. \tag{36}\] Counting events outside the volume bound or the event itself only enlarges this upper bound.

Set \(a=d/800\) and assign weights \(x_Z=e^{-a|Z|}\). For all sufficiently large \(\ell\), uniformly in \(i,k\), \[ a\geq2,\qquad \rho:=Q^2e^{-a}\leq\frac12. \tag{37}\] Indeed \(\log Q=O(\ell)\), whereas \(d=2^{4\ell}\); neither bound contains the stream lengths. Equations (36) and (37) give the explicit uniform sum \[ \sum_{Z'\sim Z}x_{Z'} \leq |Z|\sum_{m\geq1}Q^{2m}e^{-am} =|Z|\frac{\rho}{1-\rho}\leq|Z|. \tag{38}\] Since every weight is at most \(1/2\), the elementary inequality \(\log(1-x)\geq-2x\) yields \[x_Z\prod_{Z'\sim Z}(1-x_{Z'}) \geq e^{-a|Z|-2|Z|}\geq e^{-2a|Z|} \geq\mathbb P(\text{bad }Z).\] The last step uses \(v(Z)\geq d|Z|\) and Lemma 9; here \(D'\geq D/2\geq d\).

We include the finite asymmetric local-lemma argument for this inequality. The local lemma originates with Erdős and Lovász (Erdős and Lovász 1975); see (Moser and Tardos 2010, Theorem 1.1) for the asymmetric form and (Alon and Spencer 2016, sec. 5.1) for its conditional-probability proof. For any event \(A_Z\) and any list \(\mathcal S\) of other events, induct on \(|\mathcal S|\) to prove \[\mathbb P\left(A_Z\,\middle|\, \bigcap_{A\in\mathcal S}A^c\right)\leq x_Z,\] as well as positivity of the avoidance probabilities used. Split \(\mathcal S\) into neighbors \(\mathcal N\) of \(A_Z\) and nonneighbors \(\mathcal T\). Independence gives \(\mathbb P(A_Z\mid\bigcap_{\mathcal T}A^c)=\mathbb P(A_Z)\). By the induction hypothesis and the product rule, \[\mathbb P\left(\bigcap_{\mathcal N}A^c\,\middle|\, \bigcap_{\mathcal T}A^c\right) \geq\prod_{A_{Z'}\in\mathcal N}(1-x_{Z'}).\] If \(\mathcal N\) is nonempty, each conditional probability used on the left conditions on fewer than \(|\mathcal S|\) avoided events. Dividing by this lower bound proves the desired estimate using the local-lemma inequality above. If \(\mathcal N\) is empty, independence alone proves it. Beginning with the empty list and multiplying successive survival probabilities also proves their positivity. In particular the probability of avoiding the entire finite list is positive. We have obtained an actual block satisfying \[ b(Z)\geq\frac1{20}v(Z) \qquad(0<v(Z)\leq E). \tag{39}\]

There are finitely many families. In each family, fix successful current tables successively in increasing cutoff order. A current choice does not alter any smaller-cutoff block, whose padded inputs turn off the higher-cutoff gates. Proposition 10 is uniform over every earlier choice, so this succession defines all the countably many tables. For example, impose a finite ordering on each current collection of tables and choose its first successful element. The construction therefore yields all the required pre-pruning incidences with the same positive constant \(\chi\).

Gate deletions.

At each vertex and each adjacent-pair slot evaluate the gate at that pair’s own final block, whether or not the current auxiliary rule actually consults it. Delete the vertex if any of these gates is closed. The inputs before the last block are determined without using its current permutation, so this is a well-defined test on the slot state, identical for the gated and auxiliary prescriptions.

At a fixed \(A\)-slot, conditional on \(x\), the coordinates \(u_A\) and the tail of \(Q_A\) are independent uniform bits, by the parametrization in Lemma 6. The triangular equations turn them bijectively into the interleaved input \(u\)-values. Thus all preceding input coordinates are independent uniform bits. The same reasoning at a fixed \(B\)-slot uses \(x'\), its fixed bucket, \(u_B\), and the tail of \(Q_B\). In particular the four full \(s\)-blocks preceding the cutoff are jointly zero with probability exactly \(2^{-4s}\) at either slot. The union bound and the maximum degree \(6D\) show that these deletions have fraction at most \[ \varepsilon_{\rm gate}=6D\,2^{-4s}. \tag{41}\]

On vertices surviving these deletions the induced graphs from \(Y^0\) and \(Y^\#\) are identical. Indeed, from a surviving slot state its current final gate is open, so the two endpoint constructions agree. All lower rules already agree. This argument works from either side of an edge and proves equality of the induced edge sets, including multiplicities and labels.

Separation of heights.

The next deletion distinguishes larger-layer vertices from the zero padding of smaller-layer vertices with the same sign and residue. For a vertex on either side at layer \(i\), consider every layer \(i'\) with \[\operatorname{sgn}(i')=\operatorname{sgn}(i),\qquad |i'|\equiv|i|\pmod K,\qquad |i'|<|i|.\] Put \(m=(|i|-|i'|)/K\geq1\) and \[ q(i,i')=\min\{H_{i'},mK/2\}. \tag{42}\] Delete the vertex if all its own \(u\)-bits immediately after that side’s cutoff at \(i'\), for these \(q(i,i')\) positions, are zero. This interval consists of active bits at \(i\), because on either side the length increases by exactly \(mK/2\) between these two layers. Its zero probability under uniform vertex measure is \(2^{-q(i,i')}\). No layers of distinct signs are tested, and zero has no smaller layer with its sign.

The union bound gives, on every side and layer, \[ \begin{split} \varepsilon_{\rm sep} &\leq\sum_{m\geq1}2^{-mK/2}+\sum_{i'\in\mathbb Z}2^{-H_{i'}}\\ &=\frac{2^{-K/2}}{1-2^{-K/2}}+3\,2^{-H_0}. \end{split} \tag{43}\] Here \(2^{-\min(a,b)}\leq2^{-a}+2^{-b}\), and the second sum is evaluated using \(H_{i'}=H_0+|i'|\). Thus the estimate stays uniform even when the larger layer has arbitrarily many smaller layers of its residue.

Short-cycle deletions.

At layer \(i\), delete every vertex supporting a nonempty cyclically nonbacktracking closed path in \(Y^\#\) of length at most \(g_i\). By Corollary 12, the fraction deleted on either side is at most \(2^{-0.9H_i}\). This test is performed in the already specified graph \(Y^\#\), so it does not depend circularly on the final induced graph.

Let \(Y\) be the graph induced on the vertices surviving all three deletions. It is an induced subgraph both of \(Y^0\) and of \(Y^\#\). Combining the three budgets gives a uniform bound \[ \begin{split} \varepsilon_\ell &=6D\,2^{-4s} +\frac{2^{-K/2}}{1-2^{-K/2}} +3\,2^{-H_0}+2^{-0.9H_0}\longrightarrow0. \end{split} \tag{44}\] For example, \(D2^{-4s}=2^{-32\ell}\). Fractions here and below are always taken relative to the original sets \(A_i,B_i\), not relative to an already pruned set.

Graphs, presentations, and the conditional input

All graphs in this section are combinatorial graphs, possibly with loops or parallel edges. An unoriented edge has two formal orientations, interchanged by a fixed-point-free reversal operation. Traversing an edge and immediately traversing its reverse is a backtrack. A closed walk is cyclically nonbacktracking if it has no backtrack, including at its closing corner. Edge lengths are one, degrees count incidences, and a ball denotes the induced subgraph on the vertices at most its stated distance from its center. A forest has no nonempty finite circuit, with a loop and a pair of parallel edges counted as circuits of lengths one and two. Chains always have finite support. An orientation chosen once for each unoriented edge identifies the space of edge chains over a field \(k\) with the free vector space on those edges, with boundary \(\partial[x,y]=[y]-[x]\). The cycle space is \(Z_1(-;k)=\ker\partial\).

Let \(Y\) be the surviving tower. The properties of it needed in this section are the following: it is countable, has maximum degree at most \(6D\), and has an integer layer function whose change across an edge is at most one. Its oriented labeling is folded: the labels of the oriented edges leaving any vertex are distinct. Positive labels and their formal inverses are disjoint alphabets. Finally a nonbacktracking path starting in layer \(i\), of length at least \(L_i=100H_i/\log_2d\), is determined, including its location in \(Y\), by its oriented label word. This uniqueness compares paths anywhere in \(Y\). Refining these labels by arbitrary additional tags preserves both foldedness and this uniqueness property.

The following elementary estimate will be used with fixed constants, however large. If two vertices can be joined by a walk of length \(aH_i/\log_2d\), starting in layer \(i\), then \[ \left|\frac{H_j}{H_i}-1\right|\le\frac{a}{\log_2d} \tag{45}\] at every layer \(j\) encountered. This follows from \(|H_j-H_i|\le |j-i|\). Consequently all subsequent comparisons become uniform in \(i\) by increasing \(\ell\). Also \(L_i>2\) for all \(i\) with the parameters of the construction.

Let \(F\) be a countable torsion-free group. Give each positive edge \(e\) of \(Y\) a voltage \(z_e\in F\), and give its reverse voltage \(z_e^{-1}\). The ordinary voltage-cover construction of Gross and Gross–Tucker (Gross 1974; Gross and Tucker 1977) gives a graph \(P\) with vertices \((v,f)\) and an oriented lift \[(v,f)\longrightarrow(v',fz_e)\] over each oriented edge \(e:v\to v'\). The left deck action is \(\delta_a(v,f)=(v,af)\) for \(a\in F\). It acts freely on vertices and transitively on the lifts of every fixed base vertex or fixed base path; it can carry one connected component of \(P\) to another. Labels, layers, and the distinguished positive orientations are pulled back from \(Y\).

We assume that the augmented positive alphabet \(S\) is finite and that \[ \begin{gathered} \text{there is no nonempty cyclically nonbacktracking closed walk in $P$}\\ \text{based in layer $i$ of length at most } C_*H_i/\log_2d,\qquad i\in\mathbb Z. \end{gathered} \tag{46}\] Here \(C_*\) is a single absolute constant fixed below. This is a condition on the actual cover, not just on \(Y\) and not just on simple base circuits. It includes all lifts, although whether a base closed walk has trivial holonomy does not depend on the starting deck coordinate.

Define \[ \Gamma_{\mathrm{proj}}=\langle S\mid \text{label words of all closed walks in }P\rangle, \qquad X=\operatorname{Cay}_{\mathrm{right}}(\Gamma_{\mathrm{proj}},S). \tag{47}\] The Cayley graph is formal: its positive edges are the pairs \((h,\sigma)\), with endpoints \(h,h\sigma\), for \(h\in\Gamma_{\mathrm{proj}}\), \(\sigma\in S\). We do not identify distinct such edges even if their unordered endpoints coincide. Their reverse orientations have labels \(\sigma^{-1}\). Left translation preserves every formal edge label and its positive orientation.

For a connected component \(C\) of \(P\), a vertex \(v_0\in C\), and \(h\in\Gamma_{\mathrm{proj}}\), there is a unique label-preserving graph map \(\phi:C\to X\) with \(\phi(v_0)=h\): the image of the endpoint of a path from \(v_0\) is \(h\) times the label word of that path. Independence of the path follows from (47). The maps are not assumed injective at this stage.

Plane diagrams and reductions before injectivity

The same short-arc count will first rule out failures of injectivity and later bound intrinsic distances within embedded copies. We retain source paths in the diagrams: merging source walks requires actual deck alignment, not merely equality of label words.

We use the following form of the van Kampen Lemma; see (Lyndon and Schupp 1977, V, Section 1). If a word is freely equal to a product of \(J\) conjugates of defining relators and their inverses, it is the exterior contour word of a finite connected plane labeled multigraph with at most \(J\) bounded faces. Each bounded face contour reads a defining relator, with a chosen cyclic start and orientation. Conversely an exterior contour word of such a diagram is freely a product of conjugates of its bounded face words. In this statement a contour is a closed walk around a face, rather than an embedded circle: vertices and bridges may occur more than once. Every application below uses a finite number of relators even though the presentation is infinite.

For completeness, the elementary operations in this version are as follows. Draw a polygon for each relation factor and its conjugating stem, joining the stems at a base vertex in their product order. Empty factors are omitted. The exterior reads the literal product. Exterior insertion of \(aa^{-1}\) is made by attaching a spur. For a cancellation, let the two consecutive exterior traversals have vertices \(v,w,v'\). If they traverse the same edge, erase the resulting leaf. If they are distinct and \(v=v'\), their digon, or the two lobes when both edges are loops, bounds portions which can be discarded, together with these edges. The other exterior contour remains connected at \(v\). The consecutiveness at \(w\) ensures that no exterior attachment is lost away from that vertex. If \(v\ne v'\), draw an auxiliary edge in the exterior face between the indicated occurrences of \(v\) and \(v'\), so that it cuts off the two-edge portion as a triangular face. Contract the auxiliary edge. The artificial face is now a digon; delete one of its edges to merge it with the adjacent face. In that adjacent contour the replacement traversal has the same label. Thus the desired exterior cancellation has taken place without increasing the number of relation faces. This operation uses positions on contours and is valid when other vertices or contour portions repeat. Conversely, merging an exterior-adjacent bounded face across a non-bridge edge, repeatedly until a tree remains, proves the product assertion. These operations allow a prescribed literal exterior word to be constructed, after which its required break positions are marked. A marked position crossed by an intermediate cancellation need not retain its previous vertex value. All vertices of a diagram have consistent values in \(\Gamma_{\mathrm{proj}}\): propagate from one vertex along paths; simple circuits bound subdiagrams, so the product assertion proves path independence.

In our presentation every face comes with an actual closed walk in \(P\) reading its contour. This additional assignment matters: equal words alone will not be treated as equal paths. When two source incidences have been aligned by a deck transformation, deleting an edge between their faces splices two genuine source walks into a genuine closed source walk. This is again a permitted relator because the presentation uses all closed walks, including walks with backtracks and singular contours.

Suppose an injectivity failure exists. Choose, over all component maps, pairs of distinct source vertices with equal image, paths between them, and diagrams for the resulting closed image word, a choice minimizing first the number \(J\) of bounded faces and then the number of edges. The exterior has one adjustable side: it is this source path, with its break vertex marked. Its endpoints in \(P\) must remain distinct, but may vary when comparing different failure diagrams. Minimization over all failures, rather than just one originally selected path, is essential below.

We will use the same minimization after injectivity is proved, in a second setting. Adjoin to \(X\) one center \(c_Q\) for every indexed copy \(Q\), and one spoke of length one from \(c_Q\) to each vertex of \(Q\). Denote this graph by \(\widehat X\). For an edge loop in \(\widehat X\), started at a group vertex, each generator edge is a fixed side and each consecutive two-spoke passage through a center is an adjustable side. Inflate an adjustable side to any source path in its copy with the indicated endpoints. Mark all side breaks. If there are \(m\) sides there are at most \(m\) distinct marked vertices. Among diagrams and these adjustable paths minimize \((J,\text{number of edges})\) lexicographically. If the inflation is empty, retain its one marked vertex. For both minimizations, source data along adjustable sides and bounded contours are retained as part of the diagram.

Suppress every unmarked degree-two vertex. Call a resulting edge an arc; it remembers its entire original edge path and its length. Loops among these arcs are allowed. There is at least one marked vertex, so an entire degree-two component cannot disappear without a retained vertex. Every side incidence along an arc is constant: it is a bounded face or one exterior side. Indeed a change of exterior side is marked, and a change of face incidence requires branching. Degrees and contours in what follows are those of this compressed plane graph.

We henceforth use the post-injectivity minimum diagrams. One additional observation follows immediately from the indexing convention. If paths in two indexed copies have the same word and are deck-aligned, and their maps agree at one source point after alignment, their maps agree everywhere on the connected component: propagate along labeled paths. They are then the same indexed copy. Therefore an arc shared by two different copy assignments has length less than the applicable \(L_i\) on either assignment.

Short chain fillings and an explicit thin-triangle estimate

We next prepare an ordering of the copy centers by distance from one fixed group vertex, in order to control all earlier intersections with a copy at once. Thin triangles in \(\widehat X\) will give uniformly short paths that avoid the copy’s own center. The short-arc estimate will then turn such paths into intrinsic distance bounds in the copy. We first obtain thin triangles from a linear bound on decompositions of loop chains into short loops.

The next lemma is a quantitative form of the homological-isoperimetric criterion for hyperbolicity; compare Gersten (Gersten 1996, Theorem 6.3). The proof below gives an explicit thin-triangle bound under our chain-filling hypothesis, without assuming local finiteness.

Avoidance paths and simultaneous overlap

Cycle coordinates, the residual forest, and copy incidences

Because all earlier intersections with a copy lie in one tree, a nonzero cycle in the latest participating copy cannot be canceled by earlier copy cycles. The resulting cycle decomposition will control the unused edges and later supply the acyclic complex used to exclude torsion.

The next two estimates control different costs of removing overlaps. The first sums over one trimming ball, allowing repeated lifts of a base vertex. The second sums the losses from all copies at one fixed Cayley vertex, retaining the size of each trimming ball. If nonnegative numbers \(a_v\) are assigned to base vertices and \(a_Q(x)=a_{\operatorname{type}_Q(x)}\), put \[\mathcal S_a=\sum_{i\in\mathbb Z}\mathfrak w_i \sum_{v\text{ in layer }i}a_v.\] Then, whenever this sum is finite, \[\begin{align*} \sum_{x\in B(Q)}a_Q(x)&\le\mathcal S_a, \tag{55}\\ \sum_{Q:\,x\in V(Q)\setminus D_Q}|V(B(Q))|a_Q(x) &\le\mathcal S_a\qquad(x\in\Gamma_{\mathrm{proj}}). \tag{56}\end{align*}\] For the first inequality, a base vertex in layer \(i\) occurs among the lifts in \(B(Q)\) at most \(|V(B(Q))|\le\mathfrak w_i\) times. For the second, every incidence being summed has \(x\in B(Q)\), so its ball size is at most the weight of its type’s layer; the types occur at most once by Proposition 25. In particular the equivariant incidence Hilbert space is canonically \[\bigoplus_Q\ell^2(V(Q))\otimes\mathbb C^N \cong \ell^2(\Gamma_{\mathrm{proj}})\otimes\ell^2(V(Y))\otimes\mathbb C^N.\] For a deck-equivariant family of transported projections with base diagonal matrix sums \(a_v\), its direct sum has unnormalized identity diagonal sum \(\sum_v a_v\). This is a statement about all indexed copies; the well-order and assigned domains need not be equivariant.

Cone homology and exclusion of torsion

Let \(Z\) be the two-dimensional cellular complex obtained by attaching the graph cone on each indexed copy to \(X\). Its one-skeleton is \(\widehat X\). For each positive edge \(e:s(e)\to t(e)\) in \(Q\), attach one triangular cell \(\tau_{Q,e}\) with boundary \[ \partial\tau_{Q,e}=e+\sigma_{Q,s(e)}-\sigma_{Q,t(e)}, \tag{57}\] where \(\sigma_{Q,x}\) is the oriented spoke from \(c_Q\) to \(x\). Edges belonging to different indexed copies give distinct triangular cells, even when their base edge in \(X\) is the same. This is a cellular attachment, so repeated incidences would be allowed; the embeddings already proved in fact exclude loops in individual copies in this construction.

A uniform detector for short walks

Fix once and for all \(m\ge2\) with \[ m>L(201C_*). \tag{60}\] Indeed a walk based in layer \(i\) of length at most \(C_*H_i/\log_2d\) stays in layers \(j\) with \(H_j\ge H_i-C_*H_i/\log_2d\). For sufficiently large \(\ell\), the tower girth property therefore makes every circuit in its support longer than \(H_i/(201\log_2d)\). Lemma 30, with this \(g\) and \(C=201C_*\), applies. Lemma 29 can later be applied with any other fixed \(C\), without changing \(m\).

An integer affine group and its central product

The short-word test only requires a quotient onto \(U_{\mathbb Z}\), so we can add coordinates without losing that detector. The affine extension below is chosen for a second purpose: it admits a twisted representation in which Schwartz coefficient functions correspond to Schwartz integral kernels. A rank-one kernel then gives a continuous convolution projection, which we will sample on integer coordinates.

Let \(\mathfrak n\) be the strictly upper triangular real \(m\)-by-\(m\) matrices, let \(n_{\mathrm f}=m(m-1)/2\), and let \(U=1+\mathfrak n\). Write \(x_{ij}\) for the coordinates on \(\mathfrak n\) and \(\lambda_{ij}\) for their dual coordinates. For \(b\in U\), put \[A_b(x)=b(1+x)-1=(b-1)+bx,\qquad L_b(x)=bx.\] The maps \(A_b\) form an affine action: \(A_bA_{b'}=A_{bb'}\). Let \(E\) be the semidirect product of additive affine functions on \(\mathfrak n\) by \(U\), acting by \(f\mapsto f\circ A_{b^{-1}}\). Use coordinates \((\lambda,b,z)\), with affine function \(x\mapsto z+\lambda(x)\). Explicitly, \[\begin{align*} (\lambda,b,z)(\mu,b',w) &=\bigl(\lambda+\mu\circ L_{b^{-1}},bb', z+w+\mu(b^{-1}-1)\bigr),\tag{61}\\ (\lambda,b,z)^{-1} &=\bigl(-\lambda\circ L_b,b^{-1}, -z-\lambda(b-1)\bigr). \tag{62}\end{align*}\] Constants \((0,1,z)\) are central. Their quotient \(\bar E\) has coordinates \(\gamma=(\lambda,b)\) and section \(\sigma(\gamma)=(\lambda,b,0)\). For \(\eta=(\mu,b')\), put \[\gamma\eta=(\lambda+\mu\circ L_{b^{-1}},bb'),\qquad c(\gamma,\eta)=\mu(b^{-1}-1).\] Then \[ \sigma(\gamma)\sigma(\eta) =(0,1,c(\gamma,\eta))\sigma(\gamma\eta), \tag{63}\] and associativity gives \[c(\gamma,\eta)+c(\gamma\eta,\zeta) =c(\eta,\zeta)+c(\gamma,\eta\zeta).\] The cocycle is normalized at the identity, and \(c(\gamma,\gamma^{-1})=c(\gamma^{-1},\gamma)\).

Take copies \(X_{\mathrm f},Y_{\mathrm f}\) of \(E_{\mathbb Z}\); these are factor names, unrelated to the graphs. Define \[ F=(E_{\mathbb Z}\times E_{\mathbb Z})/ \{((0,1,k),(0,1,-k)):k\in\mathbb Z\}. \tag{64}\] Equivalently its coordinates are \((\gamma_X,\gamma_Y,z)\in\bar E_{\mathbb Z}^2\times\mathbb Z\), with law \[(\gamma_X,\gamma_Y,z)(\eta_X,\eta_Y,w) =(\gamma_X\eta_X,\gamma_Y\eta_Y, z+w+c(\gamma_X,\eta_X)+c(\gamma_Y,\eta_Y)).\] The coordinate map from the product sums its two central integers and has precisely the kernel in Equation 64. The opposite-pair subgroup is primitive in \(\mathbb Z^2\), so the surviving coordinate is an integer coordinate with no finite quotient. The inherited grading and first-nonzero-weight proof show directly that \(F\) is countable, nilpotent, and torsion-free. Projection to the upper unitriangular coordinate of either factor is a surjective group homomorphism to \(U_{\mathbb Z}\). Write \(z_0=(1,1,1)\) for the common central generator and \(\sigma_X,\sigma_Y\) for the two section maps into \(F\).

Central Fourier transform and equivariant trace

Use right translations \((\rho(g)\xi)(f)=\xi(fg)\). The inversion unitary \((\mathcal I\xi)(f)=\xi(f^{-1})\) satisfies \(\mathcal I\rho(g)\mathcal I=\lambda_F(g)\). After inversion, Fourier transform the central coordinate by \(\delta_j\mapsto(t\mapsto\mathrm e(tj))\), with probability Lebesgue measure on \(\mathbb T=\mathbb R/\mathbb Z\). This identifies \[ \ell^2(F)\cong L^2\bigl(\mathbb T; \ell^2(\bar E_{\mathbb Z})\otimes \ell^2(\bar E_{\mathbb Z})\bigr). \tag{65}\] The central generator acts by \(\mathrm e(t)\). In either factor, the section acts by \[ u_t(\gamma)\delta_\eta =\mathrm e(t c(\gamma,\eta))\delta_{\gamma\eta}. \tag{66}\] Thus \[u_t(\gamma)u_t(\eta)=\mathrm e(t c(\gamma,\eta))u_t(\gamma\eta), \quad u_t(\gamma)^*=\mathrm e(-t c(\gamma^{-1},\gamma))u_t(\gamma^{-1}).\] The two factor representations commute; the full quotient cocycle is their sum. There are commuting right operators \[ v_t(k)\delta_\eta=\mathrm e(t c(\eta,k))\delta_{\eta k}. \tag{67}\] The cocycle identity proves that these commute with \(u_t\). Under the Fourier transform of the central coordinate on the already inverted copy of \(\ell^2(F)\), these are the images of right multiplication by \(\sigma(k)\) on basis indices, namely \(\rho(\sigma(k)^{-1})\). They permute quotient basis vectors up to unit phases. Equivariance below means intertwining these right actions, with the identity action on auxiliary indices. Untwisted left or right regular equivariance obeys the same arguments.

A measurable uniformly bounded field on a separable Hilbert space defines a bounded operator on its circle \(L^2\) space with norm the essential supremum of the fiber norms. Integration proves the upper inequality; for the lower one, use a countable dense set of unit vectors restricted to measurable circle sets where their images exceed a given norm. Products and adjoints act pointwise. Uniform polynomial approximation gives pointwise continuous functional calculus for uniformly bounded self-adjoint fields. Thus a fixed separating continuous function or resolvent contour gives the same projection before and after decomposition.

A Schwartz convolution projection

Schwartz matrix coefficients and rank-one operators for Heisenberg representations are treated by Rieffel (Rieffel 1988, Lemma 2.3, Corollary 2.4, and Theorem 2.18). Here we derive the coefficient-to-kernel correspondence for the affine group above, whose quotient \(\bar E\) is generally nonabelian.

Equip \(\bar E\) with the Haar measure of Lemma 31. Schwartz functions refer to its Euclidean coordinates \((\lambda,b-1)\), or to the specified product coordinates. For \(\epsilon\in\{1,-1\}\), define \[\begin{align*} (J*_\epsilon K)(h) &=\int_{\bar E}J(a)K(a^{-1}h) \mathrm e\bigl(\epsilon c(a,a^{-1}h)\bigr)\,da,\\ J^{*_\epsilon}(h) &=\overline{J(h^{-1})} \mathrm e\bigl(-\epsilon c(h^{-1},h)\bigr). \end{align*}\] The cocycle identity gives associativity and the involution identities. The following kernel realization verifies the operations and gives the idempotents we need.

The lattice limit in both coefficient norms

Put \(L=\bar E_{\mathbb Z}\). For real \(\theta\), define \(C_r^*(L,\theta c)\) to be the norm closure on \(\ell^2(L)\) of the span of the operators in Equation 66 with \(t=\theta\). For \(a\in\ell^1(L)\), the series \(\sum_\gamma a_\gamma u_\theta(\gamma)\) converges in norm with norm at most \(\sum_\gamma|a_\gamma|\). Its coefficient \(\ell^2\) norm equals its norm on \(\delta_1\), because \(c(\gamma,1)=0\). The identity diagonal is its identity coefficient and is the trace of Lemma 32. In particular \(\operatorname{tr}_\theta(A^*A)=\|A\delta_1\|^2\).

The two coefficient norms have different roles in passing from the continuous idempotent to the lattice. The \(\ell^1\) defect controls the operator-norm correction by functional calculus. The \(\ell^2\) defect, compared with the sampled coefficient norm, prevents the resulting projection from being zero, while the squared \(\ell^2\) size bounds its identity trace. The next lemma supplies both controls.

A finite magnetic factor and its exact multiplicity

A single small twist makes the trace small near one endpoint of a character interval. We need it small near both endpoints, because the supporting layers will escape in opposite directions there. The finite representation below shifts the second effective twist from \(t\) to \(t-\delta\). The product projection then has trace bounded by a constant times \(N t^{n_{\mathrm f}}(\delta-t)^{n_{\mathrm f}}\). The prescribed scales will make this small even after the ordinary matrix multiplicity \(N\) and the geometric weights are included.

The global constant \(h_*=5003\) satisfies \(H_0\le h_*\log_2d\). After \(m,C_*,C_\bullet\) are fixed, choose \[ \begin{split} &E_0>10(C_*+C_\bullet+1),\\ &A_*\in\mathbb N,\qquad A_*/m>10E_0h_*,\\ &\kappa>0,\qquad \kappa/m>10(E_0+A_*+C_\bullet+1). \end{split} \tag{75}\] Set \[ q=d^{A_*},\qquad \delta=q^{-1},\qquad N=q^{n_{\mathrm f}},\qquad I=H_0. \tag{76}\] The numbers \(q,N,I\) are integers. We take \(\ell\) large enough that \(\delta<\theta_0\) in Proposition 35.

Let \(\mathfrak n_q=\mathfrak n_{\mathbb Z/q\mathbb Z}\), a set of \(q^{n_{\mathrm f}}=N\) elements. On \(\mathbb C^N=\ell^2(\mathfrak n_q)\) define a representation of the second copy \(E_{\mathbb Z}\) by \[ (R(\lambda,b,z)\psi)(x) =\mathrm e\bigl(-(z+\lambda(x))/q\bigr) \psi\bigl(b^{-1}(1+x)-1\bigr). \tag{77}\] Use any integer representative in the phase; the exponential is independent of the representative. All arguments on the right are reduced modulo \(q\). The affine map is a permutation and the phase has modulus one, so the operator is unitary. Substitution into Equation 61, exactly as for \(\pi_\epsilon\), proves that \(R\) is a group representation. Its central character is \[R(0,1,z)=\mathrm e(-\delta z)1_N.\] Write \(R_\gamma=R(\sigma(\gamma))\).

Reduction of the integer polynomial laws gives a surjective homomorphism \(L=\bar E_{\mathbb Z}\to\bar E_{\mathbb Z/q\mathbb Z}\). Its kernel is \[\Lambda_q=\{(\lambda,b)\in L: \lambda_{ij}\equiv(b-1)_{ij}\equiv0\pmod q\}.\] It has index \(q^{2n_{\mathrm f}}\) and coset representatives with every coordinate in \(\{0,\ldots,q-1\}\). Equation 77 gives exactly \[ R_y=1_N\qquad(y\in\Lambda_q). \tag{78}\]

The next lemma is a form of twisted absorption (Echterhoff and Williams 2012, Lemma 2.4). We track the quotient-identity block in its conjugacy to retain the exact unnormalized matrix-trace multiplicity.

In the full Fourier quotient space, amplified by \(\mathbb C^N\), the first factor \(u_t\) and the second \(V_t\) commute. They are equivariant for the original right quotient actions tensored with \(1_N\). For \(0<t<\delta\), both \(t\) and \(t-\delta\) fall in Proposition 35. Define \[ p(t)=p_t\otimes p_{t-\delta}[V_t]. \tag{79}\] The second-factor notation means coefficient evaluation and continuous functional calculus through Lemma 37. Set \(p(t)=0\) outside this interval. It is a measurable bounded field of equivariant projections. Its identity trace \(s_p(t)=\operatorname{Tr}_{\mathrm{id},N}(p(t))\) satisfies \[ \begin{split} 0<s_p(t) &=N\,\operatorname{tr}_t(p_t) \operatorname{tr}_{t-\delta}(p_{t-\delta})\\ &\le C N t^{n_{\mathrm f}}(\delta-t)^{n_{\mathrm f}} \qquad(0<t<\delta). \end{split} \tag{80}\] Factor the identity diagonals of the tensor factors and use the identity-block assertion of Lemma 37 for the equality. In subsequent coefficient formulas, an additional shared central power \(z_0^n\) acts by \(\mathrm e(nt)1_N\). The matrix \(R_\gamma\) is attached to a second-factor section term as in \(V_t\); these prescriptions fix all phases.

The layer window and its weighted trace

The dependency order for subsequent arguments is as follows. Geometry fixes \(C_*,C_\bullet\); Equation 60 then fixes \(m\), and Lemma 33 fixes two functions. Equation 75 fixes \(E_0,A_*,\kappa\). All accuracies, compact truncations, relative logarithmic mesh sizes, and finite norm-test exponents may now be chosen as fixed constants. Only then is \(\ell\) increased. In particular the trace estimate requires no accuracy varying with the layer, and the word detector does not depend on subsequent moment orders.

The upper space of the model

Use the notation and parameter choices of the preceding Sections. The vertex space before deletion, with its auxiliary indices, is \[\mathcal H^0= \ell^2\!\left(\coprod_{i\in\mathbb Z}(A_i\sqcup B_i)\right) \otimes\ell^2(F)\otimes\mathbb C^N.\] Let \(\Pi\) be the orthogonal projection retaining precisely the vertices of \(Y\). Let \(U^0_{ik}:\ell^2(B_k)\to\ell^2(A_i)\) be the normalized \(Y^0\) incidence from Proposition 13. It and its adjoint preserve normalized constants, and its norm between their orthogonal complements is at most \(1-\chi\). Decrease \(\chi\), if necessary, so that \(0<\chi\le1/4\). Write \(\beta_\ell\) for the supremum of the deleted fractions in the individual \(A_i,B_i\), so \(\beta_\ell\le\varepsilon_\ell\to0\) by Equation (44). Equation (79) and Lemma 38 provide the transverse projections \(p(t)\) and nonnegative layer weights \(h_i(t)\), with \[ \sum_i h_i(t)^2=1,\qquad J(t):=\{i:h_i(t)\ne0\}\text{ consists of at most two adjacent integers}. \tag{86}\] These assertions concern \(0<t<\delta\). The identity trace of \(p(t)\) is finite and strictly positive there by Equation (80). All identity traces include the ordinary, unnormalized sum over the \(N\) matrix indices.

In the central Fourier decomposition define a self-adjoint operator field \(O(t)\) by its blocks from \(B_k\) to \(A_i\): \[ O(t)_{A_iB_k}=U^0_{ik}\otimes h_i(t)h_k(t)p(t), \qquad |i-k|\le1. \tag{87}\] The blocks in the opposite direction are the adjoints; all remaining blocks vanish. The normalized incidence \(U^0_{ik}\) has norm one. Thus the block Schur estimate bounds \(O(t)\) uniformly, and it defines an operator on \(\mathcal H^0\). Here and below the formula is zero off \(0<t<\delta\). No continuity at the endpoints is needed for defining this bounded measurable field.

Let \(a_i=|A_i|^{-1/2}\mathbf1_{A_i}\) and \(b_i=|B_i|^{-1/2}\mathbf1_{B_i}\). Denote the transverse fiber Hilbert space, including its \(N\) matrix indices, by \(\mathcal H_t\), and put \[\mathcal H^0_t= \left(\bigoplus_i\ell^2(A_i)\oplus\bigoplus_i\ell^2(B_i)\right) \otimes\mathcal H_t.\]

The upper space just identified is supported on at most two adjacent layers, as shown in Figure 1. Its vertex factor is a normalized combination of the constant vectors, so its trace equals the fiber trace rather than that trace multiplied by the number of vertices. We must now approximate the compressed model by an actual voltage-cover operator with finitely many matrix weights, while ensuring the cover’s girth. Section 10 will use the model gap and deletion bound to preserve its upper band through this approximation.

Realizing the model on a voltage cover

We first reduce regular-norm estimates to finite tests. Finite empirical lists then restrict the possible matrix weights, while a block-specific distribution approximates the model mean and retains wide independent voltage coordinates. After fixing those lists, we draw once on each edge. The girth and centered-moment estimates apply to these same independent draws.

Finite tests for the full regular norm

Compact coefficient templates and masks

Fix a small accuracy \(\varepsilon>0\), to be chosen in terms of \(\eta\) at the end. In this Subsection all auxiliary errors can be made smaller than any prescribed fixed multiple of \(\varepsilon\). The constants they require are fixed before increasing \(\ell\).

By Lemma 36, choose smooth compactly supported functions \(J_\epsilon^\flat\) and a fixed relative logarithmic mesh size \(0<u\le1\) so that truncation and coefficient rounding have arbitrarily small prescribed \(\ell^1\) errors. These choices depend only on \(\varepsilon\) and the previously fixed data. The estimates apply uniformly on the active window because \(t,\delta-t\in(0,\delta)\) and \(\delta\to0\) as \(\ell\to\infty\); they give operator estimates for every unitary family used below. Throughout rounding, the translating operators, and consequently their multipliers, keep their actual parameter; only the coefficients are rounded.

Choose a sufficiently fine fixed log-grid spacing. A nonnegative smooth bump on the real line whose translates at that spacing cover the line, divided by the positive sum of those translates, gives a smooth partition of unity. Pull one such partition back under \(\log_2(t/\delta)\), and another under \(\log_2((\delta-t)/\delta)\). Denote them by \(\psi_\nu(t)\) and \(\theta_\omega(t)\), and denote their associated positive magnitude templates by \(a_\nu,b_\omega\). On the supports in question, \[|\log(a_\nu/t)|\le u,\qquad |\log(b_\omega/(\delta-t))|\le u.\] Both partitions sum to one on \(0<t<\delta\).

For a fixed block \((i,k)\), keep precisely the template pairs whose supports intersect the support of \(h_i h_k\), and call their set \(\mathcal T_{ik}\). Its cardinality is bounded by a constant \(K_\varepsilon\), uniformly in \(i,k,\ell\). Indeed \(h_i h_k\ne0\) implies \(|b(t)-i|<1\); each of \(\log_2(t/\delta)\) and \(\log_2((\delta-t)/\delta)\) varies by at most \(2\kappa\) there. Only boundedly many members of either fixed-spacing grid can meet these ranges. The specified positivity of \(h\) ensures that the nonzero incidence blocks have some such pairs.

For any twisted representation \(U'\) of \(\bar E_{\mathbb Z}\) define the finite sum \[\mathcal L_\epsilon(\alpha;U')= \sum_{\gamma\in\bar E_{\mathbb Z}} \alpha^{n_{\mathrm f}} J_\epsilon^\flat(\Delta_{\alpha^{1/m}}\gamma)U'(\gamma).\] By Proposition 35, Lemma 36, and the chosen truncation and rounding accuracies, the block field \[ \sum_{(\nu,\omega)\in\mathcal T_{ik}} f_{ik\nu\omega}(t)\, \mathcal L_+(a_\nu;u_t) \mathcal L_-(b_\omega;V_t), \qquad f_{ik\nu\omega}=h_i h_k\psi_\nu\theta_\omega, \tag{94}\] approximates \(h_i h_kp(t)\) to an arbitrarily small fixed error, uniformly on the window, for sufficiently large \(\ell\). The two factors act on their separate transverse indices. The error estimate uses the uniformly bounded coefficient \(\ell^1\) norms, positivity of the scalar partition, and its sum-one property. Extend each scalar mask by zero off the window.

The masks have a useful scale uniform in the layer. Put \[w_i=q^{-1}2^{-\kappa|i|}.\] On the support of \(h_i\), the identities \(t=\delta 2^{\kappa b(t)}/(1+2^{\kappa b(t)})\) and \(\delta-t=\delta/(1+2^{\kappa b(t)})\) show that the shorter distance to an endpoint is comparable to \(w_i\), with constants depending on \(\kappa\). They also show that the support has length at most \(Cw_i\). The chain rule for the two logarithmic charts gives, for every fixed integer \(j\ge0\), \[ \|f_{ik\nu\omega}^{(j)}\|_\infty\le C_jw_i^{-j}, \qquad \|f_{ik\nu\omega}^{(j)}\|_1\le C_jw_i^{1-j}. \tag{95}\] The compact support of the original bumps makes the zero extension smooth; each individual support is at positive distance from the endpoints. In particular, its Fourier coefficients satisfy \[ |\widehat f_{ik\nu\omega}(n)| \le C_jw_i(1+|n|w_i)^{-j},\qquad n\in\mathbb Z. \tag{96}\] For \(|n|w_i\le1\) this follows from the \(L^1\) bound. Otherwise integrate by parts \(j\) times, use (95), and combine the two bounds. Consequently \[\sum_n|\widehat f_{ik\nu\omega}(n)|\le C, \qquad \sum_{|n|>L/w_i}|\widehat f_{ik\nu\omega}(n)| \le C_j(1+L)^{1-j}.\] Choose a fixed sufficiently large \(L\), and truncate at \(K_i=\lceil L/w_i\rceil\). These are uniform approximations on the entire circle. In particular, the approximating trigonometric polynomials have small values outside the active supports; exact vanishing there is neither claimed nor used.

Finite matrix lists on the second factor

The scalar masks vary through infinitely many layers, but the final group must have a finite alphabet of matrix weights. Using a new matrix list at every layer would not meet that requirement. The range \(i<I\) uses only finitely many second-factor templates, and hence finitely many empirical lists; in the remaining range a congruence subgroup factorization replaces all the matrix factors by one common list. The next estimates justify this replacement in the full regular norm.

In blocks with \(i<I\), every second-factor template satisfies \[ \log_2 b_\omega^{-1} \le \log_2q+\kappa(I+1)+C. \tag{97}\] This follows from the formula for \(\delta-t\) on the support of \(h_i\), followed by the fixed log rounding. Thus there are only \(O(1+\log q)\) distinct such templates over all these blocks, and their coordinate supports are bounded by a fixed power of \(q\). Choose a coordinate rectangle containing each compact template support, with side radii fixed multiples of \(b_\omega^{-j/m}\) in weight \(j\). The rectangle has \(n_\omega\) lattice points. Uniform sampling of \(v'\) in it, with the term \[n_\omega b_\omega^{n_{\mathrm f}} J_-^\flat(\Delta_{b_\omega^{1/m}}v') R(\sigma(v'))\rho(\sigma_Y(v')),\] has expectation equal to the ordinary lifted template. The scalar multiplier is bounded uniformly, because \(n_\omega b_\omega^{n_{\mathrm f}}\le C\). Lemma 43 gives, for each such template, a fixed \(M\)-term list approximating that expectation in the full regular norm. Its entries retain their original scalar multipliers and matrices. Fix all these lists now.

For the remaining blocks a single common matrix list suffices. Let \(\Lambda=\Lambda_q\) be the subgroup of \(\bar E_{\mathbb Z}\) whose coordinates are all divisible by \(q\). Reduction modulo \(q\) is a surjective homomorphism by the integral polynomial group law; its kernel is \(\Lambda\), and \[ [\bar E_{\mathbb Z}:\Lambda]=q^{2n_{\mathrm f}}=:Q_q. \tag{98}\] Choose a set \(\mathcal V_q\) of representatives for the cosets \(\Lambda v\), with each coordinate in \(\{0,\ldots,q-1\}\). Every \(\gamma\) is uniquely \(yv\), with \(y\in\Lambda\), \(v\in\mathcal V_q\). Equation (78) gives \(R(\sigma(y))=1\) for \(y\in\Lambda\): its affine shift is the identity modulo \(q\), and its modulation exponent is an integer. The finite average \[ C_q=Q_q^{-1}\sum_{v\in\mathcal V_q} R(\sigma(v))\rho(\sigma_Y(v)) \tag{99}\] has an \(M\)-term empirical approximation in the full regular norm, again by Lemma 43. Fix one such list, common to all \(i\ge I\).

For those blocks replace an ordinary second-factor template by the product \[ \left( Q_q\sum_{y\in\Lambda} b_\omega^{n_{\mathrm f}} J_-^\flat(\Delta_{b_\omega^{1/m}}y)\rho(\sigma_Y(y)) \right)C_q. \tag{100}\] We next prove the needed comparison with the ordinary template, including its phase and normalization.

The scale estimates from the window and the choices of parameters give, uniformly for \(i\ge I\) and active templates, \[ b_\omega^{-1/m}/q\ge 2^{2E_0H_i} \tag{101}\] when \(\ell\) is sufficiently large. Here is the explicit calculation. Log rounding contributes a bounded constant, and \[\log_2(b_\omega^{-1/m}/q) \ge \frac\kappa m i-\left(A_*-\frac{A_*}{m}\right)\log_2d-C.\] Since \(i\ge I=H_0\ge\log_2d\) and \(H_i=H_0+i\le2i\), the hypothesis \(\kappa/m>10(E_0+A_*+C_\bullet+1)\) leaves more than the margin needed for (101). It follows that every side length of the dilated subgroup mesh tends to zero uniformly. Counting its cells shows that the coefficient \(\ell^1\) norm of the first parenthesis in (100) is bounded.

In the fiber with \(\tau=t-\delta\), the relevant projective operators satisfy \[V_t(y)V_t(v) =\exp(2\pi\mathrm i\tau c(y,v))V_t(yv).\] This is the multiplier identity, not a replacement of \(t\) by a template in the translating operators. It can also be checked by multiplying the actual section lifts and then using the center parameter \(-\delta\) of \(R\). As \(R(\sigma(y))=1\), the first parenthesis in (100) is precisely its prescribed factor in this product. The coefficient at \(yv\), before empirical replacement of \(C_q\), is therefore \[b_\omega^{n_{\mathrm f}} J_-^\flat(\Delta_{b_\omega^{1/m}}y) \exp(2\pi\mathrm i\tau c(y,v)).\] The factor \(Q_q\) in the subgroup sum has canceled the factor \(Q_q^{-1}\) in the representative average; no matrix trace normalization occurs here.

Set \(\beta=b_\omega^{1/m}\). On all the compact supports in this calculation the elements \(\Delta_\beta v\), with \(v\in\mathcal V_q\), tend to the identity uniformly, since their coordinates of weight \(j\) have absolute value at most \(q\beta^j\le q\beta\). The polynomial group law implies \(\Delta_\beta(yv)=(\Delta_\beta y)(\Delta_\beta v)\) and that this differs from \(\Delta_\beta y\) by a quantity tending to zero uniformly on those compacts. Homogeneity of the cocycle gives \[\tau c(y,v)=\frac\tau{b_\omega} c(\Delta_\beta y,\Delta_\beta v).\] On an active template \(|\tau|/b_\omega\) is bounded, while the last cocycle tends uniformly to zero. Smoothness of the compact coefficient function thus gives a uniformly vanishing difference between the preceding coefficient and \(b_\omega^{n_{\mathrm f}} J_-^\flat(\Delta_\beta(yv))\). All possibly nonzero differences lie in one fixed enlarged compact set in the scaled coordinates. The normalized number of ordinary lattice points there is bounded. Summing the coefficient differences therefore gives \(o(1)\), uniformly in the active blocks and parameters. This proves the comparison with the ordinary template in operator norm. Finally, replacing \(C_q\) by its empirical list costs at most its regular-norm error times the bounded coefficient \(\ell^1\) norm of the subgroup factor. The same bound holds almost everywhere in every central fiber.

All the coefficient sums used above have bounded absolute norms even at parameters where their templates are inactive. Thus multiplication by the masks and replacement of those masks by their Fourier truncations preserve the error estimates globally on the circle. More explicitly, on a mask support use its active comparison; off that support the untruncated mask is zero. The error made by substituting the truncated mask is bounded everywhere by its Fourier tail times the coefficient norm bounds. Sum over at most \(K_\varepsilon\) pairs. This controls the inactive leakage as well as the active approximation.

One draw per edge and the finite alphabet

We now specify a finite distribution of a single pair \((W,z)\) for each block \((i,k)\). This will be sampled independently on its undirected edges, using the positive orientation and taking the adjoint weight and inverse voltage for the reverse orientation. The choices in different parts of the prescription are independent conditional on the template pair.

First choose \((\nu,\omega)\) uniformly in \(\mathcal T_{ik}\), then choose an integer \(n\) uniformly in \(\{-K_i,\ldots,K_i\}\). Use the total central power \(n\) with scalar multiplier \[|\mathcal T_{ik}|(2K_i+1)\widehat f_{ik\nu\omega}(n).\] By (96) this multiplier is bounded uniformly. These additional central powers carry no matrix modulation.

Choose \(x\in\bar E_{\mathbb Z}\) uniformly in a full coordinate rectangle containing the support of \(J_+^\flat(\Delta_{a_\nu^{1/m}}x)\). In each coordinate of weight \(j\), its radius is a fixed positive constant times \(a_\nu^{-j/m}\), rounded up to an integer. Write \(n_\nu^+\) for its number of lattice points. Use \(\sigma_X(x)\), with scalar multiplier \[n_\nu^+ a_\nu^{n_{\mathrm f}} J_+^\flat(\Delta_{a_\nu^{1/m}}x).\] It is uniformly bounded by the rectangle cell-volume estimate.

If \(i<I\), choose one of the fixed \(M\) entries in the ordinary second-factor list for \(b_\omega\), uniformly, and use its section lift, its matrix \(R(\sigma(v'))\), and its scalar multiplier. Uniform averaging supplies the list’s normalization \(1/M\).

If \(i\ge I\), choose \(y\in\Lambda\) uniformly in the analogous full subgroup rectangle, and independently choose one entry \(v\) uniformly from the fixed representative list. Use \(\sigma_Y(y)\sigma_Y(v)\), the matrix \(R(\sigma(v))\), and scalar multiplier \[n_\omega^\Lambda Q_q b_\omega^{n_{\mathrm f}} J_-^\flat(\Delta_{b_\omega^{1/m}}y),\] where \(n_\omega^\Lambda\) is the subgroup rectangle’s number of points. Its normalized cell volume is \(Q_q b_\omega^{n_{\mathrm f}}\). By (101), each scaled side mesh is at most one, so this scalar multiplier is also bounded uniformly.

Let \(z\) be the product of the prescribed group elements, in the indicated order. Let \(c_e\) be the product of the scalar multipliers, and let \(R_v\) be the one indicated matrix. The raw weight is \(c_eR_v\), with \(|c_e|\le C_\varepsilon\). Fix a finite grid in the complex disk of radius \(C_\varepsilon+1\), and round \(c_e\) deterministically to a grid value \(c_e^\flat\) at distance at most a prescribed \(\varepsilon'\). Define \[W=c_e^\flat R_v.\] Since \(R_v\) is unitary, the rounding changes the expectation norm by at most \(\varepsilon'\). The voltage \(z\) is retained even when the weight is zero. In particular, the support of the voltage distribution is not conditioned on a nonzero weight.

All distributions in this prescription are finite. Linearity of expectation shows, term by term, that the raw expectation is the sum of the truncated Fourier masks times the appropriate first and second coefficient templates. Uniform sampling of a rectangle cancels exactly its point-count multiplier, and uniform sampling of a template pair and a frequency cancels their two count multipliers. The empirical lists give their specified averages. The preceding Subsections and the last rounding consequently show that we can arrange \[ \mathop{\mathrm{ess\,sup}}_t \bigl\|\mathbb E[W\rho(z)](t)-h_i(t)h_k(t)p(t)\bigr\| \le\varepsilon \tag{102}\] uniformly in \((i,k)\).

Only the empirical-list matrices enter the tags. Their total number is at most \(C_\varepsilon(1+\log q)M\), from the ordinary lists and the single representative list. The final scalar grid has fixed finite cardinality depending on \(\varepsilon\) alone. Thus the total number of weight tags has the same stated bound. The original tower alphabet has size \(O(d2^r(1+s)^2)\). As \(2^r=d^{7/4}\), their product is \[O_\varepsilon\bigl(d^{89/32}(1+\log d)^3\bigr)=o(d^3)=o(dD).\] In particular, neither the possibly very large group-coordinate rectangles nor the number of different first-factor templates enlarge the label alphabet. Voltages are separate data of the cover.

There is a fixed constant \(C\), independent of \(i,\ell\), such that every coordinate of every possible \(z\) in a block with first index \(i\), and of its inverse, is bounded by \[ 2^{CH_i}. \tag{103}\] Indeed the logarithms of the template radii and of \(K_i\) are \(O(\log q+\kappa|i|+1)=O(H_i)\). The representative coordinates are bounded by \(q\); the ordinary empirical terms lie in their specified rectangles. Fixed polynomial multiplication and inversion preserve a bound of the form (103).

The first factor supplies wide independent coordinates in a range overlapping that of (101). Namely, for every active first-factor template with \(i\le2I\), \[ a_\nu^{-1/m}\ge 2^{2E_0H_i} \tag{104}\] for sufficiently large \(\ell\). For \(0\le i\le2I\), the lower bound \(\log_2a_\nu^{-1}\ge\log_2q-C\), together with \(H_i\le3H_0\le3h_*\log_2d\) and \(A_*/m>10E_0h_*\), proves it. For \(i<0\), use instead \[\log_2a_\nu^{-1} \ge\log_2q+\kappa|i|-C\] and \(H_i=H_0+|i|\), with the same inequality for \(A_*\) and the stronger chosen inequality for \(\kappa\). Every upper unitriangular entry in this first rectangle is sampled independently on an integer interval containing at least \(2^{E_0H_i}\) points. For \(i\ge I\), every corresponding entry of the second-factor subgroup rectangle has at least that many possibilities in its step-\(q\) interval. Fixed rectangle radii and integer rounding are harmless because (104) and (101) have an exponential margin.

Girth with the same independent edge draws

We use the Schwartz–Zippel polynomial zero bound, whose short proof we include. The sharp total-degree bound is due to Schwartz (Schwartz 1980, Lemma 1, p. 702, and Corollary 1); Zippel’s sparse-interpolation work (Zippel 1979, sec. 3.1, Theorem 1) gives related coordinate-degree zero estimates, and DeMillo and Lipton (DeMillo and Lipton 1978) earlier used random evaluations for polynomial identity testing. The minimum-side bound below is an immediate consequence of Schwartz’s estimate for unequal coordinate sets. If a nonzero polynomial of total degree at most \(r\), over a field, is evaluated on independent uniform choices from finite sets of sizes at least \(L\), its probability of vanishing is at most \(r/L\). This follows by induction on the number of variables. Regard the polynomial as a polynomial of degree \(s\) in the last variable; its leading coefficient is a nonzero polynomial of degree at most \(r-s\). The probability that this coefficient vanishes is at most \((r-s)/L\); otherwise the one-variable root bound gives at most \(s/L\). The constant case starts the induction. Arithmetic progressions of distinct integers are allowed as the finite sets.

Fix a nonempty cyclically nonbacktracking base walk \(w\), based in layer \(i\), of length \(a\le C_*H_i/\log_2d\). The layer indices along it satisfy \(|H_j-H_i|\le a+1\), so their ratios to \(H_i\) tend uniformly to one. If some positive-edge block encountered has first index \(j_0<I\), then all such first indices are at most \(2I\) when \(\ell\) is sufficiently large. To verify this also for very negative \(j_0\), the length estimate and \(H_i\le H_{j_0}+a+1\) give \(a+1\le\epsilon_\ell H_{j_0}\), with \(\epsilon_\ell\to0\). The maximum first index is at most \(j_0+\epsilon_\ell(I+|j_0|)\). If \(j_0\ge0\), this is at most \((1+2\epsilon_\ell)I\); if \(j_0<0\), it is at most \(\epsilon_\ell I\). In this case use the first-factor quotient of \(F\) onto the upper unitriangular group. If there is no such block, every first index is at least \(I\), and use the second upper unitriangular quotient. These are the two overlapping wide ranges just proved.

Assign an independent formal upper unitriangular matrix to each undirected edge in the support of \(w\), using its inverse when the edge is traversed backwards. Lemma 30 says that the resulting word is not identically the identity. Its hypotheses apply because the support has the tower girth and the present walk has length at most the fixed \(C_*\) scale. In particular, the integer \(m\) used for this assertion was fixed at that scale. Some entry of this word minus the identity is therefore a nonzero polynomial in the upper entries of those edge matrices. Its total degree is at most \(m-1\). Indeed every term in the \((u,v)\) entry of a product of upper unitriangular matrices, including inverse matrices expanded by the finite geometric series, has total superdiagonal weight \(v-u\). Each variable has positive integer superdiagonal weight, so its ordinary total degree is at most \(v-u\le m-1\). This bound is independent of the number of factors in the word.

Condition on the template choices, frequencies, empirical-list choices, the other transverse factor, and the other independently sampled coordinates. Do not condition on the final scalar weights. In the first-factor case the remaining upper entries have their independent uniform interval distributions. In the second-factor case the edge matrix is a random subgroup upper matrix multiplied on the right by its fixed representative upper matrix. Right multiplication by that fixed matrix is an invertible polynomial coordinate change over the reals. Replacing the subgroup entries by their multiples of \(q\) is likewise an invertible linear coordinate change over the reals. Thus the nonzero word polynomial remains nonzero in the independently sampled entries. This also explains why weights that happen to vanish do not remove a voltage variable from this argument.

Each variable set has at least \(2^{E_0H_j}\) points at its local layer \(j\). The polynomial estimate therefore bounds the conditional, and hence unconditional, probability of trivial holonomy by \[(m-1)2^{-E_0\min_j H_j}.\] There are at most \[(d+1)2^{H_i} \sum_{1\le a\le C_*H_i/\log_2d}(6D)^a \le 2^{(3C_*+3)H_i}\] walks to test from all vertices of layer \(i\), for sufficiently large \(\ell\). Here the rough bound counts all walks, and the maximum degree is at most \(6D\). Since \(\min_jH_j\ge(1-o(1))H_i\) and \(E_0>10(C_*+C_\bullet+1)\), the union bound is at most \(C2^{-2H_i}\) after increasing \(\ell\). Summing over all \(i\in\mathbb Z\) gives a bound tending to zero.

A closed lift projects under a graph covering to a closed walk, and nonbacktracking, including the cyclic condition, is preserved. Trivial holonomy depends only on the base walk, not on which lift of its initial vertex is used. Consequently the tests just counted exclude every forbidden closed walk in the voltage cover.

Centered moments, with cycle edges included

To control deviations from the block means, we expand even moments of the centered edge operators. Independence and centering make a term vanish whenever its base walk traverses an undirected edge exactly once. The next lemma counts the remaining walks when their supports have bounded cycle rank; its constants do not affect the earlier nilpotence parameter.

Fix a block \((i,k)\) of the actual surviving graph. Before degree normalization let \(X_{ik}\) be its centered rectangular convolution matrix, with entries \[(X_{ik})_{ab}= \sum_{e:a\to b} \bigl(W_e\rho(z_e)-\mathbb E[W_e\rho(z_e)]\bigr).\] Double it off the diagonal to a self-adjoint matrix. By (103), Lemma 42 applies with \(x=2^{H_i}\), simultaneously for every possible assignment of these finitely many edges. The row and column coefficient bounds are \(O_\varepsilon(D)\). Choose the boundary exponent so that the absolute error in (93) tends uniformly to zero. Its finite test dimension, including all vertex, deck, and matrix indices, is bounded by \[ 2^{C_1H_i} \tag{105}\] for a fixed \(C_1\). To check this, the block has \(O((d+1)2^{H_i+1})\) vertices, the deck box has \(2^{O(H_i)}\) points, and \(N=q^{n_{\mathrm f}}=2^{A_*n_{\mathrm f}\log_2d} \le2^{O(H_i)}\).

At this point fix a constant \[ C_2>2(C_1+4),\qquad l=\left\lceil C_2H_i/\log_2d\right\rceil. \tag{106}\] The tower girth implies that the support of every length-\(2l\) walk with no singleton edge has cycle rank bounded by a constant depending on \(C_2\) alone, using Lemma 29. Indeed it has at most \(l\) edges and lies in the two fixed layers \(i,k\), whose girth lower bounds are comparable to \(H_i/(100\log_2d)\). The ratio of the edge count to that lower bound is bounded in terms of \(C_2\). This use of Lemma 29 requires no identity test for a longer word. In particular \(m\), which was fixed for the \(C_*\) girth tests, is not increased when \(C_2\) is chosen.

Let \(\widehat X_{ik}\) denote the finite self-adjoint compression. Every centered compressed edge entry has norm at most \(2C_\varepsilon\). Expand \(\mathbb E\operatorname{Tr}(\widehat X_{ik}^{2l})\) along the base-vertex indices. A summand whose walk has a singleton undirected edge has expectation zero: condition on the other edges, and the sole remaining factor is a centered entry or its adjoint. This remains true after deck compression. For the other walks, the absolute trace of the product on a fixed vertex’s deck and matrix indices is at most their dimension times \((2C_\varepsilon)^{2l}\). Lemma 44, with \(\Delta\le6D\), now gives \[ \mathbb E\operatorname{Tr}(\widehat X_{ik}^{2l}) \le 2^{C_1H_i}(C_4D)^l, \tag{107}\] where \(C_4\) is fixed after \(C_2\) and the accuracies have been chosen. It is independent of \(i,\ell\). The exponent in the dimension bound has not changed in this argument.

Use the finite norm test and Markov’s inequality at threshold \(\varepsilon\sqrt{dD_{ik}}\). For large \(\ell\), the absolute box error is less than half this threshold. Since \(D/2\le D_{ik}\le2D\), (107) implies \[ \mathbb P\{\|X_{ik}\|> \varepsilon\sqrt{dD_{ik}}\} \le 2^{C_1H_i}(C_5/d)^l. \tag{108}\] The constant \(C_5\) can be very large and can depend on \(C_2\). Nevertheless it is fixed before increasing \(\ell\). Increase \(\ell\) so that \(C_5\le d^{1/2}\). The right side is then at most \(2^{(C_1-C_2/2)H_i}\le2^{-4H_i}\), by (106). Summing over the at most three blocks with each first index gives a total failure bound tending to zero.

A simultaneous choice and the global norm

For sufficiently large \(\ell\), the sum of the girth failure bounds and the block-norm failure bounds is less than one. In the countable independent product of the finite edge distributions, the union bound therefore gives positive probability that all requirements hold. There is also an elementary compactness formulation which avoids any need for an infinite sampling construction. Enumerate the countably many edge choices and the countably many requirements. Every requirement depends on only finitely many edges: this is immediate for a fixed walk, and a fixed block contains finitely many edges even though its convolution norm acts on an infinite deck space. Any finite collection of requirements is satisfiable by the finite-product union bound, using the same total budget below one. Choose assignments satisfying the first \(n\) requirements and extend them arbitrarily to all other edges. Successive subsequences make the choice at each edge constant, since every edge has finitely many possible outcomes. The diagonal limit satisfies every requirement: once its finite set of edges has stabilized, the corresponding operators and voltages are exactly the same. Fix such an assignment.

It remains to combine the block errors. Because the distribution is common to all edges in a block, the expected normalized block equals the actual surviving normalized incidence tensored with its single-edge expectation. The surviving incidence is the compression of \(U^0_{ik}\) and has norm at most one. Equation (102) therefore bounds its difference from the corresponding block of \(\Pi O\Pi\) by \(\varepsilon\). The simultaneous success of (108) bounds the centered normalized block by \(\varepsilon\). A matrix with layer width one and block norms bounded by \(\varepsilon\) has norm at most \(3\varepsilon\): apply Cauchy–Schwarz to each row and sum, or apply the scalar row-and-column Schur bound. Its self-adjoint off-diagonal doubling has the same norm. Consequently \[\|T_P-\Pi O\Pi\|\le6\varepsilon.\] Taking \(\varepsilon<\eta/6\) proves (92). All expectation errors used above were made smaller than this chosen \(\varepsilon\) by first fixing compact cutoffs, log-grid spacing, empirical accuracies, Fourier cutoffs, and scalar rounding, and then increasing \(\ell\). The order of the constants is thus: the geometric and nilpotence parameters; the fixed desired accuracy and its coefficient data; the finite test exponent \(C_1\); the moment constant \(C_2\); and finally \(\ell\). All estimates are uniform in the layers. This proves Theorem 41.

Compression and norm perturbation

We record quantitative Hilbert-space estimates, including the projection equivalences needed later for the trace.

Set \[ \alpha=\chi/1000,\qquad r_0=\chi/3, \qquad C_\chi=4/\chi. \tag{114}\] Choose the fixed approximation accuracy \(\eta>0\) so small that \[ \eta\leq\alpha/2,\qquad \theta:=C_\chi\eta\leq1/2,\qquad 2^{C_\bullet}\theta^2\leq1/2. \tag{115}\] The other fixed parameters of the construction have already been chosen; Theorem 41 permits this accuracy. We subsequently take \(\ell\) sufficiently large that \[ 20\sqrt{\beta_\ell}\leq\alpha/2. \tag{116}\] All inequalities below concern such \(\ell\) and are uniform in the layers.

Localization of identity trace

For a surviving base vertex \(v\), let \[ e_v=\sum_{j=1}^N \big\langle E_P(\delta_{(v,1_F)}\otimes e_j), \delta_{(v,1_F)}\otimes e_j\big\rangle\geq0, \qquad \mathcal S=\sum_{i\in\mathbb Z}\mathfrak w_i \sum_{v\in V(Y)\cap(A_i\cup B_i)}e_v. \tag{119}\] Here \(e_j\) denotes the standard matrix basis; put \(e_v=0\) at a deleted base vertex when summing over \(Y^0\). These are regular identity diagonals before the central Fourier decomposition.

The weights record the two counts in Equations (55) and (56). A fixed base type may have many lifts inside one trimming ball, while the sum of losses over copies carries a ball-size factor from Cauchy–Schwarz. Controlling \(\mathcal S\) will keep both forms of overlap loss small.

An actual element of the matrix reduced group algebra

Use the finite alphabet supplied by Theorem 41 to form the group \(\Gamma_{\mathrm{proj}}\) of Theorem 15. For a positive label \(\sigma\), let \(W_\sigma\) be its matrix weight and let \(D_\sigma=D_{ik}\) be its label-determined degree normalizer. Put \[ w_\sigma=(dD_\sigma)^{-1/2}W_\sigma,\qquad (T\xi)(g)=\sum_{\sigma\in S} \big(w_\sigma\xi(g\sigma)+w_\sigma^*\xi(g\sigma^{-1})\big). \tag{125}\] This is a finite sum of bounded matrix coefficients times right regular translations. It is self-adjoint, and inversion of the group coordinate identifies it with an element of \(M_N(\mathbb C[\Gamma_{\mathrm{proj}}])\) in the left regular convention. In particular \(T\in M_N(C_r^*(\Gamma_{\mathrm{proj}}))\). We use the right convention in the proof, so that \(T\) commutes with left translations of \(\Gamma_{\mathrm{proj}}\).

For an indexed copy \(Q\), let \(T_Q\) be the adjacency using just its own formal edges. The embedding and labels identify it with the restriction of \(T_P\) to the source component. Let \(E_Q\) be its upper spectral projection on \(\mathcal C_{r_0}\). Equation (117) holds for \(T_Q,E_Q\), and if an incidence \((Q,u)\) has base type \(v\), \[ \operatorname{Tr}_{\mathbb C^N}E_Q(u,u)=e_v. \tag{126}\] The equation follows from component reduction and deck equivariance in Proposition 47; it does not require the connected component to be invariant under every deck translation.

Equivariant size of all local upper spaces

The comparison with the assigned domains proves spectral separation, but their ordering need not be equivariant. Thus the ordinary equivalence with \(F_D\) does not by itself compare canonical traces. For the trace estimate we return to all indexed copies. Their upper spaces form an equivariant space of small trace, and we will show that the common kernel of the corresponding restrictions contains no nonzero vector of the global upper space.

Write \(\mathcal H=\ell^2(\Gamma_{\mathrm{proj}})\otimes\mathbb C^N\). For a left \(\Gamma_{\mathrm{proj}}\)-equivariant positive operator \(Z\) on \(\ell^2(\Gamma_{\mathrm{proj}})\otimes\mathcal K\), with a fixed countable orthonormal basis \((k_a)\) of \(\mathcal K\), its identity trace is \[ \operatorname{Tr}_{\Gamma_{\mathrm{proj}}} Z =\sum_a\langle Z(\delta_1\otimes k_a), \delta_1\otimes k_a\rangle\in[0,\infty]. \tag{132}\] The size of a closed invariant subspace is the identity trace of its orthogonal projection. Lemma 32 proves basis independence, the adjoint-square trace identity, and invariance under equivariant partial isometries in these countably amplified spaces. In particular the size of \(p_0\mathcal H\) is \[\tau_{\Gamma_{\mathrm{proj}},N}(p_0) =\sum_{j=1}^N\tau_{\Gamma_{\mathrm{proj}}}((p_0)_{jj}),\] with no division by \(N\).

Consider the Hilbert space and projection \[ \mathcal L=\bigoplus_Q\big(\ell^2(V(Q))\otimes\mathbb C^N\big), \qquad\mathcal E=\bigoplus_Q E_Q. \tag{133}\] Left translation acts simultaneously on \(Q\) and its vertices. The incidence bijection of Proposition 25 identifies this representation, including matrix indices, with \[ \mathcal L\cong\ell^2(\Gamma_{\mathrm{proj}})\otimes\ell^2(V(Y))\otimes\mathbb C^N. \tag{134}\] More explicitly, \((Q,u)\) is sent to \((u,v)\) where \(v\) is its base type. For each \(u\in\Gamma_{\mathrm{proj}}\) and \(v\in V(Y)\) there is exactly one such incidence: choose any lift of \(v\), map its component with that lift sent to \(u\), and use the deck-alignment equivalence in the definition of indexed copies. Different lift choices give the same incidence, and any incidence arises this way. The injective label maps ensure that the base type is unambiguous. This count is valid for disconnected covers and for copies with nontrivial, possibly infinite stabilizers. The action on the pairs \((Q,u)\) is free because it is free on their group vertex \(u\); freeness of the action on the set of copies is unnecessary.

The operator \(\mathcal E\) is equivariant in this representation. Its identity diagonal at the base type \(v\) has matrix sum \(e_v\), by Equation (126). Hence \[ \operatorname{Tr}_{\Gamma_{\mathrm{proj}}}\mathcal E =\mathcal S_0:=\sum_{v\in V(Y)}e_v \leq\mathcal S<\infty. \tag{135}\] Thus \(\mathcal U:=\mathcal E\mathcal L\) is a closed invariant space of finite identity trace, even though there are countably many copies and base vertices.

Together with disjointness of the \(D_Q\), this controls the restriction map to all upper spaces.