wild_complete_thirteen_partition_card_profile
Every partition of thirteen vertices into four labeled blocks of size at least three has exactly one block of size four and all other blocks of size three.
Statement
theorem wild_complete_thirteen_partition_card_profile (p : Fin 13 → Fin 4) (hmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin 13)).filter (fun v => p v = t)).card) : ∃ t0 : Fin 4, ∀ t : Fin 4, ((Finset.univ : Finset (Fin 13)).filter (fun v => p v = t)).card = if t=t0 then 4 else 3
- 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 1
- wild_optimal_partition_fiber_excessA partition of n vertices into floor(n/3) labeled blocks, each of size at least three, has total excess over three equal to n mod3, and…
- Used by 1
- wild_complete_thirteen_partition_templateFor every partition p of thirteen vertices into four labeled blocks of size at least three, there are vertex and block-label permutations…
The proof, explained
The proof partitions the 13 vertices into four blocks, each of size at least 3, whose sizes sum to 13. Since the sum is 13, integer arithmetic forces at least one block t₀ to have size 4. By a general excess formula, the sum of all block excesses over 3 equals 13 mod 3 = 1, so the single block t₀ accounts for the entire excess, forcing all other blocks to have size exactly 3.
The sum of all four block sizes is 13, and each block size is at least 3.
Let d(t) be the number of vertices mapped to block t. Summing the fiber sizes over all four blocks via Finset.card_eq_sum_card_fiberwise, Finset.mem_univ, Finset.card_univ, and Fintype.card_fin gives ∑ d(t) = 13. The assumption hmin guarantees that 3 ≤ d(t) for every block t.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univ,Finset.card_univ,Fintype.card_finclassical let d : Fin 4 → ℕ := fun t => ((Finset.univ : Finset (Fin 13)).filter fun v => p v=t).card have hsum : (∑ t : Fin 4, d t) = 13 := by have hi := Finset.card_eq_sum_card_fiberwise (f := p) (s := (Finset.univ : Finset (Fin 13))) (t := (Finset.univ : Finset (Fin 4))) (fun _ _ => Finset.mem_univ _) simpa only [Finset.card_univ,Fintype.card_fin] using hi.symm have hmin' : ∀ t, 3 ≤ d t := hmin
At least one block has size exactly 4.
Expanding the sum using Fin.sum_univ_four gives d(0) + d(1) + d(2) + d(3) = 13. Suppose for contradiction that no block has size 4. Since each block has size at least 3, any block of size different from 3 must have size at least 5. If all four blocks had size 3, their sum would be 12, while having any block of size at least 5 would push the sum to at least 5 + 3 + 3 + 3 = 14. Neither equals 13, so linear integer arithmetic (omega) derives a contradiction.
uses
Fin.sum_univ_fourhave h := hsum rw [Fin.sum_univ_four] at h have h0 := hmin' 0 have h1 := hmin' 1 have h2 := hmin' 2 have h3 := hmin' 3 have hex : ∃ t0, d t0=4 := by by_contra! hno have hn0 := hno 0 have hn1 := hno 1 have hn2 := hno 2 have hn3 := hno 3 omega
Fixing a block t₀ of size 4, the total excess ∑ (d(j) - 3) across all blocks is 1.
We choose t₀ such that d(t₀) = 4 as our witness. We need to show that d(t) = 4 when t = t₀ and d(t) = 3 otherwise. By wild_optimal_partition_fiber_excess with n = 13, the total excess over the baseline size 3 across the four blocks is 13 mod 3 = 1.
uses
wild_optimal_partition_fiber_excessobtain ⟨t0,ht0⟩ := hex refine ⟨t0,?_⟩ intro t change d t = (if t=t0 then 4 else 3) have hexcess : (∑ j : Fin 4, (d j-3)) = 1 := (wild_optimal_partition_fiber_excess (n:=13) p hmin).1
If t = t₀, then the block size d(t) is 4.
Splitting into cases on whether t = t₀, when t = t₀ the conditional expression reduces to 4 by if_pos, which matches d(t₀) = 4.
uses
if_posby_cases he : t=t0 · rw [if_pos he,he]; exact ht0
If t ≠ t₀, then the block size d(t) is 3.
When t ≠ t₀, the conditional expression reduces to 3 by if_neg. Since t ≠ t₀, {t, t₀} is a two-element subset of Fin 4, so by Finset.sum_le_sum_of_subset, Finset.subset_univ, and Finset.sum_pair, the partial sum (d(t) - 3) + (d(t₀) - 3) is bounded by the total excess ∑ (d(j) - 3) = 1. Substituting d(t₀) = 4 gives (d(t) - 3) + 1 ≤ 1, so d(t) - 3 ≤ 0. Combined with d(t) ≥ 3, linear arithmetic (omega) forces d(t) = 3.
uses
if_neg,Finset.sum_le_sum_of_subset,Finset.subset_univ,Finset.sum_pair· rw [if_neg he] have hi : (d t-3)+(d t0-3) ≤ ∑ j : Fin 4, (d j-3) := by have hz := Finset.sum_le_sum_of_subset (s := ({t,t0} : Finset (Fin 4))) (t := (Finset.univ : Finset (Fin 4))) (f := fun j => d j-3) (Finset.subset_univ _) simpa only [Finset.sum_pair he] using hz rw [hexcess,ht0] at hi have := hmin' t omega
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set is the sum of the cardinalities of its fibers under a map.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The finite type of integers modulo n has cardinality n.
Fin.sum_univ_four- A sum of a function over the four-element set Fin 4 equals the sum of its values at 0, 1, 2, and 3.
wild_optimal_partition_fiber_excess- For a partition of n vertices into n/3 blocks of size at least 3, the sum of block excesses over 3 equals n mod 3, and every block has size at most 5.
if_pos- If a condition is true, the if-then-else expression evaluates to the then-branch.
if_neg- If a condition is false, the if-then-else expression evaluates to the else-branch.
Finset.sum_le_sum_of_subset- For non-negative terms, a sum over a subset is bounded by the sum over the superset.
Finset.subset_univ- Every finset of elements of a finite type is a subset of the universal finset.
Finset.sum_pair- The sum of a function over a pair of distinct elements equals the sum of the two function values.
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_card_profile (p : Fin 13 → Fin 4) (hmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin 13)).filter (fun v => p v = t)).card) : ∃ t0 : Fin 4, ∀ t : Fin 4, ((Finset.univ : Finset (Fin 13)).filter (fun v => p v = t)).card = if t=t0 then 4 else 3 := by classical let d : Fin 4 → ℕ := fun t => ((Finset.univ : Finset (Fin 13)).filter fun v => p v=t).card have hsum : (∑ t : Fin 4, d t) = 13 := by have hi := Finset.card_eq_sum_card_fiberwise (f := p) (s := (Finset.univ : Finset (Fin 13))) (t := (Finset.univ : Finset (Fin 4))) (fun _ _ => Finset.mem_univ _) simpa only [Finset.card_univ,Fintype.card_fin] using hi.symm have hmin' : ∀ t, 3 ≤ d t := hmin have h := hsum rw [Fin.sum_univ_four] at h have h0 := hmin' 0 have h1 := hmin' 1 have h2 := hmin' 2 have h3 := hmin' 3 have hex : ∃ t0, d t0=4 := by by_contra! hno have hn0 := hno 0 have hn1 := hno 1 have hn2 := hno 2 have hn3 := hno 3 omega obtain ⟨t0,ht0⟩ := hex refine ⟨t0,?_⟩ intro t change d t = (if t=t0 then 4 else 3) have hexcess : (∑ j : Fin 4, (d j-3)) = 1 := (wild_optimal_partition_fiber_excess (n:=13) p hmin).1 by_cases he : t=t0 · rw [if_pos he,he]; exact ht0 · rw [if_neg he] have hi : (d t-3)+(d t0-3) ≤ ∑ j : Fin 4, (d j-3) := by have hz := Finset.sum_le_sum_of_subset (s := ({t,t0} : Finset (Fin 4))) (t := (Finset.univ : Finset (Fin 4))) (f := fun j => d j-3) (Finset.subset_univ _) simpa only [Finset.sum_pair he] using hz rw [hexcess,ht0] at hi have := hmin' t omega