Vtree Alignment and Higher-Order Four-Corner Defects in Exact Boolean Factorization
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 and 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 and is semantically prime although every fixed-context two-variable slice has rank at most one.
1 Setup
Let 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 , let be the finest partition exposed recursively by the exact compressed-SDD cut criterion.
Proof. Every exposed factorization is valid, hence is a coarsening of . Conversely, build a binary vtree with one subtree for each block of 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 and a nonzero four-corner determinant witnessed by row assignments and column assignments . Let and be the coordinates on which the two row and two column assignments differ.
Proof. If not, after fixing all nonvarying coordinates every prime factor depends on row variables only, column variables only, or neither. Its corner table is rank one. Entrywise multiplication of rank-one outer products remains rank one, contradicting the nonzero determinant. □
Theorem 3 (No universal pairwise localization). For , let exactly for and . Then 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 four-corner defect exists only when the witness changes all coordinates of and all coordinates of .
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 , so it has at most one nonzero entry. Across , the only two nonzero matrix entries are the all-zero and all-one row/column pairs; a nonzero 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.