AFTD Auto-Formalizing Theoretical Domains

wild_closed_cut_defect_partition

theoremverified

For a normalized minimum proper coloring on n vertices, an arbitrary finite family of vertex cuts D_j, and a nonnegative integer r, if n times the sum of d_j! times binomial(floor(n/2),floor(d_j/2)) times (n-d_j)! is strictly less than (r+1)n!, there is a permutation for which at most r cut-color pairs are closed.

Statement

theorem wild_closed_cut_defect_partition {n : ℕ} {J : Type*} [Fintype J]
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n))
    (m : Fin n ≃ Fin n)
    (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i)
    (D : J → Finset (Fin n)) (r : ℕ)
    (hmass : n * (∑ j : J, (D j).card.factorial *
      Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) < (r+1) * n.factorial) :
    ∃ σ : Equiv.Perm (Fin n),
      ((Finset.univ : Finset (J × Fin n)).filter (fun ji =>
        w279_closed c ji.2 ((D ji.1).image σ))).card ≤ r
Source
Order-independent first-moment helper for the constant-defect structural route in OP-306. Generalizes the accepted n=13 one-defect averaging lemma without asserting that the numerical hypothesis holds at all orders.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The theorem is established by contradiction using a double-counting (probabilistic method) argument. Assuming no suitable permutation exists, every permutation of vertices creates at least r + 1 closed cut-color pairs, forcing the total sum over all n! permutations to be at least (r + 1) n!. Swapping the summation order and bounding each cut-color event via w3_closed_event_card yields an upper bound of n ∑_j |D_j|! choose(n/2, |D_j|/2) (n - |D_j|)!. Under the mass hypothesis hmass, this upper bound is strictly less than (r + 1) n!, an impossible strict self-inequality.

  1. Assume for contradiction that every permutation σ has strictly more than r closed cut-color pairs, and let Bad(σ) denote this set of closed pairs.

    We proceed by contradiction using by_contra!, assuming that for every permutation σ ∈ S_n, the number of pairs (j, i) ∈ J × Fin n where the cut σ(D_j) is closed under color i is at least r + 1. The set Bad(σ) is defined to collect these closed pairs.

    lines 14–17

      classical
      by_contra! h
      let Bad (σ : Equiv.Perm (Fin n)) : Finset (J × Fin n) :=
        Finset.univ.filter (fun ji => w279_closed c ji.2 ((D ji.1).image σ))
  2. The total count of closed pairs summed over all n! permutations is at least (r + 1) n!.

    Since every permutation σ satisfies |Bad(σ)| ≥ r + 1, summing over all σ ∈ S_n gives a sum of at least |S_n| · (r + 1) by Finset.card_nsmul_le_sum. We evaluate |S_n| = n! using Fintype.card_perm, Fintype.card_fin, and Finset.card_univ, and rewrite the natural multiplication using nsmul_eq_mul and mul_comm.

    lines 18–22

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

      have hlo : (r+1) * Nat.factorial n ≤ ∑ σ : Equiv.Perm (Fin n), (Bad σ).card := by
        have hi := Finset.card_nsmul_le_sum (s := (Finset.univ : Finset (Equiv.Perm (Fin n))))
          (f := fun σ => (Bad σ).card) (n := r+1) (fun σ _ => by exact h σ)
        rw [nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin] at hi
        exact_mod_cast hi
  3. The sum of |Bad(σ)| over all permutations equals the double sum over cuts j ∈ J and colors i of the number of permutations where (j, i) is closed.

    By converting the set sizes to sums of 1 over indicators with Finset.card_eq_sum_ones and Finset.sum_filter, we interchange the order of summation between σ and the pair (j, i) via Finset.sum_comm. Recombining indicators and splitting the product index (j, i) into separate sums over j ∈ J and i ∈ Fin n using Finset.univ_product_univ and Finset.sum_product yields the transposed double sum.

    lines 23–29

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

      have heq : (∑ σ : Equiv.Perm (Fin n), (Bad σ).card) =
          ∑ j : J, ∑ i : Fin n,
            (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i ((D 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]
  4. The transposed sum is bounded above by ∑_{j ∈ J} ∑_{i ∈ Fin n} |D_j|! * choose(n/2, |D_j|/2) * (n - |D_j|)!.

    For each fixed cut D_j and color i, the lemma w3_closed_event_card bounds the number of permutations σ making σ(D_j) closed under color i by |D_j|! * choose(n/2, |D_j|/2) * (n - |D_j|)!. Summing these termwise bounds across all j and i via Finset.sum_le_sum yields the upper bound.

    lines 30–34

    uses Finset.sum_le_sum, w3_closed_event_card

      have hup : (∑ j : J, ∑ i : Fin n,
            (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i ((D j).image σ))).card) ≤
          ∑ j : J, ∑ _i : Fin n, (D j).card.factorial *
            Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial := by
        exact Finset.sum_le_sum (fun j _ => Finset.sum_le_sum (fun i _ => w3_closed_event_card c m hm (D j) i))
  5. The upper bound simplifies to n * ∑_{j ∈ J} |D_j|! * choose(n/2, |D_j|/2) * (n - |D_j|)!.

    Because the summand does not depend on the color index i, the inner sum over all n elements of Fin n simply multiplies each term by n, using Finset.sum_const, Finset.card_univ, and Fintype.card_fin. Factoring n out of the outer sum with Finset.mul_sum gives the simplified expression.

    lines 35–40

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

      have heval : (∑ j : J, ∑ _i : Fin n, (D j).card.factorial *
            Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) =
          n * (∑ j : J, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) := by
        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul]
        rw [← Finset.mul_sum]
        rfl
  6. The lower and upper bounds contradict the mass hypothesis hmass.

    Chaining the lower bound (r + 1) n! ≤ ∑_σ |Bad(σ)|, the equality transposition, the upper bound, and its simplification shows that (r + 1) n! ≤ n * ∑_{j ∈ J} ..., which directly contradicts the hypothesis hmass asserting that this latter quantity is strictly less than (r + 1) n!. The linear arithmetic tactic omega closes the contradiction.

    line 41

      omega
