AFTD Auto-Formalizing Theoretical Domains

wild_valid_triple_factor_of_multiple_three

theoremverified

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.

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

    lines 11–13

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

    lines 14–20

    uses finCongr, wild_valid_triples_with_reservoir

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

    lines 21–33

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

    lines 34–43

    uses Fin.ext, congrArg, wild_valid_triples_nine_factor

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

    lines 44–55

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

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

    lines 56–83

    uses Fin.ext, congrArg, Function.comp_def, Nat.add_zero

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

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