AFTD Auto-Formalizing Theoretical Domains

wild_complete_thirteen_partition_template

theoremverified

For every partition p of thirteen vertices into four labeled blocks of size at least three, there are vertex and block-label permutations sigma,beta such that beta(p(sigma v)) is the canonical block owner of {0,1,2},{3,4,5},{6,7,8},{9,10,11,12}.

Statement

theorem wild_complete_thirteen_partition_template (p : Fin 13 → Fin 4)
    (hmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin 13)).filter (fun v => p v = t)).card) :
    ∃ (σ : Equiv.Perm (Fin 13)) (β : Equiv.Perm (Fin 4)),
      ∀ v, β (p (σ v)) = wsc_repair_owner v
Source
Certificate-soundness and finite averaging helpers for the OP-306 campaign on arXiv:2610.22142, Sections 3.3.1 and 3.3.2. The thirteen-vertex equivalence is a reduction, not a proof of the conjectured equality; the moment criterion supplies no unproved universal numerical hypothesis.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 2

The proof, explained

Any partition of 13 vertices into 4 blocks of size at least 3 must have block sizes (3, 3, 3, 4) by cardinality constraints. Transposing the unique size-4 block label t₀ with label 3 via a permutation β aligns the block sizes of the relabeled partition β ∘ p with those of the canonical template wsc_repair_owner. Because the fiber cardinalities match for every block label, a domain permutation σ exists that maps the fibers of β ∘ p directly to the canonical blocks, so that β(p(σ(v))) = wsc_repair_owner(v) for all vertices.

  1. The partition p has a unique block t₀ of size 4, and swapping t₀ with 3 defines a relabeled partition p' = β ∘ p.

    Since the four block sizes sum to 13 and each is at least 3, wild_complete_thirteen_partition_card_profile ensures that exactly one block label t₀ ∈ Fin 4 has size 4, while the remaining three blocks have size 3. We let β be the transposition swapping t₀ with 3, and define the relabeled partition p' = β ∘ p.

    lines 9–12

    uses wild_complete_thirteen_partition_card_profile

      classical
      obtain ⟨t0,ht0⟩ := wild_complete_thirteen_partition_card_profile p hmin
      let β : Equiv.Perm (Fin 4) := Equiv.swap t0 3
      let p' : Fin 13 → Fin 4 := fun v => β (p v)
  2. The canonical template wsc_repair_owner has a block of size 4 at label 3 and blocks of size 3 at labels 0, 1, and 2. automation

    The fiber cardinalities of wsc_repair_owner for each of the four labels in Fin 4 are checked by exhaustive evaluation in the Lean kernel via decide +kernel, confirming that label 3 has fiber size 4 and all other labels have fiber size 3.

    lines 13–15

      have hb : ∀ t : Fin 4,
          ((Finset.univ : Finset (Fin 13)).filter (fun v => wsc_repair_owner v = t)).card =
            if t=3 then 4 else 3 := by decide +kernel
  3. For every label t ∈ Fin 4, the fiber cardinality of the relabeled partition p' at t matches that of wsc_repair_owner at t.

    Fix a label t. Since β is a transposition, it is an involution, so p'(v) = t holds if and only if p(v) = β(t). The fiber of p' at t is therefore the fiber of p at β(t), which has size 4 when β(t) = t₀ and size 3 otherwise. Because β maps 3 to t₀ and β is injective, β(t) = t₀ is equivalent to t = 3. Thus the fiber size of p' at t is 4 when t = 3 and 3 otherwise, matching the fiber sizes of wsc_repair_owner.

    lines 16–27

    uses Finset.mem_filter, Finset.mem_univ, true_and, Equiv.apply_eq_iff_eq_symm_apply, Equiv.symm_swap, Equiv.swap_apply_right

      have hcard : ∀ t : Fin 4,
          ((Finset.univ : Finset (Fin 13)).filter (fun v => p' v = t)).card =
          ((Finset.univ : Finset (Fin 13)).filter (fun v => wsc_repair_owner v = t)).card := by
        intro t
        have he : ((Finset.univ : Finset (Fin 13)).filter (fun v => p' v = t)) =
            ((Finset.univ : Finset (Fin 13)).filter (fun v => p v = β t)) := by
          ext v
          simp only [Finset.mem_filter,Finset.mem_univ,true_and,p',Equiv.apply_eq_iff_eq_symm_apply,β,Equiv.symm_swap]
        rw [he,ht0,hb]
        have h3 : β (3 : Fin 4) = t0 := Equiv.swap_apply_right _ _
        have hiff : β t = t0 ↔ t=3 := by rw [← h3,β.injective.eq_iff]
        simp only [hiff]
  4. The matching fiber cardinalities yield a vertex permutation σ such that β(p(σ(v))) = wsc_repair_owner(v) for all vertices v.

    Because p' and wsc_repair_owner have identical fiber cardinalities for every label, finite_partition_permutation_of_fiber_card yields a vertex permutation σ such that p'(σ(v)) = wsc_repair_owner(v) for all v. Since p' = β ∘ p, this gives β(p(σ(v))) = wsc_repair_owner(v), so the pair (σ, β) witnesses the theorem.

    lines 28–29

    uses finite_partition_permutation_of_fiber_card

      obtain ⟨σ,hσ⟩ := finite_partition_permutation_of_fiber_card p' wsc_repair_owner hcard
      exact ⟨σ,β,hσ⟩
Equiv.apply_eq_iff_eq_symm_apply
For an equivalence f, f(x) = y if and only if x = f⁻¹(y).
Equiv.swap_apply_right
The transposition swapping a and b maps b to a.
Equiv.symm_swap
The inverse of the transposition swapping a and b is the transposition itself.
Finset.mem_filter
An element a belongs to Finset.filter p s if and only if a ∈ s and p(a) holds.
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.
finite_partition_permutation_of_fiber_card
Two functions between finite types with identical fiber cardinalities for every target value differ by a permutation of their domain.
true_and
The proposition True ∧ p is equivalent to p.
wild_complete_thirteen_partition_card_profile
Any partition of a 13-element set into 4 blocks each of size at least 3 has exactly one block of size 4 and three blocks of size 3.

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 1600000set_option maxRecDepth 100000theorem wild_complete_thirteen_partition_template (p : Fin 13 → Fin 4)    (hmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin 13)).filter (fun v => p v = t)).card) :    ∃ (σ : Equiv.Perm (Fin 13)) (β : Equiv.Perm (Fin 4)),      ∀ v, β (p (σ v)) = wsc_repair_owner v := by  classical  obtain ⟨t0,ht0⟩ := wild_complete_thirteen_partition_card_profile p hmin  let β : Equiv.Perm (Fin 4) := Equiv.swap t0 3  let p' : Fin 13 → Fin 4 := fun v => β (p v)  have hb : ∀ t : Fin 4,      ((Finset.univ : Finset (Fin 13)).filter (fun v => wsc_repair_owner v = t)).card =        if t=3 then 4 else 3 := by decide +kernel  have hcard : ∀ t : Fin 4,      ((Finset.univ : Finset (Fin 13)).filter (fun v => p' v = t)).card =      ((Finset.univ : Finset (Fin 13)).filter (fun v => wsc_repair_owner v = t)).card := by    intro t    have he : ((Finset.univ : Finset (Fin 13)).filter (fun v => p' v = t)) =        ((Finset.univ : Finset (Fin 13)).filter (fun v => p v = β t)) := by      ext v      simp only [Finset.mem_filter,Finset.mem_univ,true_and,p',Equiv.apply_eq_iff_eq_symm_apply,β,Equiv.symm_swap]    rw [he,ht0,hb]    have h3 : β (3 : Fin 4) = t0 := Equiv.swap_apply_right _ _    have hiff : β t = t0 ↔ t=3 := by rw [← h3,β.injective.eq_iff]    simp only [hiff]  obtain ⟨σ,hσ⟩ := finite_partition_permutation_of_fiber_card p' wsc_repair_owner hcard  exact ⟨σ,β,hσ⟩
See it in the graphDiscuss this resultChallenge it