One clause changes few trimmed factor balls
ProvedKSATSingleFlip.Connect.lemma_2_7_changed_ballsUnder the hypotheses of Lemma 2.7, appending a clause with at most variables changes at most locally tree-structured trimmed balls, where . The representation retains original clause occurrence labels, variable identities, and signed clauses. This is the changed-ball cardinality component of the lemma.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_TrimmedBall open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
/-- The changed-ball cardinality statement in Lemma 2.7. -/
theorem lemma_2_7_changed_balls {n : ℕ} (Φ : GFormula (Fin n)) (C : GClause (Fin n)) (k r D : ℕ)
(hk : 1 ≤ k) (hr : 1 ≤ r) (hD : 1 ≤ D)
(hwidth : ∀ c : Fin Φ.length, (vbl (Φ.get c)).card ≤ k) (hC : (vbl C).card ≤ k) :
(Finset.univ.filter fun v : Fin n =>
trimmedBall Φ v r D ≠ trimmedBall (Φ ++ [C]) v r D).card ≤
2 * k * ∑ h ∈ Finset.range (r + 2), (k * D)^h := by
sorry
end KSATSingleFlip.Connect
Source
Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 2.7 and (2.1), printed pp. 12–13 (PDF pp. 14–15), STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf