quota_population_monotone_incompatible_four_states_common_house
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
- Physlib.List.mem_take_finrangePhyslib.List.mem_take_finrange
- Physlib.List.mem_eraseIdx_nodupPhyslib.List.mem_eraseIdx_nodup
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
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.
/-- **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)