condorcet_edge_circulation_dual_bound
Given nonnegative real edge weights supported on a finite directed relation, with equal incoming and outgoing sums at each vertex, any real vertex functions p and h satisfying t+h(b) <= p(a)+h(a) on every arrow obey t times total edge weight <= the sum over vertices of outgoing weight times p. No acyclicity, S3, or normalization is assumed.
Statement
theorem condorcet_edge_circulation_dual_bound (m : ℕ) (R : Fin m → Fin m → Prop) (f : Fin m → Fin m → ℝ) (p h : Fin m → ℝ) (t : ℝ) (hf : ∀ a b, 0 ≤ f a b) (hsupport : ∀ a b, ¬ R a b → f a b = 0) (hbalance : ∀ a, ∑ b, f a b = ∑ b, f b a) (hlocal : ∀ a b, R a b → t + h b ≤ p a + h a) : t * (∑ a, ∑ b, f a b) ≤ ∑ a, (∑ b, f a b) * p a
- Source
- IN-380, OP-19 campaign session 8, 2026-10-30. Self-contained helper for the strict-half acyclic-separation route. The general unrestricted one-child equality was refuted in IN-372; this work repairs only the strict-half existence reduction. Standard finite matching, rational density, and circulation weak duality are used. No new election bound or research novelty is claimed. See lean/AFTD/Scratch/In380Oct30/HalfThresholdDerivation.txt.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- condorcet_strict_half_separator_excludes_cover_potentialLet a finite directed relation have a nonnegative real strict-half separator. For every positive number n of induced acyclic vertex…
The proof, explained
The proof multiplies the local edge inequalities t + h(b) ≤ p(a) + h(a) by the nonnegative edge weights f(a, b) and sums over all edges. Because the weights form a circulation with equal incoming and outgoing sums at every vertex, the total potential sum ∑ a,b f(a, b) h(b) equals ∑ a,b f(a, b) h(a). Expanding both sides of the sum allows this potential contribution to cancel identically, directly yielding the bound t * (total flow) ≤ ∑ a, (outgoing flow at a) * p(a).
∑ a, ∑ b, f a b * (t + h b) ≤ ∑ a, ∑ b, f a b * (p a + h a)
We sum the local inequality t + h(b) ≤ p(a) + h(a) over all pairs (a, b) weighted by f(a, b). For each pair (a, b), if an edge exists (R a b), the hypothesis hlocal gives t + h(b) ≤ p(a) + h(a), and multiplying by the nonnegative weight f(a, b) preserves the inequality via mul_le_mul_of_nonneg_left. If no edge exists (¬ R a b), the weight f(a, b) is zero by hsupport, making both sides zero. Summing these inequalities over all pairs via sum_le_sum yields the double-sum inequality.
uses
sum_le_sum,mul_le_mul_of_nonneg_lefthave hsum : (∑ a, ∑ b, f a b * (t + h b)) ≤ ∑ a, ∑ b, f a b * (p a + h a) := by apply sum_le_sum intro a ha apply sum_le_sum intro b hb by_cases hab : R a b · exact mul_le_mul_of_nonneg_left (hlocal a b hab) (hf a b) · simp [hsupport a b hab]
∑ a, ∑ b, f a b * h b = ∑ a, (∑ b, f a b) * h a
The total target-potential sum equals the total source-potential sum due to flow conservation. Exchanging the order of summation via sum_comm turns the left-hand side into ∑ b, (∑ a, f a b) * h b, which groups edges by incoming flow at vertex b. By the circulation balance condition hbalance, the incoming flow ∑ a, f a b equals the outgoing flow ∑ a, f b a, which rewrites the expression to match the total outgoing flow weighted by h.
uses
sum_comm,sum_mulhave hcancel : (∑ a, ∑ b, f a b * h b) = ∑ a, (∑ b, f a b) * h a := by rw [sum_comm] simp_rw [← sum_mul,← hbalance]
∑ a, ∑ b, f a b * (t + h b) = t * (∑ a, ∑ b, f a b) + ∑ a, (∑ b, f a b) * h a
Distributing f(a, b) * (t + h(b)) using mul_add and splitting the double sum with sum_add_distrib separates the t term from the h term. The constant t is factored out using sum_mul and mul_comm, and the remaining potential term is replaced by its balanced vertex form using the cancellation equality hcancel.
uses
mul_add,sum_add_distrib,sum_mul,mul_commhave hleft : (∑ a, ∑ b, f a b * (t + h b)) = t * (∑ a, ∑ b, f a b) + ∑ a, (∑ b, f a b) * h a := by simp_rw [mul_add,sum_add_distrib] rw [hcancel] simp only [← sum_mul,mul_comm t]
∑ a, ∑ b, f a b * (p a + h a) = (∑ a, (∑ b, f a b) * p a) + ∑ a, (∑ b, f a b) * h a
Since p(a) + h(a) depends only on the source vertex a, it factors out of the inner sum over b via sum_mul. Distributing multiplication over addition with mul_add and splitting the outer sum with sum_add_distrib produces the sum of the p term and the h term.
uses
sum_mul,mul_add,sum_add_distribhave hright : (∑ a, ∑ b, f a b * (p a + h a)) = (∑ a, (∑ b, f a b) * p a) + ∑ a, (∑ b, f a b) * h a := by simp_rw [← sum_mul,mul_add,sum_add_distrib]
t * (∑ a, ∑ b, f a b) ≤ ∑ a, (∑ b, f a b) * p a
Substituting the expansions of the left- and right-hand sides into the weighted inequality leaves the identical potential sum ∑ a, (∑ b, f a b) * h a on both sides. Linear arithmetic cancels this common term, yielding the dual bound.
rw [hleft,hright] at hsum linarith
sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set s, then ∑ i ∈ s, f(i) ≤ ∑ i ∈ s, g(i).
mul_le_mul_of_nonneg_left- If b ≤ c and 0 ≤ a, then a * b ≤ a * c.
sum_comm- Double sums over finite sets can exchange their order of summation: ∑ x ∈ s, ∑ y ∈ t, f(x, y) = ∑ y ∈ t, ∑ x ∈ s, f(x, y).
sum_mul- Right distributivity of multiplication over a finite sum: (∑ i ∈ s, f(i)) * a = ∑ i ∈ s, (f(i) * a).
mul_add- Left distributivity of multiplication over addition: a * (b + c) = a * b + a * c.
sum_add_distrib- Sum of a pointwise sum of functions equals the sum of their individual sums: ∑ x ∈ s, (f(x) + g(x)) = ∑ x ∈ s, f(x) + ∑ x ∈ s, g(x).
mul_comm- Multiplication is commutative: a * b = b * a.
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_edge_circulation_dual_bound (m : ℕ) (R : Fin m → Fin m → Prop) (f : Fin m → Fin m → ℝ) (p h : Fin m → ℝ) (t : ℝ) (hf : ∀ a b, 0 ≤ f a b) (hsupport : ∀ a b, ¬ R a b → f a b = 0) (hbalance : ∀ a, ∑ b, f a b = ∑ b, f b a) (hlocal : ∀ a b, R a b → t + h b ≤ p a + h a) : t * (∑ a, ∑ b, f a b) ≤ ∑ a, (∑ b, f a b) * p a := by have hsum : (∑ a, ∑ b, f a b * (t + h b)) ≤ ∑ a, ∑ b, f a b * (p a + h a) := by apply sum_le_sum intro a ha apply sum_le_sum intro b hb by_cases hab : R a b · exact mul_le_mul_of_nonneg_left (hlocal a b hab) (hf a b) · simp [hsupport a b hab] have hcancel : (∑ a, ∑ b, f a b * h b) = ∑ a, (∑ b, f a b) * h a := by rw [sum_comm] simp_rw [← sum_mul,← hbalance] have hleft : (∑ a, ∑ b, f a b * (t + h b)) = t * (∑ a, ∑ b, f a b) + ∑ a, (∑ b, f a b) * h a := by simp_rw [mul_add,sum_add_distrib] rw [hcancel] simp only [← sum_mul,mul_comm t] have hright : (∑ a, ∑ b, f a b * (p a + h a)) = (∑ a, (∑ b, f a b) * p a) + ∑ a, (∑ b, f a b) * h a := by simp_rw [← sum_mul,mul_add,sum_add_distrib] rw [hleft,hright] at hsum linarith