Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Complete formula family, single-depth costs, Hamming-ball restarts and archived portfolio

Definition
CorrelatedLocalSearch_Supplement_SAT

by iris · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

local-searchp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytheoretical-computer-scienceweak-random-sources

The complete formula Φn\Phi_nΦn​ contains every ordered kkk-clause with rrr positive literals first and k−rk-rk−r negative literals, on distinct variables. The definition layer also supplies the exact worst survival probability, single-depth cover cost, Ψs(L)=min⁡{L3,L/(s−s∗)}\Psi_s(L)=\min\{L^3,L/(s-s_*)\}Ψs​(L)=min{L3,L/(s−s∗​)} with L/0=∞L/0=\inftyL/0=∞, the Hamming-ball restart walk, its source-flip stopping time and restoration cost, and the archived-tape portfolio schedule of Appendix C.6.

Formalization Note The complete family is constructed rather than introduced as an unrelated variable. Hamming resets consume no new tape symbol.

Definition code
import Mathlib
import Definitions.Def_CorrelatedLocalSearch_SourceClass
import Definitions.Def_CorrelatedLocalSearch_sStar
import Definitions.Def_CorrelatedLocalSearch_Clause
import Definitions.Def_CorrelatedLocalSearch_walkTau
import Definitions.Def_CorrelatedLocalSearch_Supplement_GeneralSource

set_option autoImplicit false

namespace CorrelatedLocalSearch.Supplement

open MeasureTheory
open scoped ENNReal BigOperators

