wild_joint_canonical_matching_is_involution
For odd q>=3, the canonical matching on Fin(3q) is precisely the off-diagonal part of an involution whose unique fixed point is0. The odd-q hypothesis prevents an extra isolated vertex.
Statement
theorem wild_joint_canonical_matching_is_involution (q : ℕ) (hq : 3 ≤ q) (hodd : q % 2 = 1) : ∃ f : Equiv.Perm (Fin (3*q)), Function.Involutive f ∧ (∀ x, f x = x ↔ x = (⟨0,by omega⟩ : Fin (3*q))) ∧ ∀ x y, wild_joint_canonical_matching q x y ↔ x ≠ y ∧ f x = y
- Source
- IN-382 / OP-306 campaign9, 2026-10-30. Standard finite matching symmetry supporting the mixed-moment route for https://arxiv.org/html/2610.22142v1. Exact experiment9566 exposed the missing parity assumption. The original false helper remains retired and its proof record is preserved. No wild-number bound or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- wild_joint_canonical_matchingThe fixed matching on Fin (3q) with isolated vertex 0 and pairs {2k-1, 2k} for k >= 1: (1,2),(3,4),(5,6),...
- Used by 2
- wild_normalized_color_canonical_isomorphismFor odd q>=3, every chosen color of a symmetric idempotent row-injective array on Fin(3q) is carried to the canonical matching by a vertex…
- wild_joint_alpha_type_well_defined_oddFor odd q>=3, any two three-element subsets of the same canonical type have equal conditional whole-bad probabilities alpha. This…
The proof, explained
The proof explicitly constructs an involution p on Fin (3q) that fixes 0 and pairs every odd integer 2k - 1 with 2k. Since p is an involution, it is its own inverse and defines a permutation of Fin (3q). The proof then verifies by case analysis that 0 is the unique fixed point of p, and that the relation x ≠ y ∧ p x = y matches the definition of wild_joint_canonical_matching on every ordered pair of elements.
The function p on Fin (3q) that fixes 0 and swaps each odd number x with x + 1 is well-defined. automation
The zero element in Fin (3q) is valid because q ≥ 3 implies 0 < 3q. We define p(x) by cases: 0 maps to 0, odd x maps to x + 1, and positive even x maps to x - 1. In each case, linear arithmetic (omega) verifies that the value is strictly less than 3q, using the fact that q is odd.
(∀ x, f x = x ↔ x = (⟨0,by omega⟩ : Fin (3*q))) ∧ ∀ x y, wild_joint_canonical_matching q x y ↔ x ≠ y ∧ f x = y := by let p : Fin (3*q) → Fin (3*q) := fun x => ⟨if x.val = 0 then 0 else if x.val % 2 = 1 then x.val+1 else x.val-1, by have hx := x.isLt split_ifs <;> omega⟩
The function p is an involution, so p (p x) = x for all x.
By extensionality (Fin.ext), it suffices to check the identity on underlying values. If x = 0, p(0) = 0 and p(p(0)) = 0. If x is odd, p(x) = x + 1 is positive and even, so p(x + 1) = (x + 1) - 1 = x. If x is positive and even, p(x) = x - 1 is positive and odd, so p(x - 1) = (x - 1) + 1 = x. In each case, rewriting with the definition of p and linear arithmetic closes the goal.
uses
Fin.exthave hp : Function.Involutive p := by intro x apply Fin.ext by_cases hx0 : x.val = 0 · simp [p,hx0] · by_cases hxodd : x.val % 2 = 1 · have hn : x.val+1 ≠ 0 := by omega have heven : (x.val+1)%2 ≠ 1 := by omega simp [p,hx0,hxodd,hn,heven] · have hn : x.val-1 ≠ 0 := by omega have hprev : (x.val-1)%2 = 1 := by omega simp [p,hx0,hxodd,hn,hprev] omega
The map p forms an involutive permutation f, reducing the theorem to verifying its fixed points and the matching condition.
Because p is an involution, it is its own inverse, so it defines an element f of Equiv.Perm (Fin (3q)) that is involutive. Supplying f as the existential witness leaves two goals: showing that 0 is the only fixed point of p, and that wild_joint_canonical_matching coincides with the off-diagonal graph of p.
refine ⟨⟨p,p,hp,hp⟩,hp,?_,?_⟩0 is the unique fixed point of p. automation
We convert equality in Fin (3q) to natural number equality with Fin.ext_iff and unfold p. If x = 0, 0 = 0 is true. If x is odd, x + 1 = x has no solution. If x is even and non-zero, x - 1 = x has no solution. Linear integer arithmetic (omega) verifies each branch.
uses
Fin.ext_iff· intro x change p x = x ↔ x = (⟨0,by omega⟩ : Fin (3*q)) simp only [Fin.ext_iff,p] split_ifs <;> omega
Two vertices x and y are paired by wild_joint_canonical_matching if and only if x ≠ y and p x = y. automation
Unfolding the definition of wild_joint_canonical_matching, the matching pairs an odd positive number k with k + 1. By totality of the order on ℕ (le_total), either x ≤ y or y ≤ x. If x ≤ y, min x y = x and max x y = y by min_eq_left and max_eq_right; case analysis on x shows that the matching condition holds exactly when x is odd and y = x + 1, matching the definition of p. If y ≤ x, min x y = y and max x y = x by min_eq_right and max_eq_left; case analysis shows the condition holds exactly when x is positive even and y = x - 1, which again matches p x = y. Linear arithmetic (omega) finishes all cases.
uses
Fin.ext_iff,le_total,min_eq_left,max_eq_right,min_eq_right,max_eq_left· intro x y change wild_joint_canonical_matching q x y ↔ x ≠ y ∧ p x = y simp only [wild_joint_canonical_matching,Fin.ext_iff,p] have hx := x.isLt have hy := y.isLt rcases le_total x.val y.val with h|h · rw [min_eq_left h,max_eq_right h] split_ifs <;> omega · rw [min_eq_right h,max_eq_left h] split_ifs <;> omega
Fin.ext- Two elements of Fin n are equal if their underlying natural numbers are equal.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
le_total- For any two elements in a linear order, either a ≤ b or b ≤ a.
min_eq_left- If a ≤ b, then min a b = a.
max_eq_right- If a ≤ b, then max a b = b.
min_eq_right- If b ≤ a, then min a b = b.
max_eq_left- If b ≤ a, then max a b = a.
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.
open Finsetopen scoped BigOperators Classicalset_option maxHeartbeats 6000000set_option maxRecDepth 100000set_option synthInstance.maxSize 10000theorem wild_joint_canonical_matching_is_involution (q : ℕ) (hq : 3 ≤ q) (hodd : q % 2 = 1) : ∃ f : Equiv.Perm (Fin (3*q)), Function.Involutive f ∧ (∀ x, f x = x ↔ x = (⟨0,by omega⟩ : Fin (3*q))) ∧ ∀ x y, wild_joint_canonical_matching q x y ↔ x ≠ y ∧ f x = y := by let p : Fin (3*q) → Fin (3*q) := fun x => ⟨if x.val = 0 then 0 else if x.val % 2 = 1 then x.val+1 else x.val-1, by have hx := x.isLt split_ifs <;> omega⟩ have hp : Function.Involutive p := by intro x apply Fin.ext by_cases hx0 : x.val = 0 · simp [p,hx0] · by_cases hxodd : x.val % 2 = 1 · have hn : x.val+1 ≠ 0 := by omega have heven : (x.val+1)%2 ≠ 1 := by omega simp [p,hx0,hxodd,hn,heven] · have hn : x.val-1 ≠ 0 := by omega have hprev : (x.val-1)%2 = 1 := by omega simp [p,hx0,hxodd,hn,hprev] omega refine ⟨⟨p,p,hp,hp⟩,hp,?_,?_⟩ · intro x change p x = x ↔ x = (⟨0,by omega⟩ : Fin (3*q)) simp only [Fin.ext_iff,p] split_ifs <;> omega · intro x y change wild_joint_canonical_matching q x y ↔ x ≠ y ∧ p x = y simp only [wild_joint_canonical_matching,Fin.ext_iff,p] have hx := x.isLt have hy := y.isLt rcases le_total x.val y.val with h|h · rw [min_eq_left h,max_eq_right h] split_ifs <;> omega · rw [min_eq_right h,max_eq_left h] split_ifs <;> omega