AFTD Auto-Formalizing Theoretical Domains

cycle_power_exact_owner_order_cut_inequality

theoremverified

A nondecreasing sequence of unique exact-edge owner roots satisfies every cumulative cut inequality: the indicator of the next owner being at most a cut is no greater than the corresponding old indicator. This justifies the stochastic order cuts used in the exploratory linear relaxation.

Statement

theorem cycle_power_exact_owner_order_cut_inequality
    (D q : ℕ) (x : ℤ → ℕ → Bool)
    (hexact : ∀ v : ℤ, (range q).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat) = 1)
    (horder : ∀ (v : ℤ) (a b : ℕ), a < q → b < q →
      x (v-(a : ℤ)) a = true → x (v-(a : ℤ)) (a+D-q) = true →
      x (v+1-(b : ℤ)) b = true → x (v+1-(b : ℤ)) (b+D-q) = true → b ≤ a+1) :
    ∀ v C : ℤ,
      (range q).sum (fun b => if v+1-(b : ℤ) ≤ C then
        (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat else 0) ≤
      (range q).sum (fun a => if v-(a : ℤ) ≤ C then
        (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat else 0)
Source
Routine formal bridge for OP-205 / RT-1 owner-order LP route, experiment6658. The owner-order hypothesis is explicit; this does not prove it for optimal covers or prove the numerical LP certificate.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The inequality compares two indicator sums over owner roots, each evaluating to either 0 or 1. If the left-hand sum is 0, the inequality holds trivially. If the left-hand sum is non-zero, it equals 1, witnessing an owner root b < q for v + 1 with v + 1 - b ≤ C. By the exactness and monotonicity hypotheses, there is a unique owner root a < q for v satisfying b ≤ a + 1, which forces v - a ≤ C and makes the right-hand sum at least 1.

  1. The inequality holds whenever the left-hand sum is zero.

    Fix arbitrary v and C in ℤ. We perform a case distinction on whether the left-hand sum is zero. If it is 0, the inequality holds immediately because the right-hand sum of natural numbers is always non-negative, by Nat.zero_le.

    lines 15–19

    uses Nat.zero_le

      intro v C
      by_cases hL : (range q).sum (fun b => if v+1-(b : ℤ) ≤ C then
          (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat else 0) = 0
      · rw [hL]
        exact Nat.zero_le _
  2. The left-hand sum is at most 1.

    Assuming the left-hand sum is non-zero, we bound it from above by dropping the cut condition v + 1 - b ≤ C. Term by term, each conditional indicator is bounded by the corresponding unconditional indicator, so the sum is bounded by the total sum over b < q by sum_le_sum. By the exactness hypothesis hexact at v + 1, this full sum equals 1, proving that the left-hand sum is at most 1.

    lines 20–29

    uses sum_le_sum

      · have hL_le_one : (range q).sum (fun b => if v+1-(b : ℤ) ≤ C then
            (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat else 0) ≤ 1 := by
          have hle : (range q).sum (fun b => if v+1-(b : ℤ) ≤ C then
              (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat else 0) ≤
            (range q).sum (fun b => (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat) := by
            apply sum_le_sum
            intro i _
            split_ifs <;> omega
          rw [hexact (v + 1)] at hle
          exact hle
  3. There exists an owner index b < q at v + 1 satisfying the cut condition v + 1 - b ≤ C and both owner indicator conditions.

    Since the left-hand sum is non-zero, exists_ne_zero_of_sum_ne_zero provides an index b ∈ range q (meaning b < q by mem_range) whose summand is non-zero. This non-zero summand implies that the cut condition v + 1 - b ≤ C holds and that the boolean conjunction evaluates to true, which by Bool.and_eq_true means x(v+1-b, b) = true and x(v+1-b, b+D-q) = true.

    lines 30–41

    uses exists_ne_zero_of_sum_ne_zero, mem_range, Bool.and_eq_true

        obtain ⟨b, hb_mem, hb_ne⟩ := exists_ne_zero_of_sum_ne_zero hL
        rw [mem_range] at hb_mem
        have hb_props : v + 1 - (b : ℤ) ≤ C ∧
            x (v+1-(b : ℤ)) b = true ∧
            x (v+1-(b : ℤ)) (b+D-q) = true := by
          split_ifs at hb_ne with hC
          · have hbool : (x (v + 1 - (b : ℤ)) b && x (v + 1 - (b : ℤ)) (b + D - q)) = true := by
              revert hb_ne
              cases (x (v + 1 - (b : ℤ)) b && x (v + 1 - (b : ℤ)) (b + D - q)) <;> simp
            rw [Bool.and_eq_true] at hbool
            exact ⟨hC, hbool.1, hbool.2⟩
          · contradiction
  4. There exists an owner index a < q at v with both owner indicator conditions true.

    By the exactness hypothesis hexact at v, the unconditional sum of owner indicators over a < q equals 1, hence is non-zero. Applying exists_ne_zero_of_sum_ne_zero yields an index a < q (via mem_range) whose indicator product is non-zero, meaning x(v-a, a) = true and x(v-a, a+D-q) = true by Bool.and_eq_true.

    lines 42–51

    uses exists_ne_zero_of_sum_ne_zero, mem_range, Bool.and_eq_true

        have hne_a : (range q).sum (fun a =>
            (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat) ≠ 0 := by
          rw [hexact v]
          decide
        obtain ⟨a, ha_mem, ha_ne⟩ := exists_ne_zero_of_sum_ne_zero hne_a
        rw [mem_range] at ha_mem
        have ha_bool : (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + D - q)) = true := by
          revert ha_ne
          cases (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + D - q)) <;> simp
        rw [Bool.and_eq_true] at ha_bool
  5. The owner indices satisfy b ≤ a + 1, which implies that the cut condition v - a ≤ C holds.

    Applying the owner monotonicity hypothesis horder to the indices a at v and b at v + 1 gives b ≤ a + 1. Combining this with the cut condition v + 1 - b ≤ C from the previous step yields v - a = (v + 1) - (a + 1) ≤ v + 1 - b ≤ C by linear integer arithmetic.

    lines 52–54

        have hba : b ≤ a + 1 :=
          horder v a b ha_mem hb_mem ha_bool.1 ha_bool.2 hb_props.2.1 hb_props.2.2
        have ha_le_C : v - (a : ℤ) ≤ C := by omega
  6. The right-hand sum is at least 1.

    Because v - a ≤ C and both owner indicators are true at a, the a-th summand on the right-hand side evaluates to 1 by if_pos. Since all summands are non-negative, the single term at a ∈ range q (by mem_range) bounds the entire sum from below via single_le_sum, establishing that the right-hand sum is at least 1.

    lines 55–65

    uses if_pos, single_le_sum, mem_range

        have hpos_a : (if v-(a : ℤ) ≤ C then
            (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat else 0) = 1 := by
          rw [if_pos ha_le_C, ha_bool.1, ha_bool.2]
          rfl
        have hone_le_R : 1 ≤ (range q).sum (fun a => if v-(a : ℤ) ≤ C then
            (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat else 0) := by
          have hle := @single_le_sum ℕ ℕ _ _ (fun a => if v-(a : ℤ) ≤ C then
              (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat else 0) (range q) _
              (fun i _ => Nat.zero_le _) a (mem_range.mpr ha_mem)
          rw [hpos_a] at hle
          exact hle
  7. The left-hand sum is at most the right-hand sum.

    Having shown that the left-hand sum is at most 1 and the right-hand sum is at least 1, the desired inequality follows by transitivity of ≤ (le_trans).

    line 66

    uses le_trans

        exact le_trans hL_le_one hone_le_R
Nat.zero_le
For any natural number n, 0 ≤ n.
sum_le_sum
If f(i) ≤ g(i) for every element i in a finite set s, then the sum of f over s is at most the sum of g over s.
exists_ne_zero_of_sum_ne_zero
If the sum of a function over a finite set is non-zero, then the function is non-zero at some element of the set.
mem_range
A natural number m belongs to range(n) if and only if m < n.
Bool.and_eq_true
A boolean conjunction a && b is true if and only if both a = true and b = true.
if_pos
If a condition c holds, then the conditional expression if c then t else e reduces to t.
single_le_sum
In an ordered commutative monoid with non-negative terms, a single term from a finite set is at most the sum over that set.
le_trans
The ordering relation is transitive: if a ≤ b and b ≤ c, then a ≤ c.

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 Finsettheorem cycle_power_exact_owner_order_cut_inequality    (D q : ℕ) (x : ℤ → ℕ → Bool)    (hexact : ∀ v : ℤ, (range q).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat) = 1)    (horder : ∀ (v : ℤ) (a b : ℕ), a < q → b < q →      x (v-(a : ℤ)) a = true → x (v-(a : ℤ)) (a+D-q) = true →      x (v+1-(b : ℤ)) b = true → x (v+1-(b : ℤ)) (b+D-q) = true → b ≤ a+1) :    ∀ v C : ℤ,      (range q).sum (fun b => if v+1-(b : ℤ) ≤ C then        (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat else 0) ≤      (range q).sum (fun a => if v-(a : ℤ) ≤ C then        (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat else 0) := by  intro v C  by_cases hL : (range q).sum (fun b => if v+1-(b : ℤ) ≤ C then      (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat else 0) = 0  · rw [hL]    exact Nat.zero_le _  · have hL_le_one : (range q).sum (fun b => if v+1-(b : ℤ) ≤ C then        (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat else 0) ≤ 1 := by      have hle : (range q).sum (fun b => if v+1-(b : ℤ) ≤ C then          (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat else 0) ≤        (range q).sum (fun b => (x (v+1-(b : ℤ)) b && x (v+1-(b : ℤ)) (b+D-q)).toNat) := by        apply sum_le_sum        intro i _        split_ifs <;> omega      rw [hexact (v + 1)] at hle      exact hle    obtain ⟨b, hb_mem, hb_ne⟩ := exists_ne_zero_of_sum_ne_zero hL    rw [mem_range] at hb_mem    have hb_props : v + 1 - (b : ℤ) ≤ C ∧        x (v+1-(b : ℤ)) b = true ∧        x (v+1-(b : ℤ)) (b+D-q) = true := by      split_ifs at hb_ne with hC      · have hbool : (x (v + 1 - (b : ℤ)) b && x (v + 1 - (b : ℤ)) (b + D - q)) = true := by          revert hb_ne          cases (x (v + 1 - (b : ℤ)) b && x (v + 1 - (b : ℤ)) (b + D - q)) <;> simp        rw [Bool.and_eq_true] at hbool        exact ⟨hC, hbool.1, hbool.2⟩      · contradiction    have hne_a : (range q).sum (fun a =>        (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat) ≠ 0 := by      rw [hexact v]      decide    obtain ⟨a, ha_mem, ha_ne⟩ := exists_ne_zero_of_sum_ne_zero hne_a    rw [mem_range] at ha_mem    have ha_bool : (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + D - q)) = true := by      revert ha_ne      cases (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + D - q)) <;> simp    rw [Bool.and_eq_true] at ha_bool    have hba : b ≤ a + 1 :=      horder v a b ha_mem hb_mem ha_bool.1 ha_bool.2 hb_props.2.1 hb_props.2.2    have ha_le_C : v - (a : ℤ) ≤ C := by omega    have hpos_a : (if v-(a : ℤ) ≤ C then        (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat else 0) = 1 := by      rw [if_pos ha_le_C, ha_bool.1, ha_bool.2]      rfl    have hone_le_R : 1 ≤ (range q).sum (fun a => if v-(a : ℤ) ≤ C then        (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat else 0) := by      have hle := @single_le_sum ℕ ℕ _ _ (fun a => if v-(a : ℤ) ≤ C then          (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-q)).toNat else 0) (range q) _          (fun i _ => Nat.zero_le _) a (mem_range.mpr ha_mem)      rw [hpos_a] at hle      exact hle    exact le_trans hL_le_one hone_le_R
See it in the graphDiscuss this resultChallenge it