AFTD Auto-Formalizing Theoretical Domains

perm_second_derivative_trans_revPerm

theoremverified

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.

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

    lines 3–4

      unfold perm_second_derivative
      split_ifs with h
  2. 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).

    line 5

    uses Equiv.trans_apply, Fin.revPerm_apply, Fin.val_rev

      · simp only [Equiv.trans_apply, Fin.revPerm_apply, Fin.val_rev]
  3. 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`.

    lines 6–8

        have h1 := (σ ⟨ℓ, by omega⟩).isLt
        have h2 := (σ ⟨ℓ - 2, by omega⟩).isLt
        have h3 := (σ ⟨ℓ - 1, by omega⟩).isLt
  4. 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.

    lines 9–11

    uses Nat.cast_sub

        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)]
  5. 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 ℤ.

    line 12

        ring
  6. When ℓ 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.

    line 13

      · 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

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