Proof. The first two rows subtract \(JA+Rc\) from \(y\). The middle rows add \(R(c+Gx)+J(A+Vx)\), and the last two restore \(c\) and \(A\). The net addition is \((RG+JV)x\). The coefficient from \(x_T\) to \(y_S\) in \(RG\) is \((|S\cap T|-1)/2\). It is \(1\) for \(S=T\), \(0\) when the intersection has size \(1\), and is canceled by \(JV\) when the intersection has size \(0\) or \(2\). Hence \(RG+JV=I\). The three stages therefore send \((x,y)\) to \((x,y+x)\), then \((-y,y+x)\), then \((-y,x)\). The auxiliary values cancel in each invocation separately. ◻

Proof. For binary vectors \(x,y\), \[\mathop{\mathrm{wt}}(x+y)=\mathop{\mathrm{wt}}(x)+\mathop{\mathrm{wt}}(y)-2|\mathop{\mathrm{supp}}(x)\cap\mathop{\mathrm{supp}}(y)|.\] Thus weight is additive modulo four for orthogonal vectors. If \(V=U\mathbin\perp E\) and \(z_1,\ldots,z_\rho\) is an orthonormal basis of \(E\), then \[q_V(x)-q_U(x) =\sum_{j=1}^{\rho}\mathop{\mathrm{wt}}(z_j)[z_j\cdot x]\pmod4,\] where brackets mean the integer representative \(0\) or \(1\). Every \(\mathop{\mathrm{wt}}(z_j)\) is odd, so its value modulo four is \(1\) or \(-1\). For a decreasing edge the entire expression is negated. The identity \(i^{[z\cdot x]}=a+b(-1)^{z\cdot x}\) and Walsh conjugation give the stated kernels. Finally \(R_z^2=I\) and \(C_z^2=R_z\), whence \(C_z^{-1}=R_zC_z\). ◻

Proof. Here is the full list of nonzero or potentially nonzero residuals. All rows except the last are tensored with \(Q\). The vectors \(t_X,t_Y\) on a side wire are its two physical triple indicators. The omitted edges have zero residual. \[\begin{array}{l|l} \text{wire and edge}&\text{orthogonal residual}\\\hline X:\ \mathrm{in}\to2&B\otimes t_X^\perp\\ X:\ 2\to3&P\otimes t_X^\perp\\ Y:\ 0\to1&B\otimes t_Y^\perp\\ Y:\ 4\to5&P\otimes t_Y^\perp\\ \text{center}:\ \mathrm{source}\to1&B\otimes D\\ \text{center}:\ 1\to3,\ 3\to4,\ 4\to6&P\otimes D\quad\text{(each)}\\ \text{side}:\ \mathrm{source}\to0&B\otimes\langle t_Y\rangle\\ \text{side}:\ 0\to2&(B\otimes t_Y^\perp)\mathbin\perp (P\otimes\langle t_X\rangle)\\ \text{side}:\ 2\to5&P\otimes\langle t_X,t_Y\rangle^\perp\\ \text{side}:\ 5\to7&P\otimes\langle t_Y\rangle\\ \text{auxiliary}:\ \mathrm{last}\to\mathrm{sink} &E\otimes D\otimes Q^\perp. \end{array}\] In the last row \(Q^\perp\) is taken in the full future tensor space. The side edge \(2\to5\) explains the use of neighboring triples. Because \(t_X\cdot t_Y=0\) and both vectors have norm one, \[t_Y^\perp=\langle t_X\rangle\mathbin\perp \langle t_X,t_Y\rangle^\perp.\] Its row-\(2\) label \((B\otimes D)\mathbin\perp (P\otimes\langle t_X\rangle)\) therefore lies in its row-\(5\) label \((B\otimes D)\mathbin\perp(P\otimes t_Y^\perp)\), with precisely the displayed residual. The other rows follow by \(E=B\mathbin\perp P\) and \(D=\langle t\rangle\mathbin\perp t^\perp\). These decompositions verify all inclusions and show that the only decreases are the central edges \(3\to4\), each of dimension \(h\).

The signed changes telescope along physical wires. Source dimensions sum to \(N_0\) and sink dimensions to \(Wm-N_0\), so their total is \(Wm-2N_0\). Each of the \(I_0(101)\) central wires loses \(h=100\) dimensions once. Replacing signed changes by absolute changes adds twice these losses, proving the formula for \(s\). In particular, \[\Delta=2N_0-2I_0(h+1)h =2v^2\bigl(v-3h(h+1)\bigr)>0,\] since \(v>3h(h+1)\). Substituting \(h=100\) and \(v=161700\) gives the displayed integers.

Nondegeneracy alone would not guarantee an orthonormal basis in characteristic two: a nondegenerate form may be alternating. Here every nonzero residual contains a vector of norm one. Indeed, \(t^\perp\) and \(\langle t_X,t_Y\rangle^\perp\) contain coordinate units outside supports of size at most \(3\) and \(6\) respectively. If nonzero, \(B\) contains a coordinate unit outside a support of size \(3^{j-1}<h^{j-1}\), and the same argument applies to nonzero \(Q^\perp\). Full spaces and the lines \(P,Q,\langle t\rangle\) also contain norm-one vectors. Taking tensor products and choosing a nonzero summand in an orthogonal sum proves the claim for every residual in the table.

