Zig-zag Eulerian polynomials

The zig-zag Eulerian polynomials count alternating permutations by swaps. They have only distinct negative roots, which settles a conjecture of Petersen and Zhuang; the key input is a disk bound for the zeros of a centered family.

Results

Let $H_n(t)=\sum_\pi t^{\operatorname{sw}(\pi)}$ over the permutations $\pi$ of $[n]$ with $\pi_1<\pi_2>\pi_3<\dotsb$, where a swap of $\pi$ is a value $i$ with $\pi^{-1}(i)+1<\pi^{-1}(i+1)$ and $\operatorname{sw}(\pi)$ is the number of swaps. Then $H_0=H_1=H_2=1$, $H_3=1+t$ and $H_4=1+3t+t^2$.

Theorem. For every $n\ge1$, $H_n$ has degree $\max(n-2,0)$, splits over $\mathbb R$, and has distinct strictly negative roots.

This settles Conjecture 6.1(a) of Petersen and Zhuang: their $Z_n(t)=tH_n(t)$ is real-rooted.

Proposition (recurrence). Let $w_{n,k}$ be the number of words $u_1\le u_2\ge u_3\le\dotsb$ of length $n$ over the alphabet $[k]$. Then $w_{0,k}=1$, $w_{n,0}=0$ for $n>0$ and, for $n>0$, $$ 2w_{n,k+1}=2w_{n,k} +\sum_{p=0}^{n-1}w_{p,k}w_{n-1-p,k+1} +\mathbf{1}_{n=1}+\mathbf{1}_{n\geq2}w_{n-2,k+1}. $$ For $n\ge1$ the coefficients of $H_n$ are recovered by $$ a_{n,j}=w_{n,j+1}-\sum_{i=0}^{j-1}a_{n,i}\binom{n+j-i}{n}, \qquad H_n(t)=\sum_{j=0}^{n}a_{n,j}t^j , $$ and $a_{n,j}=0$ for $j>\max(n-2,0)$.

Theorem (disk bound). Let $p_n(c)$ be the coefficients of $$ \sum_{n\geq 0} p_n(c)\, s^n = \sqrt{1-s^2}\,(\sec + \tan)\bigl(c \arcsin s\bigr), $$ so that $p_n(c) = \sum_k e_k\, \alpha_{n,k}\, c^k$ with $e_k = [z^k](\sec z + \tan z)$ and $\alpha_{n,k} = [s^n]\sqrt{1-s^2}\,(\arcsin s)^k$. For $n \geq 2$, every complex zero $c$ of $p_n$ satisfies $|c|^2 < 13/3$.

Let $L F = (x^2-1)\,F' + 3x\,F$, and call a polynomial interval-simple if it splits over $\mathbb R$ with only simple roots, all in $(-1,1)$. For nonzero $F$, $\deg LF=\deg F+1$, with the leading coefficient multiplied by $\deg F+3$. If $F\ne0$ is interval-simple and $-3<a<3$, then $(L-a)F$ is interval-simple; if $F$ is interval-simple of degree at least $4$ and $a^2+b^2\le 13/3$, then $\bigl((L-a)^2+b^2\bigr)F$ is interval-simple. Consequently, if $Q\ne0$ has degree at least $3$, $Q(-x)=\pm Q(x)$ and all complex roots of $Q$ satisfy $|c|^2\le 13/3$, then $Q(L)\,1$ is interval-simple. Finally, if $G$ is interval-simple and $H\ne0$ has $\deg H\le\deg G$ and vanishes at $(z-1)/(z+1)$ for every root $z$ of $G$, then $H$ has the degree of $G$ and only simple negative roots.

Proof

