Peak polynomials on Ferrers boards

The refined peak polynomials of a Ferrers board satisfy a recursion that preserves six interlacing conditions, so the peak polynomial of every Ferrers board is real-rooted.

Results

We use the zero-aware interlacing convention. A peak family of width $m$ consists of polynomials $D_k$ and $U_k$, $0\le k<m$, with nonnegative coefficients. Put $$ A_k = D_k + U_k, \qquad W_k = x D_k + U_k, \qquad S_k = \sum_{j < k} A_j, \qquad T_k = \sum_{j \ge k} W_j, $$ and let $P=\sum_k A_k$ be the total peak polynomial. The family satisfies the six conditions if

For a map $\iota\colon\{0,\dots,m'-1\}\to\{0,\dots,m-1\}$, the next-level family of width $m'$ has $D^+_k=S_{\iota(k)}$ and $U^+_k=T_{\iota(k)}$. The boundary family of width $m+1$ has $D^+_k=S_k$ and $U^+_k=T_k$ for $k<m$, and $D^+_m=P$, $U^+_m=0$. The base family has width $1$, $D_0=0$ and $U_0=1$. A family is reachable if it arises from the base family by finitely many next-level steps along monotone maps $\iota$ and boundary steps. By Alexandersson, Jal and Quemener, the refined peak polynomials of a Ferrers board arise in this way.

Theorem. Let a peak family satisfy the six conditions. If some $A_k$ is nonzero, then $P$ is nonzero and real-rooted.

Proposition (recursion). The base family satisfies the six conditions. If a family satisfies them, so do its boundary family and its next-level family along every monotone $\iota$. Hence every reachable family satisfies the six conditions.

Proof

If $h\ll f$ have nonnegative coefficients, $f$ is real-rooted and $h(0)\le f(0)$, then $f\ll f+(x-1)h$. The differences $W^+_l-A^+_k$, $A^+_{k'}-A^+_k$ and $W^+_l-W^+_k$ of a next-level family are $(x-1)H$ with $H$ having nonnegative coefficients, so this shift lemma reduces conditions (c), (e) and (f) to interlacings of such $H$. Finally $P\ll W_k$ for every $k$, and $W_k\ne0$ when $A_k\ne0$.

References

See also peaks of permutations on symmetricfunctions.com.

  1. [AJQ25] Per Alexandersson, Aryaman Jal, & Maena Quemener. Rook-Eulerian polynomials and permutation ideals. arXiv e-prints, 2025.
    BibTeX
    @article{AlexanderssonJalQuemener2025x,
      author = {Per Alexandersson and Aryaman Jal and Maena Quemener},
      title = {Rook-{E}ulerian polynomials and permutation ideals},
      year = {2025},
      eprint = {2502.05939v1},
      url = {https://arxiv.org/abs/2502.05939v1},
      journal = {arXiv e-prints}
    }

Definitions

  • A peak family of width m

    RealRooted.Applications.PeakPolynomials.PeakFamilysource
    structure PeakFamily (m : ℕ) where
      /-- The refined peak polynomial `D_k`. -/
      D : Fin m → ℝ[X]
      /-- The refined peak polynomial `U_k`. -/
      U : Fin m → ℝ[X]
      hasNonnegCoeffs_D : ∀ k, HasNonnegCoeffs (D k)
      hasNonnegCoeffs_U : ∀ k, HasNonnegCoeffs (U k)
  • A_k = D_k + U_k

    RealRooted.Applications.PeakPolynomials.PeakFamily.Asource
    def A (k : Fin m) : ℝ[X] := F.D k + F.U k
  • W_k = x D_k + U_k

    RealRooted.Applications.PeakPolynomials.PeakFamily.Wsource
    def W (k : Fin m) : ℝ[X] := X * F.D k + F.U k
  • The total peak polynomial

    RealRooted.Applications.PeakPolynomials.PeakFamily.Psource
    def P : ℝ[X] := Finset.univ.sum F.A
  • The six interlacing conditions

    RealRooted.Applications.PeakPolynomials.PeakFamily.Conditionssource
    structure Conditions (F : PeakFamily m) : Prop where
      /-- (a) `D_j ≪₀ U_l` for all `j, l`. -/
      interl_D_U : ∀ j l : Fin m, Interl (F.D j) (F.U l)
      /-- (b) `U_j ≪₀ U_l` for `j ≤ l`. -/
      interl_U_U_of_le : ∀ j l : Fin m, j ≤ l → Interl (F.U j) (F.U l)
      /-- (c) `A_j ≪₀ W_l` for all `j, l`. -/
      interl_A_W : ∀ j l : Fin m, Interl (F.A j) (F.W l)
      /-- (d) reversed DD: `D_j ≪₀ D_{j'}` for `j' < j`. -/
      interl_D_D_of_lt : ∀ j j' : Fin m, j' < j → Interl (F.D j) (F.D j')
      /-- (e) reversed AA: `A_j ≪₀ A_{j'}` for `j' < j`. -/
      interl_A_A_of_lt : ∀ j j' : Fin m, j' < j → Interl (F.A j) (F.A j')
      /-- (f) `W_j ≪₀ W_l` for `j ≤ l`. -/
      interl_W_W_of_le : ∀ j l : Fin m, j ≤ l → Interl (F.W j) (F.W l)
  • The next-level family along a map of cut positions

    RealRooted.Applications.PeakPolynomials.PeakFamily.nextsource
    def next (F : PeakFamily m) (m' : ℕ) (ι : Fin m' → Fin m) : PeakFamily m' where
      D k := F.S (ι k)
      U k := F.T (ι k)
      hasNonnegCoeffs_D k := F.hasNonnegCoeffs_S (ι k)
      hasNonnegCoeffs_U k := F.hasNonnegCoeffs_T (ι k)
  • The next-level family with an extra boundary index

    RealRooted.Applications.PeakPolynomials.PeakFamily.nextBoundarysource
    def nextBoundary (F : PeakFamily m) : PeakFamily (m + 1) where
      D := F.boundaryD
      U := F.boundaryU
      hasNonnegCoeffs_D k := by
        by_cases hk : (k : ℕ) < m
        · simpa [boundaryD, hk] using F.hasNonnegCoeffs_S ⟨k, hk⟩
        · simpa [boundaryD, hk] using F.hasNonnegCoeffs_P
      hasNonnegCoeffs_U k := by
        by_cases hk : (k : ℕ) < m
        · simpa [boundaryU, hk] using F.hasNonnegCoeffs_T ⟨k, hk⟩
        · simpa [boundaryU, hk] using hasNonnegCoeffs_zero
  • The base family

    RealRooted.Applications.PeakPolynomials.PeakFamily.basesource
    def base : PeakFamily 1 where
      D _ := 0
      U _ := 1
      hasNonnegCoeffs_D _ := hasNonnegCoeffs_zero
      hasNonnegCoeffs_U _ := hasNonnegCoeffs_one
  • Families reachable from the base family

    RealRooted.Applications.PeakPolynomials.PeakFamily.IsReachablesource
    inductive IsReachable : {m : ℕ} → PeakFamily m → Prop
      | base : IsReachable base
      | next {m m' : ℕ} {F : PeakFamily m} {ι : Fin m' → Fin m} :
          IsReachable F → Monotone ι → IsReachable (F.next m' ι)
      | nextBoundary {m : ℕ} {F : PeakFamily m} : IsReachable F → IsReachable F.nextBoundary

Theorems

  • The total peak polynomial of a reachable family is real-rootedMain resultCoauthored paper

    RealRooted.Applications.PeakPolynomials.PeakFamily.IsReachable.isRealRooted_Psource
    theorem IsReachable.isRealRooted_P (hF : F.IsReachable) (hne : ∃ k : Fin m, F.A k ≠ 0) :
        F.P ≠ 0 ∧ F.P.Splits
  • The six conditions pass to the next-level familyCoauthored paper

    RealRooted.Applications.PeakPolynomials.PeakFamily.Conditions.nextsource
    theorem next (hC : F.Conditions) (hι : Monotone ι) : (F.next m' ι).Conditions where
      interl_D_U
  • The six conditions pass to the boundary familyCoauthored paper

    RealRooted.Applications.PeakPolynomials.PeakFamily.Conditions.nextBoundarysource
    theorem nextBoundary (hC : F.Conditions) : (F.nextBoundary).Conditions
  • The base family satisfies the six conditionsCoauthored paper

    RealRooted.Applications.PeakPolynomials.PeakFamily.conditions_basesource
    theorem conditions_base : base.Conditions where
      interl_D_U _ _

Lean source RealRooted/Challenges/Combinatorial/PeakPolynomials.lean at revision d6670742. Formalized 2026-07-01.