For completeness, a nondegenerate binary symmetric space with a norm-one vector has an orthonormal basis. Split off unit lines until the remaining space is alternating. A nonzero nondegenerate alternating space splits into orthogonal planes with bases \(p,q\) satisfying \(p\cdot p=q\cdot q=0\) and \(p\cdot q=1\): choose \(p\ne0\), choose \(q\) by nondegeneracy, and split off their plane. Retain a unit vector \(w\) from a line already removed. A plane perpendicular to \(w\) is absorbed by replacing \((w,p,q)\) with \[w+p,\qquad w+q,\qquad w+p+q.\] These are pairwise orthogonal unit vectors and span the same three-dimensional space. Repetition absorbs all alternating planes. All choices can be made by finite binary linear algebra with a fixed ordering of coordinates and pivots. ◻

Proof. Use the gate and terminal labels just constructed in (8), with each array address viewed as \(f\) columns of \(m\) bits. It remains to calculate the terminal frame ratios and implement the edge changes.

Except for the route \(X_d\to Y_d\), a source and its routed sink have labels \(0\) and \(\mathcal D\), so their frame ratio is \(C^{\otimes mf}\). For the exceptional route put \(u=u_d\). Since \(u\cdot u=1\), \(P_{U_d}x=u[u\cdot x]\), and orthogonal weight additivity gives \[q_{U_d^\perp}(x)-q_{U_d}(x) =\mathop{\mathrm{wt}}(x)-2\mathop{\mathrm{wt}}(u)[u\cdot x] =\mathop{\mathrm{wt}}(x)+2[u\cdot x]\pmod4.\] Here \(\mathop{\mathrm{wt}}(u)=27\) is odd. Hence the exceptional frame ratio is \(R_uC^{\otimes m}\) in each column. Correct these translations at the sinks and undo the signed bank exchange. The result is \(C^{\otimes mf}\) on each physical role, including every auxiliary array.

By Lemma 5, an edge with residual dimension \(\rho\) uses \(\rho\) products \(C_z^{\otimes f}\) or \((C_z^{-1})^{\otimes f}\). Extend \(z\) to a binary basis and apply the corresponding invertible address change in each column. Translation by \(z\) becomes a flip of one selected bit, so the forward product is \(C^{\otimes f}\) on those \(f\) selected bits, for each setting of all other bits. Inverse products add only translations. Summing the residual dimensions gives precisely \(s\) directional steps. The network, all its bases, and the number of remaining pointwise operations are fixed independently of \(f\). Spectator bits merely index additional copies of these identities. ◻

Proof. An \(m\)-bit column is a digit of radix \(2^m\). Since \(m\) and the maps are fixed, a finite table gives, for each possible column digit, its old bits, transformed bits, selected output bit, and remaining output bits. This table can be constructed once by the specified binary arithmetic; its cost is an absolute constant. The \(r\) spectator bits form one additional digit of radix \(2^r\), omitted when \(r=0\).

For a given \(k\), compute the input and output bit-position strides and the displaced table contributions for each column. This costs \(O(f+1)\) operations with a constant depending on \(m\). An input address and the desired output address are each sums of the contributions of their column digits and the spectator digit; the output contributions put the selected bits in their common field and all other bits outside it. Traverse the digit prefix tree, retaining these two partial sums. Extending a prefix by a digit adds its two tabulated contributions in constant time. At a leaf, copy the value between the two resulting addresses, using a separate output array to avoid overwriting unread values. Every internal node has at least two children. There are \(2^k\) leaves, so fewer than \(2^{k+1}\) nodes, including the root. The preparation cost is also \(O(2^k)\). Reversing the source and destination addresses implements the inverse permutation with the same bound.

Take the selected \(f\) bits as the least significant output field. Each fiber is then contiguous, and consecutive groups of \(W_*\) fibers, for any fixed \(W_*\), are consecutive blocks of \(W_*2^f\) entries. No per-entry scan of the columns is needed to form or undo these groups. Addresses have \(k+O(1)\) bits, with the fixed network sizes included in the constant. ◻

Proof. We first transform \(W_*\) arbitrary arrays simultaneously. Set \(K=m(71+1)\). For \(k<K\), apply the \(k\) factors of \(C\) one at a time along their fibers. Because \(K\) is fixed, the cost divided by \(W_*2^k\) is bounded by an absolute constant throughout this base range, including \(k=0\).

For \(k\ge K\), write \(k=mf+r\), where \(f=\lfloor k/m\rfloor\) and \(0\le r<m\). Apply the \(r\) remaining bit factors directly. On \(W\) arrays use Proposition 7 with \(f\) columns and \(r\) spectator bits. On each of the \(W_*-W\) remaining arrays use one directional step for each of the \(m\) coordinate positions, again simultaneously over all \(f\) columns. There are \(S\) directional steps in total.

