AFTD Auto-Formalizing Theoretical Domains

critical_four_two_choice_pairing_counterexample

theoremverifiedoriginal

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.

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

    lines 6–18

    uses Finset.sum_involution, ZMod.natCast_eq_zero_iff_even.mp

      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 hz
  2. 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.

    lines 24–41

    uses Finset.one_lt_card.mp, Finset.mem_filter, Finset.mem_univ, true_and, ne_of_lt, lt_asymm

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

    lines 42–54

    uses Ne.symm, Finset.mem_insert, Finset.mem_singleton, Finset.eq_of_subset_of_card_le

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

    lines 55–62

    uses Finset.mem_insert, Finset.mem_singleton

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

    line 76

      decide
  6. The 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.

    line 83

      decide
  7. Assuming 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.

    lines 91–95

    uses critical_four_odd_overlap_cert.2

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

    lines 96–105

    uses critical_four_odd_overlap_cert.1, critical_four_lows_closed

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

    lines 106–117

    uses critical_pairing_even_card, Finset.mem_inter.mpr, Finset.mem_inter.mp, Nat.not_even_iff_odd.mpr

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

    lines 130–132

    uses critical_four_odd_overlap_cert.1, critical_four_no_two_good_pairs_cert, critical_four_valid_allocation_cert

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

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

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