Finset.card_nsmul_le_sum
If each term in a finite sum over s is at least c, then |s| · c is at most the sum.
nsmul_eq_mul
Scalar multiplication by a natural number n coincides with multiplication by n in the semiring.
mul_comm
Multiplication is commutative: a * b = b * a.
Finset.card_univ
The cardinality of Finset.univ for a finite type is the cardinality of that type.
Fintype.card_perm
The number of permutations of a finite type of size k is k!.
Fintype.card_fin
The finite set Fin n has cardinality n.
Finset.card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over all its elements.
Finset.sum_filter
Summing over a filtered set {x ∈ s | p x} equals summing over s with an indicator if p x then f x else 0.
Finset.sum_comm
The order of two independent finite sums can be swapped: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
Finset.univ_product_univ
The Cartesian product of universal finsets is the universal finset of the product type.
Finset.sum_product
A sum over a Cartesian product set equals the nested iterated sum over the two components.
Finset.sum_le_sum
If f x ≤ g x for all elements x in a finite set, then the sum of f is at most the sum of g.
w3_closed_event_card
For a normalized coloring, a cut D, and a color i, the number of permutations σ making σ(D) closed for color i is at most |D|! * choose(n/2, |D|/2) * (n - |D|)!.
Finset.sum_const
The sum of a constant b over a finite set s equals |s| • b.
Finset.mul_sum
Multiplication distributes over a finite sum: a * ∑ i, f i = ∑ i, a * f i.

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 Classicalset_option maxHeartbeats 1000000theorem wild_closed_cut_defect_partition {n : ℕ} {J : Type*} [Fintype J]    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n))    (m : Fin n ≃ Fin n)    (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i)    (D : J → Finset (Fin n)) (r : ℕ)    (hmass : n * (∑ j : J, (D j).card.factorial *      Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) < (r+1) * n.factorial) :    ∃ σ : Equiv.Perm (Fin n),      ((Finset.univ : Finset (J × Fin n)).filter (fun ji =>        w279_closed c ji.2 ((D ji.1).image σ))).card ≤ r := by  classical  by_contra! h  let Bad (σ : Equiv.Perm (Fin n)) : Finset (J × Fin n) :=    Finset.univ.filter (fun ji => w279_closed c ji.2 ((D ji.1).image σ))  have hlo : (r+1) * Nat.factorial n ≤ ∑ σ : Equiv.Perm (Fin n), (Bad σ).card := by    have hi := Finset.card_nsmul_le_sum (s := (Finset.univ : Finset (Equiv.Perm (Fin n))))      (f := fun σ => (Bad σ).card) (n := r+1) (fun σ _ => by exact h σ)    rw [nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin] at hi    exact_mod_cast hi  have heq : (∑ σ : Equiv.Perm (Fin n), (Bad σ).card) =      ∑ j : J, ∑ i : Fin n,        (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i ((D 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 hup : (∑ j : J, ∑ i : Fin n,        (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i ((D j).image σ))).card) ≤      ∑ j : J, ∑ _i : Fin n, (D j).card.factorial *        Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial := by    exact Finset.sum_le_sum (fun j _ => Finset.sum_le_sum (fun i _ => w3_closed_event_card c m hm (D j) i))  have heval : (∑ j : J, ∑ _i : Fin n, (D j).card.factorial *        Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) =      n * (∑ j : J, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) := by    simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul]    rw [← Finset.mul_sum]    rfl  omega
See it in the graphDiscuss this resultChallenge it