Each such step requires \(2^{k-f}\) independent transforms \(C^{\otimes f}\). Since \(f\ge72\) and \(k-f\ge(m-1)f\ge71\), the number \(2^{k-f}\) is divisible by \(W_*=2^{71}\). After the permutation of Lemma 8, partition its fibers into exactly \(2^{k-f}/W_*\) batches and use the present \(W_*\)-array algorithm recursively on each batch. No partially filled recursive batch occurs. Its correctness follows by induction on \(k\), since \(f<k\), and because the network interface applies to arbitrary values on all its roles.

Let \(T(k)\) be the cost for \(W_*\) arrays and \(t(k)=T(k)/(W_*2^k)\). The fixed number of pointwise gates, permutations, terminal corrections, and at most \(m-1\) leftover bit layers cost at most \(A W_*2^k\) outside recursive calls, for an absolute constant \(A\). Batch setup and returning results are included in this bound: the batches partition a packed array, and their number is at most its length. Thus \[\begin{align*} T(k)&\le A W_*2^k+ S\frac{2^{k-f}}{W_*}T(f),\\ t(k)&\le A+\lambda t(\lfloor k/m\rfloor) \qquad(k\ge K). \end{align*}\] This exact recurrence permits the critical exponent \(\theta=\log_m\lambda\). To see this directly, unroll it for \(d\) steps until the argument falls below \(K\). Successive arguments are \(\lfloor k/m^j\rfloor\), and \(d\le\lceil\log_m(k+1)\rceil\). If \(B\) bounds the normalized base costs, then \[t(k)\le A\sum_{j=0}^{d-1}\lambda^j+B\lambda^d \le\left(\frac{A}{\lambda-1}+B\right)\lambda^d =O((k+1)^\theta).\] Here \(\lambda^d\le\lambda(k+1)^\theta\). The same estimate holds in the base range by increasing the constant.

Fixed tables may be generated once and reused; even generating them on the first invocation contributes an absolute constant. The recursive calls can run serially and reuse their working arrays. Their address fields, counters, and strides use \(O(k+1)\) bits: at each active level only a fixed number of arrays of the current length is needed, and the lengths shrink from \(2^k\) to \(2^{\lfloor k/m\rfloor}\) and so on. The recursion stack has \(O(\log(k+2))\) levels. Thus the claimed workspace is bounded by a constant times \(\sum_{j=0}^{d}W_*2^{\lfloor k/m^j\rfloor}+O(k+1) =O(W_*2^k)\); consecutive nonterminal array lengths decrease by at least a factor of two. The claimed index costs therefore use exactly the logarithmic-word model of the paper.

Finally, initialize \(W_*-1\) unused arrays to zero, put the requested array in the remaining role, run the simultaneous procedure, and retain that role’s output. Initialization costs \(O(W_*2^k)=O(2^k)\), and \(W_*\) is an absolute constant. This proves the stated single-array bound. ◻

Proof. For \(r=1\) take \(N=D_N=T=(1)\). Otherwise let the \(k\)th column of \(P\) be the coefficient vector of the monic Newton polynomial \(\prod_{j=0}^{k-1}(Z-u^j)\), for \(0\le k<r\). Then \(P\) is unit upper triangular and \(N=F_r(u)P\) is lower triangular. For \(i\ge k\), \[ N_{ik}=\prod_{j=0}^{k-1}(u^i-u^j) =(-1)^ku^{k(k-1)/2}\frac{H_i}{H_{i-k}}, \qquad H_j=\prod_{s=1}^j(1-u^s),\quad H_0=1. \tag{13}\] The required \(H_j\), \(0\le j<r\), are nonzero because \(u\) is primitive. Consequently \[N=\mathop{\mathrm{diag}}(H_i)\,T\, \mathop{\mathrm{diag}}\bigl((-1)^ku^{k(k-1)/2}\bigr), \qquad T_{ik}=\begin{cases}H_{i-k}^{-1},&i\ge k,\\0,&i<k.\end{cases}\] Here \(T\) is invertible lower triangular Toeplitz, with diagonal one and coefficient sequence \(h_j=H_j^{-1}\).

Let \(D_N=\mathop{\mathrm{diag}}(N_{00},\ldots,N_{r-1,r-1})\) and \(L=ND_N^{-1}\). The identity \(F_r(u)=L D_NP^{-1}\) is a unit-lower/diagonal/unit-upper factorization. Such a factorization is unique: comparing two makes a unit lower triangular matrix equal an upper triangular matrix, forcing both to be identity, and then identifies their diagonal factors. Since \(F_r(u)=F_r(u)^{\mathsf T}\), transposition gives another such factorization. Uniqueness yields \(P^{-1}=L^{\mathsf T}\), hence \[ F_r(u)=N D_N^{-1}N^{\mathsf T}. \tag{14}\] Computing the powers of \(u\), the \(H_j\), and all diagonal entries has polynomial cost. Every division above is by a product of nonzero \(H_j\) and powers of \(u\). In particular, the argument applies to composite \(r\) and to every primitive root of order \(r\). ◻

