AFTD Auto-Formalizing Theoretical Domains

ejr_committee_nine_without_three_subset

theoremverified

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`).

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

    lines 7–12

      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
  2. $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`).

    lines 13–16

    uses is_ejr_committee_iff_candidate_subsets

      have hcore : is_ejr_committee A 9 W := by
        rw [is_ejr_committee_iff_candidate_subsets]
        set_option maxRecDepth 10000 in
        decide
  3. 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`.

    lines 17–21

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

    lines 22–23

      refine ⟨A, W, hcore, ?_⟩
      rintro ⟨V, hVW, hV⟩
  5. $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`.

    line 24

    uses is_ejr_committee_iff_candidate_subsets

      have h := (is_ejr_committee_iff_candidate_subsets A 3 V).mp hV
  6. $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`.

    lines 25–32

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

    line 33

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

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

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