AFTD Auto-Formalizing Theoretical Domains

perm_second_derivative_odd_not_injOn

theoremverifiedformalization

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.

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

    line 5

    uses perm_second_derivative_odd_exists_witnesses

      obtain ⟨σ, π, hne, hσ1, hσrev, hπ1, hπrev, hfeq⟩ := perm_second_derivative_odd_exists_witnesses k hk
  2. To 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`.

    line 6

    uses not_injOn_of_exists_ne

      apply not_injOn_of_exists_ne (perm_second_derivative (n := 2 * k + 1)) _ σ π
  3. 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).

    lines 7–8

      · simp [hσ1, hσrev]
      · simp [hπ1, hπrev]
  4. 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.

    lines 9–10

      · 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)$.

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

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