Structured Boolean Factorization

Vtree Alignment and Higher-Order Four-Corner Defects in Exact Boolean Factorization

Research draft

29 September 2026

Abstract

We isolate two structural limits in exact AND-factor extraction from vtree-structured Boolean representations. First, maximizing the number of factors exposed by exact vtree cuts is a complete objective: its global optimum equals the semantic prime-factor count, while hard carrier-subtree constraints are compatible with semantic prime alignment exactly when the carrier and semantic block families are laminar. Second, a nonzero four-corner defect with varying supports U and W proves that some semantic prime block meets both supports, but this cannot in general be reduced to a pairwise interaction. The family supported only on 0n and 1n is semantically prime although every fixed-context two-variable slice has rank at most one.

1 Setup

Let Πf denote the canonical finest partition of the variable set for which a nonfalse Boolean function factors as a conjunction of functions on disjoint blocks. For a vtree T, let ET (f) be the finest partition exposed recursively by the exact compressed-SDD cut criterion.

Theorem 1 (Exposure optimum). For every nonfalse Boolean function f,

max ⁡ T |ET (f)| = |Πf|.

Proof. Every exposed factorization is valid, hence is a coarsening of Πf. Conversely, build a binary vtree with one subtree for each block of Πf and combine those subtrees arbitrarily. Every internal split is a union of prime blocks against its complement and therefore factors; recursion reaches all prime blocks. □

Theorem 2 (Carrier/semantic compatibility). Let Π and Σ be partitions of the same ground set. A binary rooted leaf-labelled tree can contain every block of both partitions as a subtree leaf set if and only if the combined block family Π ∪Σ is laminar.

Proof. Subtree leaf sets form a laminar family, giving necessity. Conversely, represent the inclusion poset of a finite laminar family as a rooted tree and refine nodes of degree greater than two by inserting binary nodes. □

2 Defect support

Consider a cut A∣B and a nonzero four-corner determinant witnessed by row assignments a0,a1 and column assignments b0,b1. Let U ⊆ A and W ⊆ B be the coordinates on which the two row and two column assignments differ.

Lemma 1 (Support crossing). Some block of Πf intersects both U and W.

Proof. If not, after fixing all nonvarying coordinates every prime factor depends on row variables only, column variables only, or neither. Its 2 × 2 corner table is rank one. Entrywise multiplication of rank-one outer products remains rank one, contradicting the nonzero determinant. □

Corollary 1. If U = {x} and W = {y}, then x and y are in the same semantic prime block.

Theorem 3 (No universal pairwise localization). For n ≥ 3, let fn(x) = 1 exactly for x = 0n and x = 1n. Then Πfn consists of one block, but every two-variable restriction obtained by fixing all remaining coordinates has matrix rank at most one. For every nontrivial cut A∣B, a four-corner defect exists only when the witness changes all coordinates of A and all coordinates of B.

Proof. A nontrivial product decomposition would make the two-point satisfying relation a nontrivial Cartesian product, which would contain mixed combinations; hence the function is prime. A fixed-context two-variable slice contains at most one of 0n,1n, so it has at most one nonzero entry. Across A∣B, the only two nonzero matrix entries are the all-zero and all-one row/column pairs; a nonzero 2 × 2 minor must select both, forcing all cut-side coordinates to change. □

3 Interpretation

The results support hyperedge-valued defect evidence rather than automatic pairwise must-link edges. They also show that carrier blocks should not be hard-wired into vtrees when they cross emerging semantic factors.