AFTD Auto-Formalizing Theoretical Domains

ejr_of_support_density_bound

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

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.

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

    lines 5–7

    uses is_ejr_committee_iff_candidate_subsets

      rw [is_ejr_committee_iff_candidate_subsets]
      refine ⟨hcard, ?_⟩
      intro T hT
  2. 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.

    lines 8–9

    uses Finset.card_pos.mpr, Nat.mul_pos

      have hb := h T
      have hp : 0 < T.card * n := Nat.mul_pos (Finset.card_pos.mpr hT) hn
  3. 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.

    lines 10–12

    uses zero_mul

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

    lines 13–15

    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

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