wild_rainbow_leaf_greedy_obstruction
There is a symmetric idempotent15-by15 color matrix with injective rows and the prescribed seven color-zero matching pairs. Its two valid leaf cherries on role pairs(0,1) and(2,3) have four distinct nonzero internal colors8,9,10,11. Every additional leaf using two of the remaining matching-pair roles4,5,6 is invalid or repeats a used internal color, so this family is inclusion maximal. Nevertheless the same matrix admits a valid/rainbow family of three leaves with disjoint matching-pair roles.
Statement
theorem wild_rainbow_leaf_greedy_obstruction : ∃ A : Fin 15 → Fin 15 → Fin 15, (∀ u, A u u = u) ∧ (∀ u v, A u v = A v u) ∧ (∀ u, Function.Injective (A u)) ∧ (let a : Fin 7 → Fin 15 := fun i => ⟨2*i.val+1, by omega⟩ let b : Fin 7 → Fin 15 := fun i => ⟨2*i.val+2, by omega⟩ (∀ j, A (a j) (b j) = 0) ∧ A 1 3 = 8 ∧ A 2 3 = 9 ∧ A 5 7 = 10 ∧ A 6 7 = 11 ∧ (∀ i j : Fin 7, 4 ≤ i.val → 4 ≤ j.val → i ≠ j → ∀ side : Bool, let z := if side then b j else a j A (a i) z = b i ∨ A (b i) z = a i ∨ A (a i) z ∈ ({8,9,10,11} : Finset (Fin 15)) ∨ A (b i) z ∈ ({8,9,10,11} : Finset (Fin 15))) ∧ (∃ (α β : Fin 3 → Fin 7) (side : Fin 3 → Bool), Function.Injective (Sum.elim α β : Fin 3 ⊕ Fin 3 → Fin 7) ∧ (∀ t, let z := if side t then b (β t) else a (β t) A (a (α t)) z ≠ b (α t) ∧ A (b (α t)) z ≠ a (α t)) ∧ (∀ t u, t ≠ u → Disjoint ({A (a (α t)) (if side t then b (β t) else a (β t)), A (b (α t)) (if side t then b (β t) else a (β t))} : Finset (Fin 15)) {A (a (α u)) (if side u then b (β u) else a (β u)), A (b (α u)) (if side u then b (β u) else a (β u))})))
- Source
- IN-338 structural/repair helpers for OP-306, the prescribed-coloring conjecture in arXiv:2610.22142 Sections3.3.2 and6. Exact matching-involution balance and the method obstruction computed in experiment8464. These are certificate/method lemmas, not new wild-number bounds or research advances.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is established by explicitly exhibiting a 15-by-15 color matrix `in338_greedy_matrix` and verifying all its properties by kernel evaluation (`decide +kernel`). Direct finite computation confirms idempotency, symmetry, row-injectivity, the seven color-zero matching pairs, and the two initial leaf cherries having four distinct internal colors {8, 9, 10, 11}. Exhaustive enumeration of the remaining three matching-pair roles proves the greedy obstruction, while an explicit choice of three disjoint role pairs witnesses the existence of a rainbow 3-leaf family.
The matching-pair endpoints $a(i) = 2i+1$ and $b(i) = 2i+2$ are well-defined elements of $\text{Fin } 15$. automation
In the theorem statement, constructing $a(i) = \langle 2i+1, \dots\rangle$ and $b(i) = \langle 2i+2, \dots\rangle$ for $i \in \text{Fin } 7$ requires proofs that $2i+1 < 15$ and $2i+2 < 15$. Linear integer arithmetic (`omega`) closes both goals from the hypothesis $i < 7$, since $2i + 2 \le 2 \cdot 6 + 2 = 14 < 15$.
(let a : Fin 7 → Fin 15 := fun i => ⟨2*i.val+1, by omega⟩ let b : Fin 7 → Fin 15 := fun i => ⟨2*i.val+2, by omega⟩
The candidate matrix `in338_greedy_matrix` is idempotent, symmetric, and has injective rows. automation
We witness the existential quantifier with the explicit 15-by-15 table `in338_greedy_matrix`. Lean's kernel decision procedure (`decide +kernel`) verifies by exhaustive finite evaluation over $\text{Fin } 15$ that $A(u, u) = u$, that $A(u, v) = A(v, u)$, and that each row map $A(u, \cdot)$ is injective (and thus a permutation of the 15 colors).
refine ⟨in338_greedy_matrix, ?_, ?_, ?_, ?_⟩ · decide +kernel · decide +kernel · decide +kernel
The seven matching pairs have color zero, the two initial leaves have internal colors 8, 9, 10, and 11, and no additional valid leaf on the remaining role pairs can avoid reusing one of these four colors. automation
We simplify the definitions of the matching pairs $a(j)$ and $b(j)$ and split the conjunction. The kernel decision procedure verifies by direct computation that $A(a(j), b(j)) = 0$ for all $0 \le j \le 6$; checks the entries $A(1, 3) = 8$, $A(2, 3) = 9$, $A(5, 7) = 10$, and $A(6, 7) = 11$; and exhaustively checks that for all distinct remaining role indices $i, j \in \{4, 5, 6\}$ and each stem $z \in \{a(j), b(j)\}$, the resulting leaf cherry is either degenerate ($A(a(i), z) = b(i)$ or $A(b(i), z) = a(i)$) or has an internal color in $\{8, 9, 10, 11\}$.
· dsimp only refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · decide +kernel · decide +kernel · decide +kernel · decide +kernel · decide +kernel · decide +kernel
There exists a valid, rainbow family of three leaves with pairwise disjoint matching-pair roles. automation
We provide explicit role selections $\alpha = [1, 2, 3]$ and $\beta = [6, 4, 5]$ and stem choices $\text{side} = [\text{false}, \text{true}, \text{true}]$, selecting stems $a(6)$, $b(4)$, and $b(5)$ respectively. The kernel decision procedure verifies by finite evaluation that all six role indices are distinct, that all three cherries are valid leaves (neither color collapses to the other partner of the matching pair), and that their pairs of internal colors are mutually disjoint.
· refine ⟨![1,2,3], ![6,4,5], ![false,true,true], ?_, ?_, ?_⟩ · decide +kernel · decide +kernel · decide +kernel
- The proof includes two inline proof obligations in the theorem statement (lines 25–26) that ensure the indices $2i+1$ and $2i+2$ stay within $\text{Fin } 15$. The main body of the proof is executed entirely via computational reflection: all properties are finite predicates over $\text{Fin } 15$ and $\text{Fin } 7$, and `decide +kernel` delegates their verification directly to Lean's kernel evaluator on the explicit matrix data.
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 Finsetset_option maxHeartbeats 7000000set_option maxRecDepth 20000private def in338_greedy_data : Array (Array (Fin 15)) := #[#[0, 10, 4, 5, 2, 1, 8, 3, 14, 6, 11, 7, 9, 12, 13],#[10, 1, 0, 8, 3, 7, 9, 2, 6, 4, 5, 13, 14, 11, 12],#[4, 0, 2, 9, 12, 8, 7, 1, 10, 5, 6, 14, 13, 3, 11],#[5, 8, 9, 3, 0, 13, 10, 12, 11, 2, 7, 4, 6, 14, 1],#[2, 3, 12, 0, 4, 14, 1, 8, 5, 11, 13, 6, 7, 9, 10],#[1, 7, 8, 13, 14, 5, 0, 10, 9, 3, 12, 2, 11, 4, 6],#[8, 9, 7, 10, 1, 0, 6, 11, 13, 14, 2, 12, 4, 5, 3],#[3, 2, 1, 12, 8, 10, 11, 7, 0, 13, 14, 9, 5, 6, 4],#[14, 6, 10, 11, 5, 9, 13, 0, 8, 12, 4, 3, 1, 7, 2],#[6, 4, 5, 2, 11, 3, 14, 13, 12, 9, 0, 1, 10, 8, 7],#[11, 5, 6, 7, 13, 12, 2, 14, 4, 0, 10, 8, 3, 1, 9],#[7, 13, 14, 4, 6, 2, 12, 9, 3, 1, 8, 11, 0, 10, 5],#[9, 14, 13, 6, 7, 11, 4, 5, 1, 10, 3, 0, 12, 2, 8],#[12, 11, 3, 14, 9, 4, 5, 6, 7, 8, 1, 10, 2, 13, 0],#[13, 12, 11, 1, 10, 6, 3, 4, 2, 7, 9, 5, 8, 0, 14]]private def in338_greedy_matrix : Fin 15 → Fin 15 → Fin 15 := fun u v => (in338_greedy_data[u.val]!)[v.val]!theorem wild_rainbow_leaf_greedy_obstruction : ∃ A : Fin 15 → Fin 15 → Fin 15, (∀ u, A u u = u) ∧ (∀ u v, A u v = A v u) ∧ (∀ u, Function.Injective (A u)) ∧ (let a : Fin 7 → Fin 15 := fun i => ⟨2*i.val+1, by omega⟩ let b : Fin 7 → Fin 15 := fun i => ⟨2*i.val+2, by omega⟩ (∀ j, A (a j) (b j) = 0) ∧ A 1 3 = 8 ∧ A 2 3 = 9 ∧ A 5 7 = 10 ∧ A 6 7 = 11 ∧ (∀ i j : Fin 7, 4 ≤ i.val → 4 ≤ j.val → i ≠ j → ∀ side : Bool, let z := if side then b j else a j A (a i) z = b i ∨ A (b i) z = a i ∨ A (a i) z ∈ ({8,9,10,11} : Finset (Fin 15)) ∨ A (b i) z ∈ ({8,9,10,11} : Finset (Fin 15))) ∧ (∃ (α β : Fin 3 → Fin 7) (side : Fin 3 → Bool), Function.Injective (Sum.elim α β : Fin 3 ⊕ Fin 3 → Fin 7) ∧ (∀ t, let z := if side t then b (β t) else a (β t) A (a (α t)) z ≠ b (α t) ∧ A (b (α t)) z ≠ a (α t)) ∧ (∀ t u, t ≠ u → Disjoint ({A (a (α t)) (if side t then b (β t) else a (β t)), A (b (α t)) (if side t then b (β t) else a (β t))} : Finset (Fin 15)) {A (a (α u)) (if side u then b (β u) else a (β u)), A (b (α u)) (if side u then b (β u) else a (β u))}))) := by refine ⟨in338_greedy_matrix, ?_, ?_, ?_, ?_⟩ · decide +kernel · decide +kernel · decide +kernel · dsimp only refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · decide +kernel · decide +kernel · decide +kernel · decide +kernel · decide +kernel · decide +kernel · refine ⟨![1,2,3], ![6,4,5], ![false,true,true], ?_, ?_, ?_⟩ · decide +kernel · decide +kernel · decide +kernel