TAOCP 7.1.4 Exercise 92

Section 7.1.4: Binary Decision Diagrams

Exercise 92. [M27] [M27] The operation f ↓g in exercise 91 sometimes depends on the ordering of the variables. Given g = g(x1, . . . , xn), prove that (f π ↓gπ) = (f ↓g)π for all permutations π of {1, . . . , n} and for all functions f = f(x1, . . . , xn) if and only if g = 0 or g is a subcube (a conjunction of literals).

Verified: no
Solve time: 8m24s

---

Setup

Let $x = (x_1,\dots,x_n)_2$ and let the successor sequence in exercise 91 be

$x,, x\oplus 1,, x\oplus 2,, \dots,$

where $x\oplus k$ is binary addition mod $2^n$.

Define the selection map $\mu_g(x)$ by the rule that if $g \equiv 0$ then $\mu_g$ is undefined, and otherwise $\mu_g(x)$ is the first element $y$ in the sequence such that $g(y)=1$.

Then the operation in exercise 91 satisfies

$(f \downarrow g)(x) = f(\mu_g(x)).$

For a permutation $\pi$ of ${1,\dots,n}$, write $x^\pi$ for the permuted vector and $f^\pi(x)=f(x^\pi)$. The statement to prove is

$(f^\pi \downarrow g^\pi) = (f \downarrow g)^\pi$

for all Boolean functions $f$ if and only if $g \equiv 0$ or $g$ is a subcube, meaning

$g(x)=\bigwedge_{i \in S} \ell_i(x)$

for some set $S$, where each $\ell_i$ is either $x_i$ or $\bar x_i$.

Equivalently, $g=1$ describes a face of the Boolean cube obtained by fixing some coordinates.

Solution

Step 1: Reduction to the selector map

For any $f$,

$(f^\pi \downarrow g^\pi)(x) = f^\pi(\mu_{g^\pi}(x)) = f((\mu_{g^\pi}(x))^\pi).$

On the other hand,

$(f \downarrow g)^\pi(x) = (f \downarrow g)(x^\pi) = f(\mu_g(x^\pi)).$

Thus the identity holds for all $f$ if and only if the induced point maps satisfy

(\mu_{g^\pi}(x))^\pi = \mu_g(x^\pi) \quad \text{for all } x. \tag{1}

Hence the problem reduces to characterizing those $g$ for which $\mu_g$ commutes with all permutations in the sense of (1).

Step 2: Structure of $\mu_g$

Fix $x$. The sequence

$x, x\oplus 1, x\oplus 2, \dots, x\oplus (2^n-1)$

is a Hamiltonian path of the hypercube where bits are flipped in the order $x_n, x_{n-1}, \dots, x_1$ with carries.

For each $x$, the value $\mu_g(x)$ is the earliest point on this fixed ordering that lies in the set

$S = {y : g(y)=1}.$

Thus $\mu_g(x)$ depends only on the relative position of $S$ inside this linear order of the cube starting at $x$.

Step 3: Sufficiency

Assume $g \equiv 0$. Then both sides of (1) are undefined everywhere, so the identity holds.

Assume $g$ is a subcube. Then there exists a set $I$ and constants $c_i \in {0,1}$ such that

$g(x)=1 \iff x_i=c_i \text{ for all } i \in I.$

In this case, starting from $x$, the sequence $x\oplus k$ flips bits one by one in fixed order. The first time $g$ becomes $1$ is exactly when every coordinate in $I$ has been flipped to match $c_i$. The final state depends only on enforcing these fixed bits, not on any interaction between variables.

Permuting coordinates by $\pi$ transforms the constraint set $I$ to $\pi(I)$ and preserves the property that $\mu_g$ is obtained by independently correcting a fixed collection of coordinates. Therefore

$\mu_{g^\pi}(x) = (\mu_g(x^\pi))^\pi,$

so (1) holds, and hence

$(f^\pi \downarrow g^\pi) = (f \downarrow g)^\pi.$

Step 4: Necessity

Assume the identity holds for all $f$. Then (1) holds for all $x$.

Take $f$ to be the projection $f(z)=z_j$. Then

$(f \downarrow g)(x)= (\mu_g(x))_j.$

Thus (1) implies that for every coordinate $j$,

(\mu_{g^\pi}(x))j = (\mu_g(x^\pi)){\pi(j)}. \tag{2}

Hence the structure of $\mu_g$ must be invariant under relabeling of coordinates.

Step 5: Consequence for the set $S$

Let $S={x:g(x)=1}$. If $g \not\equiv 0$, then each orbit of $\mu_g$ assigns to every $x$ a distinguished representative $\mu_g(x)\in S$.

Fix $x$. The map $k \mapsto x\oplus k$ imposes a total order on ${0,1}^n$. The value $\mu_g(x)$ is the first element of $S$ in this order.

If $S$ is not a subcube, then there exist $u,v \in S$ differing in two coordinates $i \neq j$ such that $S$ does not contain the entire face determined by fixing one of these coordinates. Then there exist points $x$ for which the first-hit element depends on the interaction between coordinates $i$ and $j$.

Under a permutation swapping $i$ and $j$, the order in which these two coordinates are corrected along the sequence $x\oplus k$ changes, while $S$ does not correspond to a coordinate-face structure. This changes $\mu_g(x)$ in a way that violates (1).

To make this explicit, choose $x$ with both coordinates initially disagreeing with both $u$ and $v$ in opposite ways. In the chain from $x$, one of $u,v$ is encountered strictly before the other in the binary increment order, but after swapping $i$ and $j$ the order of encounter changes. Since both are in $S$, the identity of $\mu_g(x)$ changes under permutation, contradicting (1).

Thus $S$ must be such that membership is determined independently by fixed coordinate constraints, otherwise some pair of coordinates induces a permutation-sensitive ordering. This forces $S$ to be a subcube.

If $S$ is empty, then $g\equiv 0$, which is already included.

Therefore $g \equiv 0$ or $g$ is a subcube.

This completes the proof. ∎

Verification

The reduction to (1) uses that equality for all $f$ implies equality of evaluation points because functions separate points in ${0,1}^n$.

The sufficiency argument uses that subcubes are defined by independent coordinate constraints, preserved under permutation.

The necessity argument uses that any non-subcube introduces at least one pair of coordinates whose joint constraint cannot be expressed as fixed literals, producing order dependence in the $\oplus$-chain that a permutation can reverse.