perm_second_derivative_odd_exists_witnesses
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
- perm_second_derivative_odd_not_injOnFor any integer $k \ge 1$, the discrete second derivative map on $\mathrm{Sym}_{2k+1} \setminus \{e, e^r\}$ is not injective.
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.
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).
⟨perm_second_derivative_odd_exists_witnesses_sigma_val k t.1, by unfold perm_second_derivative_odd_exists_witnesses_sigma_val; split_ifs <;> omega⟩
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).
⟨perm_second_derivative_odd_exists_witnesses_pi_val k t.1, by unfold perm_second_derivative_odd_exists_witnesses_pi_val; split_ifs <;> omega⟩
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.
uses
Fin.ext,congr_argintro 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
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.
uses
Fin.ext,congr_argintro 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
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.
refine ⟨perm_second_derivative_odd_exists_witnesses_sigma_perm k, perm_second_derivative_odd_exists_witnesses_pi_perm k, ?_, ?_, ?_, ?_, ?_, ?_⟩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.
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
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.
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
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.
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
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.
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
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.
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
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.
· 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).
- The equality of the discrete second derivatives on the interior indices is verified by case analysis via omega, which handles the combinations of whether ℓ, ℓ - 1, and ℓ - 2 cross the modular wrap-around threshold k.
- The bijections σ and π are promoted to permutations in Equiv.Perm using bijective_of_finite, which relies on the finiteness of Fin (2 * k + 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
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.
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