linopt_major_cycle_discards_corral_atom
The formal major-cycle relation can discard the previous atom even though the enlarged two-atom support is already a corral, for the base polytope of a normalized submodular function.
Statement
theorem linopt_major_cycle_discards_corral_atom :
∃ (f : Finset (Fin 2) → ℝ) (p q r : Fin 2 → ℝ),
f ∅ = 0 ∧ is_submodular f ∧
base_polytope_extreme_bases f = ({p,q} : Set (Fin 2 → ℝ)) ∧
wolfe_major_cycle (base_polytope_extreme_bases f) {p} {q} p q ∧
is_wolfe_corral ({p,q} : Finset (Fin 2 → ℝ)) r ∧ p ≠ q- Source
- Counterexample to the stated transition relation, compared with the algorithm in arXiv:2611.12680 Section 2.2.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- wolfe_major_cycleFor a set atoms : Set (Fin n → ℝ), finite subsets S, S' : Finset (Fin n → ℝ), and vectors w, w' : Fin n → ℝ, wolfe_major_cycle atoms S S'…
- is_wolfe_corralA non-empty finite set S of atoms in ℝ^n is a corral with affine minimizer w if w is an affine combination of S with strictly positive…
- is_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.
- base_polytope_extreme_basesThe set of greedy bases of a set function f on Finset (Fin n) consists of the vectors generated by Edmonds' greedy algorithm over all…
The proof, explained
To show that Wolfe's major-cycle relation can discard an atom from the active set even when the enlarged two-atom set is already a corral, the proof constructs an explicit two-dimensional counterexample on the base polytope of a normalized submodular function. On the two-element ground set, a submodular function f is defined whose base polytope has extreme bases p = (3, 0) and q = (1, 2). Starting from the singleton corral {p}, Wolfe's major cycle selects q as the entering atom and transitions to {q}, discarding p while decreasing the norm from 9 to 5. However, the enlarged set {p, q} was already a valid corral with strict interior minimizer r = (3/2, 3/2).
Every singleton set {p} ⊂ ℝ² is a Wolfe corral with minimizer p.
By definition, a finite set S with vector w is a Wolfe corral if S is nonempty, w is the orthogonal projection onto the affine hull of S (so ⟨w, x - w⟩ = 0 for all x ∈ S), and w is expressed as a strictly positive convex combination of elements in S. For S = {p} and w = p, nonemptiness is immediate, the only element is x = p where ⟨p, p - p⟩ = 0, and the weight c(p) = 1 > 0 provides the required convex combination.
classical refine ⟨by simp, ?_, ?_⟩ · intro x hx have : x=p := by simpa using hx subst x simp · refine ⟨fun _ => 1, ?_, ?_, ?_⟩ · simp · simp · simp
Define vectors p = (3, 0), q = (1, 2), and r = (3/2, 3/2), and prove that p ≠ q.
We introduce p = (3, 0), q = (1, 2), and r = (3/2, 3/2) into scope. To prove p ≠ q, we evaluate both functions at index 0, obtaining 3 and 1 respectively, which contradicts equality. By symmetry of inequality, q ≠ p also holds.
uses
congrFun,Ne.symmclassical let p : Fin 2 → ℝ := ![3,0] let q : Fin 2 → ℝ := ![1,2] let r : Fin 2 → ℝ := ![(3:ℝ)/2,3/2] have hpq : p ≠ q := by intro h have hh := congrFun h 0 norm_num [p,q] at hh have hqp : q ≠ p := Ne.symm hpq refine ⟨p,q,r,rfl,rfl,?_,?_,hpq⟩
A Wolfe major cycle transitions from corral {p} with minimizer p to corral {q} with minimizer q over the atom set {p, q}.
Both {p} and {q} are corrals by the singleton lemma. Choosing q as the entering atom, the Wolfe descent criterion ⟨p, q - p⟩ = 3(1 - 3) + 0(2 - 0) = -6 < 0 holds. Furthermore, q minimizes the linear form ⟨p, ·⟩ over {p, q} because ⟨p, q⟩ = 3 ≤ 9 = ⟨p, p⟩. The next support {q} is a subset of {p, q} containing q, and the squared Euclidean norm strictly decreases from ‖p‖² = 9 to ‖q‖² = 5.
uses
in772_counterexampleproof_single,Fin.sum_univ_two,Set.mem_insert_iff,Set.mem_singleton_iff· refine ⟨in772_counterexampleproof_single p,in772_counterexampleproof_single q,?_,?_,q,?_,?_,?_,?_,?_,?_⟩ · simp · simp · simp · norm_num [p,q,Fin.sum_univ_two] · intro x hx simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> norm_num [p,q,Fin.sum_univ_two] · simp · simp · norm_num [p,q,Fin.sum_univ_two]
The two-atom support {p, q} is already a Wolfe corral with minimizer r = (3/2, 3/2).
The set {p, q} is nonempty. The orthogonal projection condition ⟨r, x - r⟩ = 0 holds for both atoms: for x = p, ⟨(3/2, 3/2), (3/2, -3/2)⟩ = 0, and for x = q, ⟨(3/2, 3/2), (-1/2, 1/2)⟩ = 0. Assigning weights c(p) = 1/4 and c(q) = 3/4, both are strictly positive, sum to 1, and produce (1/4)p + (3/4)q = (3/2, 3/2) = r, placing r in the strict relative interior of the simplex.
uses
Finset.mem_insert,Finset.mem_singleton,Fin.sum_univ_two· refine ⟨by simp, ?_, ?_⟩ · intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl <;> norm_num [p,q,r,Fin.sum_univ_two] · let c : (Fin 2 → ℝ) → ℝ := fun x => if x=p then 1/4 else 3/4 refine ⟨c, ?_, ?_, ?_⟩ · simp [c,hpq,hqp]; norm_num · intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl <;> simp [c,hpq,hqp] <;> norm_num · ext i fin_cases i <;> simp [c,hpq,hqp,p,q,r] <;> norm_num
The function f on subsets of Fin 2 defined by f(S) = 3 if 0 ∈ S, else 2 if 1 ∈ S, else 0, is normalized and submodular. automation
We verify f(∅) = 0 by definition. Submodularity requires that for any S ⊆ T ⊂ Fin 2 and j ∉ T, the marginal return satisfies f(T ∪ {j}) - f(T) ≤ f(S ∪ {j}) - f(S). Since the ground set has only two elements, an exhaustive case split over all possible S, T, and j leaves 64 cases, all of which are closed by arithmetic evaluation.
uses
Finset.subset_iffconstructor · norm_num [in772_counterexampleproof_f] · classical intro S T j hST hj fin_cases S <;> fin_cases T <;> fin_cases j <;> norm_num [in772_counterexampleproof_f,Finset.subset_iff] at *
Every extreme base of the base polytope B(f) is either p = (3, 0) or q = (1, 2).
An extreme base a is generated by a permutation π of Fin 2 through greedy marginal increases. Since Fin 2 has two elements, π⁻¹(0) must be 0 or 1. If π⁻¹(0) = 0, injectivity forces π⁻¹(1) = 1 (the identity permutation), which evaluates to (f({0}) - f(∅), f({0, 1}) - f({0})) = (3, 0) = p. If π⁻¹(0) = 1, injectivity forces π⁻¹(1) = 0 (the transposition swapping 0 and 1), which evaluates to (f({0, 1}) - f({1}), f({1}) - f(∅)) = (1, 2) = q.
uses
Set.mem_setOf_eq,Set.mem_insert_iff,Set.mem_singleton_iffext a simp only [base_polytope_extreme_bases, Set.mem_setOf_eq, Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨pi,rfl⟩ have hpi : pi.symm 0 = 0 ∨ pi.symm 0 = 1 := by have hh := (pi.symm 0).isLt omega have hn : pi.symm 1 ≠ pi.symm 0 := by intro h have hbad := pi.symm.injective h norm_num at hbad rcases hpi with h0 | h0 · have h1 : pi.symm 1 = 1 := by have hh := (pi.symm 1).isLt omega left funext i fin_cases i <;> norm_num [in772_counterexampleproof_f,h0,h1] · have h1 : pi.symm 1 = 0 := by have hh := (pi.symm 1).isLt omega right funext i fin_cases i <;> norm_num [in772_counterexampleproof_f,h0,h1]
Both p and q are extreme bases of B(f), hence the extreme bases are precisely {p, q}.
To show the reverse inclusion, we witness p using the identity permutation (Equiv.refl) and q using the transposition swapping 0 and 1 (Equiv.swap 0 1). Evaluating the marginal increments in both cases confirms that they yield (3, 0) and (1, 2) respectively.
uses
Equiv.refl,Equiv.swap,Equiv.swap_apply_def· rintro (rfl | rfl) · refine ⟨Equiv.refl _, ?_⟩ funext i fin_cases i <;> norm_num [in772_counterexampleproof_f] · refine ⟨Equiv.swap 0 1, ?_⟩ funext i fin_cases i <;> norm_num [in772_counterexampleproof_f,Equiv.swap_apply_def]
There exists a normalized submodular function f and points p, q, r satisfying all counterexample conditions.
We combine the submodular function f with the geometric counterexample points p, q, r. The function f is normalized and submodular by the earlier lemma, its extreme bases match {p, q}, the major-cycle transition from {p} to {q} over {p, q} holds, and {p, q} is already a corral with minimizer r, with p ≠ q.
uses
in772_counterexampleproof_counterexample,in772_counterexampleproof_f_submodular,in772_counterexampleproof_atomsobtain ⟨p,q,r,hp,hq,hstep,hcorral,hne⟩ := in772_counterexampleproof_counterexample refine ⟨in772_counterexampleproof_f,p,q,r,in772_counterexampleproof_f_submodular.1,in772_counterexampleproof_f_submodular.2,?_,?_,hcorral,hne⟩ · simpa [hp,hq] using in772_counterexampleproof_atoms · simpa [in772_counterexampleproof_atoms,hp,hq] using hstep
The formal major-cycle relation can discard a previous atom even though the enlarged support is already a corral, for the base polytope of a normalized submodular function.
The theorem is concluded immediately by applying the assembled counterexample lemma.
uses
in772_counterexampleproof_submodular_false_transitionexact in772_counterexampleproof_submodular_false_transition
congrFun- If two functions are equal, their values at any argument are equal.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
in772_counterexampleproof_single- Any singleton set {p} in ℝ² is a Wolfe corral with minimizer p.
Fin.sum_univ_two- The sum of a function over the two-element type Fin 2 is the sum of its values at 0 and 1.
Set.mem_insert_iff- An element x belongs to insert a s if and only if x = a or x ∈ s.
Set.mem_singleton_iff- An element x belongs to {b} if and only if x = b.
Finset.mem_insert- An element x belongs to the finset insert b s if and only if x = b or x ∈ s.
Finset.mem_singleton- An element b belongs to the finset singleton {a} if and only if b = a.
Finset.subset_iff- A finset s₁ is a subset of s₂ if and only if every element of s₁ belongs to s₂.
Set.mem_setOf_eq- Membership in a set comprehension {x | p x} is equivalent to p x.
Equiv.refl- The identity permutation on a type.
Equiv.swap- The transposition permutation that swaps two given elements and fixes all others.
Equiv.swap_apply_def- Applying Equiv.swap a b to x yields b if x = a, a if x = b, and x otherwise.
in772_counterexampleproof_counterexample- The points p = (3, 0), q = (1, 2), and r = (3/2, 3/2) satisfy p ≠ q, a major cycle can transition from support {p} to {q}, and {p, q} is already a corral with minimizer r.
in772_counterexampleproof_f_submodular- The function in772_counterexampleproof_f is normalized (vanishes on ∅) and submodular.
in772_counterexampleproof_atoms- The extreme bases of the base polytope of in772_counterexampleproof_f are precisely (3, 0) and (1, 2).
in772_counterexampleproof_submodular_false_transition- There exist a normalized submodular function f and points p, q, r witnessing that a major cycle can discard an atom from a corral.
- In step 5, submodularity of f is proved by brute-force exhaustion of all 64 combinations of subsets S, T ⊆ Fin 2 and elements j ∉ T via fin_cases and norm_num.
- The notions is_wolfe_corral and wolfe_major_cycle are formalizations specific to this knowledge base: a corral requires the orthogonal projection to lie in the strict interior of the convex hull of the active set.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped BigOperatorsset_option backward.isDefEq.respectTransparency falseprivate lemma in772_counterexampleproof_single (p : Fin 2 → ℝ) : is_wolfe_corral {p} p := by classical refine ⟨by simp, ?_, ?_⟩ · intro x hx have : x=p := by simpa using hx subst x simp · refine ⟨fun _ => 1, ?_, ?_, ?_⟩ · simp · simp · simpprivate lemma in772_counterexampleproof_counterexample : ∃ (p q r : Fin 2 → ℝ), p = ![3,0] ∧ q = ![1,2] ∧ wolfe_major_cycle ({p, q} : Set (Fin 2 → ℝ)) {p} {q} p q ∧ is_wolfe_corral ({p,q} : Finset (Fin 2 → ℝ)) r ∧ p ≠ q := by classical let p : Fin 2 → ℝ := ![3,0] let q : Fin 2 → ℝ := ![1,2] let r : Fin 2 → ℝ := ![(3:ℝ)/2,3/2] have hpq : p ≠ q := by intro h have hh := congrFun h 0 norm_num [p,q] at hh have hqp : q ≠ p := Ne.symm hpq refine ⟨p,q,r,rfl,rfl,?_,?_,hpq⟩ · refine ⟨in772_counterexampleproof_single p,in772_counterexampleproof_single q,?_,?_,q,?_,?_,?_,?_,?_,?_⟩ · simp · simp · simp · norm_num [p,q,Fin.sum_univ_two] · intro x hx simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl <;> norm_num [p,q,Fin.sum_univ_two] · simp · simp · norm_num [p,q,Fin.sum_univ_two] · refine ⟨by simp, ?_, ?_⟩ · intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl <;> norm_num [p,q,r,Fin.sum_univ_two] · let c : (Fin 2 → ℝ) → ℝ := fun x => if x=p then 1/4 else 3/4 refine ⟨c, ?_, ?_, ?_⟩ · simp [c,hpq,hqp]; norm_num · intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl <;> simp [c,hpq,hqp] <;> norm_num · ext i fin_cases i <;> simp [c,hpq,hqp,p,q,r] <;> norm_numprivate def in772_counterexampleproof_f (S : Finset (Fin 2)) : ℝ := if (0 : Fin 2) ∈ S then 3 else if (1 : Fin 2) ∈ S then 2 else 0private lemma in772_counterexampleproof_f_submodular : in772_counterexampleproof_f ∅ = 0 ∧ is_submodular in772_counterexampleproof_f := by constructor · norm_num [in772_counterexampleproof_f] · classical intro S T j hST hj fin_cases S <;> fin_cases T <;> fin_cases j <;> norm_num [in772_counterexampleproof_f,Finset.subset_iff] at *private lemma in772_counterexampleproof_atoms : base_polytope_extreme_bases in772_counterexampleproof_f = ({(![3,0] : Fin 2 → ℝ), ![1,2]} : Set (Fin 2 → ℝ)) := by ext a simp only [base_polytope_extreme_bases, Set.mem_setOf_eq, Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨pi,rfl⟩ have hpi : pi.symm 0 = 0 ∨ pi.symm 0 = 1 := by have hh := (pi.symm 0).isLt omega have hn : pi.symm 1 ≠ pi.symm 0 := by intro h have hbad := pi.symm.injective h norm_num at hbad rcases hpi with h0 | h0 · have h1 : pi.symm 1 = 1 := by have hh := (pi.symm 1).isLt omega left funext i fin_cases i <;> norm_num [in772_counterexampleproof_f,h0,h1] · have h1 : pi.symm 1 = 0 := by have hh := (pi.symm 1).isLt omega right funext i fin_cases i <;> norm_num [in772_counterexampleproof_f,h0,h1] · rintro (rfl | rfl) · refine ⟨Equiv.refl _, ?_⟩ funext i fin_cases i <;> norm_num [in772_counterexampleproof_f] · refine ⟨Equiv.swap 0 1, ?_⟩ funext i fin_cases i <;> norm_num [in772_counterexampleproof_f,Equiv.swap_apply_def]private lemma in772_counterexampleproof_submodular_false_transition : ∃ (f : Finset (Fin 2) → ℝ) (p q r : Fin 2 → ℝ), f ∅ = 0 ∧ is_submodular f ∧ base_polytope_extreme_bases f = ({p,q} : Set (Fin 2 → ℝ)) ∧ wolfe_major_cycle (base_polytope_extreme_bases f) {p} {q} p q ∧ is_wolfe_corral ({p,q} : Finset (Fin 2 → ℝ)) r ∧ p ≠ q := by obtain ⟨p,q,r,hp,hq,hstep,hcorral,hne⟩ := in772_counterexampleproof_counterexample refine ⟨in772_counterexampleproof_f,p,q,r,in772_counterexampleproof_f_submodular.1,in772_counterexampleproof_f_submodular.2,?_,?_,hcorral,hne⟩ · simpa [hp,hq] using in772_counterexampleproof_atoms · simpa [in772_counterexampleproof_atoms,hp,hq] using hsteptheorem linopt_major_cycle_discards_corral_atom : ∃ (f : Finset (Fin 2) → ℝ) (p q r : Fin 2 → ℝ), f ∅ = 0 ∧ is_submodular f ∧ base_polytope_extreme_bases f = ({p,q} : Set (Fin 2 → ℝ)) ∧ wolfe_major_cycle (base_polytope_extreme_bases f) {p} {q} p q ∧ is_wolfe_corral ({p,q} : Finset (Fin 2 → ℝ)) r ∧ p ≠ q := by exact in772_counterexampleproof_submodular_false_transition