AFTD Auto-Formalizing Theoretical Domains

wild_valid_triple_exists_in_six

theoremverified

For any array with injective rows and any six distinct vertices, there are three distinct indices satisfying all three triple-validity inequalities. Symmetry, idempotence and finite color type are not needed for this local statement.

Statement

theorem wild_valid_triple_exists_in_six {C : Type*} (A : C → C → C)
    (hinj : ∀ x,Function.Injective (A x)) (v : Fin 6 → C) (hv : Function.Injective v) :
    ∃ i j k : Fin 6,i≠j ∧ i≠k ∧ j≠k ∧
      A (v i) (v j)≠v k ∧ A (v i) (v k)≠v j ∧ A (v j) (v k)≠v i
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 1
  • wild_valid_replacement_from_threeGiven a bad pair witness A(x,y)=z, three distinct candidate replacements all different from z cannot all fail the validity inequalities,…
Used by 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 tests whether the first three vertices v 0, v 1, v 2 already form a valid triple. If all three inequalities hold, the indices 0, 1, 2 immediately witness the theorem. Otherwise, at least one condition fails with an equality, say A(x, y) = z for some pair chosen from {v 0, v 1, v 2}. The lemma wild_valid_replacement_from_three then guarantees that testing the remaining three vertices v 3, v 4, v 5 (which are disjoint from {v 0, v 1, v 2} by injectivity of v) yields a replacement vertex that forms a valid triple with x and y.

  1. If the initial triple of vertices (v 0, v 1, v 2) satisfies the three triple-validity inequalities, the theorem is witnessed by the indices (0, 1, 2).

    We perform a case split on whether the triple (v 0, v 1, v 2) is already valid. If all three inequalities hold, the indices 0, 1, 2 are pairwise distinct (verified by finite evaluation with decide) and immediately satisfy the conditions.

    lines 7–9

      classical
      by_cases hgood : A (v 0) (v 1)≠v 2 ∧ A (v 0) (v 2)≠v 1 ∧ A (v 1) (v 2)≠v 0
      · exact ⟨0,1,2,by decide,by decide,by decide,hgood⟩
  2. Otherwise, at least one of the three validity conditions fails with an equality: A (v 0) (v 1) = v 2, A (v 0) (v 2) = v 1, or A (v 1) (v 2) = v 0.

    When the conjunction of the three inequalities is false, De Morgan's laws for propositional logic establish that at least one equality must hold, closed by tauto.

    line 10

      have hbad : A (v 0) (v 1)=v 2 ∨ A (v 0) (v 2)=v 1 ∨ A (v 1) (v 2)=v 0 := by tauto
  3. The index shift map u(i) = i + 3 from Fin 3 to Fin 6 and the restricted vertex sequence v ∘ u are both injective.

    The shift map u adds 3 to each index. If u i = u j, then extracting their natural values with congrArg and Fin.val shows i + 3 = j + 3, so i = j by linear arithmetic, proving u is injective via Fin.ext. Since v is injective by hypothesis, the composite v ∘ u is also injective.

    lines 11–18

    uses Fin.ext, congrArg

      let u : Fin 3 → Fin 6 := fun i => ⟨i.val+3,by omega⟩
      have hu : Function.Injective u := by
        intro i j hij
        apply Fin.ext
        have h := congrArg Fin.val hij
        dsimp [u] at h
        omega
      have hw : Function.Injective (v ∘ u) := hv.comp hu
  4. The three shifted vertices in v ∘ u (representing v 3, v 4, v 5) are disjoint from the first three vertices v z for z < 3.

    Assuming (v ∘ u) i = v z for some z < 3, the injectivity of v implies their indices are equal, which rewrites via Function.comp_def and congrArg to i + 3 = z. But since i ≥ 0, i + 3 ≥ 3, which contradicts z < 3 by linear arithmetic.

    lines 19–23

    uses congrArg, Function.comp_def

      have hout (z : Fin 6) (hz : z.val<3) : ∀ i,(v ∘ u) i≠v z := by
        intro i h
        have h' := congrArg Fin.val (hv h)
        dsimp [u,Function.comp_def] at h'
        omega
  5. If A (v 0) (v 1) = v 2, there is an index u i ∈ {3, 4, 5} such that (0, 1, u i) is a valid triple.

    Applying wild_valid_replacement_from_three to x = v 0, y = v 1, z = v 2 and the candidate sequence v ∘ u (which avoids v 2 by our disjointness result) yields an index i such that (v 0, v 1, (v ∘ u) i) satisfies all three validity inequalities. The indices 0, 1, and u i are pairwise distinct: 0 ≠ 1 is checked directly, and 0 ≠ u i and 1 ≠ u i hold via congrArg because u i = i + 3 ≥ 3.

    lines 24–35

    uses wild_valid_replacement_from_three, congrArg

      rcases hbad with h|h|h
      · obtain ⟨i,h1,h2,h3⟩ := wild_valid_replacement_from_three A (v 0) (v 1) (v 2)
          (hinj _) (hinj _) (v ∘ u) hw h (hout 2 (by decide))
        refine ⟨0,1,u i,by decide,?_,?_,h1,h2,h3⟩
        · intro h'
          have hh := congrArg Fin.val h'
          change 0=i.val+3 at hh
          omega
        · intro h'
          have hh := congrArg Fin.val h'
          change 1=i.val+3 at hh
          omega
  6. If A (v 0) (v 2) = v 1, there is an index u i ∈ {3, 4, 5} such that (0, 2, u i) is a valid triple.

    Applying wild_valid_replacement_from_three to x = v 0, y = v 2, z = v 1 and candidate sequence v ∘ u (which avoids v 1) yields an index i such that (v 0, v 2, (v ∘ u) i) satisfies the three validity inequalities. The indices 0, 2, and u i are pairwise distinct because 0 ≠ 2 and u i = i + 3 ≥ 3 > 2.

    lines 36–46

    uses wild_valid_replacement_from_three, congrArg

      · obtain ⟨i,h1,h2,h3⟩ := wild_valid_replacement_from_three A (v 0) (v 2) (v 1)
          (hinj _) (hinj _) (v ∘ u) hw h (hout 1 (by decide))
        refine ⟨0,2,u i,by decide,?_,?_,h1,h2,h3⟩
        · intro h'
          have hh := congrArg Fin.val h'
          change 0=i.val+3 at hh
          omega
        · intro h'
          have hh := congrArg Fin.val h'
          change 2=i.val+3 at hh
          omega
  7. If A (v 1) (v 2) = v 0, there is an index u i ∈ {3, 4, 5} such that (1, 2, u i) is a valid triple.

    Applying wild_valid_replacement_from_three to x = v 1, y = v 2, z = v 0 and candidate sequence v ∘ u (which avoids v 0) yields an index i such that (v 1, v 2, (v ∘ u) i) satisfies the three validity inequalities. The indices 1, 2, and u i are pairwise distinct because 1 ≠ 2 and u i = i + 3 ≥ 3 > 2.

    lines 47–57

    uses wild_valid_replacement_from_three, congrArg

      · obtain ⟨i,h1,h2,h3⟩ := wild_valid_replacement_from_three A (v 1) (v 2) (v 0)
          (hinj _) (hinj _) (v ∘ u) hw h (hout 0 (by decide))
        refine ⟨1,2,u i,by decide,?_,?_,h1,h2,h3⟩
        · intro h'
          have hh := congrArg Fin.val h'
          change 1=i.val+3 at hh
          omega
        · intro h'
          have hh := congrArg Fin.val h'
          change 2=i.val+3 at hh
          omega
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
congrArg
Equality is preserved under function application: if a = b, then f a = f b.
Function.comp_def
The composition of two functions f and g satisfies (f ∘ g) x = f (g x) by definition.
wild_valid_replacement_from_three
If A x y = z and the row operations A x and A y are injective, then given any three distinct candidate values disjoint from z, at least one candidate w i forms a valid triple with x and y: A x y ≠ w i, A x (w i) ≠ y, and A y (w i) ≠ x.

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 4000000theorem wild_valid_triple_exists_in_six {C : Type*} (A : C → C → C)    (hinj : ∀ x,Function.Injective (A x)) (v : Fin 6 → C) (hv : Function.Injective v) :    ∃ i j k : Fin 6,i≠j ∧ i≠k ∧ j≠k ∧      A (v i) (v j)≠v k ∧ A (v i) (v k)≠v j ∧ A (v j) (v k)≠v i := by  classical  by_cases hgood : A (v 0) (v 1)≠v 2 ∧ A (v 0) (v 2)≠v 1 ∧ A (v 1) (v 2)≠v 0  · exact ⟨0,1,2,by decide,by decide,by decide,hgood⟩  have hbad : A (v 0) (v 1)=v 2 ∨ A (v 0) (v 2)=v 1 ∨ A (v 1) (v 2)=v 0 := by tauto  let u : Fin 3 → Fin 6 := fun i => ⟨i.val+3,by omega⟩  have hu : Function.Injective u := by    intro i j hij    apply Fin.ext    have h := congrArg Fin.val hij    dsimp [u] at h    omega  have hw : Function.Injective (v ∘ u) := hv.comp hu  have hout (z : Fin 6) (hz : z.val<3) : ∀ i,(v ∘ u) i≠v z := by    intro i h    have h' := congrArg Fin.val (hv h)    dsimp [u,Function.comp_def] at h'    omega  rcases hbad with h|h|h  · obtain ⟨i,h1,h2,h3⟩ := wild_valid_replacement_from_three A (v 0) (v 1) (v 2)      (hinj _) (hinj _) (v ∘ u) hw h (hout 2 (by decide))    refine ⟨0,1,u i,by decide,?_,?_,h1,h2,h3⟩    · intro h'      have hh := congrArg Fin.val h'      change 0=i.val+3 at hh      omega    · intro h'      have hh := congrArg Fin.val h'      change 1=i.val+3 at hh      omega  · obtain ⟨i,h1,h2,h3⟩ := wild_valid_replacement_from_three A (v 0) (v 2) (v 1)      (hinj _) (hinj _) (v ∘ u) hw h (hout 1 (by decide))    refine ⟨0,2,u i,by decide,?_,?_,h1,h2,h3⟩    · intro h'      have hh := congrArg Fin.val h'      change 0=i.val+3 at hh      omega    · intro h'      have hh := congrArg Fin.val h'      change 2=i.val+3 at hh      omega  · obtain ⟨i,h1,h2,h3⟩ := wild_valid_replacement_from_three A (v 1) (v 2) (v 0)      (hinj _) (hinj _) (v ∘ u) hw h (hout 0 (by decide))    refine ⟨1,2,u i,by decide,?_,?_,h1,h2,h3⟩    · intro h'      have hh := congrArg Fin.val h'      change 1=i.val+3 at hh      omega    · intro h'      have hh := congrArg Fin.val h'      change 2=i.val+3 at hh      omega
See it in the graphDiscuss this resultChallenge it