Proof. We build a fixed word whose adjustable diagonal factors give a full-rank differential, then show that its actual values contain a nonempty Zariski open subset of \(\mathop{\mathrm{GL}}_q(\mathbb C)\). Every invertible target is a product of two values from this subset, so doubling the word gives the common pattern.

Let \(E_{ij}\) denote the matrix units. Let \(\mathfrak d\subset\mathop{\mathrm{Mat}}_q(\mathbb C)\) be the diagonal subspace and let \(\mathcal S\) be the semigroup of words in \(A\) and monomials, including identity. Inverses are not among the specified calls. First we prove \[ \mathop{\mathrm{span}}_{s\in\mathcal S}s\mathfrak d s^{-1}=\mathop{\mathrm{Mat}}_q(\mathbb C). \tag{4}\] If \(A\mathfrak d A^{-1}\subset\mathfrak d\), each rank-one idempotent \(A E_{ii}A^{-1}\) would be a diagonal rank-one idempotent, hence some \(E_{\pi(i)\pi(i)}\). Orthogonality of these idempotents forces \(\pi\) to be a permutation. The identity \(A E_{ii}=E_{\pi(i)\pi(i)}A\) then says that column \(i\) of \(A\) is supported in row \(\pi(i)\); invertibility would make \(A\) monomial. Consequently some \(X\in A\mathfrak d A^{-1}\) has \(X_{ij}\ne0\) for \(i\ne j\).

Write \(\mathcal V\) for the span on the left of [gen:eq:tangent-span]. For every invertible diagonal \(D=\mathop{\mathrm{diag}}(d_1,\ldots,d_q)\), the matrix \(DXD^{-1}\) belongs to \(\mathcal V\). If a linear functional \(\ell\) vanishes on \(\mathcal V\), then \[0=\ell(DXD^{-1}) =\sum_a X_{aa}\ell(E_{aa}) +\sum_{a\ne c}X_{ac}\ell(E_{ac})d_a/d_c \qquad(d_1,\ldots,d_q\in\mathbb C^*).\] The Laurent monomials \(1\) and \(d_a/d_c\) for \(a\ne c\) are distinct and linearly independent. Thus \(X_{ij}\ell(E_{ij})=0\), and so \(\ell(E_{ij})=0\). Finite-dimensional linear duality gives \(E_{ij}\in\mathcal V\). Conjugation by any permutation preserves \(\mathcal V\), because left multiplication of a word by that permutation is again a word. Hence \(\mathcal V\) contains every off-diagonal matrix unit. It also contains \(\mathfrak d\), using \(s=I_q\). This proves [gen:eq:tangent-span].

We next arrange the spanning directions along one word. Start with the prefix \(h_0=I_q\) and its diagonal directions. If the directions collected so far span a proper subspace and the current prefix is \(h\), then \[\mathop{\mathrm{span}}_{s\in\mathcal S}(hs)\mathfrak d(hs)^{-1} =h\mathop{\mathrm{Mat}}_q(\mathbb C)h^{-1}=\mathop{\mathrm{Mat}}_q(\mathbb C).\] Choose a word \(s\) whose directions enlarge the collected span, and append it to the right of \(h\) in written product order. Each choice increases the dimension, so finitely many choices suffice. Denote the successive appended words by \(s_1,\ldots,s_r\) and their prefixes by \(h_i=s_1\cdots s_i\). The spaces \(h_i\mathfrak d h_i^{-1}\), including \(i=0\), now span \(\mathop{\mathrm{Mat}}_q(\mathbb C)\).

Insert variable diagonal factors in the product \[\Phi(D_0,\ldots,D_r)=D_0s_1D_1s_2\cdots s_rD_r.\] At \(D_0=\cdots=D_r=I_q\), its value is \(h_r\). Varying \(D_i\) in the diagonal direction \(E_{aa}\) gives the right-translated derivative \[(\delta\Phi)h_r^{-1}=h_iE_{aa}h_i^{-1}.\] Thus the derivative has rank \(a=q^2\). Choose \(a\) diagonal entries whose derivative columns are independent, and fix all other entries to \(1\). Listing matrix entries produces a polynomial map \[f:\mathbb C^a\longrightarrow\mathbb C^a\] whose Jacobian determinant is nonzero at \((1,\ldots,1)\). Parameters in \((\mathbb C^*)^a\) give admissible words. We show next that their image contains an actual nonempty Zariski open subset of \(\mathop{\mathrm{GL}}_q(\mathbb C)\).

Write \(x_1,\ldots,x_a\) for the selected parameters and \(f_1,\ldots,f_a\) for the output entries. The \(f_i\) are algebraically independent. Indeed, a nonzero polynomial relation \(P(f)=0\) of least total degree would, upon differentiation and inversion of the Jacobian over \(\mathbb C(x_1,\ldots,x_a)\), imply \((\partial P/\partial y_i)(f)=0\) for every \(i\). In characteristic zero at least one of these is a nonzero polynomial of smaller degree, a contradiction. Both fields in the inclusion \[\mathbb C(f_1,\ldots,f_a)\subset\mathbb C(x_1,\ldots,x_a)\] therefore have transcendence degree \(a\). The latter is an algebraic extension generated by the finitely many \(x_i\), so it is finite. Each of the finitely many elements \(x_i,x_i^{-1}\) satisfies a monic equation over the smaller field. Choose a nonzero polynomial \(g(y_1,\ldots,y_a)\) divisible by the denominators of all coefficients of these equations. With \[\begin{align*} R&=\mathbb C[f_1,\ldots,f_a,1/g(f)],\\ B&=R[x_1,\ldots,x_a,x_1^{-1},\ldots,x_a^{-1}] \subset\mathbb C(x_1,\ldots,x_a), \end{align*}\] all the displayed generators of \(B\) are integral over \(R\). Reducing their powers by their monic equations shows directly that \(B\) is a finite \(R\)-module. Both are domains and \(R\hookrightarrow B\) is injective. This is the finite-type integral-extension criterion (The Stacks Project Authors 2026, Tag 02JJ, Lemma 10.36.5).

Fix any target \(y\in\mathbb C^a\) with \(g(y)\ne0\), and let \(\mathfrak m=(f_1-y_1,\ldots,f_a-y_a)\subset R\). Algebraic independence identifies \(R/\mathfrak m\) with \(\mathbb C\). Localizing the inclusion above gives \(R_{\mathfrak m}\hookrightarrow B_{\mathfrak m}\) inside the field \(\mathbb C(x_1,\ldots,x_a)\), so \(B_{\mathfrak m}\) is a nonzero finite module over the local ring \(R_{\mathfrak m}\). Its residue algebra \[ B_{\mathfrak m}/\mathfrak mB_{\mathfrak m} \tag{5}\] is nonzero. This is the lying-over step for the integral inclusion (The Stacks Project Authors 2026, Tag 00GQ, Lemma 10.36.17). For completeness, if it were zero, a finite list of module generators \(b_1,\ldots,b_e\) would satisfy \(b_i=\sum_j c_{ij}b_j\) with all \(c_{ij}\) in the maximal ideal of \(R_{\mathfrak m}\). The determinant of \(I-(c_{ij})\) is a unit in this local ring. Multiplication by its adjugate forces every \(b_i\) to be zero, contradicting \(B_{\mathfrak m}\ne0\).

The algebra in [gen:eq:nonzero-fiber] is finite dimensional over \(\mathbb C\). A quotient by a maximal ideal is a finite field extension of \(\mathbb C\), and hence is \(\mathbb C\) itself. The resulting homomorphism \(B\to\mathbb C\) sends \(x_i\) to some \(\xi_i\ne0\), since \(x_i^{-1}\) is also in \(B\). The polynomial identities defining the \(f_i\) descend to \(f_i(\xi)=y_i\). These are actual admissible parameters of the fixed word. In particular its image contains \[\Omega=\{Y\in\mathop{\mathrm{Mat}}_q(\mathbb C):g(Y)\det Y\ne0\},\] a nonempty open set, because \(g(Y)\det Y\) is a nonzero polynomial.

Finally fix \(H\in\mathop{\mathrm{GL}}_q(\mathbb C)\). There is a \(V\) for which both \(V\in\Omega\) and \(V^{-1}H\in\Omega\). To see this without any limiting argument, clear powers of \(\det V\) from \(g(V^{-1}H)\). Its numerator is a nonzero polynomial: the substitution \(V\mapsto V^{-1}H\) is a bijection of \(\mathop{\mathrm{GL}}_q(\mathbb C)\), with inverse \(W\mapsto HW^{-1}\), so this rational function is not identically zero. Avoid simultaneously the zeros of that numerator, \(g(V)\), and \(\det V\). A finite product of nonzero polynomials over \(\mathbb C\) is nonzero and has a point where it does not vanish. This supplies the required \(V\). Setting \(W=V^{-1}H\) gives \(H=VW\), with both factors realized by the same fixed word pattern. Two copies of that pattern therefore realize every \(H\).

The initial pattern contains at least one occurrence of \(A\): otherwise its values have one fixed monomial support, a space of dimension \(q\), contradicting the derivative rank \(q^2>q\). Expanding the fixed words \(s_i\) and merging adjacent monomials in the doubled pattern gives [gen:eq:common-pattern] with a fixed \(h>0\). All inverses used in the argument occurred in matrix identities or parameter selection; every factor of the constructed words is a forward call to \(A\) or a monomial. For \(w>q\), applying the same result to the nonmonomial matrix \(A\oplus I_{w-q}\) proves the wider-width assertion, because each call to this matrix is one embedded call to \(A\). ◻

Proof. Let \(L_A(k)\) be the minimum scalar gate count for \(A^{\otimes k}\), and put \(f(k)=L_A(k)/q^k\). Here \(A^{\otimes0}=I_1\) and \(f(0)=0\). These minima exist: entrywise multiplication and addition give finite circuits, and a nonempty set of nonnegative integer gate counts has a minimum. Set \[Q=q^b,\qquad p=q/Q,\qquad j=\lfloor k/b\rfloor.\] Tensor the winning word with itself over \(j\) groups, multiplying the corresponding slots together. The product of these slots is \((A^{\otimes b})^{\otimes j}=A^{\otimes bj}\).

