AFTD Auto-Formalizing Theoretical Domains

wild_joint_canonical_matching_is_involution

theoremverified

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
Used by 2

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.

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

    lines 10–15

          (∀ 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⟩
  2. 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.

    lines 16–28

    uses Fin.ext

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

    line 29

      refine ⟨⟨p,p,hp,hp⟩,hp,?_,?_⟩
  4. 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.

    lines 30–33

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

    lines 34–43

    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

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