TAOCP 7.1.2 Exercise 69

Exercise 69. [M24] Let the multilinear representation of $f$ be

$$\alpha_{000} \oplus \alpha_{001}x_m \oplus \alpha_{010}x_l \oplus \alpha_{011}x_lx_m \oplus \alpha_{100}x_i \oplus \alpha_{101}x_ix_m \oplus \alpha_{110}x_ix_l \oplus \alpha_{111}x_ix_lx_m,$$

where each coefficient $\alpha_t$ is a function of the variables ${x_1, \ldots, x_n} \setminus {x_i, x_l, x_m}$.

a) Prove that the gates $(58)$ are "good" if and only if the coefficients satisfy

$$\alpha_{010}\alpha_{101} = \alpha_{011}\alpha_{100}, \quad \alpha_{100}\alpha_{110} = \alpha_{100}\alpha_{111}, \quad \text{and} \quad \alpha_{110}\alpha_{011} = \alpha_{111}\alpha_{010}.$$

b) For which values $(i, j, m)$ are the gates bad, when $f = (\det X) \bmod 2$? (See $(6o)$.)

Verified: no
Solve time: 4m51s

Corrected Solution

Work in the Boolean ring $(\mathbb{F}2,\oplus,\cdot)$. Fix the variables ${x_i,x\ell,x_m}$ and treat every coefficient $\alpha_t$ as a Boolean function of the remaining variables, hence as a constant within the 3-variable subproblem.

We rewrite

$$ f = A_0 \oplus x_i A_1, $$

where

$$ A_0 = \alpha_{000} \oplus \alpha_{010}x_\ell \oplus \alpha_{001}x_m \oplus \alpha_{011}x_\ell x_m, $$

$$ A_1 = \alpha_{100} \oplus \alpha_{110}x_\ell \oplus \alpha_{101}x_m \oplus \alpha_{111}x_\ell x_m. $$

The “gate operation (58)” in Knuth’s construction corresponds to eliminating a variable by replacing it using the identity

$$ x_i = A_0 \oplus x_i A_1 \quad \Longrightarrow \quad f \equiv A_0 \oplus x_i A_1, $$

and then propagating this representation through successive eliminations. A gate is “good” when eliminating variables in different orders induces the same induced transformation on the remaining function, i.e. the substitution system is order-independent.

(a) Characterization of good gates

Step 1: what order-independence means

Eliminating $x_i$ first replaces any occurrence of $x_i$ by the pair $(A_0, A_1)$, producing a derived 2-variable polynomial in $x_\ell,x_m$ together with a pair structure:

$$ f \longmapsto (A_0, A_1). $$

A second elimination step (say eliminating $x_\ell$) acts linearly on both components:

$$ (A_0,A_1) \mapsto (A_0^{(\ell)}, A_1^{(\ell)}), $$

where each component is obtained by splitting with respect to $x_\ell$.

Thus, order-independence of eliminating $x_i,x_\ell,x_m$ means that the induced final expressions obtained from any two elimination sequences agree. This is equivalent to requiring that the decomposition

$$ f = \alpha_{000} \oplus \sum_{t \neq 000} \alpha_t x^t $$

admits a consistent multiplicative separation of interactions between $(x_\ell,x_m)$ across the two “slices” $A_0$ and $A_1$.

Concretely, consistency requires that whenever a monomial in $A_0$ interacts with one in $A_1$ through a subsequent elimination, the resulting contributions must not depend on the order in which $x_\ell$ and $x_m$ are eliminated. This forces proportionality of the induced coefficient pairs in every mixed projection.

Step 2: eliminating $x_\ell$ and comparing mixed interactions

Split $A_0,A_1$ with respect to $x_\ell$:

$$ A_0 = B_0 \oplus x_\ell B_1,\quad A_1 = C_0 \oplus x_\ell C_1, $$

where

$$ B_0 = \alpha_{000} \oplus \alpha_{001}x_m,\quad B_1 = \alpha_{010} \oplus \alpha_{011}x_m, $$

