Critical permutations of the symmetric group: a local test for the first degree, and the first-degree counts at n=8 and n=9

Abstract

For τ in the symmetric group Sₙ let Λ(τ)={σ:σ ≤ τ} be its principal ideal in the Bruhat order and let λⱼ(τ) be the number of elements of Λ(τ) of Coxeter length j. Following Pučinskaitė, τ is critical of degree i when i is the least index with λᵢ(τ) ≠ λ_(ℓ(τ)-i)(τ), and critical when such an i exists; equivalently, when the rank generating function of the lower Bruhat interval [id,τ] is not palindromic. The set Cₙ of critical permutations is identified in that paper with {q ∈ Sₙ:[M(idₙ):L(q)] ≥ 2} in the principal block of O(slₙ(ℂ)), and its table of |Cₙ| stops at n=7. We prove that criticality of the first degree is decided by a condition local to τ: the two quantities the criterion compares are the number of smaller neighbours of τ and the number of indices j with τ({1,…,j}) ≠ {1,…,j}, so no principal ideal need be built. This yields the number of permutations critical of degree 1 at n=8 and at n=9, namely 32 915 and 329 513; the second is out of reach of the ideal-based route. The set Cₙ itself is classical — palindromicity of that rank generating function is the Carrell–Peterson criterion for rational smoothness, so by Lakshmibai–Sandhya Cₙ is the set of permutations containing 3412 or 4231, and |Cₙ| is n! less a known sequence — but that description is silent about the degree, and neither count above follows from it. We also adjudicate an internal inconsistency in the source, which prints both 354 and 345 for |C₆|: the value is 354, as the source's own arithmetic and the classical count both show. Every theorem, proposition, lemma and corollary below is machine-checked in Lean 4; the few numerical remarks that are not are flagged where they occur.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   18f31a9fe743ba695e084a55631f593297bd6cb866cd50913b26976f19970ba4