critical_four_two_choice_pairing_counterexample
There exist four sets L_i, one for each i in Fin 4, of four low chores drawn from the nine chores Fin 9, with the following properties. For every extra chore e and every permutation p of the nine chores which fixes e, has no other fixed points and satisfies p(p(g)) = g for every chore g, there is an agent i such that at most one representative g with g < p(g) satisfies: if e is in L_i, at least one of g and p(g) is in L_i, while if e is not in L_i, both g and p(g) are in L_i. Moreover there is a function F from Fin 4 times Fin 9 to Fin 4 such that for each chore g, t maps to F(t,g) bijectively; for each t and i, exactly three chores g have F(t,g)=i when i=t, and exactly two have F(t,g)=i when i differs from t; and for each t, at most one chore assigned by F(t,−) to t is outside L_t.
Statement
theorem critical_four_two_choice_pairing_counterexample : ∃ L : Fin 4 → Finset (Fin 9), (∀ i, (L i).card = 4) ∧ (∀ (e : Fin 9) (p : Equiv.Perm (Fin 9)), p e = e → (∀ g, g ≠ e → p g ≠ g) → (∀ g, p (p g) = g) → ∃ i : Fin 4, (Finset.univ.filter (fun g => g < p g ∧ if e ∈ L i then g ∈ L i ∨ p g ∈ L i else g ∈ L i ∧ p g ∈ L i)).card ≤ 1) ∧ ∃ F : Fin 4 → Fin 9 → Fin 4, (∀ g, Function.Bijective (fun t => F t g)) ∧ (∀ t i, (Finset.univ.filter (fun g => F t g = i)).card = if i = t then 3 else 2) ∧ ∀ t, ((Finset.univ.filter (fun g => F t g = t)) \ L t).card ≤ 1
- Related work
- A counterexample to the two-good-pairs construction for OP-1112, related to arXiv:2609.35280.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
There exists a family of subsets $L : \text{Fin } 4 \to \text{Finset}(\text{Fin } 9)$ such that: 1. For every $i \in \text{Fin } 4$, $|L(i)| = 4$. 2. For every element $e \in \text{Fin } 9$ and every permutation $p$ of $\text{Fin } 9$, if: - $p(e) = e$, - for all $g \in \text{Fin } 9$, $g \ne e \implies p(g) \ne g$, and - for all $g \in \text{Fin } 9$, $p(p(g)) = g$ (i.e., $p$ is an involution whose unique fixed point is $e$), then there exists some $i \in \text{Fin } 4$ such that the number of elements $g \in \text{Fin } 9$ satisfying: - $g < p(g)$, and - if $e \in L(i)$, then $(g \in L(i) \lor p(g) \in L(i))$, otherwise $(g \in L(i) \land p(g) \in L(i))$ is at most 1. 3. There exists a function $F : \text{Fin } 4 \to \text{Fin } 9 \to \text{Fin } 4$ such that: - For every $g \in \text{Fin } 9$, the map $t \mapsto F(t, g)$ is bijective from $\text{Fin } 4$ to $\text{Fin } 4$. - For all $t, i \in \text{Fin } 4$, the cardinality of $\{g \in \text{Fin } 9 \mid F(t, g) = i\}$ is equal to 3 if $i = t$ and 2 if $i \ne t$. - For every $t \in \text{Fin } 4$, the cardinality of the set difference $\{g \in \text{Fin } 9 \mid F(t, g) = t\} \setminus L(t)$ is at most 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by constructing an explicit family of four 4-element sets of low chores and an explicit 4×9 allocation matrix F, verifying their required properties. To establish that at least one agent has at most one good pair for any fixed-point-free-on-the-rest involution p fixing only an extra chore e, the proof proceeds by contradiction. A precomputed finite certificate identifies two agents i, j neither containing e whose low sets have an odd-sized intersection. Because e is not in their low sets, having two good pairs forces both low sets to be entirely composed of two swapped pairs, making them invariant under p. Consequently, their intersection is also invariant under p and contains no fixed points, which forces its cardinality to be even, directly contradicting the certified odd cardinality.
A finite set equipped with a fixed-point-free involution has even cardinality (`critical_pairing_even_card`).
We evaluate the sum ∑_{x ∈ s} 1 in the field ℤ/2ℤ. By `Finset.sum_involution`, pairing each x ∈ s with p(x) cancels every term because 1 + 1 = 0 in ℤ/2ℤ, and p has no fixed points on s to leave an isolated term. Hence the sum is 0, so the cardinality of s mod 2 is 0, which means |s| is even by `ZMod.natCast_eq_zero_iff_even.mp`.
uses
Finset.sum_involution,ZMod.natCast_eq_zero_iff_even.mphave hsum : ∑ x ∈ s, (1 : ZMod 2) = 0 := by apply Finset.sum_involution (fun x _ => p x) · intro x hx change (1 : ZMod 2) + 1 = 0 decide · intro x hx _ exact hfix x hx · intro x hx exact hp x hx · intro x hx exact hinv x hx have hz : (s.card : ZMod 2) = 0 := by simpa using hsum exact ZMod.natCast_eq_zero_iff_even.mp hz
If a 4-element set L has at least two good pairs under an involution p, the two pairs provide four pairwise distinct elements a, p(a), b, p(b).
Since the number of representatives g < p(g) with both g, p(g) ∈ L is at least 2, `Finset.one_lt_card.mp` gives two distinct representatives a ≠ b with a < p(a) and b < p(b). Clearly a ≠ p(a) and b ≠ p(b) by strict inequality (`ne_of_lt`). If a = p(b), then p(a) = b, which would imply both a < b and b < a, contradicting the asymmetry of < (`lt_asymm`); the same argument shows p(a) ≠ b. Finally, p(a) ≠ p(b) by injectivity of the permutation p.
uses
Finset.one_lt_card.mp,Finset.mem_filter,Finset.mem_univ,true_and,ne_of_lt,lt_asymmclassical obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp (by omega : 1 < (Finset.univ.filter (fun g => g < p g ∧ g ∈ L ∧ p g ∈ L)).card) simp only [Finset.mem_filter, Finset.mem_univ, true_and] at ha hb have haa : a ≠ p a := ne_of_lt ha.1 have hbb : b ≠ p b := ne_of_lt hb.1 have hapb : a ≠ p b := by intro he have hpa : p a = b := by rw [he, hinv] have h1 : a < b := by simpa [hpa] using ha.1 have h2 : b < a := by simpa [he] using hb.1 exact (lt_asymm h1) h2 have hpab : p a ≠ b := by intro he have hpb : p b = a := by rw [← he, hinv] have h1 : a < b := by simpa [he] using ha.1 have h2 : b < a := by simpa [hpb] using hb.1 exact (lt_asymm h1) h2 have hpab' : p a ≠ p b := fun h => hab (p.injective h)
The set Q = {a, p(a), b, p(b)} equals L.
Since its four elements are pairwise distinct, Q has cardinality 4. Each element belongs to L by definition of the good pairs, so Q ⊆ L. Because |Q| = 4 = |L|, `Finset.eq_of_subset_of_card_le` implies Q = L.
uses
Ne.symm,Finset.mem_insert,Finset.mem_singleton,Finset.eq_of_subset_of_card_lelet Q : Finset (Fin 9) := {a,p a,b,p b} have hQcard : Q.card = 4 := by simp [Q, haa, hbb, hab, hapb, hpab, hpab', Ne.symm haa, Ne.symm hbb, Ne.symm hab, Ne.symm hapb, Ne.symm hpab, Ne.symm hpab'] have hQsub : Q ⊆ L := by intro x hx simp only [Q, Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl | rfl · exact ha.2.1 · exact ha.2.2 · exact hb.2.1 · exact hb.2.2 have hQeq : Q = L := Finset.eq_of_subset_of_card_le hQsub (by omega)
The set L is invariant under p, i.e., p(x) ∈ L for all x ∈ L (`critical_four_lows_closed`).
For any x ∈ L, since L = Q = {a, p(a), b, p(b)}, x must be one of these four elements. Its image under p is p(a), p(p(a)) = a, p(b), or p(p(b)) = b, all of which belong to L.
uses
Finset.mem_insert,Finset.mem_singletonintro x hx have hxQ : x ∈ Q := by rw [hQeq]; exact hx simp only [Q, Finset.mem_insert, Finset.mem_singleton] at hxQ rcases hxQ with rfl | rfl | rfl | rfl · exact ha.2.2 · simpa [hinv a] using ha.2.1 · exact hb.2.2 · simpa [hinv b] using hb.2.1
Each set L_i has cardinality 4, and for every chore e, there exist two agents i, j whose low sets omit e and have an odd-sized intersection (`critical_four_odd_overlap_cert`). automation
This combinatorial property for the four explicit sets L₀ = {0,5,6,7}, L₁ = {0,1,2,3}, L₂ = {1,2,3,4}, L₃ = {4,5,6,7} is verified by exhaustive check over the finite types Fin 4 and Fin 9 via `decide`.
decideThe allocation function F is a valid schedule satisfying the required round-by-round and per-agent chore counts (`critical_four_valid_allocation_cert`). automation
The explicit 4×9 allocation matrix F is verified by exhaustive computation via `decide`: for every chore g, t ↦ F(t,g) is a bijection; in round t, agent t receives 3 chores while all other agents receive 2; and agent t receives at most 1 chore outside L_t.
decideAssuming for contradiction that every agent has at least two good pairs, select two agents i, j whose low sets omit the fixed chore e and have odd overlap.
We introduce the chore e and involution p fixing only e, and assume for contradiction that every agent k has at least two good pairs. The certificate `critical_four_odd_overlap_cert.2` provides agents i and j such that e ∉ L_i, e ∉ L_j, and |L_i ∩ L_j| is odd.
uses
critical_four_odd_overlap_cert.2classical intro e p he hfix hinv by_contra h push_neg at h obtain ⟨i,j,hei,hej,hodd⟩ := critical_four_odd_overlap_cert.2 e
Both L_i and L_j are invariant under the involution p.
Because e ∉ L_i, the definition of a good pair for agent i simplifies to requiring both g ∈ L_i and p(g) ∈ L_i. Thus agent i has at least two pairs entirely contained in L_i. By `critical_four_lows_closed`, L_i is invariant under p. The identical deduction applies to agent j, showing p(x) ∈ L_j for all x ∈ L_j.
uses
critical_four_odd_overlap_cert.1,critical_four_lows_closedhave hi : 2 ≤ (Finset.univ.filter (fun g => g < p g ∧ g ∈ critical_four_lows i ∧ p g ∈ critical_four_lows i)).card := by have hh := h i simp only [hei, ↓reduceIte] at hh omega have hj : 2 ≤ (Finset.univ.filter (fun g => g < p g ∧ g ∈ critical_four_lows j ∧ p g ∈ critical_four_lows j)).card := by have hh := h j simp only [hej, ↓reduceIte] at hh omega have hci := critical_four_lows_closed (critical_four_lows i) (critical_four_odd_overlap_cert.1 i) p hinv hi have hcj := critical_four_lows_closed (critical_four_lows j) (critical_four_odd_overlap_cert.1 j) p hinv hj
The intersection L_i ∩ L_j is invariant under p with no fixed points, forcing its size to be both even and odd, a contradiction (`critical_four_no_two_good_pairs_cert`).
Since both L_i and L_j are invariant under p, their intersection L_i ∩ L_j is also invariant under p. Furthermore, the only fixed point of p is e, but e ∉ L_i, so p has no fixed points on L_i ∩ L_j. By `critical_pairing_even_card`, |L_i ∩ L_j| must be even. However, the certificate established that |L_i ∩ L_j| is odd; by `Nat.not_even_iff_odd.mpr`, this is impossible, completing the proof by contradiction.
uses
critical_pairing_even_card,Finset.mem_inter.mpr,Finset.mem_inter.mp,Nat.not_even_iff_odd.mprhave heven : Even ((critical_four_lows i ∩ critical_four_lows j).card) := by apply critical_pairing_even_card (critical_four_lows i ∩ critical_four_lows j) p · intro x hx exact Finset.mem_inter.mpr ⟨hci x (Finset.mem_inter.mp hx).1, hcj x (Finset.mem_inter.mp hx).2⟩ · intro x hx exact hinv x · intro x hx apply hfix intro hxe subst x exact hei (Finset.mem_inter.mp hx).1 exact (Nat.not_even_iff_odd.mpr hodd) heven
There exist sets L_i and an allocation schedule F satisfying all counterexample conditions (`critical_four_two_choice_pairing_counterexample`).
We instantiate the existential witnesses with the definitions `critical_four_lows` and `critical_four_allocations`, packaging them with the established certificates `critical_four_odd_overlap_cert.1`, `critical_four_no_two_good_pairs_cert`, and `critical_four_valid_allocation_cert`.
uses
critical_four_odd_overlap_cert.1,critical_four_no_two_good_pairs_cert,critical_four_valid_allocation_certrefine ⟨critical_four_lows, critical_four_odd_overlap_cert.1, critical_four_no_two_good_pairs_cert, critical_four_allocations, critical_four_valid_allocation_cert⟩
Finset.sum_involution- A sum over a finite set is zero if an involution on the set pairs up elements whose values sum to zero and has no fixed points on elements with non-zero values.
ZMod.natCast_eq_zero_iff_even.mp- If the canonical image of a natural number in ℤ/2ℤ is zero, then the number is even.
Finset.one_lt_card.mp- A finite set with cardinality strictly greater than 1 contains at least two distinct elements.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal set.
true_and- Conjunction with True simplifies to the second proposition.
ne_of_lt- A strictly smaller element is not equal to the larger element.
lt_asymm- Strict inequality is asymmetric: if a < b, then b cannot be strictly less than a.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or is already in s.
Finset.mem_singleton- An element is in the singleton set {a} if and only if it equals a.
Finset.eq_of_subset_of_card_le- If a finite subset has cardinality at least that of the superset, the two sets are equal.
critical_four_odd_overlap_cert.2- For every chore e in Fin 9, there exist two agents whose low sets do not contain e and have an odd number of chores in common.
critical_four_odd_overlap_cert.1- Each of the four low sets has exactly four elements.
critical_four_lows_closed- If a 4-element set contains at least two disjoint pairs swapped by an involution, the set is invariant under the involution.
critical_pairing_even_card- A finite set equipped with a fixed-point-free involution has even cardinality.
Finset.mem_inter.mpr- An element belonging to both s and t belongs to their intersection.
Finset.mem_inter.mp- An element in the intersection of s and t belongs to both s and t.
Nat.not_even_iff_odd.mpr- An odd natural number is not even.
critical_four_no_two_good_pairs_cert- For any extra chore e and any involution p fixing only e, some agent has at most one good pair.
critical_four_valid_allocation_cert- The allocation function F satisfies bijectivity across rounds, assigns 3 chores to agent t and 2 to others in round t, and assigns agent t at most 1 chore outside their low set.
- Steps 5 and 6 rely on `decide` to verify the finite combinatorial properties of the explicit four sets and the 4×9 allocation matrix by exhaustive finite checking.
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.
open Finsetprivate lemma critical_pairing_even_card {α : Type*} [DecidableEq α] (s : Finset α) (p : α → α) (hp : ∀ x ∈ s, p x ∈ s) (hinv : ∀ x ∈ s, p (p x) = x) (hfix : ∀ x ∈ s, p x ≠ x) : Even s.card := by have hsum : ∑ x ∈ s, (1 : ZMod 2) = 0 := by apply Finset.sum_involution (fun x _ => p x) · intro x hx change (1 : ZMod 2) + 1 = 0 decide · intro x hx _ exact hfix x hx · intro x hx exact hp x hx · intro x hx exact hinv x hx have hz : (s.card : ZMod 2) = 0 := by simpa using hsum exact ZMod.natCast_eq_zero_iff_even.mp hzprivate lemma critical_four_lows_closed (L : Finset (Fin 9)) (hL : L.card = 4) (p : Equiv.Perm (Fin 9)) (hinv : ∀ x, p (p x) = x) (hgood : 2 ≤ (Finset.univ.filter (fun g => g < p g ∧ g ∈ L ∧ p g ∈ L)).card) : ∀ x ∈ L, p x ∈ L := by classical obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp (by omega : 1 < (Finset.univ.filter (fun g => g < p g ∧ g ∈ L ∧ p g ∈ L)).card) simp only [Finset.mem_filter, Finset.mem_univ, true_and] at ha hb have haa : a ≠ p a := ne_of_lt ha.1 have hbb : b ≠ p b := ne_of_lt hb.1 have hapb : a ≠ p b := by intro he have hpa : p a = b := by rw [he, hinv] have h1 : a < b := by simpa [hpa] using ha.1 have h2 : b < a := by simpa [he] using hb.1 exact (lt_asymm h1) h2 have hpab : p a ≠ b := by intro he have hpb : p b = a := by rw [← he, hinv] have h1 : a < b := by simpa [he] using ha.1 have h2 : b < a := by simpa [hpb] using hb.1 exact (lt_asymm h1) h2 have hpab' : p a ≠ p b := fun h => hab (p.injective h) let Q : Finset (Fin 9) := {a,p a,b,p b} have hQcard : Q.card = 4 := by simp [Q, haa, hbb, hab, hapb, hpab, hpab', Ne.symm haa, Ne.symm hbb, Ne.symm hab, Ne.symm hapb, Ne.symm hpab, Ne.symm hpab'] have hQsub : Q ⊆ L := by intro x hx simp only [Q, Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl | rfl · exact ha.2.1 · exact ha.2.2 · exact hb.2.1 · exact hb.2.2 have hQeq : Q = L := Finset.eq_of_subset_of_card_le hQsub (by omega) intro x hx have hxQ : x ∈ Q := by rw [hQeq]; exact hx simp only [Q, Finset.mem_insert, Finset.mem_singleton] at hxQ rcases hxQ with rfl | rfl | rfl | rfl · exact ha.2.2 · simpa [hinv a] using ha.2.1 · exact hb.2.2 · simpa [hinv b] using hb.2.1private def critical_four_lows : Fin 4 → Finset (Fin 9) := ![ {0,5,6,7}, {0,1,2,3}, {1,2,3,4}, {4,5,6,7}]private def critical_four_allocations : Fin 4 → Fin 9 → Fin 4 := ![ ![0,3,3,1,1,0,0,2,2], ![1,1,1,0,0,2,2,3,3], ![2,2,2,3,3,1,1,0,0], ![3,0,0,2,2,3,3,1,1]]private theorem critical_four_odd_overlap_cert : (∀ i, (critical_four_lows i).card = 4) ∧ ∀ e : Fin 9, ∃ i j : Fin 4, e ∉ critical_four_lows i ∧ e ∉ critical_four_lows j ∧ Odd ((critical_four_lows i ∩ critical_four_lows j).card) := by decideprivate theorem critical_four_valid_allocation_cert : (∀ g : Fin 9, Function.Bijective (fun t => critical_four_allocations t g)) ∧ (∀ t i : Fin 4, ((Finset.univ.filter (fun g => critical_four_allocations t g = i))).card = if i = t then 3 else 2) ∧ ∀ t : Fin 4, ((Finset.univ.filter (fun g => critical_four_allocations t g = t)) \ critical_four_lows t).card ≤ 1 := by decideprivate theorem critical_four_no_two_good_pairs_cert : ∀ (e : Fin 9) (p : Equiv.Perm (Fin 9)), p e = e → (∀ g, g ≠ e → p g ≠ g) → (∀ g, p (p g) = g) → ∃ i : Fin 4, (Finset.univ.filter (fun g => g < p g ∧ if e ∈ critical_four_lows i then g ∈ critical_four_lows i ∨ p g ∈ critical_four_lows i else g ∈ critical_four_lows i ∧ p g ∈ critical_four_lows i)).card ≤ 1 := by classical intro e p he hfix hinv by_contra h push_neg at h obtain ⟨i,j,hei,hej,hodd⟩ := critical_four_odd_overlap_cert.2 e have hi : 2 ≤ (Finset.univ.filter (fun g => g < p g ∧ g ∈ critical_four_lows i ∧ p g ∈ critical_four_lows i)).card := by have hh := h i simp only [hei, ↓reduceIte] at hh omega have hj : 2 ≤ (Finset.univ.filter (fun g => g < p g ∧ g ∈ critical_four_lows j ∧ p g ∈ critical_four_lows j)).card := by have hh := h j simp only [hej, ↓reduceIte] at hh omega have hci := critical_four_lows_closed (critical_four_lows i) (critical_four_odd_overlap_cert.1 i) p hinv hi have hcj := critical_four_lows_closed (critical_four_lows j) (critical_four_odd_overlap_cert.1 j) p hinv hj have heven : Even ((critical_four_lows i ∩ critical_four_lows j).card) := by apply critical_pairing_even_card (critical_four_lows i ∩ critical_four_lows j) p · intro x hx exact Finset.mem_inter.mpr ⟨hci x (Finset.mem_inter.mp hx).1, hcj x (Finset.mem_inter.mp hx).2⟩ · intro x hx exact hinv x · intro x hx apply hfix intro hxe subst x exact hei (Finset.mem_inter.mp hx).1 exact (Nat.not_even_iff_odd.mpr hodd) heventheorem critical_four_two_choice_pairing_counterexample : ∃ L : Fin 4 → Finset (Fin 9), (∀ i, (L i).card = 4) ∧ (∀ (e : Fin 9) (p : Equiv.Perm (Fin 9)), p e = e → (∀ g, g ≠ e → p g ≠ g) → (∀ g, p (p g) = g) → ∃ i : Fin 4, (Finset.univ.filter (fun g => g < p g ∧ if e ∈ L i then g ∈ L i ∨ p g ∈ L i else g ∈ L i ∧ p g ∈ L i)).card ≤ 1) ∧ ∃ F : Fin 4 → Fin 9 → Fin 4, (∀ g, Function.Bijective (fun t => F t g)) ∧ (∀ t i, (Finset.univ.filter (fun g => F t g = i)).card = if i = t then 3 else 2) ∧ ∀ t, ((Finset.univ.filter (fun g => F t g = t)) \ L t).card ≤ 1 := by refine ⟨critical_four_lows, critical_four_odd_overlap_cert.1, critical_four_no_two_good_pairs_cert, critical_four_allocations, critical_four_valid_allocation_cert⟩