9.10 Recursive, block, and tensor amplification
On this page · Permalink · Source line 2593
9.10.1 Restricted block additivity
On this page · Permalink · Source line 2595
The lower metric is exactly additive on contiguous block-diagonal targets.
Proposition 9.51: Block additivity
Let \(A_i\in{\operatorname{U}}_{n_i}({\mathbb F})\) for \(1\le i\le k\). Then
Proof
The upper bound follows by running optimal lower circuits independently inside the blocks.
For the lower bound, view an element of \({\operatorname{U}}_{n_1+\cdots+n_k}({\mathbb F})\) as a lower block-triangular matrix and project to its diagonal blocks:
Because diagonal blocks multiply independently in a lower block-triangular product, \(\pi\) is a homomorphism. A lower transvection internal to one block projects to one generator in that factor, while a crossing transvection projects to the identity in every factor. If \(m_i\) gates survive in factor \(i\), then the total word length is at least
The ambient metric is subadditive:
Cross-block ambient workspace can only improve this upper bound.
Corollary 9.52: Block-sum amplification
For every field and every \(n\ge6\), there is an \(A_n\in{\operatorname{U}}_n({\mathbb F})\) with
For \(n=6k\), the target \(C^{\oplus k}\) satisfies
Proof
For \(n=6k+r\), take \(C^{\oplus k}\oplus I_r\) and apply block additivity together with \(k\) copies of the ambient six-gate word.
9.10.2 A recursive zeta-shaped lift
On this page · Permalink · Source line 2657
For \(A\in{\operatorname{U}}_m({\mathbb F})\), define
Proposition 9.53: Exact restricted lift
For every \(A\in{\operatorname{U}}_m({\mathbb F})\),
and
Consequently,
Proof
The construction first realizes \(\operatorname{diag}(A,A)\) and then applies the \(m\) root-cross gates that add top row \(i\) into bottom row \(i\).
For the lower bound, write a circuit state in \(m\times m\) blocks as
Projection to the two diagonal blocks forces at least \(2{\ell_{\downarrow}}(A)\) internal gates. A top-internal gate leaves \(Q\) unchanged. A bottom-internal gate performs an invertible row operation on \(Q\) and preserves its rank. A root-cross gate changes \(Q\) by one rank-one row contribution, so it can increase \({\operatorname{rank}} Q\) by at most one. The final cross block is \(A\), of rank \(m\), hence at least \(m\) root-cross gates are necessary.
Let \(A^{[0]}=A\) and \(A^{[r+1]}=\mathcal Z(A^{[r]})\). If \(A\) has size \(m\), restricted length \(a\), and ambient length \(b\), then
and
Thus
For the canonical atom \(C\), the first values are
| \(r\) | dimension | restricted exact | ambient upper bound | certified gap |
|---|---|---|---|---|
| \(0\) | \(6\) | \(7\) | \(6\) | \(1\) |
| \(1\) | \(12\) | \(20\) | \(18\) | \(2\) |
| \(2\) | \(24\) | \(52\) | \(48\) | \(4\) |
| \(3\) | \(48\) | \(128\) | \(120\) | \(8\) |
| \(4\) | \(96\) | \(304\) | \(288\) | \(16\) |
This gives arbitrarily deep exact recursion with identical diagonal children and a full-rank cross block while preserving a positive defect.
9.10.3 Tensor products of tree-tight targets
On this page · Permalink · Source line 2738
The tensor operation gives the stronger asymptotic amplification.
Theorem 9.54: Exact restricted tensor rule
Let \(A\in{\operatorname{U}}_m({\mathbb F})\) and \(B\in{\operatorname{U}}_n({\mathbb F})\) be tree tight. Then \(A\otimes B\) is tree tight and
Moreover,
so
Proof
Use lexicographic order on the \(mn\) coordinates. Substitute a copy of a certificate tree for \(B\) at every leaf of a certificate tree for \(A\). At an outer node, the cross block is
whose rank is \(n{\operatorname{rank}} A[R,L]\) because \(B\) is invertible. The outer nodes therefore contribute \(n{\ell_{\downarrow}}(A)\). The \(m\) diagonal copies of the inner tree contribute \(m{\ell_{\downarrow}}(B)\). This proves the lower bound.
For the matching lower construction, first realize \(I_m\otimes B\) using \(m\) copies of a circuit for \(B\). Then realize \(A\otimes I_n\). Each gate of a circuit for \(A\) lifts to \(n\) coordinatewise gates. Since
the cost is the right side of Equation (9.18). The same construction with ambient circuits proves Equation (9.19).
If \(A\) is tree tight of dimension \(m\), with restricted length \(a\) and an ambient construction of length \(b\), then
and
A positive one-copy defect therefore becomes an order-\(N\log N\) defect at dimension \(N=m^r\).
Proof of Theorem 9.10
Apply Theorem 9.54 repeatedly to the tree-tight snapshot target \(A=A(u;s_1,\ldots,s_v)\), for which
Then
Since \(N=m^r\) and \(r=\log_2N/\log_2m\), this is
Within the snapshot family, the best coefficient is obtained by the twenty-one-dimensional seed
for which
Proposition 9.55: Optimal snapshot seed for tensor rate
Among all snapshot targets, the coefficient
is maximized at
Proof
For fixed \(m\), maximize \(v\) subject to \(v\le u+1\) and \(u+v+2=m\). Thus
If \(m\) is even and at least eight, its coefficient is strictly smaller than that of \(m-1\), because the numerator is the same while
It therefore suffices to consider odd \(m\). Apart from the constant change of logarithm base, the odd-dimensional envelope is
Its derivative has the sign of
For \(x>5\) this expression crosses zero exactly once, between \(19\) and \(21\). Direct comparison gives \(f(21)>f(19)\), after which the envelope decreases. Hence the unique integer maximizer is \(m=21\).
The first tensor powers are
| \(r\) | dimension \(21^r\) | restricted exact | ambient upper bound | certified gap |
|---|---|---|---|---|
| \(1\) | \(21\) | \(29\) | \(21\) | \(8\) |
| \(2\) | \(441\) | \(1218\) | \(882\) | \(336\) |
| \(3\) | \(9261\) | \(38367\) | \(27783\) | \(10584\) |
| \(4\) | \(194481\) | \(1074276\) | \(777924\) | \(296352\) |
9.10.4 Stable tensor capacity and activation
On this page · Permalink · Source line 2878
The tensor inequality also defines a regularized ambient invariant. Let \(A\in{\operatorname{U}}_m({\mathbb F})\) and put
Applying Equation (9.19) to \(A^{\otimes r}\otimes A^{\otimes s}\) gives
Proposition 9.56: Stable tensor length
The limit
exists. If \(A\) is tree tight, then the stable catalytic capacity
satisfies
Proof
The sequence \(b_r(A)\) is subadditive, so Fekete's lemma gives the displayed limit. Since the one-copy lifted construction implies \(\tau_*(A)\le{\ell_{*}}(A)\), one has
For a tree-tight target, Equation (9.21) identifies \({\ell_{\downarrow}}(A)\) with its exact normalized restricted tensor cost.
For the twenty-one-dimensional seed \(A_{21}\),
This regularization introduces a new possibility: a target may have \({\Delta}(A)=0\) but \(\kappa_\otimes(A)>0\). In that case one copy is rigid while many tensor copies admit a collective shortcut. We call this tensor activation.
9.10.5 Extremal consequences
On this page · Permalink · Source line 2932
Define
For finite fields the supremum is a maximum. The tensor family gives the following explicit all-dimension bound.
Proof of Corollary 9.11
Let \(m=21\) and write
Take the block sum of \(d_j\) copies of \(A_{21}^{\otimes j}\) for every \(j\), with the convention \(A_{21}^{\otimes0}=I_1\). Block additivity and the tensor estimate give
Put \(S=\sum_j j d_j21^j\). Since \(r=\lfloor\log_{21}n\rfloor\),
Also \(r\ge\log_{21}n-1\). Therefore
Multiplying by \(8/21\) yields
Numerically,
The elementary bottom-to-top construction gives
Thus the current general range is