Eulerian-type polynomials

Descent and peak polynomials of derangements, words and permutations are real-rooted, and consecutive members of most families interlace.

Results

Results 1 to 7 are the theorems of [Ale26], in the order of the paper. Result 8 concerns the zig-zag Eulerian polynomials.

  1. Derangements. For $n\ge2$, the polynomial $\sum_{\pi\in\mathfrak D_n}x^{\operatorname{des}\pi}$ over derangements is nonzero and real-rooted with all roots nonpositive.
  2. Balanced cyclic words. For $n\ge1$, let $w$ range over binary words of length $2n$ with exactly $n$ ones, and let $\operatorname{cdes}w$ count the cyclic positions $i$ with $w_i=1$ and $w_{i+1}=0$. Then $\sum_w x^{\operatorname{cdes}w}$ is real-rooted with simple roots: one root is $0$ and the other $n-1$ are negative. This polynomial is $$C_n(x)=\sum_{k=1}^n2\binom nk\binom{n-1}{k-1}x^k=\frac2n\,x\,B_n'(x),$$ where $B_n(x)=\sum_k\binom nk^2x^k$ is the type $B$ Narayana polynomial.
  3. Even-top descents. Let $\operatorname{edes}\pi$ count the descents $\pi_j>\pi_{j+1}$ with $\pi_j$ even. For $n\ge2$, the polynomial $\sum_{\pi\in\mathfrak S_n}x^{\operatorname{edes}\pi}$ is real-rooted with negative roots. It strictly alternates with the same polynomial for $n+1$: both have simple roots, no root is shared, and one interlaces the other.
  4. Super-Eulerian polynomials. Let $E^{(\ell)}_{1,0}=1$ and $E^{(\ell)}_{n,k}=(k+1)^\ell E^{(\ell)}_{n-1,k}+(n-k)^\ell E^{(\ell)}_{n-1,k-1}$, with entries outside $0\le k\le n-1$ equal to zero, and let $A^{(\ell)}_n=\sum_{k<n}E^{(\ell)}_{n,k}x^k$. For $\ell\ge1$ and $n\ge0$, the polynomial $A^{(\ell)}_{n+1}$ is real-rooted with nonpositive roots, and $A^{(\ell)}_{n+1}\ll A^{(\ell)}_{n+2}$ with no common root. Moreover $$A^{(\ell)}_{n+1}(x)=\sum_{0\le i\le n/2}\gamma_i\,x^i(1+x)^{n-2i},$$ where $\gamma$ is nonzero, real-rooted, with nonpositive roots and nonnegative coefficients.
  5. Ternary words. For $w\in\{0,1,2\}^n$, let $\operatorname{run}w$ be the number of maximal strictly increasing runs. Then $T_n(x)=\sum_w x^{\operatorname{run}w}$ is a Pólya frequency polynomial and $T_n\ll T_{n+1}$. These polynomials satisfy $T_0=1$ and $$(n+1)\,T_{n+1}=3x(1-x)\,T_n'+\bigl((4n+3)x-n\bigr)\,T_n.$$
  6. Peaks. For $n\ge1$, the polynomial $\sum_{\pi\in\mathfrak S_n}x^{\operatorname{pk}\pi}$, where $\operatorname{pk}$ counts interior peaks, is real-rooted. For $n\ge3$ it has degree $\lfloor(n-1)/2\rfloor$ and negative roots, and it strictly alternates with the same polynomial for $n+1$.
  7. Peak values. Let $K_n(z_1,\dots,z_n)=\sum_{\pi\in\mathfrak S_n}\prod z_v$, with $v$ ranging over the values of the interior peaks of $\pi$. Then $K_n$ is real stable for every $n$. For $n\ge1$ and positive weights $w_1,\dots,w_{n+1}$, the polynomial $K_n(w_1x,\dots,w_nx)$ interlaces $K_{n+1}(w_1x,\dots,w_{n+1}x)$.
  1. Zig-zag swaps. Call $i$ a swap of a permutation $\pi$ of $[n]$ if $\pi^{-1}(i)+1<\pi^{-1}(i+1)$, and let $\operatorname{swap}\pi$ be the number of swaps. For $n\ge1$, the polynomial $\sum x^{\operatorname{swap}\pi}$ over up-down permutations $\pi_1<\pi_2>\pi_3<\dotsb$ is nonzero with simple negative roots, and has degree $n-2$ for $n\ge2$.

Euler insertion operators. Let $$ E_{c,d}\,p=\bigl(c+(d+1)x\bigr)\,p+(x-x^2)\,p' . $$

