wild_valid_triples_nine_factor
Every injective nine-vertex restriction of a normalized symmetric row-injective array can be permuted into three valid triples. The range of the array need not be contained in the nine vertices. This is a local packing helper, not a new wild-number case.
Statement
theorem wild_valid_triples_nine_factor {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)) (v : Fin 9 → C) (hv : Function.Injective v) : ∃ σ : Equiv.Perm (Fin (9)),∀ t : Fin (3), 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 3
- wild_valid_triple_exists_in_sixFor any array with injective rows and any six distinct vertices, there are three distinct indices satisfying all three triple-validity…
- wild_valid_triples_nine_repairFor any normalized symmetric row-injective array on an arbitrary vertex/color type, take nine distinct vertices. If their first triple has…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 1
- wild_valid_triple_factor_of_multiple_threeEvery injectively indexed set of 3q vertices, with q at least three, in a normalized symmetric row-injective array has a valid triple…
The proof, explained
Every 9-element restriction of a normalized, symmetric, row-injective array can be permuted into three valid triples. By applying the 6-element lemma `wild_valid_triple_exists_in_six` to the first six vertices, we find a valid triple and place it at indices (6, 7, 8) via a permutation σ₁. Repeating this on the remaining six elements places a second valid triple at indices (3, 4, 5) while fixing indices 6, 7, 8. Finally, if the first triple at (0, 1, 2) is not already valid, a permutation on {0, 1, 2} aligns the failure with the equation A(u₀, u₁) = u₂, and `wild_valid_triples_nine_repair` repairs the configuration into three valid triples.
A three-element vector of pairwise distinct elements defines an injective map on Fin 3.
The map ! [i, j, k] on Fin 3 is tested on all nine pairs (a, b) in Fin 3 × Fin 3. The diagonal cases hold by reflexivity, and each off-diagonal case equates two distinct elements, which contradicts pairwise distinctness via Ne.symm.
uses
Ne.symmprivate theorem in342_wrap_vec_inj {D : Type*} (i j k : D) (hij : i≠j) (hik : i≠k) (hjk : j≠k) : Function.Injective (![i,j,k] : Fin 3 → D) := by intro a b h fin_cases a <;> fin_cases b · rfl · change i=j at h exact (hij h).elim · change i=k at h exact (hik h).elim · change j=i at h exact ((Ne.symm hij) h).elim · rfl · change j=k at h exact (hjk h).elim · change k=i at h exact ((Ne.symm hik) h).elim · change k=j at h exact ((Ne.symm hjk) h).elim · rfl
Any six elements embedded in Fin N contain a valid triple, which can be placed at three designated target slots by a permutation of Fin N.
By `wild_valid_triple_exists_in_six`, any 6 elements contain a valid triple. Mapping Fin 3 to these three elements yields an injective map by `in342_wrap_vec_inj`, and `Equiv.Perm.exists_extending_pair` extends this alignment to a global permutation σ of Fin N that places the valid triple at the chosen slots.
uses
wild_valid_triple_exists_in_six,in342_wrap_vec_inj,Equiv.Perm.exists_extending_pairprivate theorem in342_wrap_place {C : Type*} (A : C → C → C) (hinj : ∀ x,Function.Injective (A x)) {N : ℕ} (v : Fin N → C) (hv : Function.Injective v) (ι : Fin 6 → Fin N) (hι : Function.Injective ι) (f : Fin 3 → Fin N) (hf : Function.Injective f) : ∃ σ : Equiv.Perm (Fin N), in342_wrap_valid A (v (σ (f 0))) (v (σ (f 1))) (v (σ (f 2))) := by obtain ⟨i,j,k,hij,hik,hjk,hgood⟩ := wild_valid_triple_exists_in_six A hinj (v ∘ ι) (hv.comp hι) let g : Fin 3 → Fin N := ι ∘ (![i,j,k] : Fin 3 → Fin 6) have hg : Function.Injective g := hι.comp (in342_wrap_vec_inj i j k hij hik hjk) obtain ⟨σ,hσ⟩ := Equiv.Perm.exists_extending_pair f g hf hg refine ⟨σ,?_⟩ rw [hσ 0,hσ 1,hσ 2] exact hgood
The goal is reformulated as finding a permutation of nine vertices that partitions them into three valid triples. automation
The nine positions are partitioned into three blocks of three slots via the indexing function (t, j) ↦ 3t + j, where the bound 3t + j < 9 is discharged by `omega`. We enable classical logic and rephrase the goal as `in342_wrap_goal A v`, which asserts the existence of a permutation σ making the triples at (0, 1, 2), (3, 4, 5), and (6, 7, 8) valid.
private def in342_wrap_slot (t j : Fin 3) : Fin 9 := ⟨3*t.val+j.val,by omega⟩ private def in342_wrap_goal {C : Type*} (A : C → C → C) (v : Fin 9 → C) : Prop := ∃ σ : Equiv.Perm (Fin 9),∀ t : Fin 3, in342_wrap_valid A (v (σ (in342_wrap_slot t 0))) (v (σ (in342_wrap_slot t 1))) (v (σ (in342_wrap_slot t 2))) theorem wild_valid_triples_nine_factor {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)) (v : Fin 9 → C) (hv : Function.Injective v) : ∃ σ : Equiv.Perm (Fin (9)),∀ t : Fin (3), 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 change in342_wrap_goal A v
There is a permutation σ₁ of Fin 9 placing a valid triple at positions 6, 7, and 8 from the first six vertices. automation
We embed the first six vertices into Fin 9 via `Fin.castAddEmb 3`. Applying `in342_wrap_place` to these six vertices with target indices (6, 7, 8) produces a permutation σ₁ such that the triple at positions 6, 7, 8 is valid. Injectivity of ![6, 7, 8] is checked by kernel evaluation with `decide`.
uses
in342_wrap_placelet E : Fin 6 ↪ Fin 9 := Fin.castAddEmb 3 obtain ⟨σ1,h1⟩ := in342_wrap_place A hinj v hv E E.injective (![6,7,8] : Fin 3 → Fin 9) (by decide +kernel) change in342_wrap_valid A (v (σ1 6)) (v (σ1 7)) (v (σ1 8)) at h1
Restricting to the first six vertices under σ₁, there is a permutation σ₂ of Fin 6 placing a second valid triple at positions 3, 4, and 5. automation
The restriction w of v ∘ σ₁ to the first six elements remains injective. Applying `in342_wrap_place` to w with target indices (3, 4, 5) yields a permutation σ₂ of Fin 6 placing a valid triple at positions 3, 4, 5. Injectivity of ![3, 4, 5] is verified by `decide`.
uses
in342_wrap_place,Function.injective_idlet w : Fin 6 → C := fun i => v (σ1 (E i)) have hw : Function.Injective w := hv.comp (σ1.injective.comp E.injective) obtain ⟨σ2,h2⟩ := in342_wrap_place A hinj w hw (id : Fin 6 → Fin 6) Function.injective_id (![3,4,5] : Fin 3 → Fin 6) (by decide +kernel) change in342_wrap_valid A (w (σ2 3)) (w (σ2 4)) (w (σ2 5)) at h2
The permutation σ₂ lifts to a permutation of Fin 9 that acts as σ₂ on the first six elements and fixes positions 6, 7, and 8. automation
Extending σ₂ along the embedding of Fin 6 into Fin 9 via `viaFintypeEmbedding` acts as σ₂ on the first six elements by `Equiv.Perm.viaFintypeEmbedding_apply_image`. Each of 6, 7, 8 lies outside the image of the embedding because i < 6 contradicts i = 6, 7, 8 (checked by `omega`); hence by `Equiv.Perm.viaFintypeEmbedding_apply_notMem_range`, the lifted permutation fixes 6, 7, and 8.
uses
Equiv.Perm.viaFintypeEmbedding_apply_image,Equiv.Perm.viaFintypeEmbedding_apply_notMem_range,congrArglet lift : Equiv.Perm (Fin 9) := σ2.viaFintypeEmbedding E have hcast (i : Fin 6) : lift (E i)=E (σ2 i) := Equiv.Perm.viaFintypeEmbedding_apply_image σ2 E i have hfix6 : lift 6=6 := by apply Equiv.Perm.viaFintypeEmbedding_apply_notMem_range σ2 E rintro ⟨i,hi⟩ have hh := congrArg Fin.val hi change i.val=6 at hh omega have hfix7 : lift 7=7 := by apply Equiv.Perm.viaFintypeEmbedding_apply_notMem_range σ2 E rintro ⟨i,hi⟩ have hh := congrArg Fin.val hi change i.val=7 at hh omega have hfix8 : lift 8=8 := by apply Equiv.Perm.viaFintypeEmbedding_apply_notMem_range σ2 E rintro ⟨i,hi⟩ have hh := congrArg Fin.val hi change i.val=8 at hh omega
Under the composed permutation ρ = lift ∘ σ₁, the array v' = v ∘ ρ has valid triples at positions (3, 4, 5) and (6, 7, 8).
The composite permutation ρ applies σ₂ on indices 0 through 5, so the triple at (3, 4, 5) is valid by construction of σ₂. Because the lift fixes indices 6, 7, 8, the triple at (6, 7, 8) remains the valid triple established by σ₁.
let ρ : Equiv.Perm (Fin 9) := lift.trans σ1 let v' : Fin 9 → C := fun i => v (ρ i) have hv' : Function.Injective v' := hv.comp ρ.injective have hT1 : in342_wrap_valid A (v' 3) (v' 4) (v' 5) := by change in342_wrap_valid A (v (σ1 (lift (E 3)))) (v (σ1 (lift (E 4)))) (v (σ1 (lift (E 5)))) rw [hcast 3,hcast 4,hcast 5] exact h2 have hT2 : in342_wrap_valid A (v' 6) (v' 7) (v' 8) := by change in342_wrap_valid A (v (σ1 (lift 6))) (v (σ1 (lift 7))) (v (σ1 (lift 8))) rw [hfix6,hfix7,hfix8] exact h1
If any permutation π of Fin 9 satisfies A(v'(π 0), v'(π 1)) = v'(π 2) while keeping triples (3, 4, 5) and (6, 7, 8) valid, the full goal follows.
By `wild_valid_triples_nine_repair`, any configuration where two triples are valid and the third satisfies A(x, y) = z can be repaired into three valid triples via a permutation τ. Composing τ ∘ π ∘ ρ yields the required permutation of Fin 9.
uses
wild_valid_triples_nine_repairhave hfinish (π : Equiv.Perm (Fin 9)) (hb : A (v' (π 0)) (v' (π 1))=v' (π 2)) (ht1 : in342_wrap_valid A (v' (π 3)) (v' (π 4)) (v' (π 5))) (ht2 : in342_wrap_valid A (v' (π 6)) (v' (π 7)) (v' (π 8))) : in342_wrap_goal A v := by obtain ⟨τ,hτ⟩ := wild_valid_triples_nine_repair A hdiag hsym hinj (v' ∘ π) (hv'.comp π.injective) hb ht1 ht2 refine ⟨(τ.trans π).trans ρ,?_⟩ intro t exact hτ t
If the first triple (v' 0, v' 1, v' 2) is already valid, the proof is complete.
If the first triple is valid, all three triples t ∈ {0, 1, 2} are valid under ρ (by assumption for t = 0, and by the preceding steps for t = 1 and t = 2), so ρ directly satisfies the goal.
by_cases hg : in342_wrap_valid A (v' 0) (v' 1) (v' 2) · refine ⟨ρ,?_⟩ intro t fin_cases t · exact hg · exact hT1 · exact hT2
If the first triple is invalid, a permutation on {0, 1, 2} aligns it with the repair lemma, completing the proof. automation
Invalidity of the first triple implies at least one of A(v' 0, v' 1) = v' 2, A(v' 0, v' 2) = v' 1, or A(v' 1, v' 2) = v' 0 holds, deduced by `tauto`. In the first case, the identity permutation `Equiv.refl` satisfies `hfinish`. In the second case, swapping indices 1 and 2 aligns with `hfinish`. In the third case, cyclically permuting (0, 1, 2) ↦ (1, 2, 0) aligns with `hfinish`. In all cases, indices 3 through 8 are untouched, so the other two triples remain valid.
uses
Equiv.refl,Equiv.ofBijectivehave hb : A (v' 0) (v' 1)=v' 2 ∨ A (v' 0) (v' 2)=v' 1 ∨ A (v' 1) (v' 2)=v' 0 := by unfold in342_wrap_valid at hg tauto rcases hb with hb|hb|hb · exact hfinish (Equiv.refl _) hb hT1 hT2 · let π : Equiv.Perm (Fin 9) := Equiv.ofBijective (![0,2,1,3,4,5,6,7,8] : Fin 9 → Fin 9) (by decide +kernel) exact hfinish π hb hT1 hT2 · let π : Equiv.Perm (Fin 9) := Equiv.ofBijective (![1,2,0,3,4,5,6,7,8] : Fin 9 → Fin 9) (by decide +kernel) exact hfinish π hb hT1 hT2
Ne.symm- Symmetry of disequality: if a ≠ b, then b ≠ a.
wild_valid_triple_exists_in_six- In any row-injective array, any six distinct elements contain three elements that form a valid triple.
in342_wrap_vec_inj- A vector of three pairwise distinct elements defines an injective map from Fin 3.
Equiv.Perm.exists_extending_pair- Given two injective maps from a finite set to the same domain, there exists a permutation of the domain extending the correspondence.
in342_wrap_place- Given six embedded vertices and three target positions, there exists a permutation of the ambient set placing a valid triple from the six vertices into the target positions.
Function.injective_id- The identity function on any type is injective.
Equiv.Perm.viaFintypeEmbedding_apply_image- A permutation extended to a larger finite type via an embedding maps embedded elements according to the original permutation.
Equiv.Perm.viaFintypeEmbedding_apply_notMem_range- A permutation extended to a larger finite type via an embedding acts as the identity on elements outside the image of the embedding.
congrArg- If two arguments are equal, the values of a function applied to them are equal.
wild_valid_triples_nine_repair- In a normalized, symmetric, row-injective array on nine vertices with two valid triples and a third triple satisfying A(v 0, v 1) = v 2, there is a permutation of Fin 9 making all three triples valid.
Equiv.refl- The identity permutation on a given type.
Equiv.ofBijective- Constructs an equivalence (permutation) from a bijective function.
- `decide +kernel` is used repeatedly to verify the injectivity and bijectivity of explicit finite vectors by direct computational reflection in the Lean kernel.
- `omega` is used to discharge finite index bounds of the form 3*t + j < 9 as well as to prove that indices 6, 7, 8 cannot belong to the image of `Fin.castAddEmb 3`.
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_wrap_valid {C : Type*} (A : C → C → C) (x y z : C) : Prop := A x y≠z ∧ A x z≠y ∧ A y z≠xprivate theorem in342_wrap_vec_inj {D : Type*} (i j k : D) (hij : i≠j) (hik : i≠k) (hjk : j≠k) : Function.Injective (![i,j,k] : Fin 3 → D) := by intro a b h fin_cases a <;> fin_cases b · rfl · change i=j at h exact (hij h).elim · change i=k at h exact (hik h).elim · change j=i at h exact ((Ne.symm hij) h).elim · rfl · change j=k at h exact (hjk h).elim · change k=i at h exact ((Ne.symm hik) h).elim · change k=j at h exact ((Ne.symm hjk) h).elim · rflprivate theorem in342_wrap_place {C : Type*} (A : C → C → C) (hinj : ∀ x,Function.Injective (A x)) {N : ℕ} (v : Fin N → C) (hv : Function.Injective v) (ι : Fin 6 → Fin N) (hι : Function.Injective ι) (f : Fin 3 → Fin N) (hf : Function.Injective f) : ∃ σ : Equiv.Perm (Fin N), in342_wrap_valid A (v (σ (f 0))) (v (σ (f 1))) (v (σ (f 2))) := by obtain ⟨i,j,k,hij,hik,hjk,hgood⟩ := wild_valid_triple_exists_in_six A hinj (v ∘ ι) (hv.comp hι) let g : Fin 3 → Fin N := ι ∘ (![i,j,k] : Fin 3 → Fin 6) have hg : Function.Injective g := hι.comp (in342_wrap_vec_inj i j k hij hik hjk) obtain ⟨σ,hσ⟩ := Equiv.Perm.exists_extending_pair f g hf hg refine ⟨σ,?_⟩ rw [hσ 0,hσ 1,hσ 2] exact hgoodprivate def in342_wrap_slot (t j : Fin 3) : Fin 9 := ⟨3*t.val+j.val,by omega⟩private def in342_wrap_goal {C : Type*} (A : C → C → C) (v : Fin 9 → C) : Prop := ∃ σ : Equiv.Perm (Fin 9),∀ t : Fin 3, in342_wrap_valid A (v (σ (in342_wrap_slot t 0))) (v (σ (in342_wrap_slot t 1))) (v (σ (in342_wrap_slot t 2)))theorem wild_valid_triples_nine_factor {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)) (v : Fin 9 → C) (hv : Function.Injective v) : ∃ σ : Equiv.Perm (Fin (9)),∀ t : Fin (3), 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 change in342_wrap_goal A v let E : Fin 6 ↪ Fin 9 := Fin.castAddEmb 3 obtain ⟨σ1,h1⟩ := in342_wrap_place A hinj v hv E E.injective (![6,7,8] : Fin 3 → Fin 9) (by decide +kernel) change in342_wrap_valid A (v (σ1 6)) (v (σ1 7)) (v (σ1 8)) at h1 let w : Fin 6 → C := fun i => v (σ1 (E i)) have hw : Function.Injective w := hv.comp (σ1.injective.comp E.injective) obtain ⟨σ2,h2⟩ := in342_wrap_place A hinj w hw (id : Fin 6 → Fin 6) Function.injective_id (![3,4,5] : Fin 3 → Fin 6) (by decide +kernel) change in342_wrap_valid A (w (σ2 3)) (w (σ2 4)) (w (σ2 5)) at h2 let lift : Equiv.Perm (Fin 9) := σ2.viaFintypeEmbedding E have hcast (i : Fin 6) : lift (E i)=E (σ2 i) := Equiv.Perm.viaFintypeEmbedding_apply_image σ2 E i have hfix6 : lift 6=6 := by apply Equiv.Perm.viaFintypeEmbedding_apply_notMem_range σ2 E rintro ⟨i,hi⟩ have hh := congrArg Fin.val hi change i.val=6 at hh omega have hfix7 : lift 7=7 := by apply Equiv.Perm.viaFintypeEmbedding_apply_notMem_range σ2 E rintro ⟨i,hi⟩ have hh := congrArg Fin.val hi change i.val=7 at hh omega have hfix8 : lift 8=8 := by apply Equiv.Perm.viaFintypeEmbedding_apply_notMem_range σ2 E rintro ⟨i,hi⟩ have hh := congrArg Fin.val hi change i.val=8 at hh omega let ρ : Equiv.Perm (Fin 9) := lift.trans σ1 let v' : Fin 9 → C := fun i => v (ρ i) have hv' : Function.Injective v' := hv.comp ρ.injective have hT1 : in342_wrap_valid A (v' 3) (v' 4) (v' 5) := by change in342_wrap_valid A (v (σ1 (lift (E 3)))) (v (σ1 (lift (E 4)))) (v (σ1 (lift (E 5)))) rw [hcast 3,hcast 4,hcast 5] exact h2 have hT2 : in342_wrap_valid A (v' 6) (v' 7) (v' 8) := by change in342_wrap_valid A (v (σ1 (lift 6))) (v (σ1 (lift 7))) (v (σ1 (lift 8))) rw [hfix6,hfix7,hfix8] exact h1 have hfinish (π : Equiv.Perm (Fin 9)) (hb : A (v' (π 0)) (v' (π 1))=v' (π 2)) (ht1 : in342_wrap_valid A (v' (π 3)) (v' (π 4)) (v' (π 5))) (ht2 : in342_wrap_valid A (v' (π 6)) (v' (π 7)) (v' (π 8))) : in342_wrap_goal A v := by obtain ⟨τ,hτ⟩ := wild_valid_triples_nine_repair A hdiag hsym hinj (v' ∘ π) (hv'.comp π.injective) hb ht1 ht2 refine ⟨(τ.trans π).trans ρ,?_⟩ intro t exact hτ t by_cases hg : in342_wrap_valid A (v' 0) (v' 1) (v' 2) · refine ⟨ρ,?_⟩ intro t fin_cases t · exact hg · exact hT1 · exact hT2 have hb : A (v' 0) (v' 1)=v' 2 ∨ A (v' 0) (v' 2)=v' 1 ∨ A (v' 1) (v' 2)=v' 0 := by unfold in342_wrap_valid at hg tauto rcases hb with hb|hb|hb · exact hfinish (Equiv.refl _) hb hT1 hT2 · let π : Equiv.Perm (Fin 9) := Equiv.ofBijective (![0,2,1,3,4,5,6,7,8] : Fin 9 → Fin 9) (by decide +kernel) exact hfinish π hb hT1 hT2 · let π : Equiv.Perm (Fin 9) := Equiv.ofBijective (![1,2,0,3,4,5,6,7,8] : Fin 9 → Fin 9) (by decide +kernel) exact hfinish π hb hT1 hT2