geometric_isolation_enables_propagation_hypothesis
The definition encodes the hypothesis that satisfiability of a CNF formula together with isolation by a linear-family XOR system implies the isolation invariant. Researchers in proof complexity would cite it when attempting to connect geometric isolation to backpropagation completeness. The definition is a direct Prop encoding that stands falsified by Tseitin formulas on expander graphs where the noStalls condition fails.
claimFor a CNF formula $φ$ on $n$ variables and an XOR system $H$, if $φ$ is satisfiable, $H$ isolates $φ$, and $H$ belongs to the linear family, then the isolation invariant holds: at least one unit XOR constraint exists, the propagation graph is connected, and no stall configurations occur.
background
The module builds fully-determined backpropagation states from total assignments. IsolationInvariant is the structure requiring hasUnits (a unit XOR constraint from $H$), connected (the propagation graph reaches all variables from initial units), and noStalls (BPStep always advances an incomplete state). The isolates predicate asserts that $φ$ conjoined with $H$ has a unique solution. The linearFamily enumerates small-bias XOR systems via mask-parity pairs up to $(n+1)^2$ pairs. Upstream, Satisfiable is the existence of an assignment evaluating the CNF to true.
proof idea
The declaration is a definition that directly assembles the implication from satisfiability, isolation, and linear-family membership to the isolation invariant as a Prop.
why it matters in Recognition Science
It is applied in the theorem geometric_isolation_enables_propagation_thm to conclude the isolation invariant from the three assumptions. The original intent was to support the geometric propagation theorem in the SAT completeness argument. The doc-comment records its falsification on 2026-04-07 via counterexamples from Ben-Sasson and Wigderson on expander Tseitin formulas, where noStalls cannot hold because local propagation stalls on incomplete states.
scope and limits
- Does not establish the isolation invariant for arbitrary satisfiable CNF formulas.
- Does not guarantee the noStalls property for expander-based Tseitin formulas.
- Does not assert intrinsic geometric structure in permutable SAT instances.
- Does not provide a constructive isolating XOR system for every satisfiable formula.
formal statement (Lean)
143def geometric_isolation_enables_propagation_hypothesis {n} (φ : CNF n) (H : XORSystem n) : Prop :=
proof body
Definition body.
144 Satisfiable φ → isolates φ H → H ∈ linearFamily n → IsolationInvariant n φ H
145