Theorem C.4 — unknown radius with an archived tape
OpenCorrelatedLocalSearch.Supplement.theorem_C_4local-searchp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytheoretical-computer-scienceweak-random-sources
The exact archived-tape portfolio, using one base walk and geometrically scheduled radius- Hamming-ball simulations, needs neither nor . With and ,
The count includes all flips and restored coordinates; at most assignments and archived symbols are kept, and every selector sees only its simulation's local history.
Differences from the source:
- encoding: ceiling base-two logarithms →
Nat.clog 2; reason: identical on the positive and relevant in the theorem - encoding: expectation of the possibly infinite total update count → an
ENNReallower Lebesgue integral of an infinity-valued natural count; reason: nonintegrability gives infinity rather than a default value
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 C.4, pp.31-32 (PDF pp.33-34).
The exact archived-tape geometric portfolio removes both radius and slack inputs, preserving the
base mean while adding a radius-free exponential tail and explicit update/storage accounting. -/
theorem theorem_C_4 (k r : Nat) (hk : k < 2 * r) (hr : r < k) :
∃ c C : Real, 0 < c ∧ 0 < C ∧
∀ n (Phi : List (CorrelatedLocalSearch.Clause k n)) (x0 : Fin n -> Bool),
∀ baseSelector : CorrelatedLocalSearch.Selector k n,
CorrelatedLocalSearch.IsValidSelector Phi baseSelector ->
∀ localSelector : Nat -> CorrelatedLocalSearch.Selector k n,
(∀ j ≤ Nat.clog 2 n,
CorrelatedLocalSearch.IsValidSelector Phi (localSelector j)) ->
∃ A : ArchivedPortfolio k n Phi x0,
A.baseSelector = baseSelector ∧ A.localSelector = localSelector ∧
IsExactArchivedSchedule A ∧ A.simulatedAssignments ≤ 2 + Nat.clog 2 n ∧
∀ xs : Fin n -> Bool, CorrelatedLocalSearch.IsStrongWitness r Phi xs ->
let h := hammingDist x0 xs
1 ≤ h -> ∀ D : Real, 1 ≤ D ->
∀ s, CorrelatedLocalSearch.sStar k r ≤ s -> s ≤ 1 ->
∀ nu : Measure (Nat -> Fin k), nu ∈ CorrelatedLocalSearch.SourceClass k s D ->
let ellh := 1 + Nat.clog 2 h
let L := (h : Real) + Real.log D + 1
(∀ T : Nat, nu {omega | (T : ℕ∞) < portfolioSigma A omega} ≤
ENNReal.ofReal (min 1 (C * D * CorrelatedLocalSearch.lam k r ^ h *
Real.exp (-c * (T : Real) / ((h : Real) ^ 2 * (ellh : Real) ^ 2))))) ∧
(∫⁻ omega, ((portfolioSigma A omega : ℕ∞) : ENNReal) ∂nu) ≤
min (ENNReal.ofReal C * Psi k r s L)
(ENNReal.ofReal (C * (h : Real) ^ 2 * (ellh : Real) ^ 2 * L)) ∧
∀ omega, portfolioArchiveSize A omega ≤ portfolioSigma A omega := by sorry
end CorrelatedLocalSearch.Supplement
Source
Xu, Local Search with Correlated Randomness, arXiv:2607.17469 (sha256 17e00d69…), Theorem C.4, pp.31–32 (PDF pp.33–34)