wild_valid_triple_exists_in_six
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.
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.
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⟩
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.
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
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.
uses
Fin.ext,congrArglet 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
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.
uses
congrArg,Function.comp_defhave 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
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.
uses
wild_valid_replacement_from_three,congrArgrcases 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
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.
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
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.
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.
- The distinctness of the chosen indices from the first three indices (for example, proving 0 ≠ i + 3 for i : Fin 3) requires explicitly converting between Fin 6 elements and natural numbers before applying linear arithmetic (omega), a type-theoretic bookkeeping detail with no counterpart on paper.
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 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