Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Observation 20 — the three-block recursions of Ωn\Omega_nΩn​ and Ωˉn\bar\Omega_nΩˉn​

Proved
TwoOptAllExp.TSP.Supplement.observation_20

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricslocal-searchp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

For the strings of Section 5 obtained from RnR_nRn​ by the insertion rule: Ω0=Ωˉ0=R0\Omega_0=\bar\Omega_0=R_0Ω0​=Ωˉ0​=R0​, and for n≥1n\ge1n≥1

Ωn=(vn,1,vn,2,ρn(1),Ωn−1,αn,vn,3,vn,4,ρn(2),Ωˉn−1,αn,vn,5,vn,6,ρn(3),Ωn−1,αn,vn,7,vn,8),\Omega_n=(v_{n,1},v_{n,2},\rho_n^{(1)},\Omega_{n-1},\alpha_n,v_{n,3},v_{n,4},\rho_n^{(2)},\bar\Omega_{n-1},\alpha_n,v_{n,5},v_{n,6},\rho_n^{(3)},\Omega_{n-1},\alpha_n,v_{n,7},v_{n,8}),Ωn​=(vn,1​,vn,2​,ρn(1)​,Ωn−1​,αn​,vn,3​,vn,4​,ρn(2)​,Ωˉn−1​,αn​,vn,5​,vn,6​,ρn(3)​,Ωn−1​,αn​,vn,7​,vn,8​), Ωˉn=(vn,1,vn,2,ρn(4),Ωˉn−1,αn,vn,3,vn,4,ρn(5),Ωn−1,αn,vn,5,vn,6,ρn(0),Ωˉn−1,αn,vn,7,vn,8).\bar\Omega_n=(v_{n,1},v_{n,2},\rho_n^{(4)},\bar\Omega_{n-1},\alpha_n,v_{n,3},v_{n,4},\rho_n^{(5)},\Omega_{n-1},\alpha_n,v_{n,5},v_{n,6},\rho_n^{(0)},\bar\Omega_{n-1},\alpha_n,v_{n,7},v_{n,8}).Ωˉn​=(vn,1​,vn,2​,ρn(4)​,Ωˉn−1​,αn​,vn,3​,vn,4​,ρn(5)​,Ωn−1​,αn​,vn,5​,vn,6​,ρn(0)​,Ωˉn−1​,αn​,vn,7​,vn,8​).

The recursion is the form of the canonical sequence used in the induction of Lemma 24.

Differences from the source:

  • encoding: for n ≥ 1, Ω_{n−1} → n − 1 in ℕ under the hypothesis 1 ≤ n; reason: no truncation occurs
Preamble
import Mathlib
import Definitions.Def_TwoOptAllExp_TSP_Supplement_MCA232
Formal statement
namespace TwoOptAllExp.TSP.Supplement

open MCA232 MCA232.Vx

/-- **Observation 20** (p. 31). `Ω_0 = Ω̄_0 = R_0`, and for `n ≥ 1`
`Ω_n = (v_{n,1}, v_{n,2}, ρ_n^{(1)}, Ω_{n-1}, α_n, v_{n,3}, v_{n,4}, ρ_n^{(2)}, Ω̄_{n-1}, α_n, v_{n,5}, v_{n,6}, ρ_n^{(3)}, Ω_{n-1}, α_n, v_{n,7}, v_{n,8})`,
`Ω̄_n = (v_{n,1}, v_{n,2}, ρ_n^{(4)}, Ω̄_{n-1}, α_n, v_{n,3}, v_{n,4}, ρ_n^{(5)}, Ω_{n-1}, α_n, v_{n,5}, v_{n,6}, ρ_n^{(0)}, Ω̄_{n-1}, α_n, v_{n,7}, v_{n,8})`. -/
theorem observation_20 :
    Omega 0 = R 0 ∧ OmegaBar 0 = R 0 ∧
    ∀ n : ℕ, 1 ≤ n →
      Omega n = [v n 1, v n 2] ++ rho n 1 ++ Omega (n - 1) ++ alpha n ++
        [v n 3, v n 4] ++ rho n 2 ++ OmegaBar (n - 1) ++ alpha n ++
        [v n 5, v n 6] ++ rho n 3 ++ Omega (n - 1) ++ alpha n ++ [v n 7, v n 8] ∧
      OmegaBar n = [v n 1, v n 2] ++ rho n 4 ++ OmegaBar (n - 1) ++ alpha n ++
        [v n 3, v n 4] ++ rho n 5 ++ Omega (n - 1) ++ alpha n ++
        [v n 5, v n 6] ++ rho n 0 ++ OmegaBar (n - 1) ++ alpha n ++ [v n 7, v n 8] := by sorry

end TwoOptAllExp.TSP.Supplement
Source
Heimann, Hoang and Hougardy, Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment, November 2, 2026 preprint, STOC 2027 submission #112, SHA-256 9ac9fdf5ac1be95dff40e95db1590649f15b4eeb94559413175c88f9a42bff60, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/112.pdf, Observation 20, p. 31

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