ejr_support_density_bound_iff_groups
The finite supporter bound is equivalent to the corresponding bound on every commonly approving group whose members all have utility below a positive demand.
Statement
theorem ejr_support_density_bound_iff_groups {n m : ℕ} (A : Fin n → Finset (Fin m)) (q : ℕ) (W : Finset (Fin m)) : ejr_support_density_bound A q W ↔ ∀ ℓ, 1 ≤ ℓ → ∀ G : Finset (Fin n), ℓ ≤ (Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i).card → (∀ i ∈ G, (A i ∩ W).card < ℓ) → G.card * q ≤ ℓ * n
- Source
- Supporting work for OP-22, arXiv:2007.01795, Q2, and the proposed max-group-density invariant in memory attempt 4342. These helpers neither settle full-chain existence nor refute the actual greedy rule. No research advance is claimed.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- ejr_support_density_boundThe finite supporter-density bound: for every candidate subset T, its undersatisfied supporter count times q is at most |T| times the…
The proof, explained
The theorem establishes that the supporter density bound over all candidate sets T is equivalent to the corresponding density bound over cohesive voter groups demanding ℓ ≥ 1 candidates. In the forward direction, given a group G commonly approving at least ℓ candidates, selecting an ℓ-element subset T of these common approvals embeds G into the voters supporting T, so the density bound on T implies the bound on G. In the reverse direction, for any nonempty candidate set T, taking G to be the group of all voters who approve T and have utility below |T| allows one to apply the group bound with ℓ = |T|; the empty candidate set case holds vacuously since utility cannot be negative.
The equivalence decomposes into two implications: the candidate-set density bound implies the voter-group bound, and conversely.
Enable classical logic and split the biconditional into forward and backward implications.
classical constructorGiven a group G commonly approving at least ℓ candidates with utility below ℓ, we obtain a subset T of ℓ jointly approved candidates and define the group H of all voters supporting T.
Assume the supporter density bound h, a positive demand ℓ ≥ 1, and a voter group G whose common approvals number at least ℓ and whose members each have utility < ℓ from the committee W. By Finset.exists_subset_card_eq, there exists an ℓ-element subset T of candidates approved by all of G. We then define H to be the set of all voters who approve every candidate in T and have utility < ℓ.
uses
Finset.exists_subset_card_eq· intro h ℓ hℓ G hcommon hunsat obtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq hcommon let H := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ
The original group G is a subset of H.
Take any voter i ∈ G. Voter i has utility < ℓ by assumption on G, and because every candidate c ∈ T is jointly approved by G, voter i approves every candidate in T. Hence i satisfies the defining condition of H.
uses
Finset.mem_filter.mpr,Finset.mem_univ,Finset.mem_filter.mphave hGH : G ⊆ H := by intro i hi apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_, hunsat i hi⟩ intro c hc exact (Finset.mem_filter.mp (hTsub hc)).2 i hi
The group density bound |G| * q ≤ ℓ * n holds.
Since G ⊆ H, we have |G| * q ≤ |H| * q. Evaluating the supporter density bound hypothesis h at candidate set T (where |T| = ℓ) gives |H| * q ≤ ℓ * n. Composing these inequalities gives |G| * q ≤ ℓ * n.
uses
Nat.mul_le_mul_right,Finset.card_le_cardhave hle := Nat.mul_le_mul_right q (Finset.card_le_card hGH) have hb := h T rw [hTcard] at hb exact hle.trans hb
To prove the supporter density bound for an arbitrary candidate set T, it suffices to consider whether T is nonempty, in which case we define G as the set of voters supporting T with low utility.
Assume the voter-group bound holds for all ℓ ≥ 1 and all groups G. Given an arbitrary candidate set T, split into cases on whether T is nonempty. If T is nonempty, define G to be the set of all voters who approve all of T and have utility < |T| from W.
· intro h T by_cases hT : T.Nonempty · let G := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card
Every candidate in T is approved by all voters in G.
For any candidate c ∈ T and voter i ∈ G, by definition of G the voter approves the entire set T, so c ∈ A(i). Thus T is a subset of the candidates jointly approved by all voters in G.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_filter.mphave hsub : T ⊆ Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i := by intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro i hi exact (Finset.mem_filter.mp hi).2.1 hc
The supporter density bound holds for any nonempty candidate set T.
Apply the group hypothesis with demand ℓ = |T| and group G. Because T is nonempty, |T| ≥ 1. The number of candidates commonly approved by G is at least |T| since T ⊆ {c | ∀ i ∈ G, c ∈ A(i)}, and every voter in G has utility < |T| by construction. The group bound gives |G| * q ≤ |T| * n, which is the density bound for T.
uses
Finset.card_pos.mpr,Finset.card_le_card,Finset.mem_filter.mpexact h T.card (by have := Finset.card_pos.mpr hT; omega) G (Finset.card_le_card hsub) (fun i hi => (Finset.mem_filter.mp hi).2.2)
The supporter density bound holds when T is empty.
When T is empty, |T| = 0. No voter can satisfy the condition of having utility < 0, so the filtered set of voters is empty. The inequality simplifies to 0 * q ≤ 0 * n, which holds trivially.
uses
Finset.not_nonempty_iff_eq_empty.mp· have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hT simp [he]
Finset.exists_subset_card_eq- If a natural number n is at most the cardinality of a finite set s, then s contains a subset of cardinality n.
Finset.mem_filter.mpr- An element belongs to the filtered subset {x ∈ s | p x} if it belongs to s and satisfies the predicate p.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set Finset.univ.
Finset.mem_filter.mp- If an element belongs to the filtered subset {x ∈ s | p x}, then it belongs to s and satisfies the predicate p.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers n ≤ m on the right by k yields n * k ≤ m * k.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.mem_filter- An element belongs to {x ∈ s | p x} if and only if it belongs to s and satisfies the predicate p.
true_and- The logical conjunction True ∧ p is equivalent to p.
Finset.card_pos.mpr- A finite set has strictly positive cardinality if it is nonempty.
Finset.not_nonempty_iff_eq_empty.mp- If a finite set is not nonempty, then it is empty.
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.
theorem ejr_support_density_bound_iff_groups {n m : ℕ} (A : Fin n → Finset (Fin m)) (q : ℕ) (W : Finset (Fin m)) : ejr_support_density_bound A q W ↔ ∀ ℓ, 1 ≤ ℓ → ∀ G : Finset (Fin n), ℓ ≤ (Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i).card → (∀ i ∈ G, (A i ∩ W).card < ℓ) → G.card * q ≤ ℓ * n := by classical constructor · intro h ℓ hℓ G hcommon hunsat obtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq hcommon let H := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ have hGH : G ⊆ H := by intro i hi apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_, hunsat i hi⟩ intro c hc exact (Finset.mem_filter.mp (hTsub hc)).2 i hi have hle := Nat.mul_le_mul_right q (Finset.card_le_card hGH) have hb := h T rw [hTcard] at hb exact hle.trans hb · intro h T by_cases hT : T.Nonempty · let G := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card have hsub : T ⊆ Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i := by intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro i hi exact (Finset.mem_filter.mp hi).2.1 hc exact h T.card (by have := Finset.card_pos.mpr hT; omega) G (Finset.card_le_card hsub) (fun i hi => (Finset.mem_filter.mp hi).2.2) · have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hT simp [he]