Geometric consequences of the looseness–rigidity transition
OpenKSATSingleFlip.Connect.theorem_1_3_geometricThis is the geometric consequence of Theorem 1.3, without the theorem's deterministic algorithm or runtime clauses. Let and be the two density endpoints in (1.5), with the and corrections respectively.
For all sufficiently large fixed and sufficiently large , uniformly in the density, the following statements hold with probability at least . Below , the formula is satisfiable and a single set of at least solution mass has both properties: every variable can be reversed along a satisfying path of at most flips, and every solution in a Hamming ball of radius is connected by a satisfying path of at most flips. Here and is absolute.
From up to , the formula is satisfiable and all but an fraction of solutions have at least variables such that reversing any of them requires changing at least variables, where and . This supporting target does not assert the constructive or running-time parts of Theorem 1.3.
import Definitions.Def_KSATSingleFlip_Connect_LoosenessRigidity open scoped Classical BigOperators open Filter Topology
namespace KSATSingleFlip.Connect
/-- The geometric consequences of Theorem 1.3; the algorithmic runtime and
constructibility clauses are separate from this target. -/
theorem theorem_1_3_geometric :
∃ pathConstant : ℝ, 0 < pathConstant ∧
∃ δ : ℕ → ℝ, Tendsto δ atTop (𝓝 0) ∧
∃ k₀ : ℕ, ∀ k ≥ k₀,
∃ looseRadius rigidRadius exceptionRate : ℝ,
0 < looseRadius ∧ 0 < rigidRadius ∧ 0 < exceptionRate ∧
∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ m : ℕ,
((m : ℝ) / n ≤ geometryDensity k false →
1 - 1 / (n : ℝ) ≤ formulaProb n k m (fun F =>
HasLooseLocalGeometry k (ofFormula F) looseRadius pathConstant)) ∧
(geometryDensity k true ≤ (m : ℝ) / n →
(m : ℝ) / n ≤ (2 : ℝ)^k * (Real.log 2 - 1 / Real.log k) →
1 - 1 / (n : ℝ) ≤ formulaProb n k m (fun F =>
HasRigidGeometry (ofFormula F) (δ k) rigidRadius exceptionRate)) := by
sorry
end KSATSingleFlip.Connect