AFTD Auto-Formalizing Theoretical Domains

condorcet_stationary_action_dual_acyclic_mass

theoremverified

For nonnegative occupations of arbitrary finite families of rooted finite-set actions, let each vertex weight equal the sum of occupations at that root and suppose triple-flow stationarity holds: three times a vertex weight equals its total incoming occupation mass. A real vertex potential and a positive finite number of vertex subsets with nonnegative coefficients, satisfying the displayed local dual inequalities, certify that some subset has coefficient-sum times its mass at least c times total vertex mass. The conclusion is homogeneous and requires neither a positive coefficient sum nor normalization. Action sets need not have cardinality three; the factor three is the specified flow coefficient. The subsets need not be acyclic, so applications verify acyclicity separately.

Statement

theorem condorcet_stationary_action_dual_acyclic_mass
    (m k : ℕ) (hk : 0 < k)
    (F : Fin m → Finset (Finset (Fin m)))
    (x : Fin m → Finset (Fin m) → ℝ) (w h : Fin m → ℝ)
    (A : Fin k → Finset (Fin m)) (d : Fin k → ℝ) (c : ℝ)
    (hd : ∀ j, 0 ≤ d j)
    (hx : ∀ a, ∀ J ∈ F a, 0 ≤ x a J)
    (hw : ∀ a, w a = ∑ J ∈ F a, x a J)
    (hflow : ∀ b, 3 * w b = ∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0)
    (hdual : ∀ a, ∀ J ∈ F a,
      c + (∑ b ∈ J, h b) ≤ (∑ j, if a ∈ A j then d j else 0) + 3 * h a) :
    ∃ j, c * (∑ a, w a) ≤ (∑ i, d i) * (∑ a ∈ A j, w a)
Source
IN-372 supporting method diagnostic for OP-19. Integer audit experiment9221 and exploratory LP9219. Standard finite LP weak duality; no novelty or research advance is claimed. The original strict election statement remains unchanged.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 3

The proof, explained

