AFTD Auto-Formalizing Theoretical Domains

wild_odd_sharpness_of_adaptive_cubic_moments

theoremverified

For any minimum proper coloring at odd order n>=3 and any finite family of rooted partitions into floor(n/3) blocks of size at least three, count the colors failing to cross some proper nonempty block cut. If these counts satisfy the adaptive cubic strict moment criterion for some positive integer r, the wild number equals the conjectured floor(4*ceil(n/2)/3).

Statement

theorem wild_odd_sharpness_of_adaptive_cubic_moments
    {J : Type*} [Fintype J] {n k : ℕ} (hn : 3 ≤ n) (hodd : n % 2 = 1)
    (hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k)
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
    (p : J → Fin n → Fin (n / 3)) (root : J → Fin (n / 3) → Fin n)
    (hroot : ∀ j t, p j (root j t) = t)
    (hmin : ∀ j t, 3 ≤ (univ.filter fun v => p j v = t).card)
    (r : ℕ) (hr : 1 ≤ r)
    (h : let D : J → Finset (Fin k) := fun j => univ.filter fun i =>
        ∃ S : Finset (Fin (n / 3)), S.Nonempty ∧ S ≠ univ ∧
          ∀ u v (huv : u ≠ v), p j u ∈ S → p j v ∉ S →
            c ⟨s(u,v), wild_kn_mem huv⟩ ≠ i
      let d : J → ℕ := fun j => (D j).card
      (r : ℝ) * (r + 1) * (∑ j, (d j : ℝ)) +
          6 * (∑ j, ((d j).choose 3 : ℝ)) <
        (r : ℝ) * (r + 1) * Fintype.card J +
          (4 * (r : ℝ) - 2) * (∑ j, ((d j).choose 2 : ℝ))) :
    simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4 * ((n + 1) / 2) / 3
Source
OP-306 / IN-338 general-route helpers for the strict prescribed-coloring conjecture in arXiv:2610.22142, Sections3.3.2 and6. Structural analysis of binary factorizations and exact finite averaging in experiments8399,8400,8402,8414. These are conditional certificate or method-diagnostic lemmas, not a new wild-number bound or research advance.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof establishes sharpness of the wild number by finding an optimal block partition in the given family. By the finite avoidance lemma for adaptive cubic moments, the moment inequality guarantees the existence of a partition $p(j)$ with defect count zero, meaning that every color crosses every proper nonempty block cut. Applying the characterization theorem relating the wild number of complete graphs of odd order to optimal partitions, this defect-free partition witnesses that the wild number equals $4 \lfloor (n+1)/2 \rfloor / 3$.

  1. There exists an index $j \in J$ whose associated partition $p(j)$ has no defect colors, so $d(j) = |D(j)| = 0$.

    We define $D(j)$ as the finset of colors that fail to cross some proper nonempty block cut $S \subset \{0, \dots, \lfloor n/3 \rfloor - 1\}$, and set $d(j) = |D(j)|$. The hypothesis $h$ states that the counts $d(j)$ satisfy the adaptive cubic strict moment inequality with parameter $r \ge 1$. Applying the moment avoidance lemma `finite_avoidance_of_adaptive_cubic_moments` directly yields an index $j \in J$ such that $d(j) = 0$.

    lines 23–29

    uses finite_avoidance_of_adaptive_cubic_moments

      classical
      let D : J → Finset (Fin k) := fun j => univ.filter fun i =>
        ∃ S : Finset (Fin (n / 3)), S.Nonempty ∧ S ≠ univ ∧
          ∀ u v (huv : u ≠ v), p j u ∈ S → p j v ∉ S →
            c ⟨s(u,v), wild_kn_mem huv⟩ ≠ i
      let d : J → ℕ := fun j => (D j).card
      obtain ⟨j, hj⟩ := finite_avoidance_of_adaptive_cubic_moments d r hr h
  2. To show that the wild number of $(K_n, c)$ equals $4 \lfloor (n+1)/2 \rfloor / 3$, it suffices to show that for every edge $e$ and every proper nonempty block cut $S$, some edge crossing $S$ has color $c(e)$ under partition $p(j)$.

    By `wild_number_complete_odd_eq_iff_optimal_partition`, the wild number of $K_n$ at odd order under coloring $c$ attains the target value if and only if there exists a valid rooted partition into $\lfloor n/3 \rfloor$ blocks of size at least 3 such that every edge color crosses every proper nonempty block cut. We instantiate this characterization with partition $p(j)$ and root map $\text{root}(j)$. The partition is rooted by hypothesis `hroot j` and has blocks of size at least 3 by hypothesis `hmin j`, leaving only the cut-crossing property to be established.

    lines 30–31

    uses wild_number_complete_odd_eq_iff_optimal_partition

      apply (wild_number_complete_odd_eq_iff_optimal_partition hn hodd hk c).mpr
      refine ⟨p j, root j, hroot j, hmin j, ?_⟩
  3. For every edge $e$ and every proper nonempty block subset $S$, there exists an edge crossing $S$ with color $c(e)$.

    We argue by contradiction: fix an edge $e$ and a proper nonempty block subset $S$, and suppose that no edge crossing $S$ has color $c(e)$. This means that for any distinct vertices $u$ and $v$ with $p(j)(u) \in S$ and $p(j)(v) \notin S$, the edge color $c(\{u, v\})$ is different from $c(e)$ (using `wild_kn_mem`). By the definition of $D(j)$, the set $S$ witnesses that $c(e) \in D(j)$ (using `mem_filter.mpr` and `mem_univ`). Consequently, $D(j)$ is nonempty, so its cardinality is strictly positive by `card_pos.mpr`. However, $d(j) = |D(j)| = 0$ from the choice of $j$, which contradicts positivity by `Nat.ne_of_gt`.

    lines 32–40

    uses wild_kn_mem, mem_univ, mem_filter.mpr, card_pos.mpr, Nat.ne_of_gt

      intro e S hS hS'
      by_contra hnot
      have hno : ∀ u v (huv : u ≠ v), p j u ∈ S → p j v ∉ S →
          c ⟨s(u,v), wild_kn_mem huv⟩ ≠ c e := by
        intro u v huv hu hv hc
        exact hnot ⟨u, v, huv, hu, hv, hc⟩
      have hi : c e ∈ D j := mem_filter.mpr ⟨mem_univ _, S, hS, hS', hno⟩
      have hpos : 0 < (D j).card := card_pos.mpr ⟨c e, hi⟩
      exact (Nat.ne_of_gt hpos) hj