Proof. Assign one coordinate \(z_v\) to each gate, in topological order. Instead of assigning the gate value, add its prescribed linear combination of predecessors into \(z_v\). This takes at most two shears. The resulting forward sweep has the form \[z\longmapsto Uz+Tx,\] where \(U\) is unit lower triangular. Write the output reads as \(Fz+Dx\), allowing outputs that read a source directly; each nonzero output is one designated read. Starting with zero gate coordinates computes the original DAG, so \(FT+D=M\).

Run the forward sweep, add its output reads into \(y\), and undo the sweep. This restores \(z\) and adds \(Mx+FUz\) to \(y\). Next run the same sweep with all direct-source edges omitted, omit \(Dx\) at the readout, subtract the resulting output \(FUz\), and undo the sweep again. The net effect is the stated map. The target coordinates are never predecessors in either sweep. The calculation is an identity in independent variables \(x,y,z\), so it remains valid for correlated initial contents.

To arrange a sweep into layers, assign gates their longest-path depth levels. Within one level, destinations are new gate coordinates and predecessors are earlier gate coordinates or sources. The undirected multigraph of shear edges has maximum degree \(\Delta\le\max\{2,\delta\}\). Greedy edge coloring uses at most \(2\Delta-1\) colors, since each edge meets at most \(2\Delta-2\) others. The operations in one color have disjoint pairs. Reordering by color is valid because no destination is a predecessor at the same level. The output additions have the same property: their sources have bounded output fan-out and each target has one read. Reverse sweeps use the reversed layers and negated coefficients. Four sweeps and two output rounds give the depth bound and the count \(8g+2a\). ◻

Proof. We split the transform into two smaller diagonal blocks and a cross update. For each rectangular part of that update, we will construct a convolution DAG and fit all its gate coordinates inside the parent block. We then count the resulting layers and the preparation work.

Write \(T_v=(h_{i-j})_{0\le j\le i<v}\), with zero entries above the diagonal and \(h_0\ne0\). The same initial sequence \(h\) specifies all smaller blocks used below. Its reciprocal-series coefficients are computed by \[ g_0=h_0^{-1},\qquad g_k=-h_0^{-1}\sum_{j=1}^k h_jg_{k-j}\quad(1\le k<r). \tag{16}\] They give the inverse of every lower triangular Toeplitz block.

For \(v>1\), put \(p=\lfloor v/2\rfloor\) and write \[T_v=\begin{pmatrix}T_p&0\\B&T_{v-p}\end{pmatrix}.\] The factorization \[T_v=\begin{pmatrix}I&0\\E&I\end{pmatrix} \mathop{\mathrm{diag}}(T_p,T_{v-p}),\qquad E=BT_p^{-1},\] first performs the two diagonal transforms in parallel, then adds to the second block from the transformed first block. In the original indices of this cross block, \[ E_{ij}=\sum_{\nu=j}^{p-1}h_{i-\nu}g_{\nu-j}, \qquad p\le i<v,\quad 0\le j<p. \tag{17}\]

Partition both intervals into consecutive chunks. For a target chunk of size \(a\) and source chunk of size \(e\), let \(M\) be the corresponding \(a\times e\) submatrix of \(E\). Let \(J_a,J_e\) denote the lower shifts. Away from the first local row and column, (17) telescopes to \[ E_{ij}-E_{i-1,j-1}=-h_{i-p}g_{p-j}. \tag{18}\] Thus, writing \(\mathcal D=M-J_aMJ_e^{\mathsf T}\), we can form \[ \mathcal D=\sum_{\nu=1}^3 v^{(\nu)}(w^{(\nu)})^{\mathsf T} \tag{19}\] without any rank test. Specifically, extend the outer product on the right of (18) to the entire chunk and subtract it from \(\mathcal D\), obtaining \(R\). If \(e_0\) is the first unit vector, the two remaining outer products are \(e_0R_{0,*}\) and \((R_{*,0}-R_{00}e_0)e_0^{\mathsf T}\). They correct its first row and first column. Keep all three terms, even when some coefficients vanish.

Iterating \(M=\mathcal D+J_aMJ_e^{\mathsf T}\) gives, by nilpotence, the finite reconstruction \[ M=\sum_{l\ge0}J_a^l\mathcal D(J_e^{\mathsf T})^l. \tag{20}\] For one outer product \(vw^{\mathsf T}\), its contribution has entries \(\sum_{l\ge0}v_{i-l}w_{j-l}\), with zero extension. Apply it to \(x\) by \[ b_l=\sum_{j=l}^{e-1}w_{j-l}x_j\quad(0\le l<e),\qquad c_i=\sum_{l=0}^{e-1}v_{i-l}b_l\quad(0\le i<a). \tag{21}\] If \(x^{\mathrm{rev}}_j=x_{e-1-j}\), the first map selects \(b_l=(w*x^{\mathrm{rev}})_{e-1-l}\) from an ordinary convolution. The second map is a truncated convolution. Using three branches and summing their outputs gives a specific DAG with absolute constants \(K_0,K_1,\delta_0\) such that \[ g\le K_0(a+e)\log_2(2+a+e),\qquad H\le K_1\log_2(2+a+e),\qquad \delta\le\delta_0. \tag{22}\] These include output uses: every source is used in only three branches, the branches retain bounded fan-out, and their sum uses a bounded number of gates per output.

