Projection is defined in the original coordinates
On this page · Permalink · Source line 414
For \(m\ge2\), put \(a=(1,\ldots,1)\) and
There is one input bit \(x_v\) for each \(v\in V\). Define
The linear map \(x\mapsto L(x)\) has rank \(m\), because the standard basis columns are present. In the \(L\) coordinates, \(P_m\) is a monomial in \(m\) independent bits. Its restored nonlinear cost is \(2m-3\).
Now extract the quadratic homogeneous ANF component \(Q_m\) in the original \(x_v\) coordinates. Since \(P_m(0)=P_m(e_v)=0\), for distinct \(u,v\) its quadratic coefficient is
The involution \(v\mapsto v+a\) pairs every variable with one other variable:
It is a quadratic inner product on \(n/2\) disjoint pairs. Its alternating polar matrix has full rank \(n\).
The coordinate choice is essential. Homogeneous grade is not invariant under arbitrary affine changes of variables. A cheap representation in the \(L\) coordinates does not imply cheap independent generation of the quadratic grade in the original coordinates. The comparison keeps the definition of projection fixed throughout.