AFTD Auto-Formalizing Theoretical Domains

quota_population_monotone_incompatible_four_states_common_house

theoremverifiedoriginal

No apportionment solution for four states satisfies quota and avoids population paradoxes between profiles at the same house size; twelve profiles at house size 8 already force a paradox.

Statement

theorem quota_population_monotone_incompatible_four_states_common_house :
    ¬ ∃ f : (Fin 4 → ℕ) → ℕ → (Fin 4 → ℕ),
      (∀ p h, (∀ i, 0 < p i) → satisfies_quota p h (f p h)) ∧
      ∀ p p' h, (∀ i, 0 < p i) → (∀ i, 0 < p' i) → ¬ population_paradox f p p' h h
Related work
operator (Claude), 2026-10-03: four-state impossibility of quota and population monotonicity with all comparisons at one common house size (h = 8, twelve profiles), the variant left open by arXiv:2608.02759, Sec. 5, of the question in In This Apportionment Lottery, the House Always Wins, arXiv:2202.11061 (EC 2022 / Operations Research), Sec. 2 and Sec. 3.1; witness found by a SAT search agent, checked by two independent brute-force scripts and by the Lean kernel
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • satisfies_quotaQuota: the seats sum to the house size and each state receives the floor or the ceiling of its standard quota h p_i / sum p.
  • population_paradoxA population paradox between (p, h) and (p', h'): two states i != j with p'_i >= p_i and p'_j <= p_j such that i loses a seat and j gains…
  • apx_search_soundIf the pruned search succeeds, every seat assignment choosing candidates for the profiles has a population paradox between two of them.
  • apx_profilesThe twelve four-state population profiles of the witness; state 2 always has population 30.
  • apx_kernel_checkThe pruned search succeeds on the twelve profiles at house size 8 (kernel computation).
  • apx_mem_candidatesA seat vector satisfying quota at house size 8 for a positive profile is among its candidates.
  • apx_paradox_iffA population paradox at a common house size is equivalent to the Boolean paradox test on the solution's seat vectors.
Used by 2

Read back from the Lean

There does not exist an apportionment function f : (Fin 4 → ℕ) → ℕ → (Fin 4 → ℕ) (mapping a population vector of 4 states and a house size to an apportionment) that satisfies both of the following properties: 1. **Quota rule**: For every population vector p : Fin 4 → ℕ and every house size h : ℕ, if every state has strictly positive population (0 < p i for all i : Fin 4), then the apportionment f p h satisfies the quota condition for p and h (the total number of apportioned seats equals h, and each state i receives an integer number of seats between the floor and the ceiling of its exact quota (h * p i) / (∑ j, p j)). 2. **Population monotonicity (no population paradox for a common house size)**: For all population vectors p, p' : Fin 4 → ℕ and every house size h : ℕ, if all states have strictly positive populations in both p and p' (0 < p i and 0 < p' i for all i : Fin 4), then f does not exhibit a population paradox between (p, h) and (p', h) (that is, there do not exist distinct states i ≠ j such that state i's population did not decrease (p i ≤ p' i), state j's population did not increase (p' j ≤ p j), but state i lost seats (f p' h i < f p h i) while state j gained seats (f p h j < f p' h j)).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- **Quota and population monotonicity are incompatible for four states, even with every monotonicity comparison at one common house size.** In This Apportionment Lottery, the House Always Wins (Sec. 3.1) asks whether impossibility holds for `n = 4`; arXiv:2608.02759 settles it when house sizes may differ and leaves open the common-house-size version. Here no apportionment solution for four states with positive integer populations satisfies quota and has no population paradox between two profiles at the same house size; twelve profiles at house size 8 already force a paradox. -/theorem quota_population_monotone_incompatible_four_states_common_house :    ¬ ∃ f : (Fin 4 → ℕ) → ℕ → (Fin 4 → ℕ),      (∀ p h, (∀ i, 0 < p i) → satisfies_quota p h (f p h)) ∧      ∀ p p' h, (∀ i, 0 < p i) → (∀ i, 0 < p' i) → ¬ population_paradox f p p' h h := by  rintro ⟨f, hquota, hmono⟩  have hpos : ∀ p ∈ apx_profiles, ∀ i, 0 < p i := by    intro p hp i    simp only [apx_profiles, List.mem_cons, List.not_mem_nil, or_false] at hp    rcases hp with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>      fin_cases i <;> decide  obtain ⟨p, q, hp, hq, hpar⟩ := apx_search_sound (fun p => f p 8) (fun p => ∀ i, 0 < p i) _ []    apx_kernel_check (by simp) (by      intro pc hpc      obtain ⟨p, hp, rfl⟩ := List.mem_map.1 hpc      exact ⟨apx_mem_candidates p (hpos p hp) _ (hquota p 8 (hpos p hp)), hpos p hp⟩)  exact hmono p q 8 hp hq ((apx_paradox_iff f p q 8).2 hpar)
See it in the graphDiscuss this resultChallenge it