A monomial slot remains monomial after taking this tensor power, and therefore costs at most \(Q^j\) scalar gates. Each call slot is permutation-conjugate to \(A\oplus I_{Q-q}\). Its \(j\)-fold tensor power, after reordering coordinates, has the following exact direct-sum decomposition: \[ (A\oplus I_{Q-q})^{\otimes j} \ \cong\ \bigoplus_{r=0}^{j} \left(A^{\otimes r}\right)^{\oplus \binom jr(Q-q)^{j-r}}. \tag{6}\] For a chosen subset of \(r\) active factors, the inactive factors supply \((Q-q)^{j-r}\) independent scalar coordinate choices, explaining the multiplicity. The total width is \(\sum_r\binom jr q^r(Q-q)^{j-r}=Q^j\). Computing the blocks separately with minimum circuits gives normalized cost at most \[\begin{align*} \frac{1}{Q^j}\sum_{r=0}^j \binom jr(Q-q)^{j-r}L_A(r) &=\sum_{r=0}^j\binom jr p^r(1-p)^{j-r}f(r)\\ &=\mathbb E f(K),\qquad K\sim\operatorname{Bin}(j,p). \tag{7}\end{align*}\] In particular, this distribution weights sectors by their coordinate dimensions; the sectors have different widths.

Replicate the resulting circuit over the coordinates of the remaining \(k-bj<b\) tensor axes. The normalized cost is unchanged by this replication. If a fixed circuit for \(A\) has \(\ell_A\) gates, applying \(A\) along each remaining axis costs \(\ell_Aq^{k-1}\) gates per axis. Since the number of monomial slots in the winning word is fixed, there is a constant \(C_0\) independent of \(k\) such that \[ f(k)\leq C_0+g\,\mathbb E f(K), \qquad K\sim\operatorname{Bin}(\lfloor k/b\rfloor,q/Q). \tag{8}\] For \(j=0\) the grouped part is identity and the same inequality follows from the bound on the fewer than \(b\) remaining axes. Every permutation used in deriving [gen:eq:sector-decomposition] is only a reindexing; every diagonal scaling has already been charged.

Put \(\rho=q/(Qb)\). The strict saving gives \(g\rho<1\), and hence we can choose \(0<\alpha<1\) sufficiently close to \(1\) that \(g\rho^\alpha<1\). Choose also a number \(\gamma\) with \(g\rho^\alpha<\gamma<1\). Since \[g\left(\frac{\rho k+1}{k+1}\right)^\alpha \longrightarrow g\rho^\alpha,\] there is \(k_0\geq1\) such that this expression is at most \(\gamma\) for all \(k\geq k_0\). Choose \(C\) at least \(C_0/(1-\gamma)\) and large enough that \(f(k)\leq C(k+1)^\alpha\) for \(k<k_0\). For \(k\geq k_0\), every value of \(K\) satisfies \(K\leq\lfloor k/b\rfloor<k\). Strong induction, concavity of \(x\mapsto x^\alpha\), and \(\mathbb E K=p\lfloor k/b\rfloor\leq\rho k\) therefore give \[f(k)\leq C_0+gC\,\mathbb E(K+1)^\alpha \leq C_0+gC(\rho k+1)^\alpha \leq C_0+C\gamma(k+1)^\alpha \leq C(k+1)^\alpha.\] All circuits used in this induction compute exact matrices; the expectation is merely the finite weighted sum in [gen:eq:weighted-cost]. Multiplying by \(q^k\) proves the scalar gate bound \[L_A(k)=O\bigl(q^k(k+1)^\alpha\bigr),\qquad 0<\alpha<1.\] ◻

Proof. Assign one distinct coordinate \(z_v\) to each gate \(v\), ordered topologically. To simulate the gate, add its prescribed linear combination of predecessors into \(z_v\). A scalar gate requires one shear, and an addition or subtraction requires at most two. An edge from the literal input zero is omitted. Predecessors are either original source coordinates or earlier gate coordinates; in particular none is the coordinate being updated. The forward sweep therefore has the form \[ z\longmapsto Uz+Tx, \tag{9}\] where \(U\) is unit lower triangular in the chosen order. Write the designated output reads as \(Fz_{\rm current}+Dx\); this includes outputs that are original inputs, and a zero output contributes no read. Each nonzero output is one designated read. Starting with zero gate coordinates computes the original DAG, so \[ FT+D=M. \tag{10}\] Run the forward sweep, add its outputs into \(y\), and undo every shear of that sweep in reverse order. The net effect on \(y\) is addition of \[F(Uz+Tx)+Dx=Mx+FUz,\] and every scratch coordinate returns to its initial value. Next run the same forward sweep with all edges from original source coordinates omitted. Omit the direct-source output term \(Dx\) as well. This sweep sends \(z\) to \(Uz\). Subtract its outputs \(FUz\) from \(y\) and undo the sweep. This leaves exactly \(y+Mx\) and restores \(z\) once more. The target coordinates are never read by either sweep. These identities hold for independent formal variables \(x,y,z\), hence remain valid after substituting correlated values for the initial scratch.

To obtain the layer bound, assign gates their longest-path depth levels. Within a level, all destinations are new gate coordinates and all predecessors belong to earlier levels or to the sources. The undirected multigraph of shear edges has maximum degree at most \(\Delta=\max\{2,\delta\}\): a destination has at most two incoming edges and a predecessor has at most \(\delta\) uses. Repeated edges can be combined, or retained with their bounded multiplicity. Greedy edge coloring uses at most \(2\Delta-1\) colors, because an edge meets at most \(2\Delta-2\) other edges. Each color is a disjoint-pair layer. These shears can be reordered by colors because no destination in this level is a predecessor in the same level. Output additions have the same bounded-degree property on source or gate coordinates and target coordinates. Reversing the colored levels gives the exact inverse sweep. Thus four sweeps and two output rounds need at most \(4(2\Delta-1)H+2(2\Delta-1)\) layers. Each sweep uses at most \(2\ell\) shears and each output round at most \(a\), proving the count. ◻

Proof. Write \(T_r=(h_{i-j})_{0\le j\le i<r}\), with zero entries above the diagonal and \(h_0\ne0\). Let \(g_0,g_1,\ldots\) be the coefficients of the inverse formal series to \(\sum_{j\ge0}h_jz^j\), extending the specified \(h_j\) arbitrarily beyond those needed. Split at \(s=\lfloor r/2\rfloor\), and put \[T_r=\begin{pmatrix}T_s&0\\ B&T_{r-s}\end{pmatrix}.\] First apply its two diagonal blocks recursively and in parallel. To finish, add from the first block into the second by \(C=BT_s^{-1}\). With global row and column indices its entries are \[ C_{ij}=\sum_{\nu=j}^{s-1}h_{i-\nu}g_{\nu-j}, \qquad s\le i<r,\quad 0\le j<s. \tag{11}\]

Partition the source and target ranges into consecutive chunks, of a size to be specified below, and consider a chunk matrix \(M\) of size \(a\times e\). Let \(S_a,S_e\) be lower-shift matrices, with ones in positions \((u,u-1)\). For entries away from the first row and first column of the chunk, [fft:cross-block] gives \[M_{uv}-(S_aMS_e^{\mathsf T})_{uv} =C_{ij}-C_{i-1,j-1}=-h_{i-s}g_{s-j}.\] The right side is an outer product on those entries. Extending this outer product to the whole chunk leaves only its first row and first column to correct; these have rank at most one each. Consequently \[ E=M-S_aMS_e^{\mathsf T} =\sum_{\nu=1}^{\rho}v^{(\nu)}(w^{(\nu)})^{\mathsf T}, \qquad \rho\le3. \tag{12}\] Nilpotence of the shifts gives the terminating telescoping identity \[M=\sum_{l\ge0}S_a^lE(S_e^{\mathsf T})^l.\] For one outer product \(vw^{\mathsf T}\) its summand matrix has entries \(\sum_{l\ge0}v_{u-l}w_{j-l}\), with both vectors zero-extended. It applies to \(x\in\mathbb C^e\) by the two maps \[ b_l=\sum_{j=l}^{e-1}w_{j-l}x_j\quad(0\le l<e), \qquad c_u=\sum_{l=0}^{e-1}v_{u-l}b_l\quad(0\le u<a). \tag{13}\] The first is a convolution after reversing the input and selecting coefficients; the second is a truncated convolution. Sum the at most three resulting vectors. The preceding binary-FFT construction therefore supplies a DAG for \(Mx\) satisfying, for absolute constants \(C_0,C_1,\delta_0\), \[ \ell\le C_0(a+e)\log_2(2+a+e),\qquad H\le C_1\log_2(2+a+e),\qquad \delta\le\delta_0. \tag{14}\] These bounds include the sums of the at most three terms and all output uses. In particular, copying the input to these three fixed networks multiplies its fan-out by only a constant. The constants do not depend on the Toeplitz entries or the chosen outer products.

Choose once and for all \(D\ge16C_0+16\) and, for sufficiently large \(r\), take chunk size \[h=\left\lfloor\frac{r}{D\log_2r}\right\rfloor.\] Choose a fixed threshold \(r_0\) so that, for all \(r\ge r_0\), \(h\ge r/(2D\log_2r)\ge1\). The final chunk in either range may be shorter. For every chunk pair, \[a+e\le\frac{2r}{D\log_2r}\le\frac r8, \qquad \log_2(2+a+e)\le2\log_2r, \qquad \ell\le\frac{4C_0r}{D}<\frac r4.\] At least \(7r/8\) coordinates of this very recursion block lie outside the source and target chunks. They suffice for the \(\ell\) scratch coordinates in 5. No extra coordinate is introduced for the padded FFT: its zero inputs require no register, and every gate requiring a register is already counted in \(\ell\). The lemma implements addition of this chunk’s contribution in \(O(\log r)\) pair layers and restores every other coordinate.

Process the chunk pairs serially. Source chunks remain unchanged, target additions accumulate, and coordinates in other chunks can be borrowed again with their current values, even if already updated. There are at most \(r/h+2=O(\log r)\) chunks in total and hence \(O(\log^2r)\) pairs. The cross-block update needs \(O(\log^3r)\) layers. For \(r<r_0\), elimination expresses \(T_r\) using scalings and coordinate shears on the same coordinates, at a bounded cost depending only on the fixed \(r_0\).

