wild_optimal_partition_fiber_excess
A 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 every block has size at most five.
Statement
theorem wild_optimal_partition_fiber_excess {n : ℕ} (p : Fin n → Fin (n/3)) (hmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter (fun v => p v = t)).card) : (∑ t : Fin (n/3), (((Finset.univ : Finset (Fin n)).filter (fun v => p v = t)).card-3)) = n%3 ∧ ∀ t, ((Finset.univ : Finset (Fin n)).filter (fun v => p v = t)).card ≤ 5
- 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- Used by 1
- 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…
The proof, explained
The proof counts the total number of vertices n as the sum of the block sizes d(t) = |p⁻¹(t)|. Because each of the ⌊n/3⌋ blocks has size at least 3, the total sum decomposes into the baseline 3 ⌊n/3⌋ plus the sum of excesses ∑ (d(t) - 3), which forces the total excess to equal n mod 3. Since the excess of each individual block is at most the total excess and n mod 3 ≤ 2, each block size d(t) is at most 3 + 2 = 5.
Define d(t) as the cardinality of each fiber block p⁻¹(t).
We work under classical logic and define the shorthand function d(t) = |{v ∈ Fin n | p(v) = t}|, which counts the number of vertices assigned to block t.
classical let d : Fin (n/3) → ℕ := fun t => ((Finset.univ : Finset (Fin n)).filter fun v => p v=t).card
The sum of all block sizes equals n: ∑_t d(t) = n.
Applying Finset.card_eq_sum_card_fiberwise decomposes the universe of n vertices into the fibers of p, showing that the total number of vertices equals the sum of the block sizes ∑_t d(t). Simplifying with Finset.card_univ and Fintype.card_fin evaluates the size of Fin n to n.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univ,Finset.card_univ,Fintype.card_finhave hsum : (∑ t : Fin (n/3), d t) = n := by have hi := Finset.card_eq_sum_card_fiberwise (f := p) (s := (Finset.univ : Finset (Fin n))) (t := (Finset.univ : Finset (Fin (n/3)))) (fun _ _ => Finset.mem_univ _) simpa only [Finset.card_univ,Fintype.card_fin] using hi.symm
The sum of block sizes decomposes into the total excess plus the baseline sum: ∑_t d(t) = ∑_t (d(t) - 3) + 3 ⌊n/3⌋.
Since each block size satisfies d(t) ≥ 3 by the hypothesis hmin, each term d(t) can be rewritten as (d(t) - 3) + 3 using Finset.sum_congr. Distributing the sum with Finset.sum_add_distrib splits it into the sum of excesses ∑_t (d(t) - 3) and the sum of the constant 3. Because there are ⌊n/3⌋ blocks in Fin (n/3), the constant sum equals 3 ⌊n/3⌋ by Finset.sum_const, Finset.card_univ, Fintype.card_fin, and nsmul_eq_mul.
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mulhave he : (∑ t : Fin (n/3), d t) = (∑ t : Fin (n/3), (d t-3)) + 3*(n/3) := by calc _ = ∑ t : Fin (n/3), ((d t-3)+3) := Finset.sum_congr rfl (fun t _ => by have := hmin t; change 3 ≤ d t at this; omega) _ = _ := by rw [Finset.sum_add_distrib]; simp only [Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul]; norm_cast <;> omega
The total excess equals n mod 3, establishing the first conjunct of the theorem.
Equating the two expressions for the sum of block sizes, n = ∑_t (d(t) - 3) + 3 ⌊n/3⌋, linear integer arithmetic (omega) determines that the total excess ∑_t (d(t) - 3) equals n - 3 ⌊n/3⌋ = n mod 3. We refine the goal with this identity to settle the first conjunct.
have htotal : (∑ t : Fin (n/3), (d t-3)) = n%3 := by omega refine ⟨htotal,?_⟩
Every block has size at most 5.
Given any block label t, since all excess terms d(t') - 3 are non-negative (Nat.zero_le), Finset.single_le_sum bounds the single term d(t) - 3 by the total sum of excesses. Rewriting with the total excess gives d(t) - 3 ≤ n mod 3. Since the remainder n mod 3 is at most 2, linear arithmetic (omega) concludes that d(t) ≤ 3 + 2 = 5.
uses
Finset.single_le_sum,Nat.zero_le,Finset.mem_univintro t have hi := Finset.single_le_sum (a := t) (s := (Finset.univ : Finset (Fin (n/3)))) (f := fun t => d t-3) (fun _ _ => Nat.zero_le _) (Finset.mem_univ _) rw [htotal] at hi change d t ≤ 5 omega
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set s is the sum over b ∈ t of the cardinalities of the fibers {a ∈ s | f a = b}, provided f maps s into t.
Finset.card_univ- The cardinality of the universal finset of a finite type is equal to the cardinality of the type itself.
Finset.mem_univ- Every element of a finite type belongs to its universal set Finset.univ.
Fintype.card_fin- The cardinality of the standard finite type Fin n is n.
Finset.single_le_sum- A single non-negative term in a finite sum is bounded above by the total sum.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set equals the sum of their individual sums.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.sum_const- The sum of a constant value over a finite set is equal to the size of the set times that constant.
Nat.zero_le- Every natural number is greater than or equal to zero.
nsmul_eq_mul- Scalar multiplication of an element by a natural number n equals ordinary multiplication by n.
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_optimal_partition_fiber_excess {n : ℕ} (p : Fin n → Fin (n/3)) (hmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter (fun v => p v = t)).card) : (∑ t : Fin (n/3), (((Finset.univ : Finset (Fin n)).filter (fun v => p v = t)).card-3)) = n%3 ∧ ∀ t, ((Finset.univ : Finset (Fin n)).filter (fun v => p v = t)).card ≤ 5 := by classical let d : Fin (n/3) → ℕ := fun t => ((Finset.univ : Finset (Fin n)).filter fun v => p v=t).card have hsum : (∑ t : Fin (n/3), d t) = n := by have hi := Finset.card_eq_sum_card_fiberwise (f := p) (s := (Finset.univ : Finset (Fin n))) (t := (Finset.univ : Finset (Fin (n/3)))) (fun _ _ => Finset.mem_univ _) simpa only [Finset.card_univ,Fintype.card_fin] using hi.symm have he : (∑ t : Fin (n/3), d t) = (∑ t : Fin (n/3), (d t-3)) + 3*(n/3) := by calc _ = ∑ t : Fin (n/3), ((d t-3)+3) := Finset.sum_congr rfl (fun t _ => by have := hmin t; change 3 ≤ d t at this; omega) _ = _ := by rw [Finset.sum_add_distrib]; simp only [Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul]; norm_cast <;> omega have htotal : (∑ t : Fin (n/3), (d t-3)) = n%3 := by omega refine ⟨htotal,?_⟩ intro t have hi := Finset.single_le_sum (a := t) (s := (Finset.univ : Finset (Fin (n/3)))) (f := fun t => d t-3) (fun _ _ => Nat.zero_le _) (Finset.mem_univ _) rw [htotal] at hi change d t ≤ 5 omega