Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 17 — AND-NOT, OR and tie-breaker vertices

Proved
TwoOptAllExp.TSP.Supplement.lemma_17

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

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

Let D>0D>0D>0 and let zzz be a vertex whose neighbors are x≠yx\neq yx=y and possibly one further neighbor ttt. Let r=w(zt)(1−2σ(t))r=w(zt)(1-2\sigma(t))r=w(zt)(1−2σ(t)) if ttt exists and r=0r=0r=0 otherwise, and suppose ∣r∣<D|r|<D∣r∣<D.

  1. (AND-NOT) If w(zx)=−Dw(zx)=-Dw(zx)=−D, w(zy)=+Dw(zy)=+Dw(zy)=+D, bz=−Db_z=-Dbz​=−D, then Δz=2D(σ(x)−σ(y))−D+r\Delta_z=2D(\sigma(x)-\sigma(y))-D+rΔz​=2D(σ(x)−σ(y))−D+r, which equals D+rD+rD+r if (σ(x),σ(y))=(1,0)(\sigma(x),\sigma(y))=(1,0)(σ(x),σ(y))=(1,0) and is at most −D+r-D+r−D+r otherwise; hence z←x∧yˉz\leftarrow x\wedge\bar yz←x∧yˉ​.
  2. (OR) If w(zx)=w(zy)=−Dw(zx)=w(zy)=-Dw(zx)=w(zy)=−D and bz=+Db_z=+Dbz​=+D, then Δz=2D(σ(x)+σ(y))−D+r\Delta_z=2D(\sigma(x)+\sigma(y))-D+rΔz​=2D(σ(x)+σ(y))−D+r; hence z←x∨yz\leftarrow x\vee yz←x∨y.
  3. (tie breaker) Suppose ttt exists. If w(zx)=w(zy)=−Dw(zx)=w(zy)=-Dw(zx)=w(zy)=−D and bz=0b_z=0bz​=0, then
Δz=2D(σ(x)+σ(y)−1)+r.\Delta_z=2D(\sigma(x)+\sigma(y)-1)+r.Δz​=2D(σ(x)+σ(y)−1)+r.

Hence z←xz\leftarrow xz←x on assignments with σ(x)=σ(y)\sigma(x)=\sigma(y)σ(x)=σ(y); on assignments with σ(x)≠σ(y)\sigma(x)\ne\sigma(y)σ(x)=σ(y), z←tˉz\leftarrow\bar tz←tˉ if w(zt)>0w(zt)>0w(zt)>0 and z←tz\leftarrow tz←t if w(zt)<0w(zt)<0w(zt)<0.

These are the Boolean gates of the Section 5 gadgets.

Differences from the source:

  • encoding: z has neighbors x, y and possibly another neighbor t → t : Option V; the neighbors of z are exactly x, y and (if t = some t₀) t₀, with x ≠ y and t₀ ∉ {x, y}; reason: makes "possibly another" precise
  • encoding: suppose |r| < D → ∀ σ, |r(σ)| < D; reason: |r| equals |w(zt)| (or 0) for every σ, so this is the same condition
  • encoding: suppose t exists → ∀ t₀, t = some t₀ → …; reason: naming the existing neighbor
Preamble
import Mathlib
import Definitions.Def_TwoOptAllExp_TSP_Supplement_GraphObjective
Formal statement
namespace TwoOptAllExp.TSP.Supplement

/-- **Lemma 17** (p. 26). Let `D > 0`, let `z` have neighbors `x, y` and possibly another neighbor
`t` (`t = none`: no further neighbor). Let `r = w(zt)(1 - 2σ(t))` if `t` exists and `0` otherwise,
and suppose `|r| < D`.
(i) (AND-NOT) If `w(zx) = -D`, `w(zy) = +D`, `b_z = -D`, then `Δ_z = 2D(σ(x) - σ(y)) - D + r`, which is
`D + r` if `(σ(x), σ(y)) = (1, 0)` and at most `-D + r` otherwise; hence `z ← x ∧ ȳ`.
(ii) (OR) If `w(zx) = w(zy) = -D` and `b_z = +D`, then `Δ_z = 2D(σ(x) + σ(y)) - D + r`; hence `z ← x ∨ y`.
(iii) (tie breaker) Suppose `t` exists. If `w(zx) = w(zy) = -D` and `b_z = 0`, then
`Δ_z = 2D(σ(x) + σ(y) - 1) + r`. Hence `z ← x` on assignments with `σ(x) = σ(y)`; on assignments
with `σ(x) ≠ σ(y)`, `z ← t̄` if `w(zt) > 0` and `z ← t` if `w(zt) < 0`. -/
theorem lemma_17 {V : Type} [Fintype V] [DecidableEq V] (W : WGraph V) (D : ℤ) (hD : 0 < D)
    (z x y : V) (t : Option V) (hxy : x ≠ y) (htx : t ≠ some x) (hty : t ≠ some y)
    (hnbr : ∀ u : V, W.G.Adj z u ↔ (u = x ∨ u = y ∨ t = some u))
    (hr : ∀ σ : V → Bool, |W.tieTerm z t σ| < D) :
    (W.w s(z, x) = -D → W.w s(z, y) = D → W.b z = -D →
      (∀ σ : V → Bool,
        W.Δ z σ = 2 * D * (b2i (σ x) - b2i (σ y)) - D + W.tieTerm z t σ ∧
        ((σ x = true ∧ σ y = false) → W.Δ z σ = D + W.tieTerm z t σ) ∧
        (¬ (σ x = true ∧ σ y = false) → W.Δ z σ ≤ -D + W.tieTerm z t σ)) ∧
      W.Follows z (fun σ => σ x && !σ y)) ∧
    (W.w s(z, x) = -D → W.w s(z, y) = -D → W.b z = D →
      (∀ σ : V → Bool,
        W.Δ z σ = 2 * D * (b2i (σ x) + b2i (σ y)) - D + W.tieTerm z t σ) ∧
      W.Follows z (fun σ => σ x || σ y)) ∧
    (∀ t₀ : V, t = some t₀ → W.w s(z, x) = -D → W.w s(z, y) = -D → W.b z = 0 →
      (∀ σ : V → Bool,
        W.Δ z σ = 2 * D * (b2i (σ x) + b2i (σ y) - 1) + W.tieTerm z t σ) ∧
      W.FollowsOn z (fun σ => σ x) {σ | σ x = σ y} ∧
      (0 < W.w s(z, t₀) → W.FollowsOn z (fun σ => !σ t₀) {σ | σ x ≠ σ y}) ∧
      (W.w s(z, t₀) < 0 → W.FollowsOn z (fun σ => σ t₀) {σ | σ x ≠ σ y})) := 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, Lemma 17, p. 26

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