AFTD Auto-Formalizing Theoretical Domains

condorcet_edge_circulation_dual_bound

theoremverified

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

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

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

    lines 14–22

    uses sum_le_sum, mul_le_mul_of_nonneg_left

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

    lines 23–26

    uses sum_comm, sum_mul

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

    lines 27–31

    uses mul_add, sum_add_distrib, sum_mul, mul_comm

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

    lines 32–34

    uses sum_mul, mul_add, sum_add_distrib

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

    lines 35–36

      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

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