The theorem is proved by first establishing a general linear programming dual bound for stationary triple-flows: weighting the dual inequalities by the action occupations and summing over all root-action pairs, the triple-flow stationarity condition guarantees that the vertex potential terms cancel out completely, leaving an aggregate bound c ∑ a, w a ≤ ∑ a, w a * p a. Setting the vertex penalty p a to the weighted sum of indicators for membership in the given subsets A j and exchanging summation order expresses this upper bound as ∑ j, d j * ∑ a ∈ A j, w a. Since the family of subsets is finite and nonempty, choosing a subset A j of maximal total weight bounds the weighted combination by (∑ i, d i) * ∑ a ∈ A j, w a.

  1. The total incoming potential to all action subsets weighted by occupation equals three times the potential weighted by vertex mass: ∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b) = ∑ b, 3 * w b * h b.

    Distribute the occupation x a J into the inner sum over b ∈ J using an indicator function, swap the order of summation so the outer sum runs over b, factor out h b, and substitute the triple-flow stationarity condition 3 * w b = ∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0.

    lines 19–31

    uses mul_sum, sum_comm, sum_mul, ite_mul

      classical
      have hchildren : (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) =
          ∑ b, 3 * w b * h b := by
        calc
          (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) =
              ∑ a, ∑ J ∈ F a, ∑ b : Fin m, if b ∈ J then x a J * h b else 0 := by
            simp [mul_sum]
          _ = ∑ b : Fin m, ∑ a, ∑ J ∈ F a, if b ∈ J then x a J * h b else 0 := by
            simp_rw [sum_comm (s := F _)]
            rw [sum_comm]
          _ = ∑ b, (∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0) * h b := by
            simp [sum_mul, ite_mul]
          _ = _ := by simp_rw [← hflow]
  2. Summing the local dual inequalities over all vertices a and actions J ∈ F a weighted by occupation preserves the inequality: ∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b) ≤ ∑ a, ∑ J ∈ F a, x a J * (p a + 3 * h a).

    Because occupations x a J are nonnegative (hx), multiplying the dual inequality hdual by x a J preserves the inequality for every pair (a, J). Summing these termwise bounds across all vertices and actions preserves the inequality.

    lines 32–38

    uses sum_le_sum, mul_le_mul_of_nonneg_left

      have hsum : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) ≤
          ∑ a, ∑ J ∈ F a, x a J * (p a + 3 * h a) := by
        apply sum_le_sum
        intro a ha
        apply sum_le_sum
        intro J hJ
        exact mul_le_mul_of_nonneg_left (hdual a J hJ) (hx a J hJ)
  3. The left-hand side of the summed dual inequality simplifies to c * (∑ a, w a) + ∑ a, 3 * w a * h a.

    Distribute the product x a J * (c + ∑ b ∈ J, h b) into two sums. The second sum evaluates to ∑ a, 3 * w a * h a using the identity hchildren established in the first step. In the first sum, c factors out of the sum over J ∈ F a, where ∑ J ∈ F a, x a J is replaced by w a using the definition of vertex weights hw.

    lines 39–48

    uses mul_add, sum_add_distrib, mul_sum, sum_congr, sum_mul

      have hleft : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) =
          c * (∑ a, w a) + ∑ a, 3 * w a * h a := by
        simp_rw [mul_add, sum_add_distrib]
        rw [hchildren]
        congr 1
        rw [mul_sum]
        apply sum_congr rfl
        intro a ha
        rw [← sum_mul, ← hw]
        ring
  4. The right-hand side of the summed dual inequality simplifies to (∑ a, w a * p a) + ∑ a, 3 * w a * h a.

    Since p a + 3 * h a is constant with respect to J, factoring it out leaves ∑ J ∈ F a, x a J, which equals w a by hw. Distributing multiplication and splitting the sum over vertices gives (∑ a, w a * p a) + ∑ a, 3 * w a * h a.

    lines 49–56

    uses sum_mul, mul_add, sum_add_distrib, sum_congr

      have hright : (∑ a, ∑ J ∈ F a, x a J * (p a + 3 * h a)) =
          (∑ a, w a * p a) + ∑ a, 3 * w a * h a := by
        simp_rw [← sum_mul, ← hw, mul_add]
        rw [sum_add_distrib]
        congr 1
        apply sum_congr rfl
        intro a ha
        ring
  5. The aggregate dual bound c * (∑ a, w a) ≤ ∑ a, w a * p a holds. automation

    Rewriting the summed inequality hsum with the expanded forms hleft and hright yields c * (∑ a, w a) + ∑ a, 3 * w a * h a ≤ (∑ a, w a * p a) + ∑ a, 3 * w a * h a. Linear arithmetic over ℝ cancels the identical potential sums ∑ a, 3 * w a * h a from both sides.

    lines 57–58

      rw [hleft, hright] at hsum
      linarith
  6. Specializing the dual bound to the penalty potential p a = ∑ j, if a ∈ A j then d j else 0 yields c * (∑ a, w a) ≤ ∑ a, w a * (∑ j, if a ∈ A j then d j else 0).

    Apply condorcet_stationary_action_dual_bound with the penalty function p a defined as the weighted indicator sum of vertex membership in subsets A j. The hypotheses hx, hw, hflow, and hdual supply all required premises directly.

    lines 72–74

    uses condorcet_stationary_action_dual_bound

      classical
      have hbound := condorcet_stationary_action_dual_bound m F x w
        (fun a => ∑ j, if a ∈ A j then d j else 0) h c hx hw hflow hdual
  7. The upper bound rewrites as the weighted sum of subset masses: ∑ a, w a * (∑ j, if a ∈ A j then d j else 0) = ∑ j, d j * (∑ a ∈ A j, w a).

    Distribute w a into the sum over subset indices j, interchange the two finite summations, and simplify the summand using mul_ite and commutativity of multiplication, turning the vertex sum of indicators into the subset sum of weights. Rewriting hbound with this equality establishes c * (∑ a, w a) ≤ ∑ j, d j * (∑ a ∈ A j, w a).

    lines 75–82

    uses mul_sum, sum_comm, sum_congr, mul_ite, mul_comm

      have hswap : (∑ a, w a * (∑ j, if a ∈ A j then d j else 0)) =
          ∑ j, d j * (∑ a ∈ A j, w a) := by
        simp_rw [mul_sum]
        rw [sum_comm]
        apply sum_congr rfl
        intro j hj
        simp [mul_ite, mul_comm]
      rw [hswap] at hbound
  8. There exists a subset index j such that c * (∑ a, w a) ≤ (∑ i, d i) * (∑ a ∈ A j, w a).

    Since k > 0, the index set Fin k is nonempty, so exists_max_image provides an index j maximizing the subset mass ∑ a ∈ A j, w a. Because coefficients d i are nonnegative (hd), termwise bounding d i * (∑ a ∈ A i, w a) ≤ d i * (∑ a ∈ A j, w a) and summing over all i shows that ∑ i, d i * (∑ a ∈ A i, w a) ≤ (∑ i, d i) * (∑ a ∈ A j, w a). Chaining this with hbound completes the proof.

    lines 83–87

    uses exists_max_image, univ, mem_univ, sum_mul, sum_le_sum, mul_le_mul_of_nonneg_left

      obtain ⟨j, hj, hmax⟩ := exists_max_image univ (fun j : Fin k => ∑ a ∈ A j, w a)
        ⟨⟨0,hk⟩, mem_univ _⟩
      refine ⟨j, hbound.trans ?_⟩
      rw [sum_mul]
      exact sum_le_sum (fun i hi => mul_le_mul_of_nonneg_left (hmax i hi) (hd i))
