wild_valid_triple_factor_of_multiple_three
Every injectively indexed set of 3q vertices, with q at least three, in a normalized symmetric row-injective array has a valid triple factor. The colors may lie outside this indexed set. It proves local validity packing, with no claim about seals formed by multiple blocks.
Statement
theorem wild_valid_triple_factor_of_multiple_three {C : Type*} (A : C → C → C) (hdiag : ∀ u,A u u=u) (hsym : ∀ u w,A u w=A w u) (hinj : ∀ u,Function.Injective (A u)) (q : ℕ) (hq : 3≤q) (v : Fin (3*q) → C) (hv : Function.Injective v) : ∃ σ : Equiv.Perm (Fin (3*q)),∀ t : Fin q, A (v (σ ⟨3*t.val+0,by omega⟩)) (v (σ ⟨3*t.val+1,by omega⟩))≠v (σ ⟨3*t.val+2,by omega⟩) ∧ A (v (σ ⟨3*t.val+0,by omega⟩)) (v (σ ⟨3*t.val+2,by omega⟩))≠v (σ ⟨3*t.val+1,by omega⟩) ∧ A (v (σ ⟨3*t.val+1,by omega⟩)) (v (σ ⟨3*t.val+2,by omega⟩))≠v (σ ⟨3*t.val+0,by omega⟩)
- Source
- IN-342 supporting steps for OP-306, arXiv:2610.22142 Sections3.3.2/6. The target remains prescribed-coloring sharpness; these are local validity and conditioning-family helpers, not a seal-free partition theorem or new wild-number bound. No research advance is claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- wild_valid_triples_nine_factorEvery injective nine-vertex restriction of a normalized symmetric row-injective array can be permuted into three valid triples. The range…
- wild_valid_triples_with_reservoirFor every finite injectively indexed set of 3q+r vertices, with r at least three, a normalized symmetric row-injective array admits a…
The proof, explained
The proof splits the 3q vertices into 3(q-3) vertices and a reservoir of 9 vertices (using q ≥ 3). It applies wild_valid_triples_with_reservoir to partition the first 3(q-3) vertices into q-3 valid triples, and wild_valid_triples_nine_factor to partition the remaining 9 vertices into 3 valid triples. Lifting the 9-element permutation to fix the first 3(q-3) vertices and composing it with the reservoir permutation produces a valid triple factor of all q triples.
The indices 3t, 3t+1, and 3t+2 are strictly less than 3q for any t < q. automation
In the statement of the theorem, linear arithmetic verifies that for each triple index t < q, the element indices 3t+0, 3t+1, and 3t+2 are strictly less than 3q, making them valid elements of Fin (3q).
A (v (σ ⟨3*t.val+0,by omega⟩)) (v (σ ⟨3*t.val+1,by omega⟩))≠v (σ ⟨3*t.val+2,by omega⟩) ∧ A (v (σ ⟨3*t.val+0,by omega⟩)) (v (σ ⟨3*t.val+2,by omega⟩))≠v (σ ⟨3*t.val+1,by omega⟩) ∧ A (v (σ ⟨3*t.val+1,by omega⟩)) (v (σ ⟨3*t.val+2,by omega⟩))≠v (σ ⟨3*t.val+0,by omega⟩) := by
Enable classical reasoning and partition the 3q indices into 3(q-3) elements and a reservoir of 9 elements.
Since q ≥ 3, we can decompose 3q as 3(q-3) + 9. We apply the reservoir theorem wild_valid_triples_with_reservoir to extract q-3 valid triples from the first part, leaving a reservoir of 9 vertices, and transport the resulting permutation back to Fin (3q) via the index equivalence e.
uses
finCongr,wild_valid_triples_with_reservoirclassical have hlen : 3*(q-3)+9=3*q := by omega let e : Fin (3*(q-3)+9) ≃ Fin (3*q) := finCongr hlen obtain ⟨σ0,h0⟩ := wild_valid_triples_with_reservoir A hdiag hsym hinj (q-3) 9 (by omega) (v ∘ e) (hv.comp e.injective) let σ1 : Equiv.Perm (Fin (3*q)) := (e.symm.trans σ0).trans e have hσ1 (i : Fin (3*(q-3)+9)) : σ1 (e i)=e (σ0 i) := by simp [σ1]
The first q-3 triples under σ1 are valid.
By construction, rewriting the indices through the equivalence e and the permutation conjugation shows each triple t < q-3 satisfies the validity condition given by the reservoir lemma.
have hfirst (t : Fin (q-3)) : in342_mult_valid A (v (σ1 ⟨3*t.val,by omega⟩)) (v (σ1 ⟨3*t.val+1,by omega⟩)) (v (σ1 ⟨3*t.val+2,by omega⟩)) := by have hh := h0 t have hidx (j : Fin 3) : (⟨3*t.val+j.val,by omega⟩ : Fin (3*q))=e ⟨3*t.val+j.val,by omega⟩ := rfl change in342_mult_valid A (v (σ1 ⟨3*t.val+(0 : Fin 3).val,by omega⟩)) (v (σ1 ⟨3*t.val+(1 : Fin 3).val,by omega⟩)) (v (σ1 ⟨3*t.val+(2 : Fin 3).val,by omega⟩)) rw [hidx 0,hidx 1,hidx 2,hσ1,hσ1,hσ1] exact hh
Define an embedding of 9 elements into the reservoir positions and obtain a 3-triple factor on them.
We embed Fin 9 into the last 9 indices starting at 3(q-3). By wild_valid_triples_nine_factor, these 9 vertices can be partitioned into 3 valid triples under a permutation τ.
uses
Fin.ext,congrArg,wild_valid_triples_nine_factorlet E : Fin 9 ↪ Fin (3*q) := ⟨fun i => ⟨3*(q-3)+i.val,by omega⟩,by intro i j h apply Fin.ext have hi := congrArg Fin.val h dsimp at hi omega⟩ let w : Fin 9 → C := v ∘ σ1 ∘ E have hw : Function.Injective w := hv.comp (σ1.injective.comp E.injective) obtain ⟨τ,hτ⟩ := wild_valid_triples_nine_factor A hdiag hsym hinj w hw
Extend the permutation τ to the full index set Fin (3q) such that it acts as τ on the reservoir and fixes all earlier indices.
We lift τ to Fin (3q) via the embedding E. By construction, it permutes the reservoir indices according to τ and fixes all indices strictly less than 3(q-3) because they lie outside the range of E.
uses
Equiv.Perm.viaFintypeEmbedding_apply_image,Equiv.Perm.viaFintypeEmbedding_apply_notMem_range,congrArglet lift : Equiv.Perm (Fin (3*q)) := τ.viaFintypeEmbedding E have himage (i : Fin 9) : lift (E i)=E (τ i) := Equiv.Perm.viaFintypeEmbedding_apply_image τ E i have hfix (t : Fin (q-3)) (j : Fin 3) : lift ⟨3*t.val+j.val,by omega⟩=⟨3*t.val+j.val,by omega⟩ := by apply Equiv.Perm.viaFintypeEmbedding_apply_notMem_range τ E rintro ⟨i,hi⟩ have hh := congrArg Fin.val hi change 3*(q-3)+i.val=3*t.val+j.val at hh have ht' := t.isLt have hj' := j.isLt omega
The composite permutation lift.trans σ1 yields a valid triple factor for all q triples.
We check each triple t < q. If t < q-3, the indices are fixed by lift, so validity follows from the first q-3 triples. If t ≥ q-3, the indices belong to the reservoir, where lift applies τ, and validity follows from the 9-element factor.
uses
Fin.ext,congrArg,Function.comp_def,Nat.add_zerorefine ⟨lift.trans σ1,?_⟩ intro t change in342_mult_valid A (v (σ1 (lift ⟨3*t.val,by omega⟩))) (v (σ1 (lift ⟨3*t.val+1,by omega⟩))) (v (σ1 (lift ⟨3*t.val+2,by omega⟩))) by_cases ht : t.val<q-3 · let s : Fin (q-3) := ⟨t.val,ht⟩ have h0 := hfix s 0 have h1 := hfix s 1 have h2 := hfix s 2 change lift ⟨3*t.val,by omega⟩=⟨3*t.val,by omega⟩ at h0 change lift ⟨3*t.val+1,by omega⟩=⟨3*t.val+1,by omega⟩ at h1 change lift ⟨3*t.val+2,by omega⟩=⟨3*t.val+2,by omega⟩ at h2 simpa only [h0,h1,h2] using hfirst s · let s : Fin 3 := ⟨t.val-(q-3),by omega⟩ have hslot (j : Fin 3) : (⟨3*t.val+j.val,by omega⟩ : Fin (3*q))=E ⟨3*s.val+j.val,by omega⟩ := by apply Fin.ext change 3*t.val+j.val=3*(q-3)+(3*(t.val-(q-3))+j.val) omega have h0 := (congrArg lift (hslot 0)).trans (himage ⟨3*s.val+0,by omega⟩) have h1 := (congrArg lift (hslot 1)).trans (himage ⟨3*s.val+1,by omega⟩) have h2 := (congrArg lift (hslot 2)).trans (himage ⟨3*s.val+2,by omega⟩) change lift ⟨3*t.val,by omega⟩=E (τ ⟨3*s.val,by omega⟩) at h0 change lift ⟨3*t.val+1,by omega⟩=E (τ ⟨3*s.val+1,by omega⟩) at h1 change lift ⟨3*t.val+2,by omega⟩=E (τ ⟨3*s.val+2,by omega⟩) at h2 simpa only [h0,h1,h2,w,Function.comp_def,in342_mult_valid,Nat.add_zero] using hτ s
finCongr- Index isomorphism Fin n ≃ Fin m induced by an equality n = m.
wild_valid_triples_with_reservoir- Guarantees the existence of q valid triples from 3q + r vertices, leaving a reservoir of r ≥ 3 vertices.
Fin.ext- Two Fin elements are equal if and only if their underlying natural values are equal.
congrArg- Function application preserves equality: if x = y then f x = f y.
wild_valid_triples_nine_factor- Partitions any 9 injectively indexed vertices into 3 valid triples.
Equiv.Perm.viaFintypeEmbedding_apply_image- The embedding lift of a permutation maps embedded elements f(a) to f(e(a)).
Equiv.Perm.viaFintypeEmbedding_apply_notMem_range- The embedding lift of a permutation fixes any element not in the image of the embedding.
Function.comp_def- Definition of function composition: (f ∘ g)(x) = f(g(x)).
Nat.add_zero- Adding zero to a natural number leaves it unchanged: n + 0 = 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.
set_option maxHeartbeats 4000000private def in342_mult_valid {C : Type*} (A : C → C → C) (x y z : C) : Prop := A x y≠z ∧ A x z≠y ∧ A y z≠xtheorem wild_valid_triple_factor_of_multiple_three {C : Type*} (A : C → C → C) (hdiag : ∀ u,A u u=u) (hsym : ∀ u w,A u w=A w u) (hinj : ∀ u,Function.Injective (A u)) (q : ℕ) (hq : 3≤q) (v : Fin (3*q) → C) (hv : Function.Injective v) : ∃ σ : Equiv.Perm (Fin (3*q)),∀ t : Fin q, A (v (σ ⟨3*t.val+0,by omega⟩)) (v (σ ⟨3*t.val+1,by omega⟩))≠v (σ ⟨3*t.val+2,by omega⟩) ∧ A (v (σ ⟨3*t.val+0,by omega⟩)) (v (σ ⟨3*t.val+2,by omega⟩))≠v (σ ⟨3*t.val+1,by omega⟩) ∧ A (v (σ ⟨3*t.val+1,by omega⟩)) (v (σ ⟨3*t.val+2,by omega⟩))≠v (σ ⟨3*t.val+0,by omega⟩) := by classical have hlen : 3*(q-3)+9=3*q := by omega let e : Fin (3*(q-3)+9) ≃ Fin (3*q) := finCongr hlen obtain ⟨σ0,h0⟩ := wild_valid_triples_with_reservoir A hdiag hsym hinj (q-3) 9 (by omega) (v ∘ e) (hv.comp e.injective) let σ1 : Equiv.Perm (Fin (3*q)) := (e.symm.trans σ0).trans e have hσ1 (i : Fin (3*(q-3)+9)) : σ1 (e i)=e (σ0 i) := by simp [σ1] have hfirst (t : Fin (q-3)) : in342_mult_valid A (v (σ1 ⟨3*t.val,by omega⟩)) (v (σ1 ⟨3*t.val+1,by omega⟩)) (v (σ1 ⟨3*t.val+2,by omega⟩)) := by have hh := h0 t have hidx (j : Fin 3) : (⟨3*t.val+j.val,by omega⟩ : Fin (3*q))=e ⟨3*t.val+j.val,by omega⟩ := rfl change in342_mult_valid A (v (σ1 ⟨3*t.val+(0 : Fin 3).val,by omega⟩)) (v (σ1 ⟨3*t.val+(1 : Fin 3).val,by omega⟩)) (v (σ1 ⟨3*t.val+(2 : Fin 3).val,by omega⟩)) rw [hidx 0,hidx 1,hidx 2,hσ1,hσ1,hσ1] exact hh let E : Fin 9 ↪ Fin (3*q) := ⟨fun i => ⟨3*(q-3)+i.val,by omega⟩,by intro i j h apply Fin.ext have hi := congrArg Fin.val h dsimp at hi omega⟩ let w : Fin 9 → C := v ∘ σ1 ∘ E have hw : Function.Injective w := hv.comp (σ1.injective.comp E.injective) obtain ⟨τ,hτ⟩ := wild_valid_triples_nine_factor A hdiag hsym hinj w hw let lift : Equiv.Perm (Fin (3*q)) := τ.viaFintypeEmbedding E have himage (i : Fin 9) : lift (E i)=E (τ i) := Equiv.Perm.viaFintypeEmbedding_apply_image τ E i have hfix (t : Fin (q-3)) (j : Fin 3) : lift ⟨3*t.val+j.val,by omega⟩=⟨3*t.val+j.val,by omega⟩ := by apply Equiv.Perm.viaFintypeEmbedding_apply_notMem_range τ E rintro ⟨i,hi⟩ have hh := congrArg Fin.val hi change 3*(q-3)+i.val=3*t.val+j.val at hh have ht' := t.isLt have hj' := j.isLt omega refine ⟨lift.trans σ1,?_⟩ intro t change in342_mult_valid A (v (σ1 (lift ⟨3*t.val,by omega⟩))) (v (σ1 (lift ⟨3*t.val+1,by omega⟩))) (v (σ1 (lift ⟨3*t.val+2,by omega⟩))) by_cases ht : t.val<q-3 · let s : Fin (q-3) := ⟨t.val,ht⟩ have h0 := hfix s 0 have h1 := hfix s 1 have h2 := hfix s 2 change lift ⟨3*t.val,by omega⟩=⟨3*t.val,by omega⟩ at h0 change lift ⟨3*t.val+1,by omega⟩=⟨3*t.val+1,by omega⟩ at h1 change lift ⟨3*t.val+2,by omega⟩=⟨3*t.val+2,by omega⟩ at h2 simpa only [h0,h1,h2] using hfirst s · let s : Fin 3 := ⟨t.val-(q-3),by omega⟩ have hslot (j : Fin 3) : (⟨3*t.val+j.val,by omega⟩ : Fin (3*q))=E ⟨3*s.val+j.val,by omega⟩ := by apply Fin.ext change 3*t.val+j.val=3*(q-3)+(3*(t.val-(q-3))+j.val) omega have h0 := (congrArg lift (hslot 0)).trans (himage ⟨3*s.val+0,by omega⟩) have h1 := (congrArg lift (hslot 1)).trans (himage ⟨3*s.val+1,by omega⟩) have h2 := (congrArg lift (hslot 2)).trans (himage ⟨3*s.val+2,by omega⟩) change lift ⟨3*t.val,by omega⟩=E (τ ⟨3*s.val,by omega⟩) at h0 change lift ⟨3*t.val+1,by omega⟩=E (τ ⟨3*s.val+1,by omega⟩) at h1 change lift ⟨3*t.val+2,by omega⟩=E (τ ⟨3*s.val+2,by omega⟩) at h2 simpa only [h0,h1,h2,w,Function.comp_def,in342_mult_valid,Nat.add_zero] using hτ s