To fit this DAG inside the parent block, reserve the \(a+e\) target and source coordinates and one borrowed coordinate for each of its \(g\) gates. All \(g\) coordinates stay assigned to their gates throughout the replay. Here is an effective choice of chunk size that does not require knowing \(K_0\). For every integer \(b\in\{1,\ldots,v\}\), partition each interval into chunks of size \(b\), except for its possible last chunk. Print the DAG skeleton for every resulting pair and count its gates. Declare \(b\) admissible precisely when, for every pair, \[ g+a+e\le v. \tag{23}\] Choose the largest admissible \(b\). This is an integer test on printed graphs, independent of the coefficients, made before any data are transformed. If no \(b\) is admissible, replace the entire recursive decomposition of \(T_v\) by a direct word: process rows in decreasing order, multiply the current coordinate by \(h_0\), and add \(h_{i-j}\) times each lower-indexed coordinate \(j<i\). The lower coordinates still have their original values, so this computes exactly \(T_v\). Width one is a scaling.

To prove the depth bound, fix for analysis a sufficiently large absolute \(D\), for example \(D\ge16K_0+16\). For all sufficiently large \(v\), \[b_0=\left\lfloor\frac{v}{D\log_2v}\right\rfloor \ge\frac{v}{2D\log_2v}\ge1\] passes (23). Indeed \(a+e\le2v/(D\log_2v)\le v/8\), while (22) gives \(g\le4K_0v/D\le v/4\). Consequently the direct fallback occurs only for bounded \(v\), and the chosen size \(b\ge b_0\) leaves \(O(\log v)\) chunks in each interval.

For a selected pair, borrow \(g\) coordinates outside its source and target chunks but inside these same \(v\) coordinates; (23) guarantees their availability. Lemma 13 implements its update in \(O(1+\log v)\) shear layers. Process the \(O(\log^2v)\) pairs serially. Every borrowed coordinate is restored before the next pair, so it may carry a source value, an already updated target value, or any other current data. The complete cross update takes \(O(1+\log^3v)\) layers. Child calls use disjoint blocks, hence the mixed-round depth satisfies \[d(v)\le\max\{d(\lfloor v/2\rfloor),d(\lceil v/2\rceil)\} +O(1+\log^3v).\] Summing along a balanced recursion path proves \(d(r)=O(1+\log^4r)\).

We finally account for preparation. Formula (16), the entries (17), and the three explicit outer products use polynomially many scalar operations. Each node of the recursion tests at most \(v\) sizes and at most \(v^2\) chunk pairs per size; every printed graph has \(O(v\log(2+v))\) gates. There are fewer than \(2r\) nodes. Even this deliberately redundant search has polynomial integer cost. Gate-level assignments, bounded-degree edge colorings, and the choice of the first available borrowed coordinates can all be performed by finite scans of these lists. Only the chosen graphs need their scalar coefficients evaluated. Fixed-vector transforms and all other coefficient computations have polynomial cost as well. Store computed scalars and references to them as an arithmetic DAG; there is no expansion into expression trees.

The first convolution in (21) has operand lengths \(e,e\), and the second has lengths \(a,e\). Their padded Fourier lengths are powers of two smaller than \(4r\). Thus a single primitive root of power-of-two order \(L_r=2^{\lceil\log_2(4r)\rceil}<8r\) supplies every needed root by taking powers. These powers and their inverses are also prepared with polynomially many operations. Integer indices in the entire compiler have \(O(\log(2+r))\) bits. This proves the claimed preparation bound, with no need to determine the finite threshold in the depth argument. ◻

Proof. Apply Lemma 14 to the Toeplitz factor of \(N\) in Lemma 12. The two diagonal factors of \(N\) are monomial layers. Equation (14) then gives the Fourier word by composing the words for \(N^{\mathsf T}\), \(D_N^{-1}\), and \(N\). Transposition preserves the layer types and reverses the factor order. Split mixed rounds into monomial and shear layers. There are \(O(1+\log^4r)\) layers in total, and all preparation bounds and nonzero-denominator guarantees follow from the two lemmas. ◻

Proof. Classify the earlier sectors by the first axis \(j\) at which their block choice differs. The preceding chosen blocks contribute width \(\prod_{i<j}q_i\), the earlier blocks at axis \(j\) have total width \(p_j\), and all later axes have total width \(\tau_j\). These disjoint classes give (28).

During digit traversal maintain four states: a sector start \(S\), a prefix width \(Q\), a within-sector offset \(o\), and an original address \(I\). Initially they are \(0,1,0,0\). On extending by the actual local digit \(a_j\), whose table supplies \(p_j,q_j,t_j\), update \[ \begin{split} S&\leftarrow S+Qp_j\tau_j,\qquad Q\leftarrow Qq_j,\\ o&\leftarrow oq_j+t_j,\qquad I\leftarrow Ir_j+a_j. \end{split} \tag{29}\] At the leaf, the packed address is \(S+o\). This proves the cost of packing and unpacking by (27).