Theorem (mixed compatibility). Let $f,g$ have nonnegative coefficients and positive leading coefficients, with $g\ll f$, $\deg f=\deg g+1$ and $\deg f\le n+1$. Then $E_{1,n}\,g$ and $E_{0,n+1}\,f$ are compatible: every nonnegative combination of them is zero or real-rooted. In particular $E_{0,n+1}f+\lambda\,E_{1,n}g$ is real-rooted for every $\lambda>0$.

Theorem (oriented completion). Let $L_Mp=Mp+(1-x)p'$. If $p\ll q$ are Pólya frequency polynomials of the same degree $D\ge1$ and $M\ge D+1$, then $L_Mp\ll L_Mq$. Moreover, if $p$ and $p+1$ are Pólya frequency polynomials of degree $D\ge2$ and $M\ge D+2$, the four polynomials $$ E_{1,M-2}\,p,\quad E_{1,M-2}(p+1),\quad E_{0,M-1}\,p,\quad E_{0,M-1}(p+1) $$ have a common left interleaver.

Proof

The two operator theorems give the proof for derangement descents.

References

  1. [Ale26] Per Alexandersson. Real-rooted Eulerian polynomials from permutations, words, and paths. arXiv e-prints, 2026.
    BibTeX
    @article{Alexandersson2026Eulerian,
      author = {Per Alexandersson},
      title = {Real-rooted {E}ulerian polynomials from permutations, words, and
        paths},
      year = {2026},
      eprint = {2609.07325v2},
      url = {https://arxiv.org/abs/2609.07325v2},
      journal = {arXiv e-prints}
    }
  2. [Sha26, Theorem C] Umesh Shankar. Multivariate stability of powered triangular recurrences and parametrised Eulerian polynomials. arXiv e-prints, 2026.
    BibTeX
    @article{Shankar2026x,
      author = {Umesh Shankar},
      title = {Multivariate stability of powered triangular recurrences and
        parametrised {E}ulerian polynomials},
      year = {2026},
      eprint = {2609.15651v1},
      url = {https://arxiv.org/abs/2609.15651v1},
      journal = {arXiv e-prints}
    }

Definitions

  • Derangement descent polynomial Σ x^des π

    RealRooted.EulerianCompendium.derangementDescentPolynomialsource
    def derangementDescentPolynomial (n : ℕ) : ℝ[X] :=
      ∑ π : Equiv.Perm (Fin n), if ∀ i, π i ≠ i then X ^ π.descentCount else 0
  • Balanced cyclic-word polynomial Σ x^cdes w

    RealRooted.EulerianCompendium.BalancedCyclic.balancedWordSumsource
    noncomputable def balancedWordSum (n : ℕ) : ℝ[X] :=
      ∑ w ∈ univ.filter (fun w : Fin (2 * n) → Bool => IsBalanced n w), X ^ cdes w
  • Even-top descent polynomial of permutations

    RealRooted.EulerianCompendium.evenTopDescentPolynomialsource
    def evenTopDescentPolynomial (n : ℕ) : ℝ[X] :=
      ∑ π : Equiv.Perm (Fin n), X ^ evenTopDescentCount π
  • Increasing-run polynomial of ternary words

    RealRooted.EulerianCompendium.ternaryWordRunEnumeratorsource
    def ternaryWordRunEnumerator (n : ℕ) : ℝ[X] :=
      ∑ w : Fin n → Fin 3, X ^ ternaryWordRunCount w
  • Peak polynomial of permutations

    RealRooted.EulerianCompendium.peakPolynomialsource
    def peakPolynomial (n : ℕ) : ℝ[X] := weightedPeakPolynomial (fun _ : Fin n => 1)
  • Strict alternation of roots

    RealRooted.EulerianCompendium.StrictlyAlternatingRootssource
    def StrictlyAlternatingRoots (p q : ℝ[X]) : Prop :=
      (RealRooted.StrictInterl p q ∨ RealRooted.StrictInterl q p) ∧
        RealRooted.HasSimpleRoots p ∧ RealRooted.HasSimpleRoots q ∧
        ∀ r ∈ p.roots, r ∉ q.roots
  • Euler insertion operator E_{c,d}

    RealRooted.eulerInsertionStepsource
    def eulerInsertionStep (c : ℝ) (d : ℕ) (p : ℝ[X]) : ℝ[X] :=
      C c * p + C ((d : ℝ) + 1) * (X * p) +
        X * p.derivative - X * (X * p.derivative)
  • Lowering Euler operator p ↦ Mp + (1 - x)p'

    RealRooted.loweringEulerStepsource
    def loweringEulerStep (M : ℕ) (p : ℝ[X]) : ℝ[X] :=
      C (M : ℝ) * p + (1 - X) * p.derivative
  • Cyclic path descent polynomial Σ 2 C(n,k) C(n-1,k-1) x^k

    RealRooted.Applications.EulerianVariations.cyclicPathDescentPolynomialsource
    def cyclicPathDescentPolynomial (n : ℕ) : ℝ[X] :=
      ∑ k ∈ Finset.Icc 1 n,
        monomial k (2 * (Nat.choose n k : ℝ) * Nat.choose (n - 1) (k - 1))
  • Ternary run polynomials, defined by a first-order differential recurrence

    RealRooted.Applications.EulerianVariations.ternaryRunPolynomialsource
    def ternaryRunPolynomial : ℕ → ℝ[X]
      | 0 => 1
      | n + 1 =>
          (C (3 / ((n : ℝ) + 1)) * X + C (-3 / ((n : ℝ) + 1)) * X ^ 2) *
              (ternaryRunPolynomial n).derivative +
            (C (-(n : ℝ) / ((n : ℝ) + 1)) +
              C ((4 * (n : ℝ) + 3) / ((n : ℝ) + 1)) * X) *
                ternaryRunPolynomial n
  • Multivariate peak-value polynomial

    RealRooted.peakValuePolynomialsource
    def peakValuePolynomial (n : ℕ) : MvPolynomial (Fin n) ℝ :=
      ∑ π : Equiv.Perm (Fin n), peakValueMonomial π
  • Super-Eulerian polynomial

    RealRooted.SuperEulerian.superEuleriansource
    def superEulerian (l n : ℕ) : ℝ[X] :=
      finPoly n fun k => (superEulerianNumber l n k : ℝ)

Theorems

  • Descent polynomials of derangements are real-rootedCoauthored paper

    RealRooted.EulerianCompendium.Challenges.derangementDescent_realRootedsource
    theorem derangementDescent_realRooted (n : ℕ) (hn : 2 ≤ n) :
        derangementDescentPolynomial n ≠ 0 ∧
          (derangementDescentPolynomial n).Splits ∧
          ∀ r ∈ (derangementDescentPolynomial n).roots, r ≤ 0
  • Balanced cyclic-word polynomials: simple roots, one at 0, the rest negativeCoauthored paper

    RealRooted.EulerianCompendium.Challenges.cyclicWordDescent_rootssource
    theorem cyclicWordDescent_roots (n : ℕ) (hn : 0 < n) :
        (BalancedCyclic.balancedWordSum n).Splits ∧
          HasSimpleRoots (BalancedCyclic.balancedWordSum n) ∧
          (BalancedCyclic.balancedWordSum n).IsRoot 0 ∧
          (∀ r ∈ (BalancedCyclic.balancedWordSum n).roots.erase 0, r < 0) ∧
          ((BalancedCyclic.balancedWordSum n).roots.erase 0).card = n - 1
  • Even-top descent polynomials have negative roots that strictly alternateCoauthored paper

    RealRooted.EulerianCompendium.Challenges.evenTopDescent_strictAlternationsource
    theorem evenTopDescent_strictAlternation (n : ℕ) (hn : 2 ≤ n) :
        (evenTopDescentPolynomial n).Splits ∧
          (∀ r ∈ (evenTopDescentPolynomial n).roots, r < 0) ∧
          StrictlyAlternatingRoots
            (evenTopDescentPolynomial n) (evenTopDescentPolynomial (n + 1))
  • Super-Eulerian polynomials: real roots, interlacing and gamma-expansionCoauthored paper

    RealRooted.EulerianCompendium.superEulerian_roots_interlacing_gammasource
    theorem EulerianCompendium.superEulerian_roots_interlacing_gamma (l n : ℕ) (hl : 0 < l) :
        (superEulerianPolynomial l (n + 1) ≠ 0 ∧
          (superEulerianPolynomial l (n + 1)).Splits ∧
          ∀ r ∈ (superEulerianPolynomial l (n + 1)).roots, r ≤ 0) ∧
        Interl (superEulerianPolynomial l (n + 1)) (superEulerianPolynomial l (n + 2)) ∧
        ∃ γ : ℝ[X], γ.natDegree ≤ n / 2 ∧
          IsGammaExpansion n (superEulerianPolynomial l (n + 1)) γ ∧
          (γ ≠ 0 ∧ γ.Splits) ∧ HasRootsNonpos γ ∧ HasNonnegCoeffs γ
  • Ternary-word run polynomials are real-rooted and interlaceCoauthored paper

    RealRooted.EulerianCompendium.Challenges.ternaryWordRun_realRooted_interlacessource
    theorem ternaryWordRun_realRooted_interlaces (n : ℕ) :
        (ternaryWordRunEnumerator n ≠ 0 ∧ (ternaryWordRunEnumerator n).Splits) ∧
          StrictInterl (ternaryWordRunEnumerator n) (ternaryWordRunEnumerator (n + 1))
  • Peak polynomials have negative roots that strictly alternateCoauthored paper

    RealRooted.EulerianCompendium.Challenges.peakPolynomial_rootssource
    theorem peakPolynomial_roots (n : ℕ) (hn : 1 ≤ n) :
        (peakPolynomial n ≠ 0 ∧ (peakPolynomial n).Splits) ∧
        (3 ≤ n → (peakPolynomial n).natDegree = (n - 1) / 2 ∧
          (∀ r ∈ (peakPolynomial n).roots, r < 0) ∧
          StrictlyAlternatingRoots (peakPolynomial n) (peakPolynomial (n + 1)))
  • Peak-value polynomials are real stable; weighted diagonals interlaceMain resultCoauthored paper

    RealRooted.EulerianCompendium.peakValue_stability_and_weightedInterlacingsource
    theorem EulerianCompendium.peakValue_stability_and_weightedInterlacing :
        (∀ n : ℕ, MvRealStable (peakValuePolynomial n)) ∧
        (∀ (n : ℕ), 1 ≤ n → ∀ (wt : Fin (n + 1) → ℝ), (∀ j, 0 < wt j) →
          StrictInterl (weightedPeakPolynomial (fun j : Fin n => wt j.castSucc))
            (weightedPeakPolynomial wt))
  • Simple roots of the cyclic path descent polynomial: 0 and n - 1 negativeCoauthored paper

    RealRooted.Applications.EulerianVariations.cyclicPathDescentPolynomial_rootssource
    theorem cyclicPathDescentPolynomial_roots
        (n : ℕ) (hn : 0 < n) :
        HasSimpleRoots (cyclicPathDescentPolynomial n) ∧
          (cyclicPathDescentPolynomial n).IsRoot 0 ∧
          (∀ r ∈ (cyclicPathDescentPolynomial n).roots.erase 0, r < 0) ∧
          ((cyclicPathDescentPolynomial n).roots.erase 0).card = n - 1
  • The cyclic path descent polynomial is (2/n) x B_n'(x) for the type B Narayana B_nCoauthored paper

    RealRooted.Applications.EulerianVariations.cyclicPathDescentPolynomial_eq_derivativesource
    theorem cyclicPathDescentPolynomial_eq_derivative (n : ℕ) (hn : 0 < n) :
        cyclicPathDescentPolynomial n =
          C (2 / (n : ℝ)) * X * (narayanaPolynomial 0 n).derivative
  • The peak-value polynomial K_n is real stableCoauthored paper

    RealRooted.peakValuePolynomial_mvRealStablesource
    theorem peakValuePolynomial_mvRealStable (n : ℕ) :
        MvRealStable (peakValuePolynomial n)
  • Positive weighted diagonals of K_n and K_{n+1} interlaceCoauthored paper

    RealRooted.peakValueWeightedDiagonal_consecutive_strictInterlsource
    theorem peakValueWeightedDiagonal_consecutive_strictInterl
        (n : ℕ) (hn : 1 ≤ n) (wt : Fin (n + 1) → ℝ)
        (hwt : ∀ j, 0 < wt j) :
        StrictInterl
          (peakValueWeightedDiagonal (fun j : Fin n => wt j.castSucc))
          (peakValueWeightedDiagonal wt)
  • Ternary run polynomials are Pólya frequency polynomialsCoauthored paper

    RealRooted.Applications.EulerianVariations.ternaryRunPolynomial_isPFsource
    theorem ternaryRunPolynomial_isPF (n : ℕ) :
        IsPFPolynomial (ternaryRunPolynomial n)
  • Consecutive ternary run polynomials interlaceCoauthored paper

    RealRooted.Applications.EulerianVariations.ternaryRunPolynomial_strictInterlsource
    theorem ternaryRunPolynomial_strictInterl (n : ℕ) :
        StrictInterl (ternaryRunPolynomial n) (ternaryRunPolynomial (n + 1))
  • For ℓ ≥ 1, super-Eulerian polynomials are nonzero and real-rootedCoauthored paper

    RealRooted.SuperEulerian.isRealRooted_superEuleriansource
    theorem isRealRooted_superEulerian {l : ℕ} (hl : l ≠ 0) (n : ℕ) :
        superEulerian l (n + 1) ≠ 0 ∧ (superEulerian l (n + 1)).Splits
  • For ℓ ≥ 1, consecutive super-Eulerian polynomials interlace, without common rootsCoauthored paper

    RealRooted.SuperEulerian.strictInterl_superEulerian_succsource
    theorem strictInterl_superEulerian_succ {l : ℕ} (hl : l ≠ 0) (n : ℕ) :
        StrictInterl (superEulerian l (n + 1)) (superEulerian l (n + 2)) ∧
          ∀ r, (superEulerian l (n + 1)).IsRoot r → ¬ (superEulerian l (n + 2)).IsRoot r
  • Super-Eulerian gamma-polynomials are real-rooted with nonnegative coefficientsCoauthored paper

    RealRooted.SuperEulerian.exists_gamma_superEuleriansource
    theorem exists_gamma_superEulerian {l : ℕ} (hl : l ≠ 0) (n : ℕ) :
        ∃ γ : ℝ[X], γ.natDegree ≤ n / 2 ∧ IsGammaExpansion n (superEulerian l (n + 1)) γ ∧
          (γ ≠ 0 ∧ γ.Splits) ∧ HasRootsNonpos γ ∧ HasNonnegCoeffs γ
  • Zig-zag Eulerian polynomials have simple negative rootsRealRooted original

    RealRooted.ZigzagEulerian.isRealRooted_and_roots_negsource
    theorem ZigzagEulerian.isRealRooted_and_roots_neg (n : ℕ) (hn : 1 ≤ n) :
        zigzagEulerianPolynomial n ≠ 0 ∧
          (zigzagEulerianPolynomial n).natDegree = n - 2 ∧
          (zigzagEulerianPolynomial n).Splits ∧
          (zigzagEulerianPolynomial n).roots.Nodup ∧
          ∀ r ∈ (zigzagEulerianPolynomial n).roots, r < 0
  • Compatibility of two adjacent Euler insertion stepsCoauthored paper

    RealRooted.compatible_eulerInsertionStep_one_zero_succsource
    theorem compatible_eulerInsertionStep_one_zero_succ
        {n : ℕ} {f g : ℝ[X]}
        (hgf : StrictInterl g f)
        (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g)
        (hdeg : g.natDegree + 1 = f.natDegree)
        (hfdeg : f.natDegree ≤ n + 1) :
        Compatible (eulerInsertionStep 1 n g)
          (eulerInsertionStep 0 (n + 1) f)
  • Positive mixtures of adjacent Euler insertion steps are real-rootedRealRooted original

    RealRooted.mixedEulerStep_splitssource
    theorem mixedEulerStep_splits
        {n : ℕ} {lam : ℝ} {f g : ℝ[X]}
        (hlam : 0 < lam)
        (hgf : StrictInterl g f)
        (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g)
        (hdeg : g.natDegree + 1 = f.natDegree)
        (hfdeg : f.natDegree ≤ n + 1) :
        (eulerInsertionStep 0 (n + 1) f +
          C lam * eulerInsertionStep 1 n g).Splits
  • The lowering Euler operator preserves interlacing of equal-degree PF polynomialsRealRooted original

    RealRooted.loweringEulerStep_strictInterlsource
    theorem loweringEulerStep_strictInterl
        {M D : ℕ} (hD : 1 ≤ D) (hM : D + 1 ≤ M) {p q : ℝ[X]}
        (hp : IsPFPolynomial p) (hq : IsPFPolynomial q)
        (hpdeg : p.natDegree = D) (hqdeg : q.natDegree = D)
        (hpq : StrictInterl p q) :
        StrictInterl (loweringEulerStep M p) (loweringEulerStep M q)
  • Four Euler insertion images have a common left interleaverRealRooted original

    RealRooted.crossedEulerCompletion_commonLeftInterleaversource
    theorem crossedEulerCompletion_commonLeftInterleaver
        {D M : ℕ} (hD : 2 ≤ D) (hM : D + 2 ≤ M) {p : ℝ[X]}
        (hp : IsPFPolynomial p) (hp1 : IsPFPolynomial (p + 1))
        (hpdeg : p.natDegree = D) :
        HasCommonLeftInterleaver
          [eulerInsertionStep 1 (M - 2) p,
            eulerInsertionStep 1 (M - 2) (p + 1),
            eulerInsertionStep 0 (M - 1) p,
            eulerInsertionStep 0 (M - 1) (p + 1)]

Lean source RealRooted/Challenges/Combinatorial/EulerianCompendium.lean at revision d6670742. Formalized 2026-10-24.