Theorem 4.2 — sharp threshold and gap from every single depth
OpenCorrelatedLocalSearch.Supplement.theorem_4_2local-searchp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytheoretical-computer-scienceweak-random-sources
For the complete formula family, every admits one source forcing nontermination for every selector. Starting with exactly zeros, uniformly in , and , the exact worst survival probability is bounded above and below by constant multiples in the exponent of
At and , the infimum over all single-depth cover costs is bounded above and below by positive -dependent constants times .
Differences from the source:
- encoding: notation → positive upper and lower constants quantified before ; reason: expands uniform asymptotic notation without changing instances
- encoding: → natural-number expression under the source hypothesis ; reason: the hypothesis excludes truncation at the boundary
- encoding: worst probabilities and cover costs written as nonnegative real quantities →
ENNReal; reason: exact extended-nonnegative encoding
Preamble
import Mathlib import Definitions.Def_CorrelatedLocalSearch_Supplement_SAT set_option autoImplicit false
Formal statement
namespace CorrelatedLocalSearch.Supplement
open MeasureTheory
open scoped ENNReal BigOperators
/-- Xu, arXiv:2607.17469 (sha256 17e00d69…), Theorem 4.2, p.11 (PDF p.13).
The complete formula family has the sharp threshold, the uniform three-regime two-sided survival
profile, and the two-sided polynomial cost for every single-depth cover. -/
theorem theorem_4_2 (k r : Nat) (hk : k < 2 * r) (hr : r < k) :
∃ cLower cUpper dLower dUpper : Real,
0 < cLower ∧ 0 < cUpper ∧ 0 < dLower ∧ 0 < dUpper ∧
(∀ s, 0 < s -> s < CorrelatedLocalSearch.sStar k r ->
∃ (n : Nat) (x0 : Fin n -> Bool) (nu : Measure (Nat -> Fin k)),
nu ∈ CorrelatedLocalSearch.SourceClass k s 1 ∧
¬ CorrelatedLocalSearch.Satisfies (completeFormula k r n) x0 ∧
∀ sel, CorrelatedLocalSearch.IsValidSelector (completeFormula k r n) sel ->
nu {omega | CorrelatedLocalSearch.walkTau (completeFormula k r n) sel x0 omega = ⊤} = 1) ∧
∀ n, 3 ≤ n - k + 2 -> ∀ (x0 : Fin n -> Bool), HasExactlyRZeros r x0 ->
∀ sel, CorrelatedLocalSearch.IsValidSelector (completeFormula k r n) sel ->
(∀ s, CorrelatedLocalSearch.sStar k r ≤ s -> s ≤ 1 -> ∀ T : Nat, 1 ≤ T ->
let X : Real := (T : Real) ^ ((1 : Real) / 3) +
(s - CorrelatedLocalSearch.sStar k r) * T + T / ((n - k + 2 : Nat) : Real) ^ 2
(∃ nu : Measure (Nat -> Fin k), nu ∈ CorrelatedLocalSearch.SourceClass k s 1 ∧
nu (satSurvivalEvent (completeFormula k r n) sel x0 T) =
completeWorstTail k r n s sel x0 T) ∧
ENNReal.ofReal (Real.exp (-cUpper * X)) ≤ completeWorstTail k r n s sel x0 T ∧
completeWorstTail k r n s sel x0 T ≤ ENNReal.ofReal (Real.exp (-cLower * X))) ∧
∀ T : Nat, 1 ≤ T -> T ≤ n - k ->
ENNReal.ofReal (dLower * (T + 1 : Real) ^ (-(3 : Real) / 2)) ≤
(⨅ t, completeSingleDepthCost k r n sel x0 T t) ∧
(⨅ t, completeSingleDepthCost k r n sel x0 T t) ≤
ENNReal.ofReal (dUpper * (T + 1 : Real) ^ (-(3 : Real) / 2)) := by sorry
end CorrelatedLocalSearch.Supplement
Source
Xu, Local Search with Correlated Randomness, arXiv:2607.17469 (sha256 17e00d69…), Theorem 4.2, p.11 (PDF p.13)