To enumerate calls, traverse block choices instead of digits, maintaining \(S,Q\), and the number of pairs. If axis \(j\) has \(b_j\) blocks, then \(b_j\le r_j\). Thus the number of block prefixes at every depth is bounded by the number of digit prefixes at that depth, and their total is also \(O(R)\). This argument includes axes with only one block. Each leaf supplies one contiguous sector, with no additional scan through its axes. ◻

Proof. Use Proposition 11 on every axis. Its words can be refined and padded to a common sequence of \(O((1+\log r_{\max})^4)\) slot types: a monomial slot or a slot of disjoint copies of \(C\) and singleton identities. Padding a pair slot means using only singleton blocks on that axis.

At each slot take the tensor product across axes. These slots multiply to the desired tensor transform because \[ (\bigotimes_j A_j)(\bigotimes_j B_j)=\bigotimes_j(A_jB_j). \tag{31}\] In particular, a local word’s correctness on arbitrary inputs suffices. Another axis may change coordinates during intermediate slots; one does not require it to preserve the local word’s borrowed coordinates throughout that word.

Tensor monomials cost \(O(R)\) by the prefix traversal. A tensor pair slot decomposes into the sectors of Lemma 16. Its width-\(2^k\) sector carries precisely \(C^{\otimes k}\). Theorem 9 bounds its cost, including invocation and movement, by \(O(2^k(k+1)^\theta)\). As \(k\le\ell\) and the sector widths sum to \(R\), their total cost is \(O(R(\ell+1)^\theta)\). Packing, unpacking, and discovering even the width-one sectors cost another \(O(R)\). This proves the first term of (30).

The local compilers use polynomial work in their widths. Suffix products, local block tables, and the other integer preparation use polynomial work in \(\ell,r_{\max},\log(R+2)\). All running scalar products have been charged in the traversal, so the polynomial term describes local preparation only. ◻

Proof. Writing \(\pi(t)\) for the number of primes at most \(t\), for integer \(u\ge1\) we have \[ \frac{4^u}{2u+1}\le\binom{2u}{u}\le(2u)^{\pi(2u)}. \tag{33}\] The first inequality follows because the central binomial coefficient is largest. In the factorial formula, the exponent of a prime \(p\) in \(\binom{2u}{u}\) is \[\sum_{a\ge1}\bigl(\lfloor2u/p^a\rfloor-2\lfloor u/p^a\rfloor\bigr) \le\lfloor\log_p(2u)\rfloor.\] Its prime-power contribution is therefore at most \(2u\), proving the second inequality. Taking \(u=(j+1)^2\) shows that \(\pi(2u)>j+1\) for all sufficiently large \(j\), so the \(j\)th odd prime is \(O((j+1)^2)\).

The upper bound on \(\log R_\ell\) now follows by summation. For the lower bound, \(r_j\ge j+2\), so \(R_\ell\ge(\ell+2)!/2\). For instance, the last half of these factors alone give a constant times \(\ell\log\ell\) in the logarithm. Maximality says \[R_\ell\le2n<R_\ell r_{\ell+1}.\] The extra logarithm is \(O(\log(\ell+2))\), giving \(\log n=\Theta(\ell\log\ell)\) and hence (32).

Primes up to the first unused prime are bounded by a fixed polynomial in \(\ell+1=O(\log(n+2))\). Testing potential divisors of each candidate is already polynomial work in \(\log(n+2)\). Maintain the product and stop at the first exceeding \(2n\); the product at stopping is at most \(2n\) times a polynomial in \(\log(n+2)\). All these integers have \(O(\log(n+2))\) bits. ◻

Proof of Theorem 1 and Corollary 2. All maps in the construction are exact and deterministic. The local word compiler and the fixed finite network have specified finite construction procedures. On the input data the algorithm is linear, including the chirp reduction, since the second convolution operand is fixed.

By (35), \(e=O(\log(\ell+2))\) and \(L=\Theta(n)\). Because \(\theta>0\), equation (37) and the constant number of transforms give \[T(n)=O(n\ell^\theta(\log\ell)^4) +\mathop{\mathrm{poly}}(\log(n+2))+O(1).\] Every fixed power of \(\log(n+2)\) is eventually negligible compared with \(n\ell^\theta\). Substituting (32) proves (2).

For an exact bound on the exponent, direct integer arithmetic in (1) gives \[\varepsilon:=\frac{\Delta}{mW_*} =\frac{1717850673}{590295810358705651712} >\frac{28}{10^{13}}.\] Since \(\log m<14\), for \(\eta_0=2/10^{13}\) one has \(\eta_0\log m<\varepsilon\). Using \(\exp(-t)\ge1-t\), \[\lambda=m(1-\varepsilon)<m\exp(-\eta_0\log m) =m^{1-2\cdot10^{-13}}.\] Hence \(\theta<1-2\cdot10^{-13}\). The fixed power of \(\log\log n\) in (2) is smaller than \((\log n)^{10^{-13}}\) for all sufficiently large \(n\). This proves Corollary 2.

