cycle_power_exact_owner_order_cut_inequality
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
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
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.
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.
uses
Nat.zero_leintro 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 _
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.
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
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.
uses
exists_ne_zero_of_sum_ne_zero,mem_range,Bool.and_eq_trueobtain ⟨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
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.
uses
exists_ne_zero_of_sum_ne_zero,mem_range,Bool.and_eq_truehave 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
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.
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
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.
uses
if_pos,single_le_sum,mem_rangehave 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
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).
uses
le_transexact 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
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 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