AFTD Auto-Formalizing Theoretical Domains

wild_complete_thirteen_one_defect_partition

theoremverified

For every normalized minimum proper coloring of K_13, there exists a vertex permutation of the block partition 3+3+3+4 for which at most one pair consisting of one of the seven cuts up to complementation and a color is closed. The hypothesis gives a bijection m between colors and their unique missing vertices; E is exactly the set of closed cut-color pairs after the permutation.

Statement

theorem wild_complete_thirteen_one_defect_partition
    (c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13)) (m : Fin 13 ≃ Fin 13)
    (hm : ∀ (i v : Fin 13), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) :
    ∃ (σ : Equiv.Perm (Fin 13)) (E : Finset (Fin 7 × Fin 13)), E.card ≤ 1 ∧
      ∀ ji : Fin 7 × Fin 13, ji ∈ E ↔
        w279_closed c ji.2 ((wsc_repair_cuts wsc_repair_blocks ji.1).image σ)
Source
First-moment helper for the finite n=13 case of OP-306. The seven cut sizes are 3,3,3,4,6,6,6. The total expected number of closed cut-color pairs is bounded by 17/11<2. This does not itself produce a seal-free partition, and the one-swap repair obstruction shows the missing step is substantive.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof uses the probabilistic method / double counting by contradiction. If every permutation σ had at least two closed cut-color pairs, the total number of incidences over all 13! permutations would be at least 2 * 13!. However, exchanging the summation order and bounding the number of permutations closing any cut-color pair yields an upper bound of 13 * ∑_{j=0}^6 bound(j), which is strictly less than 2 * 13! by direct computation, yielding a contradiction.

  1. The sum of the cut bounds over all 7 cuts, scaled by 13, is strictly less than 2 * 13! automation

    This finite numerical inequality is verified by direct calculation using the decide tactic.

    line 10

      decide
  2. Assume for contradiction that no valid permutation σ exists, define Bad(σ) as the set of closed cut-color pairs for σ, and deduce that |Bad(σ)| ≥ 2 for all σ

    We proceed by contradiction: if the theorem were false, then for every permutation σ and any set E with |E| ≤ 1, E cannot equal the set of closed pairs. In particular, choosing E = Bad(σ) (the actual set of closed pairs for σ), we must have |Bad(σ)| ≥ 2, since otherwise Bad(σ) itself would be a valid witness E of size at most 1.

    lines 18–30

    uses Finset.mem_filter, Finset.mem_univ, true_and

      classical
      by_contra! h
      let Bad (σ : Equiv.Perm (Fin 13)) : Finset (Fin 7 × Fin 13) :=
        Finset.univ.filter (fun ji => w279_closed c ji.2 ((wsc_repair_cuts wsc_repair_blocks ji.1).image σ))
      have h2 : ∀ σ, 2 ≤ (Bad σ).card := by
        intro σ
        have hσ := h σ (Bad σ)
        by_contra! hlt
        obtain ⟨ji, ⟨h1, h2⟩ | ⟨h1, h2⟩⟩ := hσ (by omega)
        · simp only [Bad, Finset.mem_filter, Finset.mem_univ, true_and] at h1
          exact h2 h1
        · simp only [Bad, Finset.mem_filter, Finset.mem_univ, true_and] at h1
          exact h1 h2
  3. The sum of |Bad(σ)| over all permutations σ is at least 2 * 13!

    Since each of the 13! permutations σ has |Bad(σ)| ≥ 2, summing over all σ ∈ S₁₃ gives at least 2 * 13!.

    lines 31–34

    uses Finset.card_nsmul_le_sum, nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin

      have h_sum_lower : 2 * Nat.factorial 13 ≤ ∑ σ : Equiv.Perm (Fin 13), (Bad σ).card := by
        have h_le := Finset.card_nsmul_le_sum (s := (Finset.univ : Finset (Equiv.Perm (Fin 13)))) (f := fun σ => (Bad σ).card) (n := 2) (fun σ _ => h2 σ)
        rw [nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin] at h_le
        exact h_le
  4. Exchanging the order of summation expresses the total badness as the sum over cuts and colors of the number of permutations closing each cut-color pair

    By double counting (rewriting the sizes of Bad(σ) as sums of indicator variables and commuting the summations), the sum of |Bad(σ)| over σ equals the sum over cuts j ∈ Fin 7 and colors i ∈ Fin 13 of the number of permutations σ that make cut j closed for color i.

    lines 35–43

    uses Finset.card_eq_sum_ones, Finset.sum_filter, Finset.sum_comm, Finset.univ_product_univ, Finset.sum_product

      have h_sum_eq :
        (∑ σ : Equiv.Perm (Fin 13), (Bad σ).card) =
        ∑ j : Fin 7, ∑ i : Fin 13,
          (Finset.univ.filter (fun σ : Equiv.Perm (Fin 13) =>
            w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ))).card := by
        simp_rw [Bad, Finset.card_eq_sum_ones, Finset.sum_filter]
        rw [Finset.sum_comm]
        simp_rw [← Finset.sum_filter, ← Finset.card_eq_sum_ones]
        rw [← Finset.univ_product_univ, Finset.sum_product]
  5. The number of permutations closing each cut-color pair is upper bounded by the cut bound

    Applying the lemma w3_closed_event_card to each cut j and color i shows that the number of permutations closing cut j for color i is at most wild_complete_thirteen_one_defect_partition_cut_bound j.

    lines 44–53

    uses Finset.sum_le_sum, w3_closed_event_card

      have h_sum_upper :
        (∑ j : Fin 7, ∑ i : Fin 13,
          (Finset.univ.filter (fun σ : Equiv.Perm (Fin 13) =>
            w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ))).card) ≤
        ∑ j : Fin 7, ∑ i : Fin 13, wild_complete_thirteen_one_defect_partition_cut_bound j := by
        apply Finset.sum_le_sum
        intro j _
        apply Finset.sum_le_sum
        intro i _
        exact w3_closed_event_card c m hm (wsc_repair_cuts wsc_repair_blocks j) i
  6. Summing over all 13 colors simplifies the upper bound to 13 times the sum over the 7 cuts

    Since the cut bound depends only on the cut j and not on the color i, summing over the 13 colors multiplies the bound for cut j by 13, and factoring out 13 yields 13 * ∑_j bound(j).

    lines 54–59

    uses Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, Finset.mul_sum

      have h_sum_eval :
        (∑ j : Fin 7, ∑ _i : Fin 13, wild_complete_thirteen_one_defect_partition_cut_bound j) =
        13 * ∑ j : Fin 7, wild_complete_thirteen_one_defect_partition_cut_bound j := by
        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul]
        rw [← Finset.mul_sum]
        rfl
  7. The lower bound 2 * 13! and upper bound strictly less than 2 * 13! contradict each other automation

    The lower bound gives ∑ |Bad(σ)| ≥ 2 * 13!, while the upper bound gives ∑ |Bad(σ)| ≤ 13 * ∑_j bound(j), which by wild_complete_thirteen_one_defect_partition_sum_bound is strictly less than 2 * 13!, a contradiction.

    lines 60–61

    uses wild_complete_thirteen_one_defect_partition_sum_bound

      have h_lt := wild_complete_thirteen_one_defect_partition_sum_bound
      omega
