Theorem 2.13 — r/b ≤ k ≤ r for an inequality with defect r and N-index k
ProvedLovaszSchrijver.Defect.defect_div_le_NIndex_le_defectLet be a finite graph with no isolated nodes, and let be an inequality with integer coefficients , , valid for , with defect
and N-index (the least such that is valid for ). Then
stated with the denominator cleared as
The theorem shows that the number of rounds of the Lovász–Schrijver operator needed to derive a stable set inequality is controlled by how far the fractional stable set polytope violates it: an inequality violated by at most on is valid after rounds, and cannot be valid before rounds.
Formalization Note
- The lower bound is written rather than . For the two are equivalent; for validity for forces and , and the cleared form avoids Lean's convention .
- The hypothesis is added. The paper's proof starts "If we have nothing to prove, so suppose that ", presuming ; without it the upper bound fails (for on a single edge, while ). It holds whenever , because .
- The defect and the N-index are given as values , with
IsGreatestandIsLeasthypotheses, never as a supremum or infimum. Coefficients are natural numbers cast to .
import Mathlib import Definitions.Def_LovaszSchrijver_Defect_Index
namespace LovaszSchrijver.Defect
theorem defect_div_le_NIndex_le_defect {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] (hG : ∀ v, ∃ w, G.Adj v w)
(a : V → ℕ) (b : ℕ) (hvalid : Valid (STAB G) (fun i => (a i : ℝ)) b)
(r : ℝ) (hr : IsDefect G (fun i => (a i : ℝ)) b r) (hr0 : 0 ≤ r)
(k : ℕ) (hk : IsNIndex G (fun i => (a i : ℝ)) b k) :
r ≤ k * b ∧ (k : ℝ) ≤ r := by sorry
end LovaszSchrijver.Defect
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Throughout, is any type with finitely many elements and decidable equality. is a simple graph on the vertex set (no loops, undirected), and its adjacency relation is decidable. Four notions come from the imported definitions bundle: , , and . Their definitions are not part of the code given here, so this read-back can only name them. What they actually require has to be checked in that bundle.
The statement has these inputs and hypotheses:
- No isolated vertices. Every vertex has at least one neighbour:
- An inequality with natural-number data. There is a coefficient vector and a right-hand side . The vector enters every predicate below as the real vector , with each viewed as a real number.
- Validity. The pair satisfies . Here is an object built from by the bundle's definition .
- A defect value. is a real number with and .
- An N-index value. is a natural number with .
Under all these hypotheses, the theorem concludes both inequalities, computed in the real numbers:
The conclusion holds for every real that satisfies the defect predicate with , and for every natural that satisfies the N-index predicate. The code does not say that either predicate picks out a unique value. The two inequalities together imply , and also with . Both inequalities are non-strict ().
Degenerate cases. If is empty, the no-isolated-vertex hypothesis holds vacuously. The graph then has no vertices and is the empty vector. The conclusion still requires , provided the three bundle predicates can hold for that empty data.
If has exactly one element, the no-isolated-vertex hypothesis cannot hold, because a simple graph has no loops. The theorem is therefore vacuous for one-vertex .
If , the conclusion becomes and . With , this forces and . If (with any ), the conclusion likewise forces .
The statement uses no division, no subtraction and no suprema or integrals, so no default values from Lean's total functions enter it directly. Any such default values would sit inside the unseen definitions of , , and .
Whether those three predicates can hold at the same time for a given , and cannot be determined from this code. If they never can, the theorem is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.