AFTD Auto-Formalizing Theoretical Domains

ejr_support_density_bound_two_voter_trap

theoremverified

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.

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

    lines 6–7

      dsimp
      unfold ejr_support_density_bound
  2. 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).

    line 8

      decide

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