Finset.mem_filter
characterization of membership in a filtered finset
Finset.mem_univ
every element of a finite type is in the universal finset
true_and
a conjunction of True and p simplifies to p
Finset.card_nsmul_le_sum
multiplying the cardinality of a finite set by a lower bound on its elements bounds the sum from below
nsmul_eq_mul
scalar multiplication of a natural number with an element equals the product
mul_comm
multiplication is commutative
Finset.card_univ
the cardinality of the universal finset is the cardinality of the underlying fintype
Fintype.card_perm
the number of permutations of a finite type of size n is n!
Fintype.card_fin
the cardinality of Fin n is n
Finset.card_eq_sum_ones
the cardinality of a finset is the sum of ones over its elements
Finset.sum_filter
sum of a function over a filtered finset equals the sum of an if-then-else over the original finset
Finset.sum_comm
the order of two finite summations can be exchanged
Finset.univ_product_univ
the Cartesian product of two universal finsets is the universal finset on pairs
Finset.sum_product
a sum over a Cartesian product finset equals an iterated sum over the factor finsets
Finset.sum_le_sum
termwise inequality implies inequality of finite sums
w3_closed_event_card
upper bound on the number of permutations closing a cut for a given color
Finset.sum_const
sum of a constant over a finset equals the cardinality times the constant
Finset.mul_sum
factoring a constant out of a finite sum
wild_complete_thirteen_one_defect_partition_sum_bound
the arithmetic inequality bounding 13 times the sum of the 7 cut bounds strictly below 2 * 13!

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 scoped BigOperators Classicalprivate def wild_complete_thirteen_one_defect_partition_cut_bound (j : Fin 7) : ℕ :=  (wsc_repair_cuts wsc_repair_blocks j).card.factorial *  (13 / 2).choose ((wsc_repair_cuts wsc_repair_blocks j).card / 2) *  (13 - (wsc_repair_cuts wsc_repair_blocks j).card).factorialprivate lemma wild_complete_thirteen_one_defect_partition_sum_bound :    13 * (∑ j : Fin 7, wild_complete_thirteen_one_defect_partition_cut_bound j) < 2 * Nat.factorial 13 := by  decidetheorem wild_complete_thirteen_one_defect_partition    (c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13)) (m : Fin 13 ≃ Fin 13)    (hm : ∀ (i v : Fin 13), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) :    ∃ (σ : Equiv.Perm (Fin 13)) (E : Finset (Fin 7 × Fin 13)), E.card ≤ 1 ∧      ∀ ji : Fin 7 × Fin 13, ji ∈ E ↔        w279_closed c ji.2 ((wsc_repair_cuts wsc_repair_blocks ji.1).image σ) := by  classical  by_contra! h  let Bad (σ : Equiv.Perm (Fin 13)) : Finset (Fin 7 × Fin 13) :=    Finset.univ.filter (fun ji => w279_closed c ji.2 ((wsc_repair_cuts wsc_repair_blocks ji.1).image σ))  have h2 : ∀ σ, 2 ≤ (Bad σ).card := by    intro σ    have hσ := h σ (Bad σ)    by_contra! hlt    obtain ⟨ji, ⟨h1, h2⟩ | ⟨h1, h2⟩⟩ := hσ (by omega)    · simp only [Bad, Finset.mem_filter, Finset.mem_univ, true_and] at h1      exact h2 h1    · simp only [Bad, Finset.mem_filter, Finset.mem_univ, true_and] at h1      exact h1 h2  have h_sum_lower : 2 * Nat.factorial 13 ≤ ∑ σ : Equiv.Perm (Fin 13), (Bad σ).card := by    have h_le := Finset.card_nsmul_le_sum (s := (Finset.univ : Finset (Equiv.Perm (Fin 13)))) (f := fun σ => (Bad σ).card) (n := 2) (fun σ _ => h2 σ)    rw [nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin] at h_le    exact h_le  have h_sum_eq :    (∑ σ : Equiv.Perm (Fin 13), (Bad σ).card) =    ∑ j : Fin 7, ∑ i : Fin 13,      (Finset.univ.filter (fun σ : Equiv.Perm (Fin 13) =>        w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ))).card := by    simp_rw [Bad, Finset.card_eq_sum_ones, Finset.sum_filter]    rw [Finset.sum_comm]    simp_rw [← Finset.sum_filter, ← Finset.card_eq_sum_ones]    rw [← Finset.univ_product_univ, Finset.sum_product]  have h_sum_upper :    (∑ j : Fin 7, ∑ i : Fin 13,      (Finset.univ.filter (fun σ : Equiv.Perm (Fin 13) =>        w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ))).card) ≤    ∑ j : Fin 7, ∑ i : Fin 13, wild_complete_thirteen_one_defect_partition_cut_bound j := by    apply Finset.sum_le_sum    intro j _    apply Finset.sum_le_sum    intro i _    exact w3_closed_event_card c m hm (wsc_repair_cuts wsc_repair_blocks j) i  have h_sum_eval :    (∑ j : Fin 7, ∑ _i : Fin 13, wild_complete_thirteen_one_defect_partition_cut_bound j) =    13 * ∑ j : Fin 7, wild_complete_thirteen_one_defect_partition_cut_bound j := by    simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul]    rw [← Finset.mul_sum]    rfl  have h_lt := wild_complete_thirteen_one_defect_partition_sum_bound  omega
See it in the graphDiscuss this resultChallenge it