Finally, all lengths, root orders, products of indices, and addresses are polynomially bounded in \(n\) with absolute constants; (40) treats the largest root order explicitly. Fixed network tables contribute absolute constants, and local tables have size polynomial in \(\log(n+2)\). Array movement and traversal were counted in Theorem 9 and Lemma 16. Therefore a fixed number of \(O(\log(n+2))\)-bit words per integer suffices throughout, as required by the model. ◻

Proof of Corollary 3. Set \(M=2n-1\) and zero-pad \(a\) and \(b\) to vectors \(\widetilde a,\widetilde b\) of length \(M\). Every sum of two indices in their supports lies between zero and \(2n-2=M-1\), so the length-\(M\) cyclic convolution has no wraparound and is exactly \((c_0,\ldots,c_{M-1})\). With the positive-exponent convention for \(F_M\), its convolution identity is \[(F_Mc)_j =\sum_{r,s=0}^{n-1}a_rb_s\zeta_M^{j(r+s)} =(F_M\widetilde a)_j(F_M\widetilde b)_j \qquad(0\le j<M).\] Compute the two forward transforms and their \(M\) pointwise products, obtaining a vector \(p=F_Mc\). If \(J\) negates indices modulo \(M\), the geometric root sum gives \(F_M^2=MJ\) and therefore \[c=F_M^{-1}p=M^{-1}JF_Mp.\] Thus one more forward transform, index reversal, and scaling give the answer.

Apply Theorem 1 at length \(M\) for each of the three transforms, charging its scalar preparation, schedule construction, and index work each time. The single specified root supplied for that length can be reused in all three calls. Its explicitly computable order satisfies \(D_*<1024M^3<8192n^3\); equivalently, the model’s root-of-unity operation returns this one root. Padding, pointwise products, reversal, and output scaling take \(O(M)\) field and address operations. To prepare \(M^{-1}\), form the complex integer \(M\) from \(1\) by binary doubling and addition in \(O(\log(M+2))\) field operations, then divide \(1\) by it; the denominator is nonzero because \(M\ge1\). All added indices and addresses fit a fixed number of \(O(\log(n+2))\)-bit words.

If \(T(M)\) denotes the charged running time in Theorem 1, the total is \(3T(M)+O(M+\log(M+2))\). Since \(M=\Theta(n)\), this gives the first bound, and Corollary 2 gives the eventual decimal power bound. The same formulas apply when \(n=1\); a finite initial range may also be handled directly. ◻

Proof. Keep a finite generating list for the ideal \(I=(f_i)\) and an integer \(m\), initially \(m=a\). Retain polynomial-combination witnesses for derived members of \(I\); rational elimination and the monic reductions below can track these witnesses. After invertible polynomial changes of coordinates, maintain, for each \(j>m\), a known member of \(I\) of the form \[x_j^{d_j}+\sum_{e<d_j}c_{je}(x_1,\ldots,x_{j-1})x_j^e, \qquad d_j\ge1.\] Thus \(S=\mathbb Q[x_1,\ldots,x_a]/I\) is finite as a module over \(R=\mathbb Q[x_1,\ldots,x_m]\).

First compute the fiber \(S/(x_1,\ldots,x_m)S\). This is effective: set \(x_1=\cdots=x_m=0\) and let \(B\) be the quotient by only the displayed monic relations. As a tower of monic extensions, \(B\) has a rational basis consisting of the monomials whose \(x_j\)-exponents are less than \(d_j\) for \(j>m\). Successive monic reduction gives its multiplication table. If \(\bar f_i\) are the images in \(B\) of the generators of \(I\), form the rational span of all \(b\bar f_i\) with \(b\) in this basis. Since the basis spans \(B\), this is exactly the ideal \(\sum_i B\bar f_i\). Its quotient is the required fiber, so rational linear algebra computes the fiber and its table. A nonzero fiber is the requested answer, after undoing the coordinate changes. If \(m=0\) and the fiber is zero, then \(S=0\), so \(I\) is the unit ideal.

Suppose the fiber is zero and \(m>0\). We claim \(I\cap R\ne0\). Otherwise \(R\hookrightarrow S\). Localize at \(\mathfrak m=(x_1,\ldots,x_m)\) in \(R\). The resulting finite \(R_{\mathfrak m}\)-module \(S_{\mathfrak m}\) is nonzero, since it still contains \(R_{\mathfrak m}\). The zero fiber would give \(S_{\mathfrak m}=\mathfrak mS_{\mathfrak m}\). For a finite generating column \(v\) this means \(v=Mv\) with all entries of \(M\) in the maximal ideal. Multiplication by the adjugate of \(I-M\) gives \(\det(I-M)v=0\); its determinant is a unit, a contradiction.

