ejr_of_support_density_bound
For a nonempty electorate, the density bound with q=k+1 implies EJR for any committee of size k.
Statement
theorem ejr_of_support_density_bound {n m : ℕ}
(A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m))
(hn : 0 < n) (hcard : W.card = k)
(h : ejr_support_density_bound A (k + 1) W) : is_ejr_committee A k W- 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 5
- 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…
- is_ejr_committeeA committee W with |W| = k satisfies EJR if for every ℓ ≥ 1 and every ℓ-cohesive group G some voter i ∈ G has |A_i ∩ W| ≥ ℓ.
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- ejr_chain_exists_of_support_density_boundA permutation whose every prefix satisfies the proposed density bound yields an EJR committee chain.
The proof, explained
The proof uses the dual characterization of Extended Justified Representation (EJR) in terms of candidate subsets, which reduces the problem to showing that for every nonempty subset of candidates T, the number of underrepresented supporters |S_T| satisfies |S_T| · k < |T| · n. The density bound hypothesis with q = k + 1 provides |S_T| · (k + 1) ≤ |T| · n. If |S_T| = 0, the strict inequality is immediate because |T| · n > 0; if |S_T| > 0, multiplying by k is strictly less than multiplying by k + 1, completing the proof.
To show that W satisfies EJR, it suffices to prove that |S_T| · k < |T| · n for an arbitrary nonempty subset of candidates T, where S_T is the set of voters approving all of T who have fewer than |T| approved candidates in W.
Rewriting with the characterization lemma is_ejr_committee_iff_candidate_subsets, committee W satisfies EJR if and only if |W| = k (which holds by hypothesis hcard) and for every nonempty subset of candidates T, |S_T| · k < |T| · n. We then introduce an arbitrary candidate set T and the hypothesis hT that it is nonempty.
uses
is_ejr_committee_iff_candidate_subsetsrw [is_ejr_committee_iff_candidate_subsets] refine ⟨hcard, ?_⟩ intro T hT
The density bound gives |S_T| · (k + 1) ≤ |T| · n, and the right-hand side |T| · n is strictly positive.
Specializing the density bound assumption h to T yields |S_T| · (k + 1) ≤ |T| · n. Since T is nonempty, its cardinality is strictly positive by Finset.card_pos.mpr; because the electorate size n is also positive (hn), their product |T| · n is strictly positive by Nat.mul_pos.
uses
Finset.card_pos.mpr,Nat.mul_poshave hb := h T have hp : 0 < T.card * n := Nat.mul_pos (Finset.card_pos.mpr hT) hn
If |S_T| = 0, the inequality |S_T| · k < |T| · n holds.
We split into cases based on whether |S_T| = 0. When |S_T| = 0, the product |S_T| · k simplifies to 0 by zero_mul, reducing the goal to 0 < |T| · n, which is precisely the strict positivity established in the previous step.
uses
zero_mulby_cases hz : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card).card = 0 · simpa only [hz, zero_mul] using hp
If |S_T| ≠ 0, the inequality |S_T| · k < |T| · n holds.
When |S_T| ≠ 0, its cardinality is strictly positive by Nat.pos_of_ne_zero. For any positive integer, multiplying by k is strictly less than multiplying by k + 1, so |S_T| · k < |S_T| · (k + 1). Combining this with the density bound |S_T| · (k + 1) ≤ |T| · n gives |S_T| · k < |T| · n by nonlinear arithmetic.
uses
Nat.pos_of_ne_zero· have hpos : 0 < (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card).card := Nat.pos_of_ne_zero hz nlinarith
is_ejr_committee_iff_candidate_subsets- A committee W of size k satisfies Extended Justified Representation (EJR) if and only if |W| = k and every nonempty candidate set T satisfies |{i | T ⊆ A(i) ∧ |A(i) ∩ W| < |T|}| · k < |T| · n.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
Finset.card_pos.mpr- A finite set has strictly positive cardinality if it is nonempty.
zero_mul- Zero multiplied by any element is zero (0 · a = 0).
Nat.pos_of_ne_zero- A natural number is strictly positive if it is nonzero.
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_of_support_density_bound {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) (hn : 0 < n) (hcard : W.card = k) (h : ejr_support_density_bound A (k + 1) W) : is_ejr_committee A k W := by rw [is_ejr_committee_iff_candidate_subsets] refine ⟨hcard, ?_⟩ intro T hT have hb := h T have hp : 0 < T.card * n := Nat.mul_pos (Finset.card_pos.mpr hT) hn by_cases hz : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card).card = 0 · simpa only [hz, zero_mul] using hp · have hpos : 0 < (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card).card := Nat.pos_of_ne_zero hz nlinarith