wild_valid_triples_with_reservoir
For every finite injectively indexed set of 3q+r vertices, with r at least three, a normalized symmetric row-injective array admits a permutation whose first q consecutive triples are all valid. The final r vertices are unconstrained. This is a validity packing statement, not color connectivity.
Statement
theorem wild_valid_triples_with_reservoir {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 r : ℕ) (hr : 3≤r) (v : Fin (3*q+r) → C) (hv : Function.Injective v) : ∃ σ : Equiv.Perm (Fin (3*q+r)),∀ 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 1
- 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…
- 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
The proof proceeds by induction on q. The base case q = 0 is vacuous using the identity permutation. For the inductive step q + 1, since the total size 3(q + 1) + r is at least 6, we invoke wild_valid_triple_exists_in_six on the first 6 elements to extract three distinct indices a, b, c that form a valid triple. Removing {a, b, c} leaves 3q + r elements, on which the induction hypothesis produces a permutation valid on the next q triples; concatenating {a, b, c} with this permutation yields the required permutation on all q + 1 triples.
Under the canonical equivalence Fin (3 + M) ≃ Fin 3 ⊕ Fin M, any index j < 3 corresponds to the left injection Sum.inl j.
We express the index ⟨j, hj⟩ as a cast of Fin.castAdd M j, after which simplifying the definitions confirms that finSumFinEquiv.symm maps it to Sum.inl j.
uses
Fin.cast,Fin.castAdd,finSumFinEquiv.symm,finCongrprivate lemma wild_valid_triples_with_reservoir_e_inl {N M : ℕ} (hN : N = 3 + M) (j : Fin 3) (hj : (j:ℕ) < N) : finSumFinEquiv.symm (finCongr hN (⟨(j:ℕ), hj⟩ : Fin N)) = Sum.inl j := by have hcast : (⟨(j:ℕ), hj⟩ : Fin N) = Fin.cast (by omega : 3 + M = N) (Fin.castAdd M j) := by ext; simp rw [hcast] simp
Under the canonical equivalence Fin (3 + M) ≃ Fin 3 ⊕ Fin M, any index 3 + j with j : Fin M corresponds to the right injection Sum.inr j.
We express the index ⟨3 + j, hj⟩ as a cast of Fin.natAdd 3 j, after which simplifying definitions confirms that finSumFinEquiv.symm maps it to Sum.inr j.
uses
Fin.cast,Fin.natAdd,finSumFinEquiv.symm,finCongrprivate lemma wild_valid_triples_with_reservoir_e_inr {N M : ℕ} (hN : N = 3 + M) (j : Fin M) (hj : 3 + (j:ℕ) < N) : finSumFinEquiv.symm (finCongr hN (⟨3 + (j:ℕ), hj⟩ : Fin N)) = Sum.inr j := by have hcast : (⟨3 + (j:ℕ), hj⟩ : Fin N) = Fin.cast (by omega : 3 + M = N) (Fin.natAdd 3 j) := by ext; simp rw [hcast] simp
When a, b, c are pairwise distinct, the selection map sending 0 ↦ a, 1 ↦ b, 2 ↦ c defines an equivalence Fin 3 ≃ {a, b, c}.
We define the forward function sending 0, 1, 2 to a, b, c and an inverse mapping a, b, c back to 0, 1, 2. The left inverse property holds by checking each element of Fin 3. The right inverse property holds by decomposing membership in {a, b, c} into cases and ruling out impossible equalities via the distinctness hypotheses.
uses
wild_valid_triples_with_reservoir_sel_val,wild_valid_triples_with_reservoir_sel_inv,Finset.mem_insert,Finset.mem_singleton,Subtype.extprivate def wild_valid_triples_with_reservoir_sel_val {α : Type*} [DecidableEq α] (a b c : α) (t : Fin 3) : α := if t = 0 then a else if t = 1 then b else c private def wild_valid_triples_with_reservoir_sel_inv {α : Type*} [DecidableEq α] (a b _c : α) (x : α) : Fin 3 := if x = a then 0 else if x = b then 1 else 2 private noncomputable def wild_valid_triples_with_reservoir_sel_equiv {α : Type*} [DecidableEq α] (a b c : α) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) : Fin 3 ≃ {x : α // x ∈ ({a,b,c} : Finset α)} where toFun t := ⟨wild_valid_triples_with_reservoir_sel_val a b c t, by dsimp [wild_valid_triples_with_reservoir_sel_val] split_ifs <;> simp [*]⟩ invFun x := wild_valid_triples_with_reservoir_sel_inv a b c (x : α) left_inv := by intro t fin_cases t <;> simp [wild_valid_triples_with_reservoir_sel_val, wild_valid_triples_with_reservoir_sel_inv, hab, hab.symm, hac, hac.symm, hbc, hbc.symm] right_inv := by intro x rcases x with ⟨x, hx⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with hxa | hxb | hxc · subst x apply Subtype.ext simp [wild_valid_triples_with_reservoir_sel_val, wild_valid_triples_with_reservoir_sel_inv, hab] · subst x apply Subtype.ext by_cases hba : b = a · exact (hab hba.symm).elim · simp [wild_valid_triples_with_reservoir_sel_val, wild_valid_triples_with_reservoir_sel_inv, hba] · subst x apply Subtype.ext by_cases hca : c = a · exact (hac hca.symm).elim · by_cases hcb : c = b · exact (hbc hcb.symm).elim · simp [wild_valid_triples_with_reservoir_sel_val, wild_valid_triples_with_reservoir_sel_inv, hca, hcb]
The theorem holds when q = 0: the identity permutation satisfies the condition vacuously.
We induct on q. When q = 0, there are no triples to check, so the identity permutation Equiv.refl trivially works via Fin.elim0.
uses
Equiv.refl,Fin.elim0theorem wild_valid_triples_with_reservoir {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 r : ℕ) (hr : 3≤r) (v : Fin (3*q+r) → C) (hv : Function.Injective v) : ∃ σ : Equiv.Perm (Fin (3*q+r)),∀ 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 induction q with | zero => exact ⟨Equiv.refl _, by intro t; exact Fin.elim0 t⟩
In the inductive step q + 1, the universe has at least 6 elements, from which we extract three indices forming a valid triple.
Since N = 3(q + 1) + r and r ≥ 3, we have N ≥ 6. Embedding Fin 6 into Fin N via Fin.castLE, the restriction of v to these 6 elements remains injective. Applying wild_valid_triple_exists_in_six gives three distinct indices i, j, k in Fin 6 whose values under v form a valid triple.
uses
Fin.castLE,Fin.castLE_injective,wild_valid_triple_exists_in_six| succ q ih => let N := 3 * (q + 1) + r let M := 3 * q + r have hN : N = 3 + M := by dsimp [N, M]; omega have hN6 : 6 ≤ N := by dsimp [N]; omega let e6 : Fin 6 → Fin N := Fin.castLE hN6 have he6 : Function.Injective e6 := Fin.castLE_injective hN6 have hw6 : Function.Injective (fun i : Fin 6 => v (e6 i)) := hv.comp he6 obtain ⟨i, j, k, hij, hik, hjk, h1, h2, h3⟩ := wild_valid_triple_exists_in_six A hinj (fun i : Fin 6 => v (e6 i)) hw6The chosen elements a, b, c in Fin N are pairwise distinct, form a valid triple, and span a 3-element subset S.
Because the embedding e6 is injective and i, j, k are pairwise distinct, their images a, b, c are pairwise distinct. Their valid triple inequalities carry over directly, and distinctness implies |S| = 3 where S = {a, b, c}.
let a : Fin N := e6 i let b : Fin N := e6 j let c : Fin N := e6 k have hab : a ≠ b := by intro h; apply hij; exact he6 h have hac : a ≠ c := by intro h; apply hik; exact he6 h have hbc : b ≠ c := by intro h; apply hjk; exact he6 h have htriple1 : A (v a) (v b) ≠ v c := by simpa [a, b, c] using h1 have htriple2 : A (v a) (v c) ≠ v b := by simpa [a, b, c] using h2 have htriple3 : A (v b) (v c) ≠ v a := by simpa [a, b, c] using h3 let S : Finset (Fin N) := {a, b, c} have hScard : S.card = 3 := by simp [S, hab, hac, hbc, hab.symm, hac.symm, hbc.symm]
The complement T = (Fin N) \ S has cardinality M = 3q + r, and applying the induction hypothesis to v restricted to T yields a valid triple permutation τ of Fin M.
The complement T has size N - |S| = N - 3 = M. We identify T with Fin M via Fintype.equivFinOfCardEq. Restricting v via this identification gives an injective sequence w : Fin M → C, to which the induction hypothesis applies to produce a permutation τ of Fin M whose first q triples are valid.
uses
Fintype.card_subtype_compl,Fintype.card_coe,Fintype.card_fin,Fintype.equivFinOfCardEq,Subtype.extlet T := {x : Fin N // x ∉ S} have hTcard : Fintype.card T = M := by dsimp [T] rw [Fintype.card_subtype_compl] have hScard' : Fintype.card {x : Fin N // x ∈ S} = 3 := by rw [Fintype.card_coe] exact hScard rw [hScard', Fintype.card_fin] dsimp [N, M] at hN ⊢ omega let eC : T ≃ Fin M := Fintype.equivFinOfCardEq hTcard let w : Fin M → C := fun s => v (eC.symm s) have hw : Function.Injective w := by intro x y hxy exact eC.symm.injective (Subtype.ext (hv hxy)) obtain ⟨τ, hτ⟩ := ih w hw
We construct the overall permutation F of Fin N by sending the first 3 coordinates to S and the remaining M coordinates to T via τ.
We identify Fin N with Fin 3 ⊕ Fin M, apply the selection equivalence on Fin 3 to hit S, and apply τ followed by the identification Fin M ≃ T on the second summand. Gluing S and T back together gives a permutation F of Fin N.
uses
wild_valid_triples_with_reservoir_sel_equiv,finCongr,finSumFinEquiv.symm,Equiv.sumCongr,Equiv.sumCompllet sel : Fin 3 ≃ S := wild_valid_triples_with_reservoir_sel_equiv a b c hab hac hbc let e : Fin N ≃ Fin 3 ⊕ Fin M := (finCongr hN).trans finSumFinEquiv.symm let eR : Fin M ≃ T := τ.trans eC.symm let F : Fin N ≃ Fin N := e.trans ((Equiv.sumCongr sel eR).trans (Equiv.sumCompl (fun x : Fin N => x ∈ S))) use F
The permutation F maps indices 0, 1, 2 to a, b, c, and maps any index 3 + j to eC.symm (τ j).
By the helper lemmas for the left and right summands, F sends the first three coordinates to sel 0 = a, sel 1 = b, and sel 2 = c, while any subsequent coordinate 3 + j is routed to eC.symm (τ j) in the complement T.
uses
Equiv.trans_apply,wild_valid_triples_with_reservoir_e_inl,Equiv.sumCompl_apply_inl,wild_valid_triples_with_reservoir_e_inr,Equiv.sumCompl_apply_inr,wild_valid_triples_with_reservoir_sel_equiv,wild_valid_triples_with_reservoir_sel_valintro t have hF_inl : ∀ j : Fin 3, F ⟨(j : ℕ), by omega⟩ = (sel j : Fin N) := by intro j dsimp only [F, e] simp only [Equiv.trans_apply] rw [wild_valid_triples_with_reservoir_e_inl hN j (by omega)] exact Equiv.sumCompl_apply_inl (sel j) have hF_inr : ∀ j : Fin M, F ⟨3 + (j : ℕ), by omega⟩ = (eC.symm (τ j) : Fin N) := by intro j dsimp only [F, e, eR] simp only [Equiv.trans_apply] rw [wild_valid_triples_with_reservoir_e_inr hN j (by omega)] exact Equiv.sumCompl_apply_inr (eC.symm (τ j)) have hsel0 : (sel (0 : Fin 3) : Fin N) = a := by simp [sel, wild_valid_triples_with_reservoir_sel_equiv, wild_valid_triples_with_reservoir_sel_val] have hsel1 : (sel (1 : Fin 3) : Fin N) = b := by simp [sel, wild_valid_triples_with_reservoir_sel_equiv, wild_valid_triples_with_reservoir_sel_val] have hsel2 : (sel (2 : Fin 3) : Fin N) = c := by simp [sel, wild_valid_triples_with_reservoir_sel_equiv, wild_valid_triples_with_reservoir_sel_val]
The first triple (t = 0) under F evaluates to (a, b, c) and is valid.
We split into cases on t : Fin (q + 1). For t = 0, the indices 3*0 + 0, 3*0 + 1, 3*0 + 2 are 0, 1, 2, so F evaluates to a, b, c. The valid triple conditions for this triple hold by the construction of a, b, c.
uses
Fin.eq_zero_or_eq_succrcases Fin.eq_zero_or_eq_succ t with rfl | ⟨t', rfl⟩ · have hF0 : F ⟨3 * (0 : Fin (q + 1)).val + 0, by omega⟩ = a := by simpa [hsel0] using hF_inl (0 : Fin 3) have hF1 : F ⟨3 * (0 : Fin (q + 1)).val + 1, by omega⟩ = b := by simpa [hsel1] using hF_inl (1 : Fin 3) have hF2 : F ⟨3 * (0 : Fin (q + 1)).val + 2, by omega⟩ = c := by simpa [hsel2] using hF_inl (2 : Fin 3) simpa [hF0, hF1, hF2] using ⟨htriple1, htriple2, htriple3⟩
Each subsequent triple (t = t' + 1) under F corresponds to triple t' under w ∘ τ and is valid by induction.
Each index 3*(t' + 1) + k can be rewritten as 3 + (3*t' + k) for k ∈ {0, 1, 2}. Therefore, F maps these indices to eC.symm (τ (3*t' + k)), which under v evaluates to w (τ (3*t' + k)). The inductive hypothesis for τ at t' confirms this triple is valid.
uses
Fin.val_succ· have hF0 : F ⟨3 * (t'.val + 1), by omega⟩ = (eC.symm (τ ⟨3 * t'.val + 0, by omega⟩) : Fin N) := by have hidx : (⟨3 * (t'.val + 1), by omega⟩ : Fin N) = ⟨3 + (⟨3 * t'.val + 0, by omega⟩ : Fin M).val, by omega⟩ := by ext simp only [Fin.val_succ] omega rw [hidx] exact hF_inr ⟨3 * t'.val + 0, by omega⟩ have hF1 : F ⟨3 * (t'.val + 1) + 1, by omega⟩ = (eC.symm (τ ⟨3 * t'.val + 1, by omega⟩) : Fin N) := by have hidx : (⟨3 * (t'.val + 1) + 1, by omega⟩ : Fin N) = ⟨3 + (⟨3 * t'.val + 1, by omega⟩ : Fin M).val, by omega⟩ := by ext simp only [Fin.val_succ] omega rw [hidx] exact hF_inr ⟨3 * t'.val + 1, by omega⟩ have hF2 : F ⟨3 * (t'.val + 1) + 2, by omega⟩ = (eC.symm (τ ⟨3 * t'.val + 2, by omega⟩) : Fin N) := by have hidx : (⟨3 * (t'.val + 1) + 2, by omega⟩ : Fin N) = ⟨3 + (⟨3 * t'.val + 2, by omega⟩ : Fin M).val, by omega⟩ := by ext simp only [Fin.val_succ] omega rw [hidx] exact hF_inr ⟨3 * t'.val + 2, by omega⟩ simpa [w, hF0, hF1, hF2] using hτ t'
Equiv.refl- The identity equivalence from any type to itself.
Equiv.sumCompl- The canonical equivalence between the disjoint sum of a subtype and its complement, and the original type.
Equiv.sumCompl_apply_inl- Evaluating Equiv.sumCompl on a left injection Sum.inl x yields the underlying element x.
Equiv.sumCompl_apply_inr- Evaluating Equiv.sumCompl on a right injection Sum.inr x yields the underlying element x.
Equiv.sumCongr- Combines two equivalences into an equivalence between their disjoint sums.
Equiv.trans_apply- Evaluating the composition of two equivalences f and g at an element a equals g(f(a)).
Fin.cast- Converts an element of Fin n to Fin m along an equality n = m, preserving its numeric value.
Fin.castAdd- Embeds Fin n into Fin (n + m) by preserving the numerical index.
Fin.castLE- Embeds Fin n into Fin m when n ≤ m, preserving the numerical index.
Fin.castLE_injective- The embedding Fin.castLE is an injective function.
Fin.elim0- Eliminates an element of the empty type Fin 0, constructing a value of any type.
Fin.eq_zero_or_eq_succ- Every element of Fin (n + 1) is either 0 or the successor of some element of Fin n.
Fin.natAdd- Embeds Fin m into Fin (n + m) by adding n to the numerical index.
Fin.val_succ- The numerical value of Fin.succ j equals j.val + 1.
finCongr- The canonical equivalence between Fin n and Fin m given an equality n = m.
finSumFinEquiv.symm- The canonical decomposition equivalence Fin (m + n) ≃ Fin m ⊕ Fin n.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Fintype.card_coe- The cardinality of the subtype associated with a finite set equals the cardinality of the finite set.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
Fintype.card_subtype_compl- The cardinality of the complement subtype {x // ¬p x} is the total cardinality minus the cardinality of {x // p x}.
Fintype.equivFinOfCardEq- Any finite type whose cardinality equals n is equivalent to Fin n.
Subtype.ext- Two elements of a subtype are equal if their underlying values in the parent type are equal.
wild_valid_triple_exists_in_six- In any row-injective binary operation, every sequence of six distinct elements contains three distinct indices whose values form a valid triple.
wild_valid_triples_with_reservoir_e_inl- Under the decomposition Fin (3 + M) ≃ Fin 3 ⊕ Fin M, an index j < 3 corresponds to Sum.inl j.
wild_valid_triples_with_reservoir_e_inr- Under the decomposition Fin (3 + M) ≃ Fin 3 ⊕ Fin M, an index 3 + j corresponds to Sum.inr j.
wild_valid_triples_with_reservoir_sel_equiv- When a, b, c are pairwise distinct, Fin 3 is equivalent to the three-element subtype {a, b, c}.
wild_valid_triples_with_reservoir_sel_inv- The inverse map from a three-element set {a, b, c} to Fin 3, sending a to 0, b to 1, and any other value to 2.
wild_valid_triples_with_reservoir_sel_val- The valuation function from Fin 3 to {a, b, c}, sending 0 to a, 1 to b, and 2 to c.
- On paper, identifying {0, ..., N-1} with {0, 1, 2} ⊔ {0, ..., M-1} and combining the two permutations is immediate set-theoretic notation. Formally in Lean, this requires constructing explicit equivalences using finSumFinEquiv, Fin.cast, and Equiv.sumCompl, and separately verifying their behavior on left and right summands.
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.
private lemma wild_valid_triples_with_reservoir_e_inl {N M : ℕ} (hN : N = 3 + M) (j : Fin 3) (hj : (j:ℕ) < N) : finSumFinEquiv.symm (finCongr hN (⟨(j:ℕ), hj⟩ : Fin N)) = Sum.inl j := by have hcast : (⟨(j:ℕ), hj⟩ : Fin N) = Fin.cast (by omega : 3 + M = N) (Fin.castAdd M j) := by ext; simp rw [hcast] simpprivate lemma wild_valid_triples_with_reservoir_e_inr {N M : ℕ} (hN : N = 3 + M) (j : Fin M) (hj : 3 + (j:ℕ) < N) : finSumFinEquiv.symm (finCongr hN (⟨3 + (j:ℕ), hj⟩ : Fin N)) = Sum.inr j := by have hcast : (⟨3 + (j:ℕ), hj⟩ : Fin N) = Fin.cast (by omega : 3 + M = N) (Fin.natAdd 3 j) := by ext; simp rw [hcast] simpprivate def wild_valid_triples_with_reservoir_sel_val {α : Type*} [DecidableEq α] (a b c : α) (t : Fin 3) : α := if t = 0 then a else if t = 1 then b else cprivate def wild_valid_triples_with_reservoir_sel_inv {α : Type*} [DecidableEq α] (a b _c : α) (x : α) : Fin 3 := if x = a then 0 else if x = b then 1 else 2private noncomputable def wild_valid_triples_with_reservoir_sel_equiv {α : Type*} [DecidableEq α] (a b c : α) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) : Fin 3 ≃ {x : α // x ∈ ({a,b,c} : Finset α)} where toFun t := ⟨wild_valid_triples_with_reservoir_sel_val a b c t, by dsimp [wild_valid_triples_with_reservoir_sel_val] split_ifs <;> simp [*]⟩ invFun x := wild_valid_triples_with_reservoir_sel_inv a b c (x : α) left_inv := by intro t fin_cases t <;> simp [wild_valid_triples_with_reservoir_sel_val, wild_valid_triples_with_reservoir_sel_inv, hab, hab.symm, hac, hac.symm, hbc, hbc.symm] right_inv := by intro x rcases x with ⟨x, hx⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with hxa | hxb | hxc · subst x apply Subtype.ext simp [wild_valid_triples_with_reservoir_sel_val, wild_valid_triples_with_reservoir_sel_inv, hab] · subst x apply Subtype.ext by_cases hba : b = a · exact (hab hba.symm).elim · simp [wild_valid_triples_with_reservoir_sel_val, wild_valid_triples_with_reservoir_sel_inv, hba] · subst x apply Subtype.ext by_cases hca : c = a · exact (hac hca.symm).elim · by_cases hcb : c = b · exact (hbc hcb.symm).elim · simp [wild_valid_triples_with_reservoir_sel_val, wild_valid_triples_with_reservoir_sel_inv, hca, hcb]theorem wild_valid_triples_with_reservoir {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 r : ℕ) (hr : 3≤r) (v : Fin (3*q+r) → C) (hv : Function.Injective v) : ∃ σ : Equiv.Perm (Fin (3*q+r)),∀ 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 induction q with | zero => exact ⟨Equiv.refl _, by intro t; exact Fin.elim0 t⟩ | succ q ih => let N := 3 * (q + 1) + r let M := 3 * q + r have hN : N = 3 + M := by dsimp [N, M]; omega have hN6 : 6 ≤ N := by dsimp [N]; omega let e6 : Fin 6 → Fin N := Fin.castLE hN6 have he6 : Function.Injective e6 := Fin.castLE_injective hN6 have hw6 : Function.Injective (fun i : Fin 6 => v (e6 i)) := hv.comp he6 obtain ⟨i, j, k, hij, hik, hjk, h1, h2, h3⟩ := wild_valid_triple_exists_in_six A hinj (fun i : Fin 6 => v (e6 i)) hw6 let a : Fin N := e6 i let b : Fin N := e6 j let c : Fin N := e6 k have hab : a ≠ b := by intro h; apply hij; exact he6 h have hac : a ≠ c := by intro h; apply hik; exact he6 h have hbc : b ≠ c := by intro h; apply hjk; exact he6 h have htriple1 : A (v a) (v b) ≠ v c := by simpa [a, b, c] using h1 have htriple2 : A (v a) (v c) ≠ v b := by simpa [a, b, c] using h2 have htriple3 : A (v b) (v c) ≠ v a := by simpa [a, b, c] using h3 let S : Finset (Fin N) := {a, b, c} have hScard : S.card = 3 := by simp [S, hab, hac, hbc, hab.symm, hac.symm, hbc.symm] let T := {x : Fin N // x ∉ S} have hTcard : Fintype.card T = M := by dsimp [T] rw [Fintype.card_subtype_compl] have hScard' : Fintype.card {x : Fin N // x ∈ S} = 3 := by rw [Fintype.card_coe] exact hScard rw [hScard', Fintype.card_fin] dsimp [N, M] at hN ⊢ omega let eC : T ≃ Fin M := Fintype.equivFinOfCardEq hTcard let w : Fin M → C := fun s => v (eC.symm s) have hw : Function.Injective w := by intro x y hxy exact eC.symm.injective (Subtype.ext (hv hxy)) obtain ⟨τ, hτ⟩ := ih w hw let sel : Fin 3 ≃ S := wild_valid_triples_with_reservoir_sel_equiv a b c hab hac hbc let e : Fin N ≃ Fin 3 ⊕ Fin M := (finCongr hN).trans finSumFinEquiv.symm let eR : Fin M ≃ T := τ.trans eC.symm let F : Fin N ≃ Fin N := e.trans ((Equiv.sumCongr sel eR).trans (Equiv.sumCompl (fun x : Fin N => x ∈ S))) use F intro t have hF_inl : ∀ j : Fin 3, F ⟨(j : ℕ), by omega⟩ = (sel j : Fin N) := by intro j dsimp only [F, e] simp only [Equiv.trans_apply] rw [wild_valid_triples_with_reservoir_e_inl hN j (by omega)] exact Equiv.sumCompl_apply_inl (sel j) have hF_inr : ∀ j : Fin M, F ⟨3 + (j : ℕ), by omega⟩ = (eC.symm (τ j) : Fin N) := by intro j dsimp only [F, e, eR] simp only [Equiv.trans_apply] rw [wild_valid_triples_with_reservoir_e_inr hN j (by omega)] exact Equiv.sumCompl_apply_inr (eC.symm (τ j)) have hsel0 : (sel (0 : Fin 3) : Fin N) = a := by simp [sel, wild_valid_triples_with_reservoir_sel_equiv, wild_valid_triples_with_reservoir_sel_val] have hsel1 : (sel (1 : Fin 3) : Fin N) = b := by simp [sel, wild_valid_triples_with_reservoir_sel_equiv, wild_valid_triples_with_reservoir_sel_val] have hsel2 : (sel (2 : Fin 3) : Fin N) = c := by simp [sel, wild_valid_triples_with_reservoir_sel_equiv, wild_valid_triples_with_reservoir_sel_val] rcases Fin.eq_zero_or_eq_succ t with rfl | ⟨t', rfl⟩ · have hF0 : F ⟨3 * (0 : Fin (q + 1)).val + 0, by omega⟩ = a := by simpa [hsel0] using hF_inl (0 : Fin 3) have hF1 : F ⟨3 * (0 : Fin (q + 1)).val + 1, by omega⟩ = b := by simpa [hsel1] using hF_inl (1 : Fin 3) have hF2 : F ⟨3 * (0 : Fin (q + 1)).val + 2, by omega⟩ = c := by simpa [hsel2] using hF_inl (2 : Fin 3) simpa [hF0, hF1, hF2] using ⟨htriple1, htriple2, htriple3⟩ · have hF0 : F ⟨3 * (t'.val + 1), by omega⟩ = (eC.symm (τ ⟨3 * t'.val + 0, by omega⟩) : Fin N) := by have hidx : (⟨3 * (t'.val + 1), by omega⟩ : Fin N) = ⟨3 + (⟨3 * t'.val + 0, by omega⟩ : Fin M).val, by omega⟩ := by ext simp only [Fin.val_succ] omega rw [hidx] exact hF_inr ⟨3 * t'.val + 0, by omega⟩ have hF1 : F ⟨3 * (t'.val + 1) + 1, by omega⟩ = (eC.symm (τ ⟨3 * t'.val + 1, by omega⟩) : Fin N) := by have hidx : (⟨3 * (t'.val + 1) + 1, by omega⟩ : Fin N) = ⟨3 + (⟨3 * t'.val + 1, by omega⟩ : Fin M).val, by omega⟩ := by ext simp only [Fin.val_succ] omega rw [hidx] exact hF_inr ⟨3 * t'.val + 1, by omega⟩ have hF2 : F ⟨3 * (t'.val + 1) + 2, by omega⟩ = (eC.symm (τ ⟨3 * t'.val + 2, by omega⟩) : Fin N) := by have hidx : (⟨3 * (t'.val + 1) + 2, by omega⟩ : Fin N) = ⟨3 + (⟨3 * t'.val + 2, by omega⟩ : Fin M).val, by omega⟩ := by ext simp only [Fin.val_succ] omega rw [hidx] exact hF_inr ⟨3 * t'.val + 2, by omega⟩ simpa [w, hF0, hF1, hF2] using hτ t'