Weak alternating words identify a centered polynomial built from $p_n$ with the swap enumerator. The disk bound follows [Ale26, App. A–B]: a Riccati equation for the generating function, an exact matrix for multiplication by $c^2$ on the centered basis, and a weighted column-sum estimate for that matrix. The operator $L$ then inserts one real or conjugate-pair factor of $Q$ at a time, starting from cubic or even quartic seeds, which gives roots in $(-1,1)$. The map $z\mapsto(z-1)/(z+1)$ sends $(-1,1)$ to the negative real axis.

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. [PZ24, Conjecture 6.1(a)] T. Kyle Petersen & Yan Zhuang. Zig-zag Eulerian polynomials. arXiv e-prints, 2024.
    BibTeX
    @article{PetersenZhuang2024x,
    Author = {T. Kyle Petersen and Yan Zhuang},
    Title = {Zig-zag {E}ulerian polynomials},
    Year = {2024},
    Eprint = {2403.07181},
      url = {https://arxiv.org/abs/2403.07181},
    journal = {arXiv e-prints}
    }
  3. [CS23] Jane Ivy Coons & Seth Sullivant. The $h^*$-polynomial of the order polytope of the zig-zag poset. The Electronic Journal of Combinatorics, 30(2), P2.44, 2023.
    BibTeX
    @article{CoonsSullivant2023,
      author = {Jane Ivy Coons and Seth Sullivant},
      title = {The {$h^*$}-polynomial of the order polytope of the zig-zag poset},
      journal = {The Electronic Journal of Combinatorics},
      volume = {30},
      number = {2},
      pages = {P2.44},
      year = {2023},
      doi = {10.37236/11526}
    }

Definitions

  • Word counts defined by the first-maximum recurrence

    RealRooted.ZigzagEulerian.recursiveWordCountsource
    def recursiveWordCount : ℕ → ℕ → ℕ
      | 0, _ => 1
      | _ + 1, 0 => 0
      | n + 1, k + 1 =>
          (2 * recursiveWordCount (n + 1) k +
            ∑ p : Fin (n + 1), recursiveWordCount p.val k * recursiveWordCount (n - p.val) (k + 1) +
            (if n + 1 = 1 then 1 else 0) +
            (if 2 ≤ n + 1 then recursiveWordCount (n - 1) (k + 1) else 0)) / 2
    termination_by n k => (n, k)
    decreasing_by
      · exact Prod.Lex.right _ (by lia)
      · exact Prod.Lex.left _ _ p.isLt
      · exact Prod.Lex.left _ _ (by lia)
      · exact Prod.Lex.left _ _ (by lia)
  • Numerator coefficients by triangular inversion

    RealRooted.ZigzagEulerian.recursiveCoefficientsource
    def recursiveCoefficient (n : ℕ) : ℕ → ℝ
      | j => (recursiveWordCount n (j + 1) : ℝ) -
          ∑ i : Fin j, recursiveCoefficient n i.val * (Nat.choose (n + j - i.val) n : ℝ)
    termination_by j => j
    decreasing_by exact i.isLt
  • Recurrence-defined zig-zag Eulerian polynomial

    RealRooted.ZigzagEulerian.polynomialsource
    def polynomial (n : ℕ) : ℝ[X] :=
      if n = 0 then 1 else
        ∑ j ∈ range (n + 1), monomial j (recursiveCoefficient n j)
  • Alternating permutations

    RealRooted.ZigzagEulerian.IsUpDownsource
    def IsUpDown {n : ℕ} (π : Equiv.Perm (Fin n)) : Prop :=
      ∀ i j : Fin n, i.val + 1 = j.val →
        if Even i.val then π i < π j else π j < π i
  • Swap statistic

    RealRooted.ZigzagEulerian.swapCountsource
    def swapCount {n : ℕ} (π : Equiv.Perm (Fin n)) : ℕ :=
      (swapSet π).card
  • Zig-zag Eulerian polynomial

    RealRooted.ZigzagEulerian.zigzagEulerianPolynomialsource
    def zigzagEulerianPolynomial (n : ℕ) : ℝ[X] := by
      classical
      exact ∑ π ∈ (univ : Finset (Equiv.Perm (Fin n))).filter IsUpDown,
        X ^ swapCount π
  • Centered polynomial p_n(c)

    RealRooted.CenteredEulerian.polynomialsource
    noncomputable def polynomial (n : ℕ) : Polynomial ℝ :=
      ∑ k ∈ Finset.range (n + 1), Polynomial.C (eulerCoeff k * alpha n k) * Polynomial.X ^ k
  • Weighted column bound for multiplication by c² on the centered basis

    RealRooted.CenteredEulerian.ColumnBoundsource
    def ColumnBound : Prop :=
      ∀ N j : ℕ, ∑ i ∈ Finset.range N, columnWeight i * |rMat i j| < 13 / 3 * columnWeight j
  • The centered zigzag differential operator

    RealRooted.IntervalDifferential.zigzagOperatorsource
    def zigzagOperator : ℝ[X] →ₗ[ℝ] ℝ[X] where
      toFun F := (X ^ 2 - 1) * F.derivative + C 3 * X * F
      map_add' F G := by
        simp only [derivative_add, mul_add]
        ring
      map_smul' c F := by
        simp only [smul_eq_C_mul, derivative_C_mul, RingHom.id_apply]
        ring
  • The centered zigzag transform Q(L)1

    RealRooted.IntervalDifferential.zigzagTransformsource
    def zigzagTransform (Q : ℝ[X]) : ℝ[X] :=
      zigzagFunctionalCalculus Q 1

Theorems

  • Simple negative roots of the recurrence-defined familyRealRooted original

    RealRooted.ZigzagEulerian.polynomial_rootssource
    theorem polynomial_roots (n : ℕ) (hn : 1 ≤ n) :
        (polynomial n).natDegree = n - 2 ∧
          (polynomial n).Splits ∧
          (polynomial n).roots.Nodup ∧
          ∀ r ∈ (polynomial n).roots, r < 0
  • The recurrence-defined polynomial equals the swap enumerator

    RealRooted.ZigzagEulerian.polynomial_eq_zigzagEulerianPolynomialsource
    theorem polynomial_eq_zigzagEulerianPolynomial (n : ℕ) (hn : 0 < n) :
        polynomial n = zigzagEulerianPolynomial n
  • Simple negative roots of zig-zag Eulerian polynomialsMain resultRealRooted original

    RealRooted.ZigzagEulerian.zigzagEulerianPolynomial_rootssource
    theorem zigzagEulerianPolynomial_roots (n : ℕ) (hn : 1 ≤ n) :
        (zigzagEulerianPolynomial n).natDegree = n - 2 ∧
          (zigzagEulerianPolynomial n).Splits ∧
          (zigzagEulerianPolynomial n).roots.Nodup ∧
          ∀ r ∈ (zigzagEulerianPolynomial n).roots, r < 0
  • First-maximum recurrence for weak alternating words

    RealRooted.ZigzagEulerian.weakUpDownWordCount_recurrencesource
    theorem weakUpDownWordCount_recurrence (n k : ℕ) :
        2 * weakUpDownWordCount n (k + 1) =
          2 * weakUpDownWordCount n k +
            ∑ p ∈ Finset.range n,
              weakUpDownWordCount p k * weakUpDownWordCount (n - 1 - p) (k + 1) +
            (if n = 1 then 1 else 0) +
            (if 2 ≤ n then weakUpDownWordCount (n - 2) (k + 1) else 0)
  • Complex zeros of the centered polynomials satisfy |c|² < 13/3RealRooted original

    RealRooted.CenteredEulerian.polynomial_root_normSq_ltsource
    theorem polynomial_root_normSq_lt {n : ℕ} (hn : 2 ≤ n) {c : ℂ} (hc : pC n c = 0) :
        Complex.normSq c < 13 / 3
  • The weighted column bound implies the root diskRealRooted original

    RealRooted.CenteredEulerian.root_bound_of_columnBoundsource
    theorem root_bound_of_columnBound (hcol : ColumnBound) {n : ℕ} (hn : 2 ≤ n) {c : ℂ}
        (hc : pC n c = 0) : Complex.normSq c < 13 / 3
  • The weighted column bound holdsRealRooted original

    RealRooted.CenteredEulerian.columnBoundsource
    theorem columnBound : ColumnBound
  • Exact entries of the matrix of multiplication by c² on the centered basisRealRooted original

    RealRooted.CenteredEulerian.rMat_decompsource
    theorem rMat_decomp (i j : ℕ) :
        rMat i j = aConst * coeff (i + 2) (hS * X ^ j)
          + (if j = 0 then (2 - aConst) * coeff (i + 2) qS else 0)
          + (if j = 1 then (3 - aConst) * coeff (i + 2) (qS * fS) else 0)
          + ∑ k ∈ Finset.range (i + 1), (eulerRatio (k + 2) - aConst) * alpha (i + 2) (k + 2) *
              phi j (k + 2)
  • The Riccati equation determines the centered generating functionRealRooted original

    RealRooted.CenteredEulerian.riccati_uniquesource
    theorem riccati_unique {c : ℝ} {G H : ℝ⟦X⟧} (hG : Riccati c G) (hH : Riccati c H)
        (h0 : constantCoeff G = constantCoeff H) : G = H
  • A Möbius map sends Riccati solutions for c to c + 2RealRooted original

    RealRooted.CenteredEulerian.riccati_mobiussource
    theorem riccati_mobius {c : ℝ} {G H : ℝ⟦X⟧} (hG : Riccati c G)
        (hH : H * (1 - X ^ 2 - X * G) = (1 - X ^ 2) * (G + X)) : Riccati (c + 2) H
  • Analytic expansion of cot(π/4 − z/2)RealRooted original

    RealRooted.CenteredEulerian.hasSum_eulerGsource
    lemma hasSum_eulerG (z : ℝ) (hz : |z| ≤ 1 / 2) :
        HasSum (fun k : ℕ => eulerG k * z ^ k) (Real.cot (π / 4 - z / 2))
  • The zigzag operator raises the degree of a nonzero polynomial by oneRealRooted original

    RealRooted.IntervalDifferential.zigzagOperator_natDegreesource
    theorem zigzagOperator_natDegree (F : ℝ[X]) (hF : F ≠ 0) :
        (zigzagOperator F).natDegree = F.natDegree + 1
  • Inserting a real factor inserts a simple root into each gapRealRooted original

    RealRooted.IntervalDifferential.zigzagLinearFactor_rootssource
    theorem zigzagLinearFactor_roots (F : ℝ[X]) (a : ℝ)
        (hFsplit : F.Splits) (hFne0 : F ≠ 0) (hFnodup : F.roots.Nodup)
        (hinside : ∀ z ∈ F.roots, -1 < z ∧ z < 1)
        (haL : -3 < a) (haR : a < 3) :
        (zigzagLinearFactor a F).Splits ∧
          (zigzagLinearFactor a F).roots.Nodup ∧
          ∀ z ∈ (zigzagLinearFactor a F).roots, -1 < z ∧ z < 1
  • Polynomial identity behind the insertion of a conjugate pairRealRooted original

    RealRooted.IntervalDifferential.zigzag_quadratic_certificatesource
    theorem zigzag_quadratic_certificate (d : ℕ) (a b : ℝ) (F : ℝ[X]) :
        -C ((d + 2 : ℕ) : ℝ) * F * zigzagQuadraticFactor a b F +
            C ((d + 1 : ℕ) : ℝ) * zigzagLinearFactor a F ^ 2 +
            C 2 * (C ((d + 3 : ℕ) : ℝ) * X - C a) * F *
              zigzagLinearFactor a F =
          C 2 * (1 - X ^ 2) * zigzagJ d F +
            (1 - X ^ 2) ^ 2 * zigzagK d F +
            (C ((d + 3 : ℕ) : ℝ) * (C a - X) ^ 2 +
              C ((5 * d + 6 : ℕ) : ℝ) -
              C ((d + 2 : ℕ) : ℝ) * C (a ^ 2 + b ^ 2)) * F ^ 2
  • Inserting a conjugate pair in the disk of squared radius 13/3 keeps simple interval rootsRealRooted original

    RealRooted.IntervalDifferential.zigzagQuadraticFactor_rootssource
    theorem zigzagQuadraticFactor_roots (F : ℝ[X]) (a b : ℝ)
        (hF : F.Splits) (hnd : F.roots.Nodup) (hdeg : 4 ≤ F.natDegree)
        (hinside : ∀ r ∈ F.roots, -1 < r ∧ r < 1)
        (hdisk : a ^ 2 + b ^ 2 ≤ 13 / 3) :
        (zigzagQuadraticFactor a b F).Splits ∧
          (zigzagQuadraticFactor a b F).roots.Nodup ∧
          ∀ r ∈ (zigzagQuadraticFactor a b F).roots, -1 < r ∧ r < 1
  • The cubic seed has three simple transformed roots in (−1, 1)RealRooted original

    RealRooted.IntervalDifferential.zigzagTransform_cubic_roots_of_disksource
    theorem zigzagTransform_cubic_roots_of_disk (k : ℝ)
        (hroots : ∀ c : ℂ,
          ((X ^ 3 + C k * X : ℝ[X]).map (algebraMap ℝ ℂ)).eval c = 0 →
            Complex.normSq c ≤ 13 / 3) :
        (zigzagTransform (X ^ 3 + C k * X)).Splits ∧
          (zigzagTransform (X ^ 3 + C k * X)).roots.Nodup ∧
          ∀ r ∈ (zigzagTransform (X ^ 3 + C k * X)).roots, -1 < r ∧ r < 1
  • The even quartic seed has four simple transformed roots in (−1, 1)RealRooted original

    RealRooted.IntervalDifferential.zigzagTransform_quartic_roots_of_disksource
    theorem zigzagTransform_quartic_roots_of_disk (k p : ℝ)
        (hroots : ∀ c : ℂ,
          ((X ^ 4 + C k * X ^ 2 + C p : ℝ[X]).map (algebraMap ℝ ℂ)).eval c = 0 →
            Complex.normSq c ≤ 13 / 3) :
        (zigzagTransform (X ^ 4 + C k * X ^ 2 + C p)).Splits ∧
          (zigzagTransform (X ^ 4 + C k * X ^ 2 + C p)).roots.Nodup ∧
          ∀ r ∈ (zigzagTransform (X ^ 4 + C k * X ^ 2 + C p)).roots,
            -1 < r ∧ r < 1
  • The map (z − 1)/(z + 1) carries simple roots in (−1, 1) to simple negative rootsRealRooted original

    RealRooted.IntervalDifferential.splits_roots_nodup_neg_of_mobius_evalsource
    theorem splits_roots_nodup_neg_of_mobius_eval
        {H G : ℝ[X]}
        (hHne : H ≠ 0)
        (hHdeg : H.natDegree ≤ G.natDegree)
        (hGne : G ≠ 0)
        (hGsplit : G.Splits)
        (hGsimple : G.roots.Nodup)
        (hGbounds : ∀ z ∈ G.roots, -1 < z ∧ z < 1)
        (hroot : ∀ z, -1 < z → z < 1 → G.eval z = 0 →
          H.eval (mobiusIntervalRoot z) = 0) :
        H.natDegree = G.natDegree ∧ H.Splits ∧ H.roots.Nodup ∧
          ∀ r ∈ H.roots, r < 0
  • A parity polynomial with all roots in the disk transforms to simple roots in (−1, 1)RealRooted original

    RealRooted.IntervalDifferential.zigzagTransform_parity_roots_of_disksource
    theorem zigzagTransform_parity_roots_of_disk (Q : ℝ[X]) (hQ0 : Q ≠ 0)
        (hdeg : 3 ≤ Q.natDegree)
        (hparity : Q.comp (-X) = Q ∨ Q.comp (-X) = -Q)
        (hroot : ∀ c : ℂ, (Q.map (algebraMap ℝ ℂ)).eval c = 0 →
          Complex.normSq c ≤ 13 / 3) :
        (zigzagTransform Q).Splits ∧ (zigzagTransform Q).roots.Nodup ∧
          ∀ r ∈ (zigzagTransform Q).roots, -1 < r ∧ r < 1

Lean source RealRooted/Challenges/Combinatorial/ZigzagEulerian.lean at revision d6670742. Formalized 2026-10-23.