Homogeneous projection: cost and safety
On this page · Permalink · Source line 385
CLAIM C05 This chapter separates the nonlinear cost of a complete function from the nonlinear cost of one extracted homogeneous component. It also shows that an algebraic projection need not preserve safe support.
17.1 Two supporting lower bounds
On this page · Permalink · Source line 389
Lemma 17.1: Affine subspace after multiplication restrictions
If a Boolean function on \(n\) inputs is computed with \(t\) AND gates in an XOR–AND circuit, there is an affine subspace of dimension at least \(n-t\) on which the output is affine.
Proof
Process the AND gates in topological order while maintaining an affine subspace on which all preceding product outputs are affine. The operands of the next gate are then affine on the current subspace. If an operand is constant, their product is already affine. Otherwise impose one nonempty affine equation setting that operand to zero. This loses at most one dimension and makes the product affine. Earlier affine outputs stay affine under restriction. After at most \(t\) restrictions the output is affine on a subspace of dimension at least \(n-t\).
This is the affine-restriction method used in the background literature on multiplicative complexity [53]. The proof is reproduced here in the scalar convention needed below.
Proposition 17.2: Exact cost of a nondegenerate paired quadratic
For even \(n\), let
Then
Proof
The polar bilinear form of \(Q\) is the full-rank alternating form made of \(n/2\) disjoint \(2\times2\) blocks. If \(Q\) is affine on an affine subspace with direction space \(U\), its second differences vanish on \(U\), so \(U\) is totally isotropic. Nondegeneracy gives \(\dim U\le n/2\).
Lemma 17.1 therefore implies \(n-t\le n/2\), or \(t\ge n/2\), for any XOR–AND computation. Every restored Toffoli implementation gives such a computation by fixing its ancillary inputs and initial target, so the same lower bound applies to \({T_{\mathrm{rest}}}\). Directly add the \(n/2\) disjoint pair products to the target with one Toffoli each. This attains both bounds and requires no nonlinear work register.