condorcet_stationary_action_dual_bound
Under triple-flow stationarity, dual feasibility of potential h and vertex penalty p certifies that c times total vertex mass is bounded above by the p-weighted vertex mass: c ∑ a, w a ≤ ∑ a, w a * p a.
exists_max_image
Any nonempty finite set contains an element achieving the maximum of a given real-valued function.
ite_mul
Multiplication on the right distributes into an if-then-else condition: (if P then a else b) * c = if P then a * c else b * c.
mem_univ
Every element of a finite type belongs to the universal finset univ.
mul_add
Left multiplication distributes over addition: a * (b + c) = a * b + a * c.
mul_comm
Multiplication in a commutative magma is symmetric: a * b = b * a.
mul_ite
Multiplication on the left distributes into an if-then-else condition: a * (if P then b else c) = if P then a * b else a * c.
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c on the left by a nonnegative element a ≥ 0 preserves the inequality: a * b ≤ a * c.
mul_sum
Left multiplication by a scalar distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
sum_add_distrib
A sum of termwise additions splits into the sum of the two sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
sum_comm
The order of summation in a double finite sum can be interchanged: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
sum_congr
Two finite sums are equal if their index sets coincide and their summands agree on that set.
sum_le_sum
A finite sum of termwise smaller quantities is less than or equal to the sum of the larger quantities.
sum_mul
Right multiplication by a scalar distributes over a finite sum: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
univ
The finite set of all elements of a finite type.

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 20000000set_option maxRecDepth 20000open Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_stationary_action_dual_bound    (m : ℕ) (F : Fin m → Finset (Finset (Fin m)))    (x : Fin m → Finset (Fin m) → ℝ) (w p h : Fin m → ℝ) (c : ℝ)    (hx : ∀ a, ∀ J ∈ F a, 0 ≤ x a J)    (hw : ∀ a, w a = ∑ J ∈ F a, x a J)    (hflow : ∀ b, 3 * w b = ∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0)    (hdual : ∀ a, ∀ J ∈ F a, c + (∑ b ∈ J, h b) ≤ p a + 3 * h a) :    c * (∑ a, w a) ≤ ∑ a, w a * p a := by  classical  have hchildren : (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) =      ∑ b, 3 * w b * h b := by    calc      (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) =          ∑ a, ∑ J ∈ F a, ∑ b : Fin m, if b ∈ J then x a J * h b else 0 := by        simp [mul_sum]      _ = ∑ b : Fin m, ∑ a, ∑ J ∈ F a, if b ∈ J then x a J * h b else 0 := by        simp_rw [sum_comm (s := F _)]        rw [sum_comm]      _ = ∑ b, (∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0) * h b := by        simp [sum_mul, ite_mul]      _ = _ := by simp_rw [← hflow]  have hsum : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) ≤      ∑ a, ∑ J ∈ F a, x a J * (p a + 3 * h a) := by    apply sum_le_sum    intro a ha    apply sum_le_sum    intro J hJ    exact mul_le_mul_of_nonneg_left (hdual a J hJ) (hx a J hJ)  have hleft : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) =      c * (∑ a, w a) + ∑ a, 3 * w a * h a := by    simp_rw [mul_add, sum_add_distrib]    rw [hchildren]    congr 1    rw [mul_sum]    apply sum_congr rfl    intro a ha    rw [← sum_mul, ← hw]    ring  have hright : (∑ a, ∑ J ∈ F a, x a J * (p a + 3 * h a)) =      (∑ a, w a * p a) + ∑ a, 3 * w a * h a := by    simp_rw [← sum_mul, ← hw, mul_add]    rw [sum_add_distrib]    congr 1    apply sum_congr rfl    intro a ha    ring  rw [hleft, hright] at hsum  linariththeorem condorcet_stationary_action_dual_acyclic_mass    (m k : ℕ) (hk : 0 < k)    (F : Fin m → Finset (Finset (Fin m)))    (x : Fin m → Finset (Fin m) → ℝ) (w h : Fin m → ℝ)    (A : Fin k → Finset (Fin m)) (d : Fin k → ℝ) (c : ℝ)    (hd : ∀ j, 0 ≤ d j)    (hx : ∀ a, ∀ J ∈ F a, 0 ≤ x a J)    (hw : ∀ a, w a = ∑ J ∈ F a, x a J)    (hflow : ∀ b, 3 * w b = ∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0)    (hdual : ∀ a, ∀ J ∈ F a,      c + (∑ b ∈ J, h b) ≤ (∑ j, if a ∈ A j then d j else 0) + 3 * h a) :    ∃ j, c * (∑ a, w a) ≤ (∑ i, d i) * (∑ a ∈ A j, w a) := by  classical  have hbound := condorcet_stationary_action_dual_bound m F x w    (fun a => ∑ j, if a ∈ A j then d j else 0) h c hx hw hflow hdual  have hswap : (∑ a, w a * (∑ j, if a ∈ A j then d j else 0)) =      ∑ j, d j * (∑ a ∈ A j, w a) := by    simp_rw [mul_sum]    rw [sum_comm]    apply sum_congr rfl    intro j hj    simp [mul_ite, mul_comm]  rw [hswap] at hbound  obtain ⟨j, hj, hmax⟩ := exists_max_image univ (fun j : Fin k => ∑ a ∈ A j, w a)    ⟨⟨0,hk⟩, mem_univ _⟩  refine ⟨j, hbound.trans ?_⟩  rw [sum_mul]  exact sum_le_sum (fun i hi => mul_le_mul_of_nonneg_left (hmax i hi) (hd i))
See it in the graphDiscuss this resultChallenge it