Recursive Halving and Shannon Expansion

3. Recursive Halving, Thue-Morse, and Shannon Cofactor Expansion

The core observation

Split any n-bit truth table by its most-significant input bit. Top half = rows where that bit is 0; bottom half = rows where it’s 1. What the bottom half needs from the top half depends on the gate:

AND — top half is always all-zero. Bottom half = the (n−1)-bit AND table itself, recursively:

AND_n = [ 0,0,...,0 (2^(n-1) zeros) , AND_(n-1) ]

OR — bottom half is always all-one. Top half = the (n−1)-bit OR table:

OR_n = [ OR_(n-1) , 1,1,...,1 (2^(n-1) ones) ]

XOR — bottom half = top half with every bit flipped:

XOR_n = [ XOR_(n-1) , NOT(XOR_(n-1)) ]

Check against n=2: XOR_1 = [0,1]. XOR_2 = [0,1, 1,0] — the top half [0,1] inverted gives the bottom half [1,0].

Why this scales

At n=2 this saves almost nothing. But the recursion is self-referential: XOR_3 = [XOR_2, invert(XOR_2)], XOR_4 = [XOR_3, invert(XOR_3)], and so on. Each new bit doubles the table via copy+invert — O(1) work per row instead of re-evaluating a growing boolean expression per row.

The tradeoff: this needs the whole table in memory to exploit (build once, copy-invert forever). A function recomputes on demand with zero storage but pays the per-row cost every time — a classic space/time tradeoff.

The Thue-Morse connection

The copy-then-invert doubling rule for XOR is the standard recursive definition of the Thue-Morse sequence (0, 1, 1, 0, 1, 0, 0, 1, …), which shows up in fair-division algorithms, avoiding resonance in physical systems, and combinatorics on words. The XOR truth table, ordered by binary counting, is the parity function — and the parity function’s value sequence is exactly Thue-Morse.

Sharper version: n/2 as a compression claim

A cleaner way to state the halving trick: you only ever need to store or compute half of the table’s components. The other half is fully determined by a fixed rule (copy for AND, invert for XOR, constant for OR). The table’s real degrees of freedom are 2^(n−1), not 2^n, even though it displays as a full-length vector.

XOR_n has 2^n entries, but only 2^(n-1) bits of actual information —
the rest is a deterministic mirror (invert) of the first half.

This is the same shape as a parity-check bit in error-correcting codes: the redundant half stores a checkable function of the first half, not new data.

The formal name: Shannon cofactor expansion

Splitting f(x1, x2, x3, …) by the first bit produces two cofactors:

Top half    = f with x1=0  →  the "0-cofactor," f₀
Bottom half = f with x1=1  →  the "1-cofactor," f₁

This is a real, established technique in digital design and formal verification. Combining the two cofactors elementwise with a boolean operator gives specific, named results:

f₀ XOR f₁ = the Boolean derivative of f with respect to x1. Wherever this is 1, flipping x1 changes the output; wherever it’s 0, x1 doesn’t matter for that row. This is how sensitivity analysis and test-pattern generation work in chip verification.

f₀ OR f₁ = existential quantification / smoothing: “does there exist a value of x1 that makes this row true?” Used constantly in formal verification (BDD-based model checking) to eliminate a variable while keeping everything still reachable.

f₀ AND f₁ = universal quantification / consensus: “is this row true no matter what x1 is?” The classic tool for finding redundant terms during logic minimization (used inside Quine-McCluskey).

Worked example: majority(x1, x2, x3)

Output 1 if 2 or more inputs are 1:

f₀ (x1=0): rows (x2,x3)=00,01,10,11 → 0,0,0,1
f₁ (x1=1): rows (x2,x3)=00,01,10,11 → 0,1,1,1

f₀ XOR f₁ = 0,1,1,0   → derivative: x1 matters exactly when x2≠x3
f₀ OR  f₁ = 0,1,1,1   → true if EITHER x2 or x3 is 1
f₀ AND f₁ = 0,0,0,1   → true only if x2 AND x3 both 1, regardless of x1

The “split, then combine the halves with AND/OR/XOR” instinct is the actual mechanism binary decision diagram (BDD) tools use to reason about which variables matter and where a circuit can be simplified.