AFTD Auto-Formalizing Theoretical Domains

op1525_pair_coloring_profile_classification

theoremverified

If two Boolean colorings of finitely many labeled pairs have the same number of monochromatic pairs and the same total number of true vertices, one coloring can be transformed into the other by permuting the pairs and independently swapping their two vertices.

Statement

theorem op1525_pair_coloring_profile_classification
    {I : Type*} [DecidableEq I] [Fintype I] (f g : I → Fin 2 → Bool)
    (hmono : ((Finset.univ : Finset I).filter (fun i => f i 0 = f i 1)).card =
      ((Finset.univ : Finset I).filter (fun i => g i 0 = g i 1)).card)
    (htrue : ((Finset.univ : Finset (I × Fin 2)).filter (fun x => f x.1 x.2 = true)).card =
      ((Finset.univ : Finset (I × Fin 2)).filter (fun x => g x.1 x.2 = true)).card) :
    ∃ σ : Equiv.Perm I, ∃ τ : I → Bool, ∀ i : I, ∀ j : Fin 2,
      f (σ i) (j + if τ i then 1 else 0) = g i j
Source
The color-profile classification for the complete pair-part route to OP-1525.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

Two colorings of labeled pairs with matching counts of monochromatic pairs and true vertices can be made identical by a pair permutation and vertex transpositions. By encoding each pair's vertex colors into a 3-valued code (the number of true vertices), the problem reduces to a linear system showing that the counts of each pair type match. Fiberwise bijections yield the desired permutation of pairs, and local swaps align the individual pairs.

  1. op1525_pair_code_val holds automation

    By finite exhaustion.

    lines 8–11

    lemma op1525_pair_code_val (h : Fin 2 → Bool) :
        (op1525_pair_code h).val = (if h 0 then 1 else 0) + (if h 1 then 1 else 0) := by
      revert h; decide
    
  2. op1525_pair_code_mono holds automation

    By finite exhaustion.

    lines 12–15

    lemma op1525_pair_code_mono (h : Fin 2 → Bool) :
        (h 0 = h 1) ↔ (op1525_pair_code h = 0 ∨ op1525_pair_code h = 2) := by
      revert h; decide
    
  3. op1525_pair_code_exists_tau holds automation

    By finite exhaustion.

    lines 16–19

    lemma op1525_pair_code_exists_tau (h h' : Fin 2 → Bool) (hc : op1525_pair_code h = op1525_pair_code h') :
        ∃ b : Bool, ∀ j : Fin 2, h (j + if b then 1 else 0) = h' j := by
      revert hc; revert h h'; decide
    
  4. op1525_c_wf_total holds

    Fiberwise card.

    lines 23–28

    lemma op1525_c_wf_total {I : Type*} [Fintype I] [DecidableEq I] (f : I → Fin 2 → Bool) :
        Fintype.card I = op1525_c_wf f 0 + op1525_c_wf f 1 + op1525_c_wf f 2 := by
      have h := @Finset.card_eq_sum_card_fiberwise I (Fin 3) _ (fun i => op1525_pair_code (f i)) univ univ (fun _ _ => mem_univ _)
      rw [Fin.sum_univ_three] at h
      exact h
    
  5. op1525_c_wf_mono holds

    Fiberwise mono.

    lines 29–43

    lemma op1525_c_wf_mono {I : Type*} [Fintype I] [DecidableEq I] (f : I → Fin 2 → Bool) :
        ((univ : Finset I).filter (fun i => f i 0 = f i 1)).card = op1525_c_wf f 0 + op1525_c_wf f 2 := by
      have heq : ((univ : Finset I).filter (fun i => f i 0 = f i 1)) =
          ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = 0)) ∪
          ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = 2)) := by
        ext i; simp [op1525_pair_code_mono]
      have hdisj : Disjoint ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = 0))
          ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = 2)) := by
        rw [disjoint_filter]
        intro x _ h0 h2
        have : (0 : Fin 3) = 2 := h0.symm.trans h2
        revert this; decide
      rw [heq, card_union_of_disjoint hdisj]
      rfl
    
  6. op1525_c_wf_true holds

    Fiberwise true.

    lines 44–70

    lemma op1525_c_wf_true {I : Type*} [Fintype I] [DecidableEq I] (f : I → Fin 2 → Bool) :
        ((univ : Finset (I × Fin 2)).filter (fun x => f x.1 x.2 = true)).card =
        op1525_c_wf f 1 + 2 * op1525_c_wf f 2 := by
      have h1 : ((univ : Finset (I × Fin 2)).filter (fun x => f x.1 x.2 = true)).card =
          ∑ x : I × Fin 2, if f x.1 x.2 = true then 1 else 0 :=
        (sum_boole (fun (x : I × Fin 2) => f x.1 x.2 = true) univ).symm
      rw [h1, ← Finset.univ_product_univ, sum_product]
      simp_rw [Fin.sum_univ_two, ← op1525_pair_code_val (f _)]
      have hfiber := @Finset.sum_fiberwise_of_maps_to I (Fin 3) ℕ _ univ univ _
        (fun i => op1525_pair_code (f i)) (fun _ _ => mem_univ _) (fun i => (op1525_pair_code (f i)).val)
      rw [← hfiber]
      rw [Fin.sum_univ_three]
      dsimp [op1525_c_wf]
      have hz : ∀ j : Fin 3, (∑ i ∈ univ with op1525_pair_code (f i) = j, (op1525_pair_code (f i)).val) =
          j.val * ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = j)).card := by
        intro j
        have : (∑ i ∈ univ with op1525_pair_code (f i) = j, (op1525_pair_code (f i)).val) =
            ∑ i ∈ univ with op1525_pair_code (f i) = j, j.val := by
          apply sum_congr rfl
          intro x hx
          rw [mem_filter] at hx
          rw [hx.2]
        rw [this, sum_const, nsmul_eq_mul, mul_comm]
        rfl
      rw [hz 0, hz 1, hz 2]
      omega
    
  7. main theorem holds

    Classification.

    lines 71–108

    theorem op1525_pair_coloring_profile_classification
        {I : Type*} [DecidableEq I] [Fintype I] (f g : I → Fin 2 → Bool)
        (hmono : ((Finset.univ : Finset I).filter (fun i => f i 0 = f i 1)).card =
          ((Finset.univ : Finset I).filter (fun i => g i 0 = g i 1)).card)
        (htrue : ((Finset.univ : Finset (I × Fin 2)).filter (fun x => f x.1 x.2 = true)).card =
          ((Finset.univ : Finset (I × Fin 2)).filter (fun x => g x.1 x.2 = true)).card) :
        ∃ σ : Equiv.Perm I, ∃ τ : I → Bool, ∀ i : I, ∀ j : Fin 2,
          f (σ i) (j + if τ i then 1 else 0) = g i j := by
      have h_tot_f := op1525_c_wf_total f
      have h_tot_g := op1525_c_wf_total g
      have h_mono_f := op1525_c_wf_mono f
      have h_mono_g := op1525_c_wf_mono g
      have h_true_f := op1525_c_wf_true f
      have h_true_g := op1525_c_wf_true g
      rw [h_mono_f, h_mono_g] at hmono
      rw [h_true_f, h_true_g] at htrue
      have hc0 : op1525_c_wf g 0 = op1525_c_wf f 0 := by omega
      have hc1 : op1525_c_wf g 1 = op1525_c_wf f 1 := by omega
      have hc2 : op1525_c_wf g 2 = op1525_c_wf f 2 := by omega
      have hcard : ∀ c : Fin 3, Fintype.card {i : I // op1525_pair_code (g i) = c} =
          Fintype.card {i : I // op1525_pair_code (f i) = c} := by
        intro c
        rw [Fintype.subtype_card (univ.filter (fun i => op1525_pair_code (g i) = c)) (fun x => by simp)]
        rw [Fintype.subtype_card (univ.filter (fun i => op1525_pair_code (f i) = c)) (fun x => by simp)]
        fin_cases c <;> assumption
      let e (c : Fin 3) : {i : I // op1525_pair_code (g i) = c} ≃ {i : I // op1525_pair_code (f i) = c} :=
        Classical.choice (Fintype.card_eq.mp (hcard c))
      let σ : Equiv.Perm I := (sigmaFiberEquiv (fun i => op1525_pair_code (g i))).symm.trans
        ((sigmaCongrRight e).trans (sigmaFiberEquiv (fun i => op1525_pair_code (f i))))
      have hσ : ∀ i : I, op1525_pair_code (f (σ i)) = op1525_pair_code (g i) := by
        intro i
        dsimp [σ]
        exact (Classical.choice (Fintype.card_eq.mp (hcard (op1525_pair_code (g i)))) ⟨i, rfl⟩).2
      have hτ : ∀ i : I, ∃ b : Bool, ∀ j : Fin 2, f (σ i) (j + if b then 1 else 0) = g i j := by
        intro i
        exact op1525_pair_code_exists_tau (f (σ i)) (g i) (hσ i)
      choose τ hτ using hτ
      exact ⟨σ, τ, hτ⟩

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 Finset Equivdef op1525_pair_code (h : Fin 2 → Bool) : Fin 3 :=  if h 0 = h 1 then    if h 0 then 2 else 0  else 1lemma op1525_pair_code_val (h : Fin 2 → Bool) :    (op1525_pair_code h).val = (if h 0 then 1 else 0) + (if h 1 then 1 else 0) := by  revert h; decidelemma op1525_pair_code_mono (h : Fin 2 → Bool) :    (h 0 = h 1) ↔ (op1525_pair_code h = 0 ∨ op1525_pair_code h = 2) := by  revert h; decidelemma op1525_pair_code_exists_tau (h h' : Fin 2 → Bool) (hc : op1525_pair_code h = op1525_pair_code h') :    ∃ b : Bool, ∀ j : Fin 2, h (j + if b then 1 else 0) = h' j := by  revert hc; revert h h'; decidedef op1525_c_wf {I : Type*} [Fintype I] [DecidableEq I] (f : I → Fin 2 → Bool) (k : Fin 3) : ℕ :=  ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = k)).cardlemma op1525_c_wf_total {I : Type*} [Fintype I] [DecidableEq I] (f : I → Fin 2 → Bool) :    Fintype.card I = op1525_c_wf f 0 + op1525_c_wf f 1 + op1525_c_wf f 2 := by  have h := @Finset.card_eq_sum_card_fiberwise I (Fin 3) _ (fun i => op1525_pair_code (f i)) univ univ (fun _ _ => mem_univ _)  rw [Fin.sum_univ_three] at h  exact hlemma op1525_c_wf_mono {I : Type*} [Fintype I] [DecidableEq I] (f : I → Fin 2 → Bool) :    ((univ : Finset I).filter (fun i => f i 0 = f i 1)).card = op1525_c_wf f 0 + op1525_c_wf f 2 := by  have heq : ((univ : Finset I).filter (fun i => f i 0 = f i 1)) =      ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = 0)) ∪      ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = 2)) := by    ext i; simp [op1525_pair_code_mono]  have hdisj : Disjoint ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = 0))      ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = 2)) := by    rw [disjoint_filter]    intro x _ h0 h2    have : (0 : Fin 3) = 2 := h0.symm.trans h2    revert this; decide  rw [heq, card_union_of_disjoint hdisj]  rfllemma op1525_c_wf_true {I : Type*} [Fintype I] [DecidableEq I] (f : I → Fin 2 → Bool) :    ((univ : Finset (I × Fin 2)).filter (fun x => f x.1 x.2 = true)).card =    op1525_c_wf f 1 + 2 * op1525_c_wf f 2 := by  have h1 : ((univ : Finset (I × Fin 2)).filter (fun x => f x.1 x.2 = true)).card =      ∑ x : I × Fin 2, if f x.1 x.2 = true then 1 else 0 :=    (sum_boole (fun (x : I × Fin 2) => f x.1 x.2 = true) univ).symm  rw [h1, ← Finset.univ_product_univ, sum_product]  simp_rw [Fin.sum_univ_two, ← op1525_pair_code_val (f _)]  have hfiber := @Finset.sum_fiberwise_of_maps_to I (Fin 3) ℕ _ univ univ _    (fun i => op1525_pair_code (f i)) (fun _ _ => mem_univ _) (fun i => (op1525_pair_code (f i)).val)  rw [← hfiber]  rw [Fin.sum_univ_three]  dsimp [op1525_c_wf]  have hz : ∀ j : Fin 3, (∑ i ∈ univ with op1525_pair_code (f i) = j, (op1525_pair_code (f i)).val) =      j.val * ((univ : Finset I).filter (fun i => op1525_pair_code (f i) = j)).card := by    intro j    have : (∑ i ∈ univ with op1525_pair_code (f i) = j, (op1525_pair_code (f i)).val) =        ∑ i ∈ univ with op1525_pair_code (f i) = j, j.val := by      apply sum_congr rfl      intro x hx      rw [mem_filter] at hx      rw [hx.2]    rw [this, sum_const, nsmul_eq_mul, mul_comm]    rfl  rw [hz 0, hz 1, hz 2]  omegatheorem op1525_pair_coloring_profile_classification    {I : Type*} [DecidableEq I] [Fintype I] (f g : I → Fin 2 → Bool)    (hmono : ((Finset.univ : Finset I).filter (fun i => f i 0 = f i 1)).card =      ((Finset.univ : Finset I).filter (fun i => g i 0 = g i 1)).card)    (htrue : ((Finset.univ : Finset (I × Fin 2)).filter (fun x => f x.1 x.2 = true)).card =      ((Finset.univ : Finset (I × Fin 2)).filter (fun x => g x.1 x.2 = true)).card) :    ∃ σ : Equiv.Perm I, ∃ τ : I → Bool, ∀ i : I, ∀ j : Fin 2,      f (σ i) (j + if τ i then 1 else 0) = g i j := by  have h_tot_f := op1525_c_wf_total f  have h_tot_g := op1525_c_wf_total g  have h_mono_f := op1525_c_wf_mono f  have h_mono_g := op1525_c_wf_mono g  have h_true_f := op1525_c_wf_true f  have h_true_g := op1525_c_wf_true g  rw [h_mono_f, h_mono_g] at hmono  rw [h_true_f, h_true_g] at htrue  have hc0 : op1525_c_wf g 0 = op1525_c_wf f 0 := by omega  have hc1 : op1525_c_wf g 1 = op1525_c_wf f 1 := by omega  have hc2 : op1525_c_wf g 2 = op1525_c_wf f 2 := by omega  have hcard : ∀ c : Fin 3, Fintype.card {i : I // op1525_pair_code (g i) = c} =      Fintype.card {i : I // op1525_pair_code (f i) = c} := by    intro c    rw [Fintype.subtype_card (univ.filter (fun i => op1525_pair_code (g i) = c)) (fun x => by simp)]    rw [Fintype.subtype_card (univ.filter (fun i => op1525_pair_code (f i) = c)) (fun x => by simp)]    fin_cases c <;> assumption  let e (c : Fin 3) : {i : I // op1525_pair_code (g i) = c} ≃ {i : I // op1525_pair_code (f i) = c} :=    Classical.choice (Fintype.card_eq.mp (hcard c))  let σ : Equiv.Perm I := (sigmaFiberEquiv (fun i => op1525_pair_code (g i))).symm.trans    ((sigmaCongrRight e).trans (sigmaFiberEquiv (fun i => op1525_pair_code (f i))))  have hσ : ∀ i : I, op1525_pair_code (f (σ i)) = op1525_pair_code (g i) := by    intro i    dsimp [σ]    exact (Classical.choice (Fintype.card_eq.mp (hcard (op1525_pair_code (g i)))) ⟨i, rfl⟩).2  have hτ : ∀ i : I, ∃ b : Bool, ∀ j : Fin 2, f (σ i) (j + if b then 1 else 0) = g i j := by    intro i    exact op1525_pair_code_exists_tau (f (σ i)) (g i) (hσ i)  choose τ hτ using hτ  exact ⟨σ, τ, hτ⟩
See it in the graphDiscuss this resultChallenge it