AFTD Auto-Formalizing Theoretical Domains

wild_optimal_partition_fiber_excess

theoremverified

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

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.

  1. 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.

    lines 9–10

      classical
      let d : Fin (n/3) → ℕ := fun t => ((Finset.univ : Finset (Fin n)).filter fun v => p v=t).card
  2. 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.

    lines 11–14

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ, Finset.card_univ, Fintype.card_fin

      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
  3. 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.

    lines 15–17

    uses Finset.sum_congr, Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul

      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
  4. 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.

    lines 18–19

      have htotal : (∑ t : Fin (n/3), (d t-3)) = n%3 := by omega
      refine ⟨htotal,?_⟩
  5. 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.

    lines 20–25

    uses Finset.single_le_sum, Nat.zero_le, Finset.mem_univ

      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
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

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
See it in the graphDiscuss this resultChallenge it