ejr_support_density_bound_two_voter_trap
The two-voter private-approval profile has a size-one committee satisfying the stronger density bound, but no size-two extension satisfying the next bound.
Statement
theorem ejr_support_density_bound_two_voter_trap : let A : Fin 2 → Finset (Fin 3) := ![{0}, {1}] ejr_support_density_bound A 2 {2} ∧ ¬ ∃ W : Finset (Fin 3), {2} ⊆ W ∧ W.card = 2 ∧ ejr_support_density_bound A 3 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 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 a "trap" in greedy committee selection: for two voters with approval sets $\{0\}$ and $\{1\}$, the singleton committee $\{2\}$ (containing an unapproved candidate) satisfies the EJR support density bound with quota $q = 2$, yet cannot be extended to any size-$2$ committee satisfying the bound with quota $q = 3$. After unfolding definitions, the statement involves only finite sets of sizes $2$ and $3$, and the proof concludes via finite exhaustive computation.
The goal is reduced to an explicit assertion over the finite sets of voters and candidates.
The profile definition $A = ![\{0\}, \{1\}]$ is simplified into the goal, and the definition of `ejr_support_density_bound` is unfolded. This expresses both parts of the conjunction directly as bounded quantifications over the subsets of the 3-element candidate universe $\{0, 1, 2\}$.
dsimp unfold ejr_support_density_bound
The singleton committee $\{2\}$ satisfies the density bound with quota $q = 2$, but neither of its size-two extensions satisfies the bound with quota $q = 3$. automation
Because the candidate set $\mathrm{Fin}(3)$ has only $2^3 = 8$ subsets and there are only two voters, the entire formula is decidable. The `decide` tactic checks the condition by exhaustive evaluation: $\{2\}$ satisfies the inequality for $q = 2$ across all test sets $T$, whereas the only two size-$2$ supersets of $\{2\}$—namely $\{0, 2\}$ and $\{1, 2\}$—both fail for $q = 3$ (witnessed by $T = \{1\}$ and $T = \{0\}$ respectively, where $1 \cdot 3 \le 1 \cdot 2$ fails).
decide
- The entire combinatorial verification is delegated to the `decide` tactic, which evaluates the finite quantifications by exhaustive computation rather than presenting manual case analysis or witness counterexamples.
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_two_voter_trap : let A : Fin 2 → Finset (Fin 3) := ![{0}, {1}] ejr_support_density_bound A 2 {2} ∧ ¬ ∃ W : Finset (Fin 3), {2} ⊆ W ∧ W.card = 2 ∧ ejr_support_density_bound A 3 W := by dsimp unfold ejr_support_density_bound decide