recognition › ask › explain-the-lean-structure-unsatgapcondition-in-module-indis-8ba712d9

Explain the Lean structure `UNSATGapCondition` in module `IndisputableMonolith.Complexity.SpectralGap`. Write for an educated reader who knows science and programming but may not know Lean. Cover: (1) what the declaration says in plain English, (2) why it matters in Recognition Science, (3) how to read the formal statement, (4) visible dependencies or certificates in the supplied source, and (5) what this declaration does not prove. Cite only declarations present in the supplied Recognition source.

permalink: https://pith.science/recognition/ask/explain-the-lean-structure-unsatgapcondition-in-module-indis-8ba712d9 · first asked 2026-05-10 · browse all asks

confidence: high in recognition cached

UNSATGapCondition in IndisputableMonolith.Complexity.SpectralGap

(1) In plain English, UNSATGapCondition n f is a bundled record asserting that a CNF formula f on n variables is unsatisfiable and that its J-cost landscape has a uniform positive lower bound on edge weights: there exists a positive integer min_sensitivity such that every jcostEdgeWeight f a k is at least this value.

(2) In Recognition Science this matters because the J-cost Laplacian models recognition as gradient descent on a cost landscape; a positive gap for unsatisfiable instances separates the landscape into distinct regions, supporting the forcing of recognition structures from cost minima and controlling convergence speed of the recognition operator.

(3) The formal statement is read as a Lean structure with four fields: is_unsat (witness that f is unsatisfiable), min_sensitivity (a natural number), sensitivity_pos (proof that the number is positive), and sensitivity_bound (universal quantification showing every edge weight meets or exceeds the minimum). In standard math this is the predicate "f is UNSAT and min-edge-weight(f) ≥ m > 0".

(4) Visible dependencies appear via imports of CNFFormula and jcostEdgeWeight; within the module it is used by unsat_has_positive_gap to extract a positive real gap, and it participates in the certificate SpectralGapCert alongside variance_nonneg and empty_formula_flat_landscape. The instance spectralGapCert records related landscape facts.

(5) The declaration does not prove existence of the gap for arbitrary unsat formulas, does not establish the Cheeger inequality, and does not derive iteration counts or full convergence rates (though iteration_bound_from_clauses exists separately).

cited recognition theorems

SpectralGap.UNSATGapCondition The structure whose meaning is requested.
SpectralGap.unsat_has_positive_gap Extracts a positive real gap value from the condition.
SpectralGap.SpectralGapCert Bundles the condition with related landscape certificates.
SpectralGap.variance_nonneg Provides non-negativity of variance used in the spectral-gap context.
SpectralGap.empty_formula_flat_landscape Shows the contrasting flat landscape for the empty (satisfiable) case.
SpectralGap.iteration_bound_from_clauses Related bound on iterations derived from a gap value.

outside recognition

Aspects Recognition does not yet address:

The Cheeger-type inequality `unsat_has_spectral_gap` (noted as containing a sorry in the module docstring).
Existence of an UNSATGapCondition for every unsatisfiable formula.
Direct derivation of convergence rates or full spectral-gap consequences beyond the positive-gap extraction.

recognition modules consulted

The Recognition library is at github.com/jonwashburn/shape-of-logic. The model is restricted to the supplied Lean source and instructed not to invent theorem names. Treat output as a starting point, not a verified proof.