wild_complete_thirteen_partition_template
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
- finite_partition_permutation_of_fiber_cardFor two maps p,b from Fin n to Fin q whose corresponding fibers have equal cardinality, there is a permutation sigma of Fin n such that…
- wild_complete_thirteen_partition_card_profileEvery partition of thirteen vertices into four labeled blocks of size at least three has exactly one block of size four and all other…
- wild_complete_thirteen_one_swap_repair_obstructionThere exists a minimum proper 13-coloring of K_13, normalized so that color i misses vertex i, with this property. The fixed partition…
- Used by 2
- wild_number_complete_thirteen_eq_iff_permuted_cutsFor every proper 13-coloring of K_13, its wild number is nine if and only if some permutation of the canonical 3+3+3+4 vertex partition…
- wild_no_closed_union_of_blocksIf every used color crosses every nonempty proper cut of the block labels under p, then no nonempty proper vertex set that is a union of…
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.
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.
uses
wild_complete_thirteen_partition_card_profileclassical 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)
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.
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
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Equiv.apply_eq_iff_eq_symm_apply,Equiv.symm_swap,Equiv.swap_apply_righthave 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]
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.
uses
finite_partition_permutation_of_fiber_cardobtain ⟨σ,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.
- The fiber cardinalities of the canonical template `wsc_repair_owner` (lines 13–15) are verified by exhaustive computation in the Lean kernel via `decide +kernel`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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σ⟩