finite_avoidance_of_adaptive_cubic_moments
If a family of non-negative integer counts $d(j)$ indexed by a finite set $J$ satisfies the adaptive cubic strict moment inequality for some integer $r \ge 1$, then there exists an index $j \in J$ with $d(j) = 0$.
wild_number_complete_odd_eq_iff_optimal_partition
For an odd integer $n \ge 3$ and a proper edge coloring $c$ of the complete graph $K_n$ using the minimum number of colors $k$, the wild number equals $4 \lfloor (n+1)/2 \rfloor / 3$ if and only if there exists a rooted partition of the vertices into $\lfloor n/3 \rfloor$ blocks of size at least 3 such that every edge color appears on at least one edge crossing every proper nonempty subset of blocks.
wild_kn_mem
In the complete graph on $n$ vertices, any pair of distinct vertices forms an edge.
mem_univ
Every element of a finite type belongs to its universal finset.
mem_filter.mpr
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
card_pos.mpr
A finset has strictly positive cardinality if and only if it is nonempty.
Nat.ne_of_gt
If a natural number is strictly greater than another, then the two numbers are not equal.

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 Finsetopen scoped BigOperators Classicalset_option maxHeartbeats 2500000theorem wild_odd_sharpness_of_adaptive_cubic_moments    {J : Type*} [Fintype J] {n k : ℕ} (hn : 3 ≤ n) (hodd : n % 2 = 1)    (hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k)    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))    (p : J → Fin n → Fin (n / 3)) (root : J → Fin (n / 3) → Fin n)    (hroot : ∀ j t, p j (root j t) = t)    (hmin : ∀ j t, 3 ≤ (univ.filter fun v => p j v = t).card)    (r : ℕ) (hr : 1 ≤ r)    (h : let D : J → Finset (Fin k) := fun j => univ.filter fun i =>        ∃ S : Finset (Fin (n / 3)), S.Nonempty ∧ S ≠ univ ∧          ∀ u v (huv : u ≠ v), p j u ∈ S → p j v ∉ S →            c ⟨s(u,v), wild_kn_mem huv⟩ ≠ i      let d : J → ℕ := fun j => (D j).card      (r : ℝ) * (r + 1) * (∑ j, (d j : ℝ)) +          6 * (∑ j, ((d j).choose 3 : ℝ)) <        (r : ℝ) * (r + 1) * Fintype.card J +          (4 * (r : ℝ) - 2) * (∑ j, ((d j).choose 2 : ℝ))) :    simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4 * ((n + 1) / 2) / 3 := by  classical  let D : J → Finset (Fin k) := fun j => univ.filter fun i =>    ∃ S : Finset (Fin (n / 3)), S.Nonempty ∧ S ≠ univ ∧      ∀ u v (huv : u ≠ v), p j u ∈ S → p j v ∉ S →        c ⟨s(u,v), wild_kn_mem huv⟩ ≠ i  let d : J → ℕ := fun j => (D j).card  obtain ⟨j, hj⟩ := finite_avoidance_of_adaptive_cubic_moments d r hr h  apply (wild_number_complete_odd_eq_iff_optimal_partition hn hodd hk c).mpr  refine ⟨p j, root j, hroot j, hmin j, ?_⟩  intro e S hS hS'  by_contra hnot  have hno : ∀ u v (huv : u ≠ v), p j u ∈ S → p j v ∉ S →      c ⟨s(u,v), wild_kn_mem huv⟩ ≠ c e := by    intro u v huv hu hv hc    exact hnot ⟨u, v, huv, hu, hv, hc⟩  have hi : c e ∈ D j := mem_filter.mpr ⟨mem_univ _, S, hS, hS', hno⟩  have hpos : 0 < (D j).card := card_pos.mpr ⟨c e, hi⟩  exact (Nat.ne_of_gt hpos) hj
See it in the graphDiscuss this resultChallenge it