perm_second_derivative_trans_revPerm
Reversing the values of a permutation σ of Fin n (composing with Fin.revPerm, v ↦ n-1-v) negates its discrete second derivative at every ℓ: perm_second_derivative (σ.trans Fin.revPerm) ℓ = - perm_second_derivative σ ℓ.
Statement
theorem perm_second_derivative_trans_revPerm {n : ℕ} (σ : Equiv.Perm (Fin n)) (ℓ : ℕ) :
perm_second_derivative (σ.trans Fin.revPerm) ℓ = - perm_second_derivative σ ℓ- Source
- arXiv:2610.38237 (Inflection sets of permutations), Example 3.4: the value-reversal symmetry used as its WLOG step
- Verified
- 07 Nov 2026
- Axioms
Quot.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_inflection_set_trans_revPermReversing the values of a permutation σ of Fin n (σ.trans Fin.revPerm) does not change its inflection set: perm_inflection_set (σ.trans…
The proof, explained
The discrete second derivative of a sequence evaluates the linear combination x(ℓ) + x(ℓ - 2) - 2x(ℓ - 1), whose coefficients sum to 1 + 1 - 2 = 0. Composing a permutation σ with Fin.revPerm replaces each value v with (n - 1) - v; because the constant n - 1 cancels in the second difference, the resulting second derivative is the exact negation of the original. The proof unfolds the definition, splits on whether ℓ is in range, pushes the integer cast through the natural subtractions, and verifies the resulting algebraic identity with ring arithmetic.
The equality reduces to two cases depending on whether 2 ≤ ℓ ≤ n - 1.
Unfolding the definition of `perm_second_derivative` exposes an if-then-else condition on whether 2 ≤ ℓ ≤ n - 1. A case split via `split_ifs` separates the argument into the valid index case and the out-of-bounds case.
unfold perm_second_derivative split_ifs with h
In the valid index range, the reversed permutation values evaluate to n - (σ(k) + 1).
Rewriting with `Equiv.trans_apply` evaluates the composition (σ.trans Fin.revPerm) at each offset. Then `Fin.revPerm_apply` and `Fin.val_rev` rewrite the reversed Fin values to their numerical form n - (σ(k) + 1).
uses
Equiv.trans_apply,Fin.revPerm_apply,Fin.val_rev· simp only [Equiv.trans_apply, Fin.revPerm_apply, Fin.val_rev]The values σ(ℓ), σ(ℓ - 2), and σ(ℓ - 1) are strictly less than n.
The hypothesis 2 ≤ ℓ ≤ n - 1 implies by linear arithmetic (via `omega`) that ℓ < n, ℓ - 2 < n, and ℓ - 1 < n. Each permutation value therefore belongs to Fin n, so its underlying natural value is strictly less than n by `isLt`.
have h1 := (σ ⟨ℓ, by omega⟩).isLt have h2 := (σ ⟨ℓ - 2, by omega⟩).isLt have h3 := (σ ⟨ℓ - 1, by omega⟩).isLt
The natural number subtractions n - (σ(k) + 1) push through the cast to integers.
Because each σ(k) < n, we have σ(k) + 1 ≤ n by linear arithmetic (`omega`). Thus `Nat.cast_sub` applies to rewrite each ↑(n - (σ(k) + 1)) as ↑n - (↑σ(k) + 1) in ℤ, and `push_cast` distributes the cast.
uses
Nat.cast_subpush_cast [Nat.cast_sub (by omega : (σ ⟨ℓ, by omega⟩ : ℕ) + 1 ≤ n), Nat.cast_sub (by omega : (σ ⟨ℓ - 2, by omega⟩ : ℕ) + 1 ≤ n), Nat.cast_sub (by omega : (σ ⟨ℓ - 1, by omega⟩ : ℕ) + 1 ≤ n)]
The integer identity holds by polynomial ring simplification.
Expanding [n - (σ(ℓ) + 1)] + [n - (σ(ℓ - 2) + 1)] - 2[n - (σ(ℓ - 1) + 1)] in ℤ, the terms involving n and the constants cancel completely (since 1 + 1 - 2 = 0), leaving -(σ(ℓ) + σ(ℓ - 2) - 2σ(ℓ - 1)). The `ring` tactic verifies this equality in ℤ.
ringWhen ℓ is out of bounds, both sides are zero by definition.
When ¬(2 ≤ ℓ ≤ n - 1), both sides evaluate to 0 by definition, leaving 0 = -0, which `simp` simplifies and closes.
· simp
Equiv.trans_apply- applying a composite equivalence is the composition of the applications
Fin.revPerm_apply- the reversal permutation revPerm maps an index i to i.rev
Fin.val_rev- the numerical value of the reversal i.rev in Fin n is n - (i + 1)
Nat.cast_sub- for natural numbers with m ≤ n, the cast to an additive group with one satisfies ↑(n - m) = ↑n - ↑m
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 perm_second_derivative_trans_revPerm {n : ℕ} (σ : Equiv.Perm (Fin n)) (ℓ : ℕ) : perm_second_derivative (σ.trans Fin.revPerm) ℓ = - perm_second_derivative σ ℓ := by unfold perm_second_derivative split_ifs with h · simp only [Equiv.trans_apply, Fin.revPerm_apply, Fin.val_rev] have h1 := (σ ⟨ℓ, by omega⟩).isLt have h2 := (σ ⟨ℓ - 2, by omega⟩).isLt have h3 := (σ ⟨ℓ - 1, by omega⟩).isLt push_cast [Nat.cast_sub (by omega : (σ ⟨ℓ, by omega⟩ : ℕ) + 1 ≤ n), Nat.cast_sub (by omega : (σ ⟨ℓ - 2, by omega⟩ : ℕ) + 1 ≤ n), Nat.cast_sub (by omega : (σ ⟨ℓ - 1, by omega⟩ : ℕ) + 1 ≤ n)] ring · simp