Why sharing does not break the degree bound
On this page · Permalink · Source line 85
A STRONGER INVARIANT THAN SINGLE-REGISTER DEGREE For a current state \(s(x)\) after \(t\) Toffolis, the invariant is
\(L\) may be any finite list, including repeated registers. Initially each coordinate is a variable or a constant, so a product of \(r\) coordinates has degree at most \(r\).
Suppose the next gate toggles target \(u\) by the product of a control list of length \(q\). A product that omits \(u\) is unchanged. If \(u\) occurs, idempotence removes all its repetitions. With \(R\) the remaining list, the updated product is
The two old-state products have certified degrees at most
Since \(|R|+1\le |L|\), the invariant's budget rises by at most \(\max\{q-1,0\}\): zero for NOT and CNOT, one for Toffoli.
Induction along the actual gate list gives
With \(r=1\), every register has degree at most \(T+1\).
Why this handles a DAG rather than just a formula
The proof never unfolds a reused intermediate value into duplicated computation. It estimates arbitrary products of the current registers in one shared state. The budget increases once per actual Toffoli, including when its controls share earlier work or its target participates in feedback.
The statements are workspaceDegree_run and canonical_run_coordinate_degree. This formalizes the maintained NCT specialization of F3. A separate generic XOR–AND circuit syntax and simulation theorem are not added here.