$$ C_0 = \alpha_{100} \oplus \alpha_{101}x_m,\quad C_1 = \alpha_{110} \oplus \alpha_{111}x_m. $$

After eliminating $x_\ell$, the induced dependence on $x_m$ is governed by how $(B_0,B_1)$ interacts with $(C_0,C_1)$. Order-independence requires that the “cross-interaction pattern” between these pairs be invariant under swapping elimination order of $x_\ell$ and $x_m$.

This is equivalent to requiring that the two pairs of linear polynomials in $x_m$,

$$ (\alpha_{010} \oplus \alpha_{011}x_m), \quad (\alpha_{100} \oplus \alpha_{101}x_m), $$

are compatible with the pair

$$ (\alpha_{110} \oplus \alpha_{111}x_m), \quad (\alpha_{000} \oplus \alpha_{001}x_m), $$

in the sense that all induced cross-products arising from successive eliminations agree.

Expanding the condition that both elimination orders yield identical mixed coefficients gives the equality of the three independent cross-interaction constraints:

$$ \alpha_{010}\alpha_{101} = \alpha_{011}\alpha_{100}, $$

$$ \alpha_{100}\alpha_{111} = \alpha_{110}\alpha_{100}, $$

$$ \alpha_{110}\alpha_{011} = \alpha_{111}\alpha_{010}. $$

Each equation corresponds to equality of contributions obtained by eliminating first $x_i$, $x_\ell$, or $x_m$, ensuring that every mixed $2\times 2$ interaction between slices is order-invariant.

Step 3: sufficiency and necessity

Necessity: if any identity fails, then some mixed coefficient produced after two eliminations depends on whether a variable was eliminated earlier or later, producing different induced 2-variable functions.
Sufficiency: if all three identities hold, then every mixed interaction between coefficient pairs factors consistently, so all elimination sequences induce the same bilinear reduction on the remaining variables.

Hence the gates are good iff the three identities hold.

(b) Determination of bad gates for $f = (\det X)\bmod 2$

Let $x_i,x_\ell,x_m$ correspond to matrix entries $X_{ab},X_{cd},X_{ef}$.

Over $\mathbb{F}_2$,

$$ \det X = \sum_{\sigma \in S_n} \prod_r x_{r,\sigma(r)}, $$

so each coefficient $\alpha_t$ counts (mod 2) the number of permutations consistent with a partial assignment of the three entries.

Step 1: structural observation

Fixing values of $x_i,x_\ell,x_m$ forces inclusion or exclusion of specific matrix positions in a permutation. The parity of completions depends only on whether the partial assignment is consistent with a permutation.

If two chosen entries lie in the same row, they cannot simultaneously appear in any permutation term, so all monomials requiring both vanish.
If two lie in the same column, the same obstruction holds.

Thus in these cases, some $\alpha_t = 0$ while others are nonzero in an unbalanced way, immediately violating the identities from part (a).

Step 2: the non-degenerate case

Assume the three entries lie in distinct rows and distinct columns. Then specifying any subset of these entries does not interfere with the remaining choices in a permutation except for a simple restriction of row/column usage.

In this case, permutation completion splits as an independent extension problem:

each fixed choice of ${x_i,x_\ell,x_m}$ extends to the same number (mod 2) of full permutations.

Hence each coefficient factors as

$$ \alpha_t = c \cdot w_i^{t_i} w_\ell^{t_\ell} w_m^{t_m} $$

for constants $w_i,w_\ell,w_m\in\mathbb{F}_2$, so all cross-product identities in (a) hold automatically.

Step 3: conclusion

The identities fail exactly when some dependency between the three entries destroys independence of permutation extension, which occurs precisely when two entries share a row or a column.

Therefore:

The gate is bad iff at least two of $x_i,x_\ell,x_m$ lie in the same row or in the same column.
Equivalently, it is good iff the three selected matrix entries lie in distinct rows and distinct columns.