condorcet_stationary_action_dual_acyclic_mass
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
- condorcet_optimized_all_triple_policy_lower_boundOn the same explicit eight-vertex relation, allow every three-element subset of each root's out-neighborhood, including nonprivate…
- condorcet_optimized_private_policy_lower_boundOn the explicit eight-vertex globally minimal, arc-minimal S3 relation from condorcet_minimal_private_averaging_obstruction, every choice…
- condorcet_all_triple_policy_one_third_bridge_obstructionFor the explicit six-vertex irreflexive relation with predecessor masks[62,61,35,7,11,19], every set of at most three vertices has an…
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.
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.
uses
mul_sum,sum_comm,sum_mul,ite_mulclassical 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]
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.
uses
sum_le_sum,mul_le_mul_of_nonneg_lefthave 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)
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.
uses
mul_add,sum_add_distrib,mul_sum,sum_congr,sum_mulhave 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
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.
uses
sum_mul,mul_add,sum_add_distrib,sum_congrhave 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
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.
rw [hleft, hright] at hsum linarith
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.
uses
condorcet_stationary_action_dual_boundclassical 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
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).
uses
mul_sum,sum_comm,sum_congr,mul_ite,mul_commhave 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
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.
uses
exists_max_image,univ,mem_univ,sum_mul,sum_le_sum,mul_le_mul_of_nonneg_leftobtain ⟨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.
- Line 58 uses linarith to cancel the identical potential sums ∑ a, 3 * w a * h a appearing on both sides of the summed inequality.
- Line 81 uses simp with mul_ite and mul_comm to automatically recognize that summing w a * (if a ∈ A j then d j else 0) over all vertices is equal to d j * ∑ a ∈ A j, w 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 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))