AFTD Auto-Formalizing Theoretical Domains

wild_complete_thirteen_partition_card_profile

theoremverified

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
Used by 1

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.

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

    lines 9–15

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

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

    lines 16–28

    uses Fin.sum_univ_four

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

    lines 29–34

    uses wild_optimal_partition_fiber_excess

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

    lines 35–36

    uses if_pos

      by_cases he : t=t0
      · rw [if_pos he,he]; exact ht0
  5. 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.

    lines 37–44

    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

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