Let \(d(r)\) denote the worst mixed-round depth of this construction. The child recursions use only their own disjoint blocks, so their depths take a maximum, and \[d(r)\le\max\{d(\lfloor r/2\rfloor), d(\lceil r/2\rceil)\} +O(1+\log^3r).\] Summing along the \(O(\log r)\) balanced recursion levels gives \(d(r)=O(1+\log^4r)\). Splitting mixed rounds into at most two layers finishes the proof, still on exactly \(r\) coordinates. ◻

Proof. The case \(r=1\) is identity. For \(r\ge2\) put \(u=\zeta_r\), and let \(P\) have as its \(k\)th column the coefficients of the monic Newton polynomial \(\prod_{j=0}^{k-1}(X-u^j)\), for \(0\le k<r\). Thus \(P\) is unit upper triangular. Evaluating these polynomials gives \(N=F_rP\), a lower triangular matrix, with \[ N_{ik}=\prod_{j=0}^{k-1}(u^i-u^j) =(-1)^k u^{k(k-1)/2}\frac{H_i}{H_{i-k}}\quad(i\ge k), \qquad H_j=\prod_{e=1}^j(1-u^e),\quad H_0=1. \tag{15}\] Only \(H_0,\ldots,H_{r-1}\) occur, all nonzero since \(u\) is a primitive \(r\)th root. In particular \(N\) is invertible and \[N=\mathop{\mathrm{diag}}(H_i)\,T\, \mathop{\mathrm{diag}}\bigl((-1)^ku^{k(k-1)/2}\bigr), \qquad T_{ik}=\begin{cases}1/H_{i-k},&i\ge k,\\0,&i<k.\end{cases}\] The middle matrix is invertible triangular Toeplitz, and the outer factors are invertible diagonal matrices.

Let \(D_N=\mathop{\mathrm{diag}}(N_{00},\ldots,N_{r-1,r-1})\) and \(L=ND_N^{-1}\). Then \(F_r=L D_N P^{-1}\) is a unit-lower/diagonal/unit-upper factorization. Such a factorization, when it exists, is unique: on equating two, a unit lower triangular matrix equals an upper triangular matrix, hence is identity, after which the diagonal and upper factors agree. Since \(F_r=F_r^{\mathsf T}\), transposition supplies another such factorization. Uniqueness gives \(P^{-1}=L^{\mathsf T}\), and therefore \[ F_r=N D_N^{-1}N^{\mathsf T}. \tag{16}\] Apply 6 to \(T\) and include its two diagonal factors to factor \(N\). Transposing a product reverses its factor order; the transpose of each monomial or pair layer is again of that type. Thus [fft:fourier-toeplitz] has the asserted factorization. ◻

Proof. Fix the winning matrix \(A\) of width \(q\), the winning tensor exponent, and the entire winning word. Since \(A\) is nonmonomial, \(q\ge2\). By 4, there are fixed constants \(C\) and \(0<\alpha<1\) such that \(A^{\otimes k}\) has a scalar circuit of size at most \(Cq^k(k+1)^\alpha\) for every \(k\ge0\). All constants depending on this win remain fixed from now on.

We first obtain enough moderately sized, distinct primes by an elementary estimate. If \(\pi(v)\) counts primes at most \(v\), then \[\binom{2h}{h}\ge\frac{4^h}{2h+1},\qquad \binom{2h}{h}\le(2h)^{\pi(2h)}.\] The first inequality follows because the central binomial coefficient is the largest of the \(2h+1\) coefficients whose sum is \(4^h\). For the second, the exponent of a prime \(p\) in that coefficient is \[\sum_{j\ge1}\left( \left\lfloor\frac{2h}{p^j}\right\rfloor -2\left\lfloor\frac{h}{p^j}\right\rfloor\right) \le\lfloor\log_p(2h)\rfloor.\] Here each term is zero or one, and the formula itself follows by counting the multiples of \(p,p^2,\ldots\) in a factorial. The total power contributed by each prime is consequently at most \(2h\). It follows that \[\pi(2h)\ge \frac{h\log4-\log(2h+1)}{\log(2h)}.\] With \(h=m^2\), this exceeds \(m+\pi(2q)\) for all sufficiently large \(m\). Let \(r_1<r_2<\cdots\) be the primes greater than \(2q\) and put \(n_m=\prod_{i=1}^m r_i\). Thus \(r_m\le2m^2\) eventually, \(n_m\to\infty\), and \(\log n_m\ge m\log2\).

For clarity, the Chinese remainder factorization here involves only permutations. Write \(n=n_m\) and choose integers \(e_i\) whose residue is one modulo \(r_i\) and zero modulo every other \(r_j\). These satisfy \(e_i^2=e_i\), \(e_ie_j=0\) for \(i\ne j\), and \(\sum_i e_i=1\), all modulo \(n\). The bijections \(j=\sum_i e_i j_i\), \(k=\sum_i e_i k_i\) yield \[\zeta_n^{jk}=\prod_{i=1}^m(\zeta_n^{e_i})^{j_ik_i}.\] For example, take \(e_i=(n/r_i)d_i\), where \((n/r_i)d_i\equiv1\pmod {r_i}\); then \(\zeta_n^{e_i}=\zeta_{r_i}^{d_i}\) and \(d_i\) is a unit modulo \(r_i\). Permuting \(k_i\) by this unit converts the corresponding factor to \(F_{r_i}\). Hence \(F_n\) is \(\bigotimes_{i=1}^mF_{r_i}\) up to input and output permutations.

By 7, each factor has at most \[T=O(1+\log^4m)\] layers, uniformly for these \(r_i\). Pad the shorter sequences in time by identity layers. We next refine a synchronized time step by a bounded number of slots depending only on \(A\).

First reserve a monomial slot: on an axis whose current layer is monomial perform it, and on the other axes perform identity. On a pair-layer axis of width \(r_i\), there are at most \(\lfloor r_i/2\rfloor\) pairs. Split them into at most \(q\) batches of at most \(\lfloor r_i/q\rfloor\) pairs each. Indeed \(\lfloor r_i/q\rfloor\ge r_i/(2q)\), so the required number of batches is at most \(q\). Within a batch with \(t\) pairs, choose a disjoint \(q\)-tuple containing each pair: the \(2t\) pair coordinates are already distinct and there are enough remaining coordinates because \(qt\le r_i\). The desired map on that tuple is its prescribed pair operation together with identity on the \(q-2\) spectators.

By 3, every such map has an implementation using the same fixed sequence of positive \(A\)-call slots and monomial slots; denote its total number of slots by \(s_A\). Run these words in parallel on the disjoint tuples. At a monomial slot their disjoint union, with identity on unused coordinates, is monomial. At an \(A\)-call slot the layer is a disjoint union of embedded \(A\) calls and identity on unused coordinates. Use the same slots for every axis, padding to \(q\) batches and using identity throughout empty batches or axes. The number of refined slots per original time is at most \(1+qs_A\), independently of \(m\) and the \(r_i\).

The spectator coordinates may belong to pairs processed in later batches. A completed tuple word is exactly the required pair map direct-sum identity, so every spectator is restored before the next batch on its axis. For simultaneous execution on different axes, the exact product identity \[ (\bigotimes_i W_{i,s})\cdots(\bigotimes_i W_{i,1}) =\bigotimes_i(W_{i,s}\cdots W_{i,1}) \tag{17}\] proves correctness even though intermediate spectator values change. We implement each tensor slot as a complete linear map; no assumption about intermediate values on other axes is required. Throughout, the coordinate width remains exactly \(n\).

It remains to charge these refined slots in the scalar model. A tensor product of monomial layers is itself monomial and costs at most \(n\) scalar multiplications; permutations merely reindex available values. At an \(A\)-call slot, decompose each axis into its active \(q\)-tuples and its unused singleton coordinates. Distributing the tensor product over these blocks expresses that slot, up to permutation, as a direct sum of matrices \(A^{\otimes K}\) with \(0\le K\le m\). A sector of width \(q^K\) costs at most \(Cq^K(K+1)^\alpha\le Cq^K(m+1)^\alpha\). The sector widths sum to \(n\), so the whole slot costs at most \(Cn(m+1)^\alpha\). The \(K=0\) sectors are identities and need no gates.

Thus the complete circuit, including all monomial scalings, has size \[ O\bigl(n_m(1+\log^4m)(m+1)^\alpha\bigr). \tag{18}\] The constants in tensor monomials, Fourier convolutions, and generation words may all be prechosen, as permitted by the nonuniform model. A shear uses at most a scalar multiplication and an addition, and each binary fixed-coefficient combination uses at most three charged gates; no unbounded-fan-in operation is used. Finally, division of [fft:final-size] by \(n_m\log_2n_m\) gives \(O\bigl((1+\log^4m)(m+1)^\alpha/m\bigr)\to0\). All matrix identities and all circuits used above are exact. ◻

Proof. Suppose such a combination exists. We will choose a block-diagonal matrix \(J\) containing many copies of every \(A_i\) and many identity blocks, and compute \(J^{\otimes b}\) in fewer than the usual \(b|J|^{b-1}\) calls to \(J\). Its tensor sectors give disjoint places to run copies of the comparison programs. The strict savings in every type leave room to spread these programs over fewer time slots while preserving each program’s order.

For a slot to be one call to \(J\), however, it must contain exactly the prescribed number of calls to each \(A_i\). Random start times will first keep all slot loads below these capacities. We then fill every vacancy with a call belonging to an identity word on separate coordinates. The construction must therefore provide both slack in each slot and enough unused coordinates for these identity words. We first choose block proportions that reserve enough identity space; the strict comparison savings will then supply the slot slack.

Proof. A shear adding a nonzero multiple of one coordinate into another is a monomial conjugate of \(U\oplus I\), so its price is one by [price:monomial-law,price:sum-law,price:normalization]. For an invertible pair matrix, first permute rows if needed to make its upper-left entry nonzero. With entries \(\alpha,\beta,\gamma,\delta\) and determinant \(D\ne0\), it factors as \[\begin{pmatrix}\alpha&\beta\\\gamma&\delta\end{pmatrix} =\begin{pmatrix}1&0\\\gamma/\alpha&1\end{pmatrix} \begin{pmatrix}\alpha&0\\0&D/\alpha\end{pmatrix} \begin{pmatrix}1&\beta/\alpha\\0&1\end{pmatrix}.\] This uses at most two nontrivial shears and a monomial. Finally an embedded call to \(A\) is a permutation conjugate of \(A\oplus I_{w-|A|}\), omitting the identity block when it has size zero, whose price is \(p(A)\). Repeated product subadditivity gives the word bound. Identity padding has price zero by direct-sum additivity. The last assertion is an exact matrix identity on all input coordinates; it does not assume zero scratch values. ◻

