AFTD Auto-Formalizing Theoretical Domains

linopt_major_cycle_discards_corral_atom

theoremverified

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).

  1. 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.

    lines 5–14

      classical
      refine ⟨by simp, ?_, ?_⟩
      · intro x hx
        have : x=p := by simpa using hx
        subst x
        simp
      · refine ⟨fun _ => 1, ?_, ?_, ?_⟩
        · simp
        · simp
        · simp
  2. 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.

    lines 21–30

    uses congrFun, Ne.symm

      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⟩
  3. 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.

    lines 31–41

    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]
  4. 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.

    lines 42–53

    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
  5. 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.

    lines 60–65

    uses Finset.subset_iff

      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 *
  6. 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.

    lines 69–92

    uses Set.mem_setOf_eq, Set.mem_insert_iff, Set.mem_singleton_iff

      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]
  7. 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.

    lines 93–99

    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]
  8. 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.

    lines 108–111

    uses in772_counterexampleproof_counterexample, in772_counterexampleproof_f_submodular, in772_counterexampleproof_atoms

      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 hstep
  9. 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.

    line 119

    uses in772_counterexampleproof_submodular_false_transition

      exact 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.

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

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
See it in the graphDiscuss this resultChallenge it