ejr_committee_nine_without_three_subset
There is an approval profile with nine voters and eleven candidates and an EJR committee of size nine that contains no EJR committee of size three. This is an obstruction to building a whole monotone chain inside an arbitrary large EJR committee, not a refutation of monotone-chain existence.
Statement
theorem ejr_committee_nine_without_three_subset :
∃ (A : Fin 9 → Finset (Fin 11)) (W : Finset (Fin 11)),
is_ejr_committee A 9 W ∧ ¬ ∃ V, V ⊆ W ∧ is_ejr_committee A 3 V- Source
- Helper counterexample for the fixed-core proof route to ejr_committee_monotone_chain_exists (OP-22; arXiv:2007.01795 Q2). Computations 4299 and 4310: three private candidate triples, each approved by a bloc of three voters, with two voters per bloc additionally approving a shared pair.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
- 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| ≥ ℓ.
- VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
The proof, explained
The proof constructs an explicit counterexample: an approval voting profile with 9 voters and 11 candidates, and a committee $W$ of 9 candidates satisfying Extended Justified Representation (EJR). Candidates $\{0,\dots,8\}$ are partitioned into three blocks of three approved by the corresponding three blocks of voters, while candidates $\{9,10\}$ are approved by two voters in each block. Any size-3 subcommittee $V \subseteq W$ would need to contain one candidate from each block to satisfy the quota for the singletons $\{0\}$, $\{3\}$, and $\{6\}$, but then all 6 voters approving $\{9,10\}$ would have only 1 approved candidate in $V$, violating EJR for $\{9,10\}$. Both the EJR property of $W$ and the certificate ruling out all $\binom{9}{3}=84$ size-3 subcommittees of $W$ are checked by finite computational verification (`decide`).
Define an approval profile $A$ with 9 voters and 11 candidates, a committee $W$ of size 9, and the representation-deficit counting function `under`.
Candidates $\{0, \dots, 8\}$ are partitioned into three blocks of three: $\{0, 1, 2\}$, $\{3, 4, 5\}$, and $\{6, 7, 8\}$. Voters are also partitioned into three blocks of three: voters in block $j$ approve candidates in block $j$, and the first two voters in each block additionally approve candidates 9 and 10. The committee $W$ is defined as $\{0, \dots, 8\}$. Finally, `under V T` counts the number of voters who approve all candidates in $T$ but have strictly fewer than $|T|$ approved candidates in committee $V$.
let A : Fin 9 → Finset (Fin 11) := fun i => let B := Finset.univ.filter fun c : Fin 11 => c.val < 9 ∧ c.val / 3 = i.val / 3 if i.val % 3 < 2 then B ∪ {9, 10} else B let W : Finset (Fin 11) := Finset.univ.filter fun c => c.val < 9 let under : Finset (Fin 11) → Finset (Fin 11) → ℕ := fun V T => (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ V).card < T.card).card
$W$ is an EJR committee of size 9. automation
Using the candidate-subset characterization of EJR (`is_ejr_committee_iff_candidate_subsets`), $W$ is an EJR committee of size 9 if and only if $|W| = 9$ and for every nonempty candidate set $T$, `under W T * 9 < |T| * 9`. Since candidate sets from a universe of 11 candidates are finite, Lean checks this condition by exhaustive computation (`decide`).
uses
is_ejr_committee_iff_candidate_subsetshave hcore : is_ejr_committee A 9 W := by rw [is_ejr_committee_iff_candidate_subsets] set_option maxRecDepth 10000 in decide
No size-3 committee $V \subseteq W$ can simultaneously satisfy the candidate-subset EJR inequalities for the test sets $\{0\}$, $\{3\}$, $\{6\}$, and $\{9, 10\}$. automation
The certificate lemma `cert` asserts that for every 3-element subset $V \subseteq W$, at least one of the four candidate-subset inequalities required by EJR fails: namely, `under V {0} * 3 < 9`, `under V {3} * 3 < 9`, `under V {6} * 3 < 9`, or `under V {9, 10} * 3 < 18`. Lean verifies this by checking all $\binom{9}{3} = 84$ possible committees $V$ using `decide`.
have cert : ∀ V : Finset (Fin 11), V ⊆ W → V.card = 3 → ¬ (under V {0} * 3 < 9 ∧ under V {3} * 3 < 9 ∧ under V {6} * 3 < 9 ∧ under V {9, 10} * 3 < 18) := by set_option maxRecDepth 10000 in decide
Assume, for contradiction, that there exists an EJR committee $V \subseteq W$ of size 3.
We provide $A$, $W$, and the proof `hcore` as witnesses to the existential statement. We then suppose, for contradiction, that there exists a committee $V \subseteq W$ that is an EJR committee of size 3.
refine ⟨A, W, hcore, ?_⟩ rintro ⟨V, hVW, hV⟩$V$ has cardinality 3 and satisfies the candidate-subset EJR inequality for all nonempty candidate sets $T$.
We apply the forward direction of `is_ejr_committee_iff_candidate_subsets` to the assumption that $V$ is an EJR committee of size 3, which yields $|V| = 3$ and the property that for every nonempty candidate set $T$, `under V T * 3 < |T| * 9`.
uses
is_ejr_committee_iff_candidate_subsetshave h := (is_ejr_committee_iff_candidate_subsets A 3 V).mp hV$V$ must satisfy the representation inequalities for each of $\{0\}$, $\{3\}$, $\{6\}$, and $\{9, 10\}$.
Specializing the universal EJR property of $V$ to the nonempty candidate sets $\{0\}$, $\{3\}$, $\{6\}$, and $\{9, 10\}$ gives four inequalities. The nonemptiness of each set is verified by `decide`, and `change` aligns the terms with the definition of `under`, yielding `under V {0} * 3 < 9`, `under V {3} * 3 < 9`, `under V {6} * 3 < 9`, and `under V {9, 10} * 3 < 18`.
have h0 := h.2 {0} (by decide) have h3 := h.2 {3} (by decide) have h6 := h.2 {6} (by decide) have h9 := h.2 {9, 10} (by decide) change under V {0} * 3 < 9 at h0 change under V {3} * 3 < 9 at h3 change under V {6} * 3 < 9 at h6 change under V {9, 10} * 3 < 18 at h9
Contradiction, completing the proof.
The certificate `cert` established that no 3-element subset $V \subseteq W$ can satisfy all four inequalities simultaneously. Supplying $V$, $V \subseteq W$, $|V| = 3$, and the conjunction of the four inequalities to `cert` produces `False`.
exact cert V hVW h.1 ⟨h0, h3, h6, h9⟩
is_ejr_committee_iff_candidate_subsets- A committee $W$ of size $k$ satisfies Extended Justified Representation (EJR) for an approval profile $A$ on $n$ voters if and only if $|W| = k$ and for every nonempty subset of candidates $T$, the number of voters who approve all candidates in $T$ but have strictly fewer than $|T|$ committee members in their approval set satisfies that count times $k$ is strictly less than $|T| \times n$.
- The verification that $W$ is an EJR committee of size 9 (lines 13–16) and the obstruction certificate showing no 3-element subset of $W$ satisfies EJR (lines 17–21) rely on Lean's `decide` tactic performing exhaustive finite computation.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 5000000theorem ejr_committee_nine_without_three_subset : ∃ (A : Fin 9 → Finset (Fin 11)) (W : Finset (Fin 11)), is_ejr_committee A 9 W ∧ ¬ ∃ V, V ⊆ W ∧ is_ejr_committee A 3 V := by let A : Fin 9 → Finset (Fin 11) := fun i => let B := Finset.univ.filter fun c : Fin 11 => c.val < 9 ∧ c.val / 3 = i.val / 3 if i.val % 3 < 2 then B ∪ {9, 10} else B let W : Finset (Fin 11) := Finset.univ.filter fun c => c.val < 9 let under : Finset (Fin 11) → Finset (Fin 11) → ℕ := fun V T => (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ V).card < T.card).card have hcore : is_ejr_committee A 9 W := by rw [is_ejr_committee_iff_candidate_subsets] set_option maxRecDepth 10000 in decide have cert : ∀ V : Finset (Fin 11), V ⊆ W → V.card = 3 → ¬ (under V {0} * 3 < 9 ∧ under V {3} * 3 < 9 ∧ under V {6} * 3 < 9 ∧ under V {9, 10} * 3 < 18) := by set_option maxRecDepth 10000 in decide refine ⟨A, W, hcore, ?_⟩ rintro ⟨V, hVW, hV⟩ have h := (is_ejr_committee_iff_candidate_subsets A 3 V).mp hV have h0 := h.2 {0} (by decide) have h3 := h.2 {3} (by decide) have h6 := h.2 {6} (by decide) have h9 := h.2 {9, 10} (by decide) change under V {0} * 3 < 9 at h0 change under V {3} * 3 < 9 at h3 change under V {6} * 3 < 9 at h6 change under V {9, 10} * 3 < 18 at h9 exact cert V hVW h.1 ⟨h0, h3, h6, h9⟩