Proof. A finite DAG has finite depth and finite maximum fan-out, counting repeated operand edges and designated output uses. Apply 5 to this DAG with source coordinates \(x\), target coordinates \(y\), and one additional coordinate per gate, with arbitrary initial values. It gives at most \(8l+2a\) elementary shears realizing \((x,y,z)\mapsto(x,y+Gx,z)\). Although depth and fan-out may vary with the DAG, the shear count is independent of both; the layer bound is not needed here. By 11 and identity padding, this proves [corner:eq:shear-dag]. If only \(a_0\) rows are nonzero, apply the same replay to the submap of those rows, retaining all \(l\) gate coordinates, and identity-pad the omitted targets. This gives \(8l+2a_0\) instead; if \(a_0=0\), the shear is identity. ◻

Proof. Only the first \(t\) coefficients of \(f\) affect the matrix. Pad these coefficients and the input coefficient vector to a power-of-two length \(m\) with \(2t\le m<4t\). A length-\(m\) Fourier transform, multiplication by the prechosen Fourier transform of the fixed kernel, and an inverse Fourier transform compute their ordinary convolution, since its degree is at most \(2t-2<m\). Selecting the first \(t\) coefficients gives \(\mathcal T_t(f)\). The binary Fourier recursion splits even and odd indices and combines each pair by one scalar multiplication and two additions or subtractions, so it and its inverse use \(O(m\log(2m))\) permitted scalar gates. The frequency scalings and inverse normalization cost \(O(m)\) gates, even when some kernel frequencies are zero. This is a DAG construction and does not require those intermediate scalings to be invertible.

Exactly the same construction applies to the first \(t\) coefficients of \(1/f\), which exist because \(f(0)\ne0\). Apply [lem:shear-dag,corner:eq:two-way-bound] to these two DAGs. Every kernel coefficient and Fourier constant is prechosen; there is no charge for generating its description, but its multiplication on variable data has been included in the count. ◻

Proof. Write \(K=\begin{pmatrix}M&C\\0&D\end{pmatrix}\) and fix \(k\ge1\). The usual computation of \(Y=D^{\otimes k}\) on \(R=r^k\) bottom coordinates applies \(D\) along axes \(1,\ldots,k\), using \(u=kr^{k-1}\) calls. Replace each call by a \(K\) call, supplying a fresh group of \(n\) data coordinates for its \(M\) side. Since these groups are used only once and do not affect the bottom coordinates, the resulting matrix is \[\begin{pmatrix}I_u\otimes M&E\\0&Y\end{pmatrix}, \qquad p\left(\begin{pmatrix}I_u\otimes M&E\\0&Y\end{pmatrix}\right) \le u p(K).\] We will compress the \(u\) whole \(n\times R\) row blocks of \(EY^{-1}\). No independent change of its individual scalar rows is used.

Label a call by its axis \(j\) and fiber indices \(\mathbf i=(i_\ell)_{\ell\ne j}\). For \(1\le a\le n\) and a bottom multi-index \(\boldsymbol\ell=(\ell_1,\ldots,\ell_k)\), its row block \(R_{j,\mathbf i}\) in \(EY^{-1}\) has entries \[ (R_{j,\mathbf i})_{a,\boldsymbol\ell} =(CD^{-1})_{a,\ell_j} \prod_{h<j}\delta_{i_h,\ell_h} \prod_{h>j}(D^{-1})_{i_h,\ell_h}. \tag{42}\] To see this, the call’s contamination uses \(C\) at axis \(j\), with \(D\) already applied on axes \(h<j\) and identity on axes \(h>j\). Multiplication by \(Y^{-1}\) cancels the earlier \(D\) factors, leaves \(CD^{-1}\) locally, and introduces \(D^{-1}\) on the later axes.

For fixed \(j\), insertion of the fixed matrix \(CD^{-1}\) in the \(j\)th slot defines a linear map from the complementary tensor covector space to \(\mathop{\mathrm{Mat}}_{n\times R}(\mathbb C)\). The complementary covectors in [corner:eq:actual-row-block] form a basis, because every \(D^{-1}\) is invertible. Coordinate covectors form another basis. The images of either basis therefore span the same image space, whether or not this linear map is injective. Images of coordinate covectors have at most \(nr\) nonzero entries. Taking their union over \(j\) gives a sparse spanning family for the span \(S\) of all actual row blocks. Select a basis \(B_1,\ldots,B_h\) from this family; then \[h\le\min(u,nR),\qquad \mathop{\mathrm{nnz}}(B_i)\le nr.\] Overlaps between axis spans and dependencies among rows of \(C\) can only decrease \(h\).

The map \(\Phi:\mathbb C^u\longrightarrow S\) sending coefficients to their linear combination of the actual row blocks is surjective. Choose one lift of each \(B_i\) under \(\Phi\), and append a basis of \(\ker\Phi\). These \(u\) vectors form a basis of \(\mathbb C^u\): applying \(\Phi\) to a relation first kills the coefficients of the \(B_i\), and then independence in the kernel kills the others. Put these vectors as the rows of \(V\in\mathop{\mathrm{GL}}_u(\mathbb C)\). Postapply \(V\otimes I_n\) to the data groups. The data block becomes exactly \[(V\otimes I_n)(I_u\otimes M)=V\otimes M,\] while its contamination expressed in the final bottom variables is the stack \(B_1,\ldots,B_h,0,\ldots,0\). Cancel it by at most \(hnr\) elementary shears from those bottom variables into the data groups. The final map is exactly \((V\otimes M)\oplus Y\).

The previously proved price laws now give \[n p(V)+u p(M)+u p(D) \le u p(K)+n p(V)+hnr.\] The identical \(n p(V)\) terms cancel, without any estimate on \(V\). Since \(h\le nr^k\), division by \(u=kr^{k-1}\) yields \[p(M)+p(D)\le p(K)+\frac{n^2r^2}{k}.\] Let \(k\) tend to infinity with \(K,n,r\) fixed. This proves [corner:eq:triangular]. If \(r=1\), the same construction has \(R=1\), \(u=k\) and error at most \(n^2/k\). If \(S=0\), there are no \(B_i\) and a kernel basis alone supplies \(V\); no cancellation shears are needed. Empty diagonal blocks simply reduce to the other block. Exchanging the two groups proves the lower triangular case, and induction on the number of blocks proves the last assertion. ◻

Proof. If \(r=0\), the state is absent and \(H=M=K\) is constant. The exact tensor and direct-sum laws already give the assertion. Suppose \(r\ge1\) and introduce polynomial matrices and scalar polynomials \[\begin{gathered} a(z)=\det(I_r-zD),\qquad R(z)=\operatorname{adj}(I_r-zD),\\ F(z)=a(z)M+zCR(z)B,\qquad b(z)=\det F(z),\qquad J(z)=\operatorname{adj}F(z). \end{gathered}\] Then \(H=F/a\), \(H^{-1}=aJ/b\), \(a(0)=1\), and \(b(0)=\det M\ne0\). We have \[\deg a\le r,\quad\deg R\le r-1,\quad \deg F\le r,\quad\deg b\le nr,\quad\deg J\le(n-1)r.\] For \(n=1\) the adjugate \(J\) is the constant \(1\), as required by these formulas. Cancelling the later-axis responses in [corner:eq:state-response] gives \[H_k^{-1}E_j =(H^{-1})^{\otimes(j-1)}\otimes(JCR/b) \otimes I_n^{\otimes(k-j)}.\] Thus \(q_k=b^k\) clears the entire matrix \(H_k^{-1}E\). Its \(j\)th cleared block is the following explicit polynomial map \(W_j\to\mathbb C^N\): \[ Q_{k,j}(z) =a(z)^{j-1}b(z)^{k-j}\Bigl( J(z)^{\otimes(j-1)}\otimes\bigl(J(z)CR(z)\bigr) \otimes I_n^{\otimes(k-j)}\Bigr). \tag{46}\] Its degree is at most \[(j-1)r+(k-j)nr+(j-1)(n-1)r+(nr-1)=knr-1.\] The scalar \(q_k\) has degree at most \(knr\) and has nonzero constant term. The identities also hold when any of the displayed matrix polynomials vanish.

Here is an explicit DAG bound for the nonzero time coordinates of \(Q_k(z)w=\sum_{j=1}^kQ_{k,j}(z)w_j\). Put \(m=knr\), and choose \(m\) distinct complex evaluation points. Because [corner:eq:cleared-state] is polynomial, no avoidance of poles is needed. At one evaluation point, a rectangular application of \(JCR\) on its \(r\)-axis costs at most \(2rN\) scalar gates. Applying \(J\) on the preceding \(j-1\) axes costs at most \(2n(j-1)N\) gates, by doing the fixed \(n\times n\) map on all fibers of each axis. The scalar factor costs at most \(N\) gates. Adding the \(k\) contributions costs at most \((k-1)N\) more. One evaluation therefore uses at most \[\bigl(nk(k-1)+2(r+1)k-1\bigr)N=O_K(k^2N)\] gates. All local entries and scalar powers here are prechosen constants. Applying the inverse scalar Vandermonde matrix to the \(m\) evaluations, separately on each of the \(N\) coordinates, recovers all \(m\) coefficient vectors using at most \(2m^2N\) further scalar gates. The total is \(O_K((k+1)^3N)\). For any run length \(t\), keep only the first \(\min(t,m)\) coefficient vectors; all other rows of the truncated response are zero. This bound is consequently uniform in \(t\).

