AFTD Auto-Formalizing Theoretical Domains

perm_second_derivative_odd_exists_witnesses

theoremverified

For any integer $k \ge 1$, there exist two distinct permutations $\sigma, \pi \in \mathrm{Sym}_{2k+1}$, neither of which is the identity or its reverse, having the same discrete second derivative.

Statement

theorem perm_second_derivative_odd_exists_witnesses (k : ℕ) (hk : 1 ≤ k) :
    ∃ (σ π : Equiv.Perm (Fin (2 * k + 1))),
      σ ≠ π ∧
      σ ≠ 1 ∧ σ ≠ Fin.revPerm ∧
      π ≠ 1 ∧ π ≠ Fin.revPerm ∧
      perm_second_derivative σ = perm_second_derivative π
Source
scout/2610-38237-inflection-sets-of-permutations.md:383
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • perm_second_derivativeFor a permutation σ : Equiv.Perm (Fin n) and a natural number ℓ : ℕ, the discrete second derivative perm_second_derivative σ ℓ : ℤ is (σ…
Used by 1

Read back from the Lean

For every natural number $k \ge 1$, there exist two permutations $\sigma$ and $\pi$ of $\mathrm{Fin}(2k + 1)$ such that: 1. $\sigma \neq \pi$, 2. $\sigma$ is neither the identity permutation $1$ nor the reversal permutation $\mathrm{Fin.revPerm}$, 3. $\pi$ is neither the identity permutation $1$ nor the reversal permutation $\mathrm{Fin.revPerm}$, and 4. The discrete second derivatives of $\sigma$ and $\pi$ are equal as functions from $\mathbb{N}$ to $\mathbb{Z}$ ($\mathrm{perm\_second\_derivative}\ \sigma = \mathrm{perm\_second\_derivative}\ \pi$).

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

To prove the existence of two distinct non-trivial permutations on Fin (2 * k + 1) with identical discrete second derivatives, we construct explicit witnesses σ and π. Identifying Fin (2 * k + 1) with ℤ/(2k + 1)ℤ, the map σ(t) ≡ 2t is doubling and π(t) ≡ t + k is a cyclic shift; because gcd(2, 2k + 1) = 1, both are permutations. Evaluating at 0 and 1 distinguishes σ and π from each other, the identity, and the reversal permutation since k ≥ 1. Finally, their discrete second derivatives coincide everywhere because the linear terms cancel in the second difference, while both maps experience identical wrap-around jumps of -(2k + 1) at the same transition points.

  1. The piecewise function σ on ℕ maps {0, …, 2k} into {0, …, 2k}.

    To define σ as a map from Fin (2 * k + 1) to itself, we must verify that its value on any t < 2k + 1 is strictly less than 2k + 1. Unfolding the definition of σ, if t ≤ k, then 2t ≤ 2k < 2k + 1. If t > k, since t ≤ 2k, we have 2t - (2k + 1) ≤ 4k - (2k + 1) = 2k - 1 < 2k + 1. Both bounds are closed by linear arithmetic (omega).

    lines 8–9

      ⟨perm_second_derivative_odd_exists_witnesses_sigma_val k t.1, by
        unfold perm_second_derivative_odd_exists_witnesses_sigma_val; split_ifs <;> omega⟩
  2. The piecewise function π on ℕ maps {0, …, 2k} into {0, …, 2k}.

    To ensure π is well-defined on Fin (2 * k + 1), we check that π(t) < 2k + 1 whenever t < 2k + 1. Unfolding the definition, if t ≤ k, then t + k ≤ 2k < 2k + 1. If t > k, then t - (k + 1) < t < 2k + 1. Both branches are verified by linear arithmetic (omega).

    lines 12–13

      ⟨perm_second_derivative_odd_exists_witnesses_pi_val k t.1, by
        unfold perm_second_derivative_odd_exists_witnesses_pi_val; split_ifs <;> omega⟩
  3. The map σ : Fin (2 * k + 1) → Fin (2 * k + 1) is injective.

    Assume σ(a) = σ(b) for a, b ∈ Fin (2 * k + 1). By Fin.ext, it suffices to show that their underlying values in ℕ are equal. Taking values via congr_arg and unfolding the definition of σ, we consider the four cases according to whether a ≤ k and b ≤ k. When both inputs fall in the same branch, 2a = 2b or 2a - (2k + 1) = 2b - (2k + 1), which directly implies a = b. The mixed branches 2a = 2b - (2k + 1) and 2a - (2k + 1) = 2b are impossible because the left- and right-hand sides have different parities. Linear arithmetic (omega) closes all cases.

    lines 17–22

    uses Fin.ext, congr_arg

      intro a b hab
      apply Fin.ext
      have h := congr_arg Fin.val hab
      dsimp [perm_second_derivative_odd_exists_witnesses_sigma_fn,
             perm_second_derivative_odd_exists_witnesses_sigma_val] at h
      split_ifs at h <;> omega
  4. The map π : Fin (2 * k + 1) → Fin (2 * k + 1) is injective.

    Assume π(a) = π(b). By Fin.ext, it suffices to show a = b. Applying congr_arg to extract numerical values and unfolding the definition of π, we split into cases based on whether a ≤ k and b ≤ k. If both inputs lie in the same branch, a + k = b + k or a - (k + 1) = b - (k + 1), yielding a = b. The mixed branches would require |a - b| = 2k + 1, which is impossible because both a and b are strictly less than 2k + 1. Linear arithmetic (omega) resolves all branches.

    lines 26–31

    uses Fin.ext, congr_arg

      intro a b hab
      apply Fin.ext
      have h := congr_arg Fin.val hab
      dsimp [perm_second_derivative_odd_exists_witnesses_pi_fn,
             perm_second_derivative_odd_exists_witnesses_pi_val] at h
      split_ifs at h <;> omega
  5. It suffices to show that the permutations σ and π induced by these maps are distinct, neither is the identity or its reversal, and their second derivatives agree.

    Because the domain Fin (2 * k + 1) is finite, the injective maps σ and π are automatically bijections, defining permutations of Fin (2 * k + 1). We instantiate the existential witnesses with these permutations, reducing the goal to verifying six conditions: σ ≠ π, σ ≠ 1, σ ≠ Fin.revPerm, π ≠ 1, π ≠ Fin.revPerm, and that their second derivatives agree everywhere.

    lines 50–51

      refine ⟨perm_second_derivative_odd_exists_witnesses_sigma_perm k,
              perm_second_derivative_odd_exists_witnesses_pi_perm k, ?_, ?_, ?_, ?_, ?_, ?_⟩
  6. The permutations σ and π are not equal (σ ≠ π).

    Suppose, for contradiction, that σ = π. Evaluating both sides at 0 and taking values via congr_arg, we must have σ(0) = π(0). By definition, σ(0) = 2 * 0 = 0, while π(0) = 0 + k = k, which forces k = 0. This contradicts the assumption that 1 ≤ k.

    lines 52–62

    uses congr_arg

      · intro h
        have h0 : perm_second_derivative_odd_exists_witnesses_sigma_perm k ⟨0, by omega⟩ =
                  perm_second_derivative_odd_exists_witnesses_pi_perm k ⟨0, by omega⟩ := by rw [h]
        have hval := congr_arg Fin.val h0
        dsimp [perm_second_derivative_odd_exists_witnesses_sigma_perm,
               perm_second_derivative_odd_exists_witnesses_pi_perm,
               perm_second_derivative_odd_exists_witnesses_sigma_fn,
               perm_second_derivative_odd_exists_witnesses_pi_fn,
               perm_second_derivative_odd_exists_witnesses_sigma_val,
               perm_second_derivative_odd_exists_witnesses_pi_val] at hval
        omega
  7. The permutation σ is not the identity (σ ≠ 1).

    Suppose, for contradiction, that σ = 1. Evaluating at 1 and extracting numerical values via congr_arg gives σ(1) = 1. Since 1 ≤ k, the definition of σ gives σ(1) = 2 * 1 = 2. This implies 2 = 1, a contradiction.

    lines 63–70

    uses congr_arg

      · intro h
        have h1 : perm_second_derivative_odd_exists_witnesses_sigma_perm k ⟨1, by omega⟩ = ⟨1, by omega⟩ := by rw [h]; rfl
        have hval := congr_arg Fin.val h1
        dsimp [perm_second_derivative_odd_exists_witnesses_sigma_perm,
               perm_second_derivative_odd_exists_witnesses_sigma_fn,
               perm_second_derivative_odd_exists_witnesses_sigma_val] at hval
        split_ifs at hval
        omega
  8. The permutation σ is not the reversal permutation (σ ≠ Fin.revPerm).

    Suppose, for contradiction, that σ = Fin.revPerm. Evaluating at 0 and extracting values via congr_arg gives σ(0) = Fin.revPerm(0). Using Fin.revPerm_apply and Fin.val_rev, the reversal of 0 in Fin (2 * k + 1) has value (2 * k + 1) - (0 + 1) = 2 * k. But σ(0) = 0, so 0 = 2 * k. Since 1 ≤ k, this contradicts 2 * k > 0.

    lines 71–80

    uses congr_arg, Fin.revPerm_apply, Fin.val_rev

      · intro h
        have h0 : perm_second_derivative_odd_exists_witnesses_sigma_perm k ⟨0, by omega⟩ = Fin.revPerm ⟨0, by omega⟩ := by rw [h]
        have hval := congr_arg Fin.val h0
        have hr : ((Fin.revPerm (⟨0, by omega⟩ : Fin (2 * k + 1))) : Fin (2 * k + 1)).val = 2 * k := by
          rw [Fin.revPerm_apply, Fin.val_rev]; rfl
        rw [hr] at hval
        dsimp [perm_second_derivative_odd_exists_witnesses_sigma_perm,
               perm_second_derivative_odd_exists_witnesses_sigma_fn,
               perm_second_derivative_odd_exists_witnesses_sigma_val] at hval
        omega
  9. The permutation π is not the identity (π ≠ 1).

    Suppose, for contradiction, that π = 1. Evaluating at 0 and taking values with congr_arg yields π(0) = 0. By definition, π(0) = 0 + k = k, which implies k = 0, contradicting 1 ≤ k.

    lines 81–87

    uses congr_arg

      · intro h
        have h0 : perm_second_derivative_odd_exists_witnesses_pi_perm k ⟨0, by omega⟩ = ⟨0, by omega⟩ := by rw [h]; rfl
        have hval := congr_arg Fin.val h0
        dsimp [perm_second_derivative_odd_exists_witnesses_pi_perm,
               perm_second_derivative_odd_exists_witnesses_pi_fn,
               perm_second_derivative_odd_exists_witnesses_pi_val] at hval
        omega
  10. The permutation π is not the reversal permutation (π ≠ Fin.revPerm).

    Suppose, for contradiction, that π = Fin.revPerm. Evaluating at 0 and applying congr_arg gives π(0) = Fin.revPerm(0). By Fin.revPerm_apply and Fin.val_rev, Fin.revPerm(0) = 2 * k, while π(0) = k. Thus k = 2 * k, which implies k = 0, contradicting 1 ≤ k.

    lines 88–97

    uses congr_arg, Fin.revPerm_apply, Fin.val_rev

      · intro h
        have h0 : perm_second_derivative_odd_exists_witnesses_pi_perm k ⟨0, by omega⟩ = Fin.revPerm ⟨0, by omega⟩ := by rw [h]
        have hval := congr_arg Fin.val h0
        have hr : ((Fin.revPerm (⟨0, by omega⟩ : Fin (2 * k + 1))) : Fin (2 * k + 1)).val = 2 * k := by
          rw [Fin.revPerm_apply, Fin.val_rev]; rfl
        rw [hr] at hval
        dsimp [perm_second_derivative_odd_exists_witnesses_pi_perm,
               perm_second_derivative_odd_exists_witnesses_pi_fn,
               perm_second_derivative_odd_exists_witnesses_pi_val] at hval
        omega
  11. The discrete second derivatives of σ and π are identical everywhere.

    By function extensionality, it suffices to show that the second derivatives of σ and π agree at every index ℓ ∈ ℕ. Unfolding perm_second_derivative, if ℓ is outside the range 2 ≤ ℓ ≤ 2k, both second derivatives are 0 by definition. When 2 ≤ ℓ ≤ 2k, the second derivative equals τ(ℓ) + τ(ℓ - 2) - 2 * τ(ℓ - 1) for τ ∈ {σ, π}. Unfolding the piecewise definitions and splitting into cases on whether each of ℓ, ℓ - 1, and ℓ - 2 is ≤ k, both permutations undergo the exact same modular jump of -(2k + 1) at the same threshold k. In each of the resulting cases, linear integer arithmetic (omega) verifies that the second derivatives match.

    lines 98–108

      · funext ℓ
        unfold perm_second_derivative
        split_ifs with h
        · dsimp [perm_second_derivative_odd_exists_witnesses_sigma_perm,
                 perm_second_derivative_odd_exists_witnesses_pi_perm,
                 perm_second_derivative_odd_exists_witnesses_sigma_fn,
                 perm_second_derivative_odd_exists_witnesses_pi_fn]
          unfold perm_second_derivative_odd_exists_witnesses_sigma_val
                 perm_second_derivative_odd_exists_witnesses_pi_val
          split_ifs <;> omega
        · rfl
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
congr_arg
If two inputs are equal, then any function applied to them yields equal values.
Fin.revPerm_apply
The reversal permutation Fin.revPerm applied to an index i equals the reversed index i.rev.
Fin.val_rev
The natural number value of the reversed index i.rev in Fin n is n - (i + 1).

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

def perm_second_derivative_odd_exists_witnesses_sigma_val (k t : ℕ) : ℕ :=  if t ≤ k then 2 * t else 2 * t - (2 * k + 1)def perm_second_derivative_odd_exists_witnesses_pi_val (k t : ℕ) : ℕ :=  if t ≤ k then t + k else t - (k + 1)def perm_second_derivative_odd_exists_witnesses_sigma_fn (k : ℕ) (t : Fin (2 * k + 1)) : Fin (2 * k + 1) :=  ⟨perm_second_derivative_odd_exists_witnesses_sigma_val k t.1, by    unfold perm_second_derivative_odd_exists_witnesses_sigma_val; split_ifs <;> omega⟩def perm_second_derivative_odd_exists_witnesses_pi_fn (k : ℕ) (t : Fin (2 * k + 1)) : Fin (2 * k + 1) :=  ⟨perm_second_derivative_odd_exists_witnesses_pi_val k t.1, by    unfold perm_second_derivative_odd_exists_witnesses_pi_val; split_ifs <;> omega⟩theorem perm_second_derivative_odd_exists_witnesses_sigma_fn_inj (k : ℕ) :    Function.Injective (perm_second_derivative_odd_exists_witnesses_sigma_fn k) := by  intro a b hab  apply Fin.ext  have h := congr_arg Fin.val hab  dsimp [perm_second_derivative_odd_exists_witnesses_sigma_fn,         perm_second_derivative_odd_exists_witnesses_sigma_val] at h  split_ifs at h <;> omegatheorem perm_second_derivative_odd_exists_witnesses_pi_fn_inj (k : ℕ) :    Function.Injective (perm_second_derivative_odd_exists_witnesses_pi_fn k) := by  intro a b hab  apply Fin.ext  have h := congr_arg Fin.val hab  dsimp [perm_second_derivative_odd_exists_witnesses_pi_fn,         perm_second_derivative_odd_exists_witnesses_pi_val] at h  split_ifs at h <;> omeganoncomputable def perm_second_derivative_odd_exists_witnesses_sigma_perm (k : ℕ) :    Equiv.Perm (Fin (2 * k + 1)) :=  Equiv.ofBijective (perm_second_derivative_odd_exists_witnesses_sigma_fn k)    ((perm_second_derivative_odd_exists_witnesses_sigma_fn_inj k).bijective_of_finite)noncomputable def perm_second_derivative_odd_exists_witnesses_pi_perm (k : ℕ) :    Equiv.Perm (Fin (2 * k + 1)) :=  Equiv.ofBijective (perm_second_derivative_odd_exists_witnesses_pi_fn k)    ((perm_second_derivative_odd_exists_witnesses_pi_fn_inj k).bijective_of_finite)/-- Existence of distinct permutations of odd order 2k+1, neither identity nor its reverse, with identical second derivatives. -/theorem perm_second_derivative_odd_exists_witnesses (k : ℕ) (hk : 1 ≤ k) :    ∃ (σ π : Equiv.Perm (Fin (2 * k + 1))),      σ ≠ π ∧      σ ≠ 1 ∧ σ ≠ Fin.revPerm ∧      π ≠ 1 ∧ π ≠ Fin.revPerm ∧      perm_second_derivative σ = perm_second_derivative π := by  refine ⟨perm_second_derivative_odd_exists_witnesses_sigma_perm k,          perm_second_derivative_odd_exists_witnesses_pi_perm k, ?_, ?_, ?_, ?_, ?_, ?_⟩  · intro h    have h0 : perm_second_derivative_odd_exists_witnesses_sigma_perm k ⟨0, by omega⟩ =              perm_second_derivative_odd_exists_witnesses_pi_perm k ⟨0, by omega⟩ := by rw [h]    have hval := congr_arg Fin.val h0    dsimp [perm_second_derivative_odd_exists_witnesses_sigma_perm,           perm_second_derivative_odd_exists_witnesses_pi_perm,           perm_second_derivative_odd_exists_witnesses_sigma_fn,           perm_second_derivative_odd_exists_witnesses_pi_fn,           perm_second_derivative_odd_exists_witnesses_sigma_val,           perm_second_derivative_odd_exists_witnesses_pi_val] at hval    omega  · intro h    have h1 : perm_second_derivative_odd_exists_witnesses_sigma_perm k ⟨1, by omega⟩ = ⟨1, by omega⟩ := by rw [h]; rfl    have hval := congr_arg Fin.val h1    dsimp [perm_second_derivative_odd_exists_witnesses_sigma_perm,           perm_second_derivative_odd_exists_witnesses_sigma_fn,           perm_second_derivative_odd_exists_witnesses_sigma_val] at hval    split_ifs at hval    omega  · intro h    have h0 : perm_second_derivative_odd_exists_witnesses_sigma_perm k ⟨0, by omega⟩ = Fin.revPerm ⟨0, by omega⟩ := by rw [h]    have hval := congr_arg Fin.val h0    have hr : ((Fin.revPerm (⟨0, by omega⟩ : Fin (2 * k + 1))) : Fin (2 * k + 1)).val = 2 * k := by      rw [Fin.revPerm_apply, Fin.val_rev]; rfl    rw [hr] at hval    dsimp [perm_second_derivative_odd_exists_witnesses_sigma_perm,           perm_second_derivative_odd_exists_witnesses_sigma_fn,           perm_second_derivative_odd_exists_witnesses_sigma_val] at hval    omega  · intro h    have h0 : perm_second_derivative_odd_exists_witnesses_pi_perm k ⟨0, by omega⟩ = ⟨0, by omega⟩ := by rw [h]; rfl    have hval := congr_arg Fin.val h0    dsimp [perm_second_derivative_odd_exists_witnesses_pi_perm,           perm_second_derivative_odd_exists_witnesses_pi_fn,           perm_second_derivative_odd_exists_witnesses_pi_val] at hval    omega  · intro h    have h0 : perm_second_derivative_odd_exists_witnesses_pi_perm k ⟨0, by omega⟩ = Fin.revPerm ⟨0, by omega⟩ := by rw [h]    have hval := congr_arg Fin.val h0    have hr : ((Fin.revPerm (⟨0, by omega⟩ : Fin (2 * k + 1))) : Fin (2 * k + 1)).val = 2 * k := by      rw [Fin.revPerm_apply, Fin.val_rev]; rfl    rw [hr] at hval    dsimp [perm_second_derivative_odd_exists_witnesses_pi_perm,           perm_second_derivative_odd_exists_witnesses_pi_fn,           perm_second_derivative_odd_exists_witnesses_pi_val] at hval    omega  · funext ℓ    unfold perm_second_derivative    split_ifs with h    · dsimp [perm_second_derivative_odd_exists_witnesses_sigma_perm,             perm_second_derivative_odd_exists_witnesses_pi_perm,             perm_second_derivative_odd_exists_witnesses_sigma_fn,             perm_second_derivative_odd_exists_witnesses_pi_fn]      unfold perm_second_derivative_odd_exists_witnesses_sigma_val             perm_second_derivative_odd_exists_witnesses_pi_val      split_ifs <;> omega    · rfl
See it in the graphDiscuss this resultChallenge it