/-- The complete family `Phi_n`: every ordered clause with `r` positive literals first and
`k-r` negative literals, on distinct variables. -/
noncomputable def completeFormula (k r n : Nat) : List (CorrelatedLocalSearch.Clause k n) := by
  classical
  let fs : Finset {f : Fin k -> Fin n // Function.Injective f} := Finset.univ
  exact fs.toList.map (fun f =>
    { lit := fun i => (f.1 i, decide (i.val < r))
      inj := f.2 })

/-- The all-one assignment, the complete family's strong witness. -/
def allOneAssignment (n : Nat) : Fin n -> Bool := fun _ => true

/-- An assignment has exactly `r` zero coordinates. -/
def HasExactlyRZeros {n : Nat} (r : Nat) (x : Fin n -> Bool) : Prop :=
  Set.ncard {i | x i = false} = r

/-- Survival of the published promise-SAT walk beyond a deadline. -/
def satSurvivalEvent {k n : Nat} (Phi : List (CorrelatedLocalSearch.Clause k n))
    (sel : CorrelatedLocalSearch.Selector k n) (x0 : Fin n -> Bool) (T : Nat) :
    Set (Nat -> Fin k) :=
  {omega | (T : ℕ∞) < CorrelatedLocalSearch.walkTau Phi sel x0 omega}

/-- The exact worst survival probability for the complete family at `D=1`. -/
noncomputable def completeWorstTail (k r n : Nat) (s : Real)
    (sel : CorrelatedLocalSearch.Selector k n) (x0 : Fin n -> Bool) (T : Nat) : ENNReal :=
  ⨆ nu : {nu : Measure (Nat -> Fin k) //
      nu ∈ CorrelatedLocalSearch.SourceClass k s 1},
    nu.1 (satSurvivalEvent (completeFormula k r n) sel x0 T)

/-- The uniform reference distribution on `[k]`. -/
noncomputable def uniformPi (k : Nat) : Fin k -> Real := fun _ => (k : Real)⁻¹

/-- The best single-depth cover cost for the complete-family survival event. -/
noncomputable def completeSingleDepthCost (k r n : Nat)
    (sel : CorrelatedLocalSearch.Selector k n) (x0 : Fin n -> Bool) (T t : Nat) : ENNReal :=
  singleDepthCost (uniformPi k) (CorrelatedLocalSearch.sStar k r)
    (satSurvivalEvent (completeFormula k r n) sel x0 T) t

/-- `Psi_s(L)=min{L^3,L/(s-s_*)}`, with the second branch infinite at the threshold. -/
noncomputable def Psi (k r : Nat) (s L : Real) : ENNReal :=
  min (ENNReal.ofReal (L ^ 3))
    (if s = CorrelatedLocalSearch.sStar k r then ⊤
      else ENNReal.ofReal (L / (s - CorrelatedLocalSearch.sStar k r)))

open Classical in
/-- One step of the Hamming-ball restart walk: reset an unsatisfying proposal outside radius
`2H` to `x0`, without consuming another source symbol. -/
noncomputable def hammingRestartStep {k n : Nat}
    (Phi : List (CorrelatedLocalSearch.Clause k n))
    (sel : CorrelatedLocalSearch.Selector k n) (x0 : Fin n -> Bool) (H : Nat)
    (pre : List (Fin k)) (x : Fin n -> Bool) (a : Fin k) : Fin n -> Bool :=
  let y := CorrelatedLocalSearch.walkStep Phi sel pre x a
  if CorrelatedLocalSearch.Satisfies Phi y then y
  else if 2 * H < hammingDist y x0 then x0 else y

noncomputable def hammingRestartRun {k n : Nat}
    (Phi : List (CorrelatedLocalSearch.Clause k n))
    (sel : CorrelatedLocalSearch.Selector k n) (x0 : Fin n -> Bool) (H : Nat) :
    List (Fin k) -> (Fin n -> Bool) -> List (Fin k) -> (Fin n -> Bool)
  | _, x, [] => x
  | pre, x, a :: rest =>
      hammingRestartRun Phi sel x0 H (pre ++ [a])
        (hammingRestartStep Phi sel x0 H pre x a) rest

noncomputable def hammingRestartState {k n : Nat}
    (Phi : List (CorrelatedLocalSearch.Clause k n))
    (sel : CorrelatedLocalSearch.Selector k n) (x0 : Fin n -> Bool) (H : Nat)
    (w : List (Fin k)) : Fin n -> Bool :=
  hammingRestartRun Phi sel x0 H [] x0 w

/-- Source-driven flips until the Hamming-ball restart walk satisfies the formula. -/
noncomputable def hammingRestartTau {k n : Nat}
    (Phi : List (CorrelatedLocalSearch.Clause k n))
    (sel : CorrelatedLocalSearch.Selector k n) (x0 : Fin n -> Bool) (H : Nat)
    (omega : Nat -> Fin k) : ℕ∞ :=
  ⨅ (t : Nat) (_h : CorrelatedLocalSearch.Satisfies Phi
      (hammingRestartState Phi sel x0 H (CorrelatedLocalSearch.tapePrefix omega t))), (t : ℕ∞)

open Classical in
/-- Variable updates used by the list-restoration implementation on a finite consumed word:
one per source-driven flip plus one per coordinate restored at each reset. -/
noncomputable def hammingRestartUpdateCost {k n : Nat}
    (Phi : List (CorrelatedLocalSearch.Clause k n))
    (sel : CorrelatedLocalSearch.Selector k n) (x0 : Fin n -> Bool) (H : Nat)
    (w : List (Fin k)) : Nat :=
  w.length + ∑ i : Fin w.length,
    let pre := w.take i.val
    let x := hammingRestartState Phi sel x0 H pre
    let y := CorrelatedLocalSearch.walkStep Phi sel pre x w[i]
    if ¬ CorrelatedLocalSearch.Satisfies Phi y ∧ 2 * H < hammingDist y x0
      then hammingDist y x0 else 0

/-- A deterministic archived-tape portfolio with the exact schedule in Appendix C.6 is represented
by its total update count and its semantic schedule obligations. -/
structure ArchivedPortfolio (k n : Nat)
    (Phi : List (CorrelatedLocalSearch.Clause k n)) (x0 : Fin n -> Bool) where
  simulatedAssignments : Nat
  baseSelector : CorrelatedLocalSearch.Selector k n
  auxiliaryRadius : Nat -> Nat
  groupAtRound : Nat -> Nat
  auxiliaryAtRound : Nat -> Nat
  activationCount : Nat -> Nat -> Nat
  localSelector : Nat -> CorrelatedLocalSearch.Selector k n

def portfolioHaltedByRound {k n : Nat}
    {Phi : List (CorrelatedLocalSearch.Clause k n)} {x0 : Fin n -> Bool}
    (A : ArchivedPortfolio k n Phi x0) (omega : Nat -> Fin k) (m : Nat) : Prop :=
  CorrelatedLocalSearch.Satisfies Phi
      (CorrelatedLocalSearch.walkState Phi A.baseSelector x0
        (CorrelatedLocalSearch.tapePrefix omega m)) ∨
    ∃ j ≤ Nat.clog 2 n,
      CorrelatedLocalSearch.Satisfies Phi
        (hammingRestartState Phi (A.localSelector j) x0 (A.auxiliaryRadius j)
          (CorrelatedLocalSearch.tapePrefix omega (A.activationCount j m)))

noncomputable def portfolioUpdatesAtRound {k n : Nat}
    {Phi : List (CorrelatedLocalSearch.Clause k n)} {x0 : Fin n -> Bool}
    (A : ArchivedPortfolio k n Phi x0) (omega : Nat -> Fin k) (m : Nat) : Nat :=
  m + ∑ j ∈ Finset.range (Nat.clog 2 n + 1),
    hammingRestartUpdateCost Phi (A.localSelector j) x0 (A.auxiliaryRadius j)
      (CorrelatedLocalSearch.tapePrefix omega (A.activationCount j m))

/-- Total variable updates at the first scheduled round in which a simulation satisfies `Phi`. -/
noncomputable def portfolioSigma {k n : Nat}
    {Phi : List (CorrelatedLocalSearch.Clause k n)} {x0 : Fin n -> Bool}
    (A : ArchivedPortfolio k n Phi x0) (omega : Nat -> Fin k) : ℕ∞ :=
  ⨅ (m : Nat) (_h : portfolioHaltedByRound A omega m),
    (portfolioUpdatesAtRound A omega m : ℕ∞)

/-- The number of source symbols retained when the first simulation halts.  The base walk reads
and archives exactly one new symbol per portfolio round. -/
noncomputable def portfolioArchiveSize {k n : Nat}
    {Phi : List (CorrelatedLocalSearch.Clause k n)} {x0 : Fin n -> Bool}
    (A : ArchivedPortfolio k n Phi x0) (omega : Nat -> Fin k) : ℕ∞ :=
  ⨅ (m : Nat) (_h : portfolioHaltedByRound A omega m), (m : ℕ∞)

/-- The exact schedule required of the portfolio: one base walk; auxiliary radii `2^j`; in round
`m>=1`, group `G_{v_2(m)}={2^b-1,...,2^(b+1)-2}` advances cyclically; auxiliary activation `q`
replays archived symbol `omega_q`; resets restore changed coordinates. -/
def IsExactArchivedSchedule {k n : Nat}
    {Phi : List (CorrelatedLocalSearch.Clause k n)} {x0 : Fin n -> Bool}
    (A : ArchivedPortfolio k n Phi x0) : Prop :=
  A.simulatedAssignments = 2 + Nat.clog 2 n ∧
  (∀ j, A.auxiliaryRadius j = 2 ^ j) ∧
  (∀ m, 0 < m -> 2 ^ A.groupAtRound m ∣ m ∧
    ¬ 2 ^ (A.groupAtRound m + 1) ∣ m) ∧
  (∀ m, 0 < m ->
    2 ^ A.groupAtRound m - 1 ≤ A.auxiliaryAtRound m ∧
    A.auxiliaryAtRound m ≤ 2 ^ (A.groupAtRound m + 1) - 2 ∧
    A.auxiliaryAtRound m = 2 ^ A.groupAtRound m - 1 +
      (((m / 2 ^ A.groupAtRound m - 1) / 2) % 2 ^ A.groupAtRound m)) ∧
  (∀ j m, A.activationCount j m =
    ((Finset.Icc 1 m).filter (fun q => A.auxiliaryAtRound q = j)).card)

/-- Main catalog declaration for the complete-family and restart SAT supplement. -/
noncomputable abbrev SAT (k r n : Nat) := completeFormula k r n

end CorrelatedLocalSearch.Supplement
Source
Xu, Local Search with Correlated Randomness, arXiv:2607.17469 (sha256 17e00d69…), §4 pp.10–12 and App. C.5–C.6 pp.31–32 (PDF pp.12–14, 33–34)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me