Find a nonzero member \(h\in I\cap R\) by enumerating increasing degree cutoffs for monomial multiples of the generators of \(I\). At each cutoff, rational linear algebra tests whether their span has a nonzero element involving only the first \(m\) variables. This search terminates by the claim and the definition of an ideal. A nonzero constant certifies \(I=(1)\). Otherwise let \(d=\deg h\ge1\) and substitute \[x_i=y_i+y_m^{(d+1)^i}\quad(1\le i<m),\qquad x_m=y_m,\] leaving later variables unchanged. This change is invertible. The weights \(1,(d+1),\ldots,(d+1)^{m-1}\) distinguish all monomials of total degree at most \(d\) by base-\((d+1)\) expansion. Consequently the highest power of \(y_m\) in the transformed \(h\) has a nonzero rational leading coefficient: it comes from a unique monomial, taking the pure-power term in every substituted factor. Divide by that coefficient to obtain a monic relation in \(y_m\). Earlier triangular relations remain monic in their respective later variables. Rename the variables and decrease \(m\) by one. At most \(a\) such decreases occur, proving termination. Every step uses finite rational arithmetic. Finally, the equation \(uv=1\) forces \(u\) to be a unit in every output algebra, including one with zero divisors. ◻

Proof. The printing budget will control both the circuit description and all literal scalar data, without requiring a bound on when a record appears. Normalize the printer to output at most one bit per machine step. For \(n\ge2\), run it from the beginning for \(B=\lfloor\log_2 n\rfloor\) bit steps. Select the last completed record with \(2\le m_t\le\sqrt B\); if there is none, use the ordinary radix \(m=2\) circuit. Every fixed record eventually finishes and satisfies the width bound, so the selected stream index tends to infinity. In particular \(m\to\infty\) and \(s/(m\log m)\to0\).

The total visible description has at most \(B\) bits. Decode the selected explicit lists to addressable arrays and evaluate its preparation program once. Construct rational literals by their binary expansions and perform each listed operation in the stated arithmetic model. This costs \(B^{O(1)}\), including parsing and bit simulation. The gate list then executes on each new input in \(O(m+s)\) time, including entry and output copies. There is no expansion of a succinct circuit during its invocation.

Put \(X=2n-1\), let \(m^H\) be the largest power of \(m\) not exceeding \(X\), and set \[p=\lceil X/m^H\rceil,\qquad P=m^Hp.\] Then \(1\le p\le m\), \(X\le P<2X<4n\), and \(H\le\log(2n)/\log m\). The mixed-radix Fourier recursion uses \(H\) copies of radix \(m\) and one radix \(p\), the latter computed directly. For clarity, at a split \(ab\) use input index \(bj_a+j_b\) and output index \(k_a+ak_b\). The identity \[(bj_a+j_b)(k_a+ak_b) \equiv bj_ak_a+aj_bk_b+j_bk_a\pmod {ab}\] gives the two smaller Fourier transforms and their intervening twiddle. At each level, copying subarrays into the required order, tabulating or reading twiddles, and enumerating the two indices cost linear work. Reuse the decoded radix circuit each time. Tabulate powers of \(\zeta_P\) in \(O(P)\) operations; every recursive width divides \(P\). Thus one transform, or its inverse by frequency reversal and scaling, costs \[ O\bigl(P[1+p+H(1+s/m)]\bigr)+B^{O(1)}. \tag{45}\] All indices and products of indices have polynomial bounds in \(n\), so a constant number of \(O(\log(n+2))\)-bit words suffices per access.

Finally reduce \(F_n\) to convolution of length \(P\). With \(\eta=\zeta_{2n}\), store \(\eta^{j^2}x_j\) for \(0\le j<n\) and pad with zeros. The fixed kernel stores \(\eta^{-h^2}\) at the residues of \(-(n-1)\le h\le n-1\); these residues are distinct since \(P\ge2n-1\). Multiply convolution output \(k\) by \(\eta^{k^2}\). The identity \(k^2+j^2-(k-j)^2=2kj\) gives exactly \(F_nx\). Computing the fixed kernel’s transform, the variable transform and the inverse uses only a constant number of transforms bounded by (45), plus linear preparation and scaling work. The chirp scalars come from an \(O(n)\)-size table of powers of \(\eta\), indexed by the squared exponents modulo \(2n\).

For the root accounting, let \(R\) be the product of the root orders listed in the selected preparation program, or \(1\) if there are none. Their total binary length is at most \(B\), whence \(R\le2^B\le n\). The single root \(\zeta_D\), where \(D=2nPR<8n^3\), supplies every listed root and the two outer roots by integer powering. There are at most \(B\) such requests, and powering and forming their exponents cost \(B^{O(1)}\). This includes obtaining the required powers of the supplied root in the preparation bound.

Since \(p=O(1+\sqrt{\log n})\), dividing the arithmetic term of (45) by \(n\log n\) gives \[O\left(\frac{1+p}{\log n} +\frac1{\log m}+\frac{s}{m\log m}\right)=o(1).\] The polynomial logarithmic preparation term is also \(o(n\log n)\). Length \(1\) is the identity. This proves the claim, with all choices independent of the input values. ◻