Set \(P=\mathcal T_t(1/q_k)\) and \(A'=A_{k,t}(P\otimes I_N)\). In formal series modulo \(z^t\), \(A'^{-1}E_t\) is precisely the coefficient map of \(q_kH_k^{-1}E=Q_k\) just constructed. Hence 13, with zero output rows omitted, bounds the price of the shear with block \(-A'^{-1}E_t\) by \(O_K((k+1)^3N)\). This uses only the rectangular shear law, not a price bound for an arbitrary invertible circuit output.

Now form the exact product \[ \mathcal K_{k,t} \begin{pmatrix}P\otimes I_N&0\\0&I\end{pmatrix} \begin{pmatrix}I&-A'^{-1}E_t\\0&I\end{pmatrix}. \tag{47}\] Its top row of blocks is \((A',0)\). Each factor is invertible, and \(A'\) is invertible because \(H(0)=M\) and \(q_k(0)\ne0\). Therefore the other diagonal block of this lower triangular product is also invertible. By 15 its price is at least \(p(A')\). There are \(tkn^{k-1}\) cell calls in \(\mathcal K_{k,t}\), so \[p(A')\le tkn^{k-1}p(K)+N p(P)+O_K((k+1)^3N).\] Here the tensor and direct-sum laws price the scalar preprocessing by \(Np(P)\), including its identity on the state. Finally \(A_{k,t}=A'(P^{-1}\otimes I_N)\) and inverse symmetry give \[p(A_{k,t})\le tkn^{k-1}p(K)+2Np(P)+O_K((k+1)^3N).\] Apply 14 to \(P\). Its bound is uniform even though \(q_k\) varies with \(k\), proving [corner:eq:cascade-bound]. ◻

Proof of 12. Independent row and column permutations move \(M\) to the top-left corner and preserve \(p(K)\). Write the resulting matrix as in [corner:eq:cell]. If the complementary width is zero the claim is equality; otherwise apply 16. The matrix \(A_{k,t}=\mathcal T_t(H^{\otimes k})\) is lower triangular in time with \(t\) identical diagonal blocks \(M^{\otimes k}\). Thus 15 and the tensor law imply \[p(A_{k,t})\ge t p(M^{\otimes k}) =tkn^{k-1}p(M).\] Fix \(K,n,r\) first and use the bound of [corner:eq:cascade-bound]. For example, choose \(t=t(k)=2^{\lceil8\log_2(k+1)\rceil}\), so \((k+1)^8\le t<2(k+1)^8\). Division by \(tkn^{k-1}=tkN/n\) gives \[p(M)\le p(K)+C_K n\left( \frac{\log(2t)}{k}+\frac{(k+1)^3}{tk}\right).\] Both errors tend to zero. The matrices \(M\) and \(K\) in this real inequality are fixed, so it proves the exact inequality \(p(M)\le p(K)\). No continuity assertion about the price, or limiting circuit for a matrix, has been used. A zero-size submatrix, if allowed, can simply be omitted and assigned price zero. ◻

Proof. \(G\) is an invertible square submatrix of \(\begin{pmatrix}I_m&G\\0&I_m\end{pmatrix}\), so 12 gives its first inequality, and 13 gives the second. Although the proof of the corner law fixed each individual matrix while taking a limit, the resulting inequality is exact for every finite matrix. The numerical constants here come entirely from the dirty scratch simulation. ◻

Proof. Choose once and for all polynomial \(J(z)\) and scalar polynomial \(u(z)\) such that \[G(z)^{-1}=J(z)/u(z),\qquad u(0)\ne0;\] for example, take \(J=\operatorname{adj}G\) and \(u=\det G\). Write \[G_k(z)=G(z)^{\otimes k}=\sum_{j=0}^{d}G_jz^j, \qquad J_k(z)=J(z)^{\otimes k}=\sum_{i=0}^{e}J_iz^i, \qquad e=k\deg J.\] These are degree bounds with zero coefficient matrices permitted. The subscript on \(G_j\) or \(J_i\) in this proof denotes a coefficient of the tensor power, rather than of the original fixed matrix. Both \(d\) and \(e\) are bounded by a fixed multiple of \(k\). If \(d=0\), multiplication is coefficientwise, so \(W=A_G\) and the result holds. Assume \(d>0\) and set \(T=t-d\).

Let \(L=W-A_G\). An input supported at times less than \(T\) has product with \(G_k\) of degree less than \(t\), so \(L\) has zero columns at those times. Scalar polynomial division also shows that, for every input \(x(z)\) of degree less than \(t\), \[ Lx=\ell(z)v_x(z)\pmod {z^t},\qquad \deg v_x<d. \tag{50}\] Here \(v_x\) is minus the quotient of \(G_kx\) by \(\ell\), with scalar division applied to every coordinate. The degree bound follows from \(\deg(G_kx)<t+d\).

The invertible relative map and the scalar prefix map are \[R=A_G^{-1}W=I+S,\qquad S=A_G^{-1}L, \qquad P=\mathcal T_T(u^k/\ell)\oplus I_d.\] The series in \(P\) is regular and nonzero at zero. Since \(S\) has zero prefix columns and \(P^{-1}\) is identity on the suffix of length \(d\), \[ S(P^{-1}\otimes I_N)=S,\qquad \widehat R=(P\otimes I_N)R(P^{-1}\otimes I_N) =I+(P\otimes I_N)S. \tag{51}\] This identity uses the entire prefix–suffix decomposition; a general scalar change of basis on all \(t\) times would not have this property.

On the prefix, the output of the correction in [feedback:eq:prefix-conjugation] is, modulo \(z^T\), \[\frac{u^k}{\ell}\frac{J_k}{u^k}\ell v_x=J_kv_x.\] It therefore vanishes at prefix times greater than or equal to \(e+d\). Define the disjoint sets \[\mathcal E=\{0,\ldots,\min(T,e+d)-1\},\quad \mathcal B=\{T,\ldots,t-1\},\quad \mathcal U=\mathcal E\cup\mathcal B.\] The correction has columns only in \(\mathcal B\) and rows only in \(\mathcal U\), where \(|\mathcal U|\leq e+2d=O(k)\). Thus both blocks coupling \(\mathcal U\) to its complement are zero in the correction. A simultaneous permutation of rows and columns gives \[ \widehat R\simeq R_{\mathcal U}\oplus I_{(t-|\mathcal U|)N}, \qquad R_{\mathcal U}\in\mathop{\mathrm{GL}}_{|\mathcal U|N}(\mathbb C). \tag{52}\] Invertibility of the active block follows from invertibility of \(\widehat R\). If the coarse early and suffix ranges would overlap, the minimum in \(\mathcal E\) truncates the former: the middle set is then empty and \(t\leq e+2d\). The bound and the direct-sum conclusion still hold. 3 displays the support of the correction \(\widehat R-I\) when the middle set is nonempty.

The small number of active times alone would not bound the cost of their \(N\times N\) spatial blocks. We next give an indexed formula that controls those blocks uniformly. For each integer \(m\geq0\) that occurs below, divide the scalar monomial \(z^m\) by \(\ell\) and write \[z^m=\ell(z)q_m(z)+r_m(z),\qquad \deg r_m<t, \qquad q_{s,m}=[z^s]q_m(z).\] For \(m=b+j\) with \(0\leq b<t\) and \(0\leq j\leq d\), we have \(\deg q_m<d\). Set \(q_{s,m}=0\) when \(s<0\) or \(s\geq d\); also \(q_m=0\) when \(m<t\). Let \[\eta_h=[z^h](\ell/u^k),\qquad \eta_h=0\quad(h<0).\] All these scalars may depend on \(k,t,\ell\). For \(0\leq a,b<t\), define \[ \gamma_{abij}= \begin{cases} -q_{a-i,b+j},&a<T,\\[2pt] -\displaystyle\sum_{s=0}^{d-1}\eta_{a-i-s}q_{s,b+j},&a\geq T. \end{cases} \tag{53}\] Then the exact block formula is \[ \widehat R_{ab}=\delta_{ab}I_N+ \sum_{i=0}^{e}\sum_{j=0}^{d}\gamma_{abij}J_iG_j. \tag{54}\] Indeed, on an input \(z^bx_b\), scalar division gives \(v_x=-\sum_jq_{b+j}G_jx_b\) in [feedback:eq:boundary-quotient]. The prefix correction is \(J_kv_x\), which gives the first case of [feedback:eq:ordered-coefficients]. The suffix is unchanged by the left prefix map, so its correction is \((\ell/u^k)J_kv_x\) modulo \(z^t\), which gives the second case. Right conjugation has already disappeared by [feedback:eq:prefix-conjugation]. Every spatial product is ordered as \(J_iG_j\): no commutation of coefficient matrices is used. Reduction and scalar convolution introduce only the displayed scalar weights, irrespective of the length of the underlying coefficient lists.

Here is a gate count for applying the active block. Applying a fixed \(n\times n\) matrix on each of the \(N/n\) fibers of one tensor axis uses at most \(2nN\) scalar gates, by direct multiplication and addition. Consequently \(G(\xi)^{\otimes k}\) applies in at most \(2nkN\) gates for any \(\xi\in\mathbb C\), including points where \(G(\xi)\) is singular. At \(d+1\) distinct points, interpolation expresses any chosen coefficient \(G_j\) as a scalar linear combination of these evaluation matrices. Running the \(d+1\) evaluation circuits on the same input and combining their outputs uses at most \[2nkN(d+1)+2(d+1)N=O_G((k+1)^2N)\] gates. The same argument with \(e+1\) points applies to \(J_i\), so the ordered product \(J_iG_j\) has a circuit of this order by composition. No inverse of an evaluation matrix is needed; only the scalar Vandermonde interpolation matrix is inverted in choosing constants.

There are \(O_G((k+1)^2)\) active ordered pairs of time indices and \((e+1)(d+1)=O_G((k+1)^2)\) spatial generators in [feedback:eq:ordered-span]. For each active block entry, apply each required generator to its input vector, multiply its output by \(\gamma_{abij}\), and add the resulting vectors. The generator applications cost \(O_G((k+1)^6N)\) gates in total. The scalar weights and output additions cost only \(O_G((k+1)^4N)\) additional gates, and the identity contribution uses the already available input values. The output count is \(|\mathcal U|N=O_G((k+1)N)\). Thus the universal one-way DAG bound, 17, and [feedback:eq:active-summand] give \[ p(\widehat R)=p(R_{\mathcal U}) \leq C_G(k+1)^6N. \tag{55}\] The potentially complicated coefficients in [feedback:eq:ordered-coefficients] are prechosen circuit scalars. Every use of such a scalar has been charged; the model does not charge for producing its description. This is precisely why the gate bound is independent of \(t\) and \(\ell\).

By 14, direct-sum additivity and the tensor law, \[p(P)=O(T\log(2T))=O(t\log(2t)),\qquad p(P\otimes I_N)=Np(P).\] Undoing the conjugation and using inverse symmetry gives \[p(R)=p(R^{-1})\leq2Np(P)+C_G(k+1)^6N.\] Finally \(W=A_GR\) and \(A_G=WR^{-1}\) imply \(|p(W)-p(A_G)|\leq p(R)\), proving [feedback:eq:boundary-error]. Dividing that bound by \(tkN\) gives \[ \frac{|p(W)-p(A_G)|}{tkN} \leq C_G\left(\frac{\log(2t)}{k} +\frac{(k+1)^6}{tk}\right). \tag{56}\] For the choice of \(t\) in [feedback:eq:common-length], both terms tend to zero. Also \(t>d\) eventually, since \(G\) was fixed before \(k\) grows. Every estimate holds uniformly for all admissible \(\ell\) at that \(k,t\). ◻

Proof. If there is no state block, \(H=M=K\). With a state block present, \(s_0=0\) is the invertible corner law, 12. We prove the claim for \(s_0\ne0\) by fixing \(K,s_0\) throughout the following estimates. Let \[q(z)=\det(I_r-zD),\qquad G(z)=q(z)M+zC\operatorname{adj}(I_r-zD)B=q(z)H(z).\] Then \(G\) is polynomial, \(q(0)=1\), \(q(s_0)\ne0\) and \(G(0)=M\) is invertible. Put \(N=n^k\) and choose \(t=t(k)\) as in [feedback:eq:common-length]. For sufficiently large \(k\), this choice meets the degree condition in 18.

Write \(A_H=\mathcal T_t(H(z)^{\otimes k})\). The cascade estimate in [corner:eq:cascade-bound] gives, with constants depending only on the fixed cell, \[ p(A_H)\leq tk n^{k-1}p(K) +C_KN\bigl(t\log(2t)+(k+1)^3\bigr). \tag{58}\] Moreover, \[A_G=(\mathcal T_t(q^k)\otimes I_N)A_H,\] and the scalar factor is invertible. The scalar-convolution bound and the product law in both directions show that \[ |p(A_G)-p(A_H)|\leq C N t\log(2t). \tag{59}\] Its constant is independent of the degree or coefficients of \(q^k\).

Apply the coefficient-boundary comparison with \(\ell(z)=(z-s_0)^t\). To verify its remaining invertibility hypothesis, translate a polynomial to its coefficients at \(s_0\). The scalar translation matrix \(V_{s_0}\) has entries \[(V_{s_0})_{ij}= \begin{cases}\binom ji s_0^{j-i},&j\geq i,\\0,&j<i, \end{cases} \qquad 0\leq i,j<t.\] It is invertible with inverse \(V_{-s_0}\). In the translated coordinates, multiplication modulo \((z-s_0)^t\) becomes multiplication by \(G(s_0+w)^{\otimes k}\) modulo \(w^t\). Hence \[ (V_{s_0}\otimes I_N)W(V_{s_0}^{-1}\otimes I_N) =\mathcal T_t(G(s_0+w)^{\otimes k}). \tag{60}\] The right-hand side is lower triangular in time, with repeated invertible diagonal block \(G(s_0)^{\otimes k}\). Thus \(W\) is invertible, as required.

The price of translation is also small. If \(D_!=\mathop{\mathrm{diag}}(0!,1!,\ldots, (t-1)!)\) and \(U_{s_0}\) is the upper triangular Toeplitz matrix with entry \(s_0^{j-i}/(j-i)!\) at \(j\geq i\), then \[V_{s_0}=D_!^{-1}U_{s_0}D_!.\] Monomial invariance, transpose symmetry and 14 imply \[ p(V_{s_0})=O(t\log(2t)). \tag{61}\] Applying triangular monotonicity, 15, to [feedback:eq:taylor-conjugacy], then undoing its two scalar changes of basis, gives \[\begin{align*} p(W) &\geq t\,p(G(s_0)^{\otimes k})-2Np(V_{s_0})\\ &=tk n^{k-1}p(H(s_0))-O(Nt\log(2t)). \tag{62}\end{align*}\] For the equality, use the tensor law and the nonzero scalar relation \(G(s_0)=q(s_0)H(s_0)\), which preserves price.

Combining [feedback:eq:boundary-error,feedback:eq:cascade-use,feedback:eq:clear-denominator-cost,feedback:eq:feedback-lower] yields \[tk n^{k-1}\bigl(p(H(s_0))-p(K)\bigr) \leq C_{K,s_0}N\bigl(t\log(2t)+(k+1)^6\bigr).\] Divide by \(tk n^{k-1}=tkN/n\) and let \(k\) tend to infinity with the single fixed choice of \(t\) in [feedback:eq:common-length]. The error vanishes by [feedback:eq:normalized-error], proving [feedback:eq:feedback-law]. ◻

Proof. Replace \(X(z)\) by \(X(z_0+z)\) and \(E\) by \(E-z_0\), so it suffices to treat \(z_0=0\). By regularity, the entries have polynomial denominator representations nonzero at zero. Their product gives a scalar polynomial \(q\) with \(q(0)\ne0\) for which \(G=qX\) is polynomial. In particular \(G(0)\) is invertible. Enlarge the finite exceptional set to \[E'=E\cup\{s:q(s)=0\}.\] At every \(s\notin E'\), the matrix \(G(s)\) is invertible and \(p(G(s))=p(X(s))\leq C_0\).

Fix \(X,q,E'\) before letting \(k\) grow, put \(N=n^k\), and again choose the single run length specified in [feedback:eq:common-length]. For each such finite \(t\), let \(\zeta_t\) be the specified primitive \(t\)th root of unity. Choose \[ a=a_k\notin \{0\}\cup\bigcup_{h=0}^{t-1}\zeta_t^{-h}E'. \tag{63}\] Only finitely many complex numbers are forbidden, so this choice exists for every \(k\). No fixed dilation is asserted to work for all \(k\), and no bound on \(a_k\) is needed. The polynomial \[\ell(z)=z^t-a^t\] has nonzero constant term and distinct roots \(s_h=a\zeta_t^h\), all outside \(E'\). Let \(W\) be multiplication by \(G_k\) modulo this polynomial. Scalar evaluation at the roots has matrix \[V_a=(s_h^j)_{0\leq h,j<t} =F_t\mathop{\mathrm{diag}}(1,a,\ldots,a^{t-1}).\] The roots are distinct, so this matrix is invertible, and evaluation gives the exact conjugacy \[ (V_a\otimes I_N)W(V_a^{-1}\otimes I_N) =\bigoplus_{h=0}^{t-1}G(s_h)^{\otimes k}. \tag{64}\] This also proves that \(W\) is invertible.

Since \(t\) is a power of two, the binary FFT computes \(F_t\) with \(O(t\log(2t))\) scalar gates. The universal DAG-price bound and monomial invariance therefore give \[p(V_a)=p(F_t)=O(t\log(2t)),\] uniformly in \(a\). The direct-sum and tensor laws applied to [feedback:eq:root-evaluation] imply \[\begin{align*} p(W) &\leq\sum_{h=0}^{t-1}p(G(s_h)^{\otimes k})+2Np(V_a)\\ &\leq tk n^{k-1}C_0+O(Nt\log(2t)). \tag{65}\end{align*}\] On the other hand, \(A_G=\mathcal T_t(G_k)\) is lower triangular with diagonal \(G(0)^{\otimes k}\) repeated \(t\) times. Thus \[ p(A_G)\geq tk n^{k-1}p(G(0)) =tk n^{k-1}p(X(0)). \tag{66}\] For sufficiently large \(k\) the degree condition of 18 holds. Its uniform estimate applies to the modulus just chosen, even though \(a=a_k\) can vary. Combining it with [feedback:eq:specialization-upper,feedback:eq:specialization-lower] and dividing by \(tkN/n\) proves \[p(X(0))\leq C_0+ C_X\left(\frac{\log(2t)}{k}+\frac{(k+1)^6}{tk}\right).\] Letting \(k\) tend to infinity proves the assertion. ◻

Proof. Solving \(z_{\rm out}=Bx+Dz_{\rm in}\) gives the displayed formula. Its determinant is \(\det A/\det D\), as follows by taking the Schur complement of \(D^{-1}\), so it is invertible. Both pivot hypotheses are relevant: \(D\) makes the solve possible, whereas \(A\) makes its resulting transition invertible.

We realize this solve as a feedback operation to which 19 applies. Use data \((x,y)\) of widths \(n,r\) and state \(z\) of width \(r\). First apply, separately on the \(r\) pairs \((y_i,z_i)\), the matrix \[P_\beta=\begin{pmatrix}\beta&1\\1&1\end{pmatrix}, \qquad (\widehat y,z_{\rm in})=(\beta y+z,y+z).\] Next apply \(K\) on \((x,z_{\rm in})\), leaving \(\widehat y\) fixed. Finally apply \[Q_\beta=\begin{pmatrix}1&1-\beta\\1&-\beta\end{pmatrix} \quad\hbox{on each pair }(\widehat y_i,z_{{\rm out},i}),\] with outputs \((y',z')\). The full cell, denoted \(\mathcal K_\beta\), sends \((x,y,z)\) to \((x',y',z')\). Since \(\det P_\beta=\beta-1\) and \(\det Q_\beta=-1\), it is invertible whenever \(\beta\ne1\), and \[ p(\mathcal K_\beta)\le p(K)+4r. \tag{68}\] The blocks of this cell with respect to its data/state split are \[ \mathcal K_\beta= \left( \begin{array}{cc|c} A&C&C\\ (1-\beta)B&\beta I_r+(1-\beta)D&I_r+(1-\beta)D\\ \hline -\beta B&\beta(I_r-D)&I_r-\beta D \end{array} \right). \tag{69}\] Its direct data block \[M_\beta= \begin{pmatrix}A&C\\(1-\beta)B&\beta I_r+(1-\beta)D\end{pmatrix}\] has polynomial determinant and satisfies \(M_0=K\). Thus the precise genericity requirement is \[ \beta\notin\{0,1\}\cup \{b\in\mathbb C:\det M_b=0\}. \tag{70}\] This excludes only finitely many numbers and hence allows a choice of \(\beta\). At feedback parameter one, the feedback denominator is \(I_r-(I_r-\beta D)=\beta D\), which is invertible.

Indeed, closing the state by \(z=z'\) in \(z'=\beta y+z-\beta z_{\rm out}\) forces \(z_{\rm out}=y\). Consequently \[y'=\beta y+z+(1-\beta)z_{\rm out}=y+z=z_{\rm in}.\] The feedback output map on \((x,y)\) is therefore exactly \(\widetilde K\), already proved invertible. The full cell, its direct block, its feedback denominator, and its output all meet the hypotheses of 19. That Theorem and [pivot:eq:cell-price] prove the inequality. ◻

Proof. Let the shared coordinate occupy port \(i_0\) of \(Y_1\) and port \(j_0\) of \(Y_2\). Index the tensor grid by \((i,j)\in\{1,\ldots,a\}\times\{1,\ldots,b\}\). The usual word for \(Y_1\otimes Y_2\) first applies \(Y_1\) along each fiber with fixed \(j\), and then \(Y_2\) along each fiber with fixed \(i\). Calls within either stage have disjoint coordinate sets, so put the \(j=j_0\) call last in the first stage and the \(i=i_0\) call first in the second stage. These two consecutive calls have the prescribed port identification: send port \(i\) of \(Y_1\) to \((i,j_0)\) and port \(j\) of \(Y_2\) to \((i_0,j)\). 4 shows the selected fibers of this consecutive call pair and their single shared coordinate.

Their union has \(a+b-1\) coordinates. On all other grid coordinates their product is identity, so the consecutive subproduct is a permutation conjugate of \[P\oplus I_{ab-(a+b-1)} =P\oplus I_{(a-1)(b-1)}.\] The exact direct-sum law makes its price \(p(P)\), even when this padding is empty. Grouping these two calls in the tensor word yields \[b\,p(Y_1)+a\,p(Y_2) =p(Y_1\otimes Y_2) \le (b-1)p(Y_1)+(a-1)p(Y_2)+p(P).\] Thus \(p(P)\ge p(Y_1)+p(Y_2)\). Product subadditivity applied to the two identity-padded calls gives the reverse inequality. ◻

Proof. Write \(D=d\ne0\). For each positive integer \(\ell\), use \(\ell\) copies of \(K\), with fresh data groups \(x_1,\ldots,x_\ell\) of width \(n\) and one shared state coordinate. In chronological order the recurrences are \[ y_j=Ax_j+Cw_{j-1},\qquad w_j=Bx_j+dw_{j-1},\qquad 1\le j\le\ell. \tag{71}\] Let \(\mathcal C_\ell\) send \((x_1,\ldots,x_\ell,w_0)\) to \((y_1,\ldots,y_\ell,w_\ell)\). At every extension the previous chain is regarded as a matrix only on its old data groups and its one state coordinate. The next data group is outside this set, so the intersection with the next call is exactly the one state coordinate. Coordinates fixed by the old chain remain members of its old set; no padding from the tensor-grid proof is added to it. Induction using 22 gives \[ p(\mathcal C_\ell)=\ell p(K). \tag{72}\]

The full chain is invertible as a product of invertible calls. Its state-to-state block is \(d^\ell\), and its direct block on the data is lower block triangular with diagonal blocks \(A\). In fact its \((j,i)\) block for \(i<j\) is \(Cd^{j-1-i}B\), and its blocks for \(i>j\) vanish. Both blocks required by 21 are therefore invertible for every \(\ell\).

Pivoting the boundary state means that \(w_\ell\) is given and \(w_0\) is requested. The exact backward recurrence is \[ w_{j-1}=d^{-1}w_j-d^{-1}Bx_j,\qquad y_j=(A-Cd^{-1}B)x_j+Cd^{-1}w_j. \tag{73}\] Thus the pivoted chain \(\widetilde{\mathcal C}_\ell\) consists of copies of \(\widetilde K\) in the order \(j=\ell,\ldots,1\), again with fresh data groups and one shared state. The same intersection argument gives \[ p(\widetilde{\mathcal C}_\ell)=\ell p(\widetilde K). \tag{74}\] Put \(S=A-Cd^{-1}B\). Since \(\det K=d\det S\), the matrix \(S\) is invertible. The reverse chain has state block \(d^{-\ell}\) and a direct data block upper triangular in chronological order, with diagonal blocks \(S\); equivalently it is lower triangular in reverse chronological order. Its full matrix is invertible too. Hence 21 applies both to the forward chain and to the reverse chain. Pivoting the reverse chain returns the forward chain, and therefore \[\ell p(\widetilde K)\le\ell p(K)+4, \qquad \ell p(K)\le\ell p(\widetilde K)+4.\] Equivalently, \(|p(\widetilde K)-p(K)|\le4/\ell\) for every \(\ell\). Letting \(\ell\) tend to infinity proves equality. The earlier pivot inequality is an exact statement for each finite matrix, so this argument requires no estimate uniform in the increasing data width. ◻

Proof. Relative to \(U\), the coefficient matrices of \(U'\) and \(V'\) are \[\begin{pmatrix}I_n&0\\ B&d\end{pmatrix},\qquad \begin{pmatrix}A&C\\0&1\end{pmatrix},\] with determinants \(d\) and \(\det A\), respectively. These give the asserted criterion exactly. When both are nonzero, the transition between them is [pivot:eq:pivot-matrix] with scalar pivot. Apply 23. Reorderings have zero price. ◻

Proof. For a pair matrix \(H\), the tensor law reads \(p(H\otimes H)=4p(H)\). We therefore seek a four-coordinate map of price at most six that becomes a tensor square after monomial changes. Two shears and the basis exchanges below put this map into the form of a rank-one perturbation of the identity, making the required monomial changes explicit.

Fix \(\lambda\in\mathbb C\setminus\{0,1\}\) and four independent linear forms \(a,b,c,d\). We first bound the transition from \[Y^{(0)}=(a,b,c,d)\quad\hbox{to}\quad X=(a+b,b+c,c+d,d+\lambda a).\] Its matrix is \(I_4+J\), where \[J=\begin{pmatrix} 0&1&0&0\\0&0&1&0\\0&0&0&1\\\lambda&0&0&0 \end{pmatrix},\qquad J^4=\lambda I_4.\] Here \(J\) is monomial because \(\lambda\ne0\), and \[(I_4+J)(I_4-J+J^2-J^3)=(1-\lambda)I_4\] shows that \(I_4+J\) is invertible. Apply 19 at parameter one to \[\mathcal L=\begin{pmatrix}I_4&J\\I_4&0\end{pmatrix}.\] This full cell is invertible, its direct block and feedback denominator are identities, and its output is \(I_4+J\). To implement \(\mathcal L\), send \((h,l)\) to \((h,Jl)\) by a monomial, add \(h_i\) into the second coordinate of each of the four pairs, and swap the two blocks. Consequently \[ p(I_4+J)\le p(\mathcal L)\le4. \tag{76}\]

We change the first and third members on the \(Y\) side using two shears and legal exchanges. For clarity, all intermediate lists are displayed below. Put \[X_b=(a+b,b,c+d,d+\lambda a),\qquad X_d=(a+b,b+c,c+d,d).\] Every determinant in the last two columns is computed from the coefficient rows in the original ordered basis \((a,b,c,d)\).

The steps \(0\to1\) and \(2\to3\) exchange the second members; the steps \(3\to4\) and \(5\to6\) exchange the fourth members. The step \(1\to2\) adds the second member of \(Y\) into its first, and \(4\to5\) adds its fourth member into its third. These are the only two shears. The determinant table proves that every list is a basis, including on both sides of every exchange; it follows also by direct elementary row operations. Thus 24 applies at all four exchanges. Changing the source basis from \(Y\) to \(EY\) by a shear replaces its transition matrix \(T\) by \(TE^{-1}\), increasing price by at most one. Together with [pivot:eq:four-start], this proves that the transition from the last \(Y\) list to \(X\) has price at most six.

Reorder these final lists as \[\overline Y=(a+b+c,b,d,c+d+\lambda a),\qquad \overline X=(b+c,b+a,d+\lambda a,c+d).\] Let \[k=(1,-1,1,-1)^{\mathsf T},\qquad \Delta=(-1,1,\lambda,-\lambda)^{\mathsf T}.\] Then \(k^{\mathsf T}\overline Y=(1-\lambda)a\) and \(\overline X-\overline Y=\Delta a\), so the transition matrix is the explicit rank-one perturbation \[ T=I_4+\frac{\Delta k^{\mathsf T}}{1-\lambda}, \qquad p(T)\le6. \tag{77}\]

We now give the diagonal scalings. All their entries are nonzero under the stated hypotheses on \(\lambda\). Set \(u=\lambda^{-1}\) and \[L_1=\mathop{\mathrm{diag}}\left(\frac{1-\lambda}{\Delta_1}, \frac{1-\lambda}{\Delta_2}, \frac{1-\lambda}{\Delta_3}, \frac{1-\lambda}{\Delta_4}\right),\qquad R_1=\mathop{\mathrm{diag}}(1,-1,1,-1).\] The rank-one summand of \(L_1TR_1\) has every entry equal to one, and a direct calculation gives \[L_1TR_1= \begin{pmatrix} \lambda&1&1&1\\1&\lambda&1&1\\ 1&1&u&1\\1&1&1&u \end{pmatrix}.\] With the further scalings \[L_2=\mathop{\mathrm{diag}}(u,u,u,1),\qquad R_2=\mathop{\mathrm{diag}}(1,1,1,\lambda),\] we obtain \[ L_2L_1TR_1R_2= \begin{pmatrix} 1&u&u&1\\u&1&u&1\\u&u&u^2&1\\1&1&1&1 \end{pmatrix}. \tag{78}\] Write \(B(u)=\left(\begin{smallmatrix}1&1\\1&u\end{smallmatrix}\right)\). The \((\alpha,\gamma)\) entry of \(B(u)\otimes B(u)\), for bit pairs \(\alpha,\gamma\in\{0,1\}^2\), is \(u^{\alpha_1\gamma_1+\alpha_2\gamma_2}\). Ordering its rows by \(10,01,11,00\) and its columns by \(01,10,11,00\) gives exactly [pivot:eq:tensor-rescaling]. All the scalings and permutations preserve price. The tensor law therefore yields \[4p(B(u))=p(B(u)\otimes B(u))=p(T)\le6.\] Every \(u\ne0,1\) arises from the permitted choice \(\lambda=1/u\), proving [pivot:eq:pair-bound].

Finally, if \(H=\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)\) is dense and invertible, then \[\mathop{\mathrm{diag}}(a^{-1},c^{-1})\,H\,\mathop{\mathrm{diag}}(1,a/b) =B\left(\frac{ad}{bc}\right).\] Density makes \(ad/(bc)\ne0\), and invertibility makes it different from one. Monomial invariance completes the proof. ◻

Proof. We have \(T_1=U\), so \(p(T_1)=1\). Put \(n=2^m\) and consider the transition from input forms \(x=(x_1,\ldots,x_{2n})\) to output forms \(y=K_0x\), where \[K_0=U\otimes T_m =\begin{pmatrix}T_m&0\\ T_m&T_m\end{pmatrix}.\] We shall exchange each bottom input form with the corresponding bottom output form, using only the exact scalar pivot law of 23. Here is a determinant check for every intermediate exchange.

For any subset \(H\subseteq\{n+1,\ldots,2n\}\) of already exchanged positions, keep the forms in their original index positions and set \[u_i=\begin{cases}y_i&i\in H,\\x_i&i\notin H,\end{cases} \qquad v_i=\begin{cases}x_i&i\in H,\\y_i&i\notin H.\end{cases}\] Let \(U_H,V_H\) be their coefficient matrices relative to \(x\). Simultaneously permuting rows and columns to put \(H\) first gives \[U_H\sim \begin{pmatrix}K_0[H,H]&K_0[H,H^c]\\0&I\end{pmatrix},\qquad V_H\sim \begin{pmatrix}I&0\\K_0[H^c,H]&K_0[H^c,H^c]\end{pmatrix}.\] The row and column permutation signs cancel. Every principal submatrix of the unit lower triangular matrix \(K_0\) is unit lower triangular, so \[ \det U_H=\det K_0[H,H]=1, \qquad \det V_H=\det K_0[H^c,H^c]=1. \tag{80}\] The empty principal minor, when it occurs, has determinant one. Thus both lists are bases and their current transition \(Q_H=V_HU_H^{-1}\) has determinant one.

For the next index \(j\notin H\) in the bottom half, replacing \(u_j\) by \(v_j\) changes the input determinant by the factor \((Q_H)_{jj}\). Replacing \(v_j\) by \(u_j\) changes the output determinant by \((Q_H^{-1})_{jj}\). Applying (80) to \(H\) and \(H\cup\{j\}\) therefore gives \[(Q_H)_{jj}=\frac{\det U_{H\cup\{j\}}}{\det U_H}=1, \qquad (Q_H^{-1})_{jj}=\frac{\det V_{H\cup\{j\}}}{\det V_H}=1.\] Move position \(j\) to the last port in both bases. The scalar diagonal block required for the pivot is consequently one; the determinant of its complementary principal block is, by the cofactor identity, \[\det Q_H\,(Q_H^{-1})_{jj}=1.\] Both hypotheses of 23 hold at every step, and each exchange preserves the price exactly.

After all bottom positions have been exchanged, write the original inputs as \((a,b)\) and the bottom output as \(z=T_ma+T_mb\). Solving gives \(b=T_m^{-1}z-a\). Thus the final transition, from \((a,z)\) to \((T_ma,b)\), is \[\begin{pmatrix}T_m&0\\-I&T_m^{-1}\end{pmatrix}.\] Conjugating by \(\mathop{\mathrm{diag}}(I,-I)\) changes the lower left block to \(I\); the result is \(T_{m+1}\) by (79). Monomial invariance and the tensor law now give \[p(T_{m+1})=p(U\otimes T_m)=2^m+2p(T_m),\] which proves the formula by induction. ◻

Proof. Write \(e_{ij}\) for matrix units, and fix any order of the supported pairs. Form the polynomial matrix \[ K(\varepsilon)=\left(I+\varepsilon\mathop{\mathrm{diag}}(A_{11},\ldots,A_{ww})\right) \prod_{\substack{i<j\\A_{ij}\ne0}} \left(I+\varepsilon A_{ij}(e_{ij}+e_{ji})\right). \tag{88}\] Then \(K(0)=I\) and \(K'(0)=A\). Outside a finite set \(E_0\), the diagonal factor is an invertible monomial and every other factor acts on its two coordinates as the dense invertible matrix \[\begin{pmatrix}1&\varepsilon A_{ij}\\\varepsilon A_{ij}&1\end{pmatrix}.\] For example, \(E_0\) may contain zero, the roots of the diagonal-factor determinant, and all roots of \(1-\varepsilon^2A_{ij}^2\) for the supported pairs. These are finitely many roots of nonzero polynomials. By 25, direct sums, and product subadditivity, \[ p(K(\varepsilon))\leq \frac32h\qquad(\varepsilon\notin E_0). \tag{89}\]

Put \(Q(\varepsilon)=(K(\varepsilon)-I)/\varepsilon\), with its polynomial extension \(Q(0)=A\). First fix a parameter \(t\) outside the single finite set \[ \mathcal E=\{0\}\cup \{\lambda^{-1},-\lambda^{-1}: \lambda\in\operatorname{spec}(A),\ \lambda\ne0\}. \tag{90}\] The polynomial matrices \[C_+(\varepsilon)=I+tQ(\varepsilon),\qquad C_-(\varepsilon)=I-tQ(\varepsilon)\] have nonzero determinants at zero, since \(I\pm tA\) are invertible. Consequently the rational output \[H_t(\varepsilon)=C_+(\varepsilon)C_-(\varepsilon)^{-1}\] is regular and invertible at zero.

For this fixed \(t\), exclude also \(\varepsilon=0,t,-t\) and the roots of \(\det C_+(\varepsilon)\det C_-(\varepsilon)\), in addition to \(E_0\). This defines a finite set \(E_t\), which may depend on \(t\). For \(\varepsilon\notin E_t\) define \[m=\frac{\varepsilon-t}{\varepsilon+t},\qquad s=\frac{t}{\varepsilon+t},\qquad v=\frac{2\varepsilon t}{(\varepsilon+t)^2},\] and consider the data–state cell \[ F_{t,\varepsilon}= \begin{pmatrix}mI_w&K(\varepsilon)\\vI_w&sK(\varepsilon)\end{pmatrix} =\begin{pmatrix}mI_w&I_w\\vI_w&sI_w\end{pmatrix} \mathop{\mathrm{diag}}(I_w,K(\varepsilon)). \tag{91}\] The first factor is a direct sum, after reordering, of \(w\) scalar pair matrices. Their determinants are \[ms-v=-\frac{t}{\varepsilon+t}\ne0.\] Hence the cell is invertible. Its direct block \(mI_w\) is invertible, and its feedback denominator at feedback parameter one satisfies \[ I_w-sK(\varepsilon)=\frac{\varepsilon}{\varepsilon+t}C_-(\varepsilon), \tag{92}\] so that denominator is invertible too. Its feedback output is exactly \[\begin{align*} mI_w+K(\varepsilon)(I_w-sK(\varepsilon))^{-1}v &=\bigl(mI_w+(v-ms)K(\varepsilon)\bigr) (I_w-sK(\varepsilon))^{-1}\\ &=C_+(\varepsilon)C_-(\varepsilon)^{-1}=H_t(\varepsilon). \end{align*}\] The last equality follows from \(mI_w+(v-ms)K(\varepsilon)=\varepsilon C_+(\varepsilon)/(\varepsilon+t)\). The output is invertible by the choice of \(E_t\), so every hypothesis of 19 is satisfied.

An invertible scalar pair has price at most two. The factorization (91) and (89) therefore imply \[p(H_t(\varepsilon))\leq p(F_{t,\varepsilon}) \leq p(K(\varepsilon))+2w \leq \frac32h+2w \qquad(\varepsilon\notin E_t).\] Apply 20 to the rational matrix \(H_t\) at \(\varepsilon=0\). This proves \[ p\bigl((I+tA)(I-tA)^{-1}\bigr)\leq C_A, \qquad C_A=\frac32h+2w, \qquad t\notin\mathcal E. \tag{93}\] The quantifiers here are useful: \(A,w,h\) and \(C_A\) were fixed first; for each \(t\notin\mathcal E\) there is a finite \(E_t\) giving the same bound, and specialization is applied separately for that \(t\). Thus (93) holds for every \(t\) outside one finite set, with one price bound. Only the rational output is specialized. At \(\varepsilon=0\) the cell itself would have \(m=-1\), \(s=1\), \(v=0\), and \(K=I\), making its feedback denominator zero; no feedback law is applied to that cell.

For the second specialization use \(z=1/t\) and the rational matrix \[Y(z)=(zI_w+A)(zI_w-A)^{-1}.\] By the Real Spectral Theorem, \(A=O\mathop{\mathrm{diag}}(\lambda_1,\ldots,\lambda_w) O^{\mathsf T}\) for a real orthogonal \(O\) and real eigenvalues \(\lambda_i\). In this basis, the corresponding rational functions are \((z+\lambda_i)/(z-\lambda_i)\). If \(\lambda_i=0\), this function is identically one after cancellation; if \(\lambda_i\ne0\), it is regular at zero with value minus one. It follows that \(Y\) is regular at zero and \(Y(0)=R\), an invertible matrix. In particular, the zero eigenspace is semisimple; real symmetry supplies exactly the diagonalizability needed for this removable-singularity assertion.

For all \(z\) outside \(\{0\}\cup\{\lambda,-\lambda:\lambda\in\operatorname{spec}(A), \lambda\ne0\}\), we may take \(t=1/z\) in (93). Hence \(p(Y(z))\leq C_A\) outside a finite set. A second application of 20 yields \(p(R)\leq C_A\). The orthogonal diagonalization was used to identify a rational matrix and its value; it was not used as a priced implementation. Neither specialization assumes continuity of \(p\). ◻

Proof. If there were no finite win, the preceding construction and all its price bounds would apply for every fixed integer \(d\geq1\). Equations (94) and (100) would imply \[dw\leq\left(\frac{3d}{4}+\frac{15}{2}\right)w.\] Since \(w>0\), this says \(d\leq30\), contrary to choosing any fixed integer \(d>30\). This contradiction proves the theorem. ◻