perm_second_derivative_odd_not_injOn
For any integer $k \ge 1$, the discrete second derivative map on $\mathrm{Sym}_{2k+1} \setminus \{e, e^r\}$ is not injective.
Statement
theorem perm_second_derivative_odd_not_injOn (k : ℕ) (hk : 1 ≤ k) :
¬ Set.InjOn (perm_second_derivative (n := 2 * k + 1))
({1, Fin.revPerm} : Set (Equiv.Perm (Fin (2 * k + 1))))ᶜ- Formalizes
- arXiv:2610.38237 Theorem 2.10 -- Inflection sets of permutations
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- not_injOn_of_exists_neA function $f$ is not injective on a set $s$ if there exist distinct elements $x, y \in s$ such that $f(x) = f(y)$.
- perm_second_derivative_odd_exists_witnessesFor any integer $k \ge 1$, there exist two distinct permutations $\sigma, \pi \in \mathrm{Sym}_{2k+1}$, neither of which is the identity…
- perm_second_derivativeFor a permutation σ : Equiv.Perm (Fin n) and a natural number ℓ : ℕ, the discrete second derivative perm_second_derivative σ ℓ : ℤ is (σ…
Read back from the Lean
For every natural number $k$ such that $1 \le k$, the function perm_second_derivative on permutations of $\mathrm{Fin}(2k + 1)$ is not injective on the complement of the set $\{1, \mathrm{Fin.revPerm}\}$. That is, there exist two distinct permutations $\sigma_1, \sigma_2$ of $\mathrm{Fin}(2k + 1)$, neither of which is the identity permutation nor the reversal permutation $\mathrm{Fin.revPerm}$, such that perm_second_derivative σ₁ = perm_second_derivative σ₂ as functions $\mathbb{N} \to \mathbb{Z}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by exhibiting an explicit pair of witness permutations. For any odd size $2k+1$ with $k \ge 1$, a helper lemma provides two distinct permutations $\sigma$ and $\pi$, neither equal to the identity nor the reversal permutation, that have the same discrete second derivative. Applying a general criterion for non-injectivity, verifying that these witnesses belong to the complement of $\{1, \mathrm{revPerm}\}$ and share the same image completes the proof.
There exist two distinct permutations $\sigma$ and $\pi$ of $2k+1$ elements, neither equal to the identity nor the reversal permutation, whose discrete second derivatives coincide.
Applying the witness lemma `perm_second_derivative_odd_exists_witnesses` to $k \ge 1$ produces permutations $\sigma$ and $\pi$ along with hypotheses asserting that $\sigma \ne \pi$, $\sigma \ne 1$, $\sigma \ne \mathrm{revPerm}$, $\pi \ne 1$, $\pi \ne \mathrm{revPerm}$, and $\mathrm{perm\_second\_derivative}(\sigma) = \mathrm{perm\_second\_derivative}(\pi)$.
uses
perm_second_derivative_odd_exists_witnessesobtain ⟨σ, π, hne, hσ1, hσrev, hπ1, hπrev, hfeq⟩ := perm_second_derivative_odd_exists_witnesses k hkTo prove non-injectivity of the discrete second derivative on $\{1, \mathrm{revPerm}\}^c$, it suffices to show that $\sigma$ and $\pi$ lie in $\{1, \mathrm{revPerm}\}^c$, are distinct, and have the same discrete second derivative.
Applying the criterion `not_injOn_of_exists_ne` with the witnesses $\sigma$ and $\pi$ reduces non-injectivity on the complement to four obligations: $\sigma \in \{1, \mathrm{revPerm}\}^c$, $\pi \in \{1, \mathrm{revPerm}\}^c$, $\sigma \ne \pi$, and equality of their images under `perm_second_derivative`.
uses
not_injOn_of_exists_neapply not_injOn_of_exists_ne (perm_second_derivative (n := 2 * k + 1)) _ σ πBoth $\sigma$ and $\pi$ belong to $\{1, \mathrm{revPerm}\}^c$.
Membership in $\{1, \mathrm{revPerm}\}^c$ means being distinct from both $1$ and $\mathrm{revPerm}$. The simplification tactic unfolds complement and pair membership, resolving the goal for $\sigma$ from $\sigma \ne 1$ and $\sigma \ne \mathrm{revPerm}$ (line 7), and for $\pi$ from $\pi \ne 1$ and $\pi \ne \mathrm{revPerm}$ (line 8).
· simp [hσ1, hσrev] · simp [hπ1, hπrev]
The witnesses $\sigma$ and $\pi$ are distinct and have identical discrete second derivatives.
The two remaining obligations, $\sigma \ne \pi$ and $\mathrm{perm\_second\_derivative}(\sigma) = \mathrm{perm\_second\_derivative}(\pi)$, are discharged directly by the hypotheses `hne` and `hfeq` provided by the witness lemma.
· exact hne · exact hfeq
perm_second_derivative_odd_exists_witnesses- For any $k \ge 1$, there exist two distinct permutations of $2k+1$ elements, neither equal to the identity nor the reversal permutation, that have identical discrete second derivatives.
not_injOn_of_exists_ne- A function $f$ is not injective on a set $s$ if there exist two distinct elements $x, y \in s$ such that $f(x) = f(y)$.
- Lines 7 and 8 use `simp` to discharge membership in the set complement by automatically unfolding the definitions of complement and pair membership, reducing them to the hypotheses that the permutations differ from the identity and the reversal permutation.
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.
/-- Theorem 2.10 of arXiv:2610.38237: the discrete second derivative on permutations of odd length 2k+1 is not injective outside {e, e^r}. -/theorem perm_second_derivative_odd_not_injOn (k : ℕ) (hk : 1 ≤ k) : ¬ Set.InjOn (perm_second_derivative (n := 2 * k + 1)) ({1, Fin.revPerm} : Set (Equiv.Perm (Fin (2 * k + 1))))ᶜ := by obtain ⟨σ, π, hne, hσ1, hσrev, hπ1, hπrev, hfeq⟩ := perm_second_derivative_odd_exists_witnesses k hk apply not_injOn_of_exists_ne (perm_second_derivative (n := 2 * k + 1)) _ σ π · simp [hσ1, hσrev] · simp [hπ1, hπrev] · exact hne · exact hfeq