AFTD Auto-Formalizing Theoretical Domains

wild_valid_triples_nine_factor

theoremverified

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

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.

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

    lines 4–23

    uses Ne.symm

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

    lines 25–39

    uses wild_valid_triple_exists_in_six, in342_wrap_vec_inj, Equiv.Perm.exists_extending_pair

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

    lines 40–53

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

    lines 54–57

    uses in342_wrap_place

      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
  5. 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`.

    lines 58–62

    uses in342_wrap_place, Function.injective_id

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

    lines 63–83

    uses Equiv.Perm.viaFintypeEmbedding_apply_image, Equiv.Perm.viaFintypeEmbedding_apply_notMem_range, congrArg

      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
  7. 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 σ₁.

    lines 84–94

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

    lines 95–104

    uses wild_valid_triples_nine_repair

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

    lines 105–111

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

    lines 112–120

    uses Equiv.refl, Equiv.ofBijective

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

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

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