Descent polynomials of separable permutations

For $n\ge2$ the descent polynomials of the separable permutations of $[n]$ and $[n+1]$ interlace and have no common root; the same holds for their gamma-polynomials. The proof transfers interlacing through factorial compression, which maps polynomials with negative roots to strictly interlacing pairs.

Results

A permutation is separable if it avoids $2413$ and $3142$. Let $S_n(t)=\sum_\pi t^{\operatorname{des}\pi}$ over the separable permutations $\pi$ of $[n]$. Fu, Lin and Zeng [FLZ18] give the gamma-polynomials $\Gamma_n$ of $S_n$: $$ S_n(t)=(1+t)^{n-1}\,\Gamma_n\bigl(t/(1+t)^2\bigr). $$ For integers $N\ge1$ and $0\le\ell\le N$, the level-$\ell$ factorial compression of $p=\sum_kp_kx^k$ is $$ C_{N,\ell}\,p=\sum_{k\le N,\ 2k\le N+\ell}\frac{(N-k)!}{(N+\ell-2k)!}\,p_k\,x^k , $$ and for $a\in\mathbb R$ we put $E_ap=(x+a)p+xp'$. Zhang [Zha26] represents $\Gamma_{N+2}$ as the level-one factorial compression of $B_N$, where $B_0=1$ and $B_{N+1}=E_{(N+2)/2}B_N$; here $\Gamma_0=0$, $\Gamma_1=1$, $\Gamma_2=1$ and $\Gamma_3=1+2x$.

Theorem (Zhang). For $n\ge2$:

Also $B_N\ll B_{N+1}$ without a common root, for $N\ge0$.

Theorem (identification). The descent enumerator of the separable permutations of $[n+1]$ equals $S_{n+1}$ as defined through $\Gamma_{n+1}$, for $n\ge0$. Hence $S_n\ll S_{n+1}$ for the permutation statistic. The gamma-polynomials satisfy, for $n\ge2$ and $\Gamma_0=0$, $$ \Gamma_n=\Gamma_{n-1}+x\sum_{i+j=n-1}\Gamma_i\Gamma_j+x\sum_{i+j+l=n}\Gamma_i\Gamma_j\Gamma_l , $$ that is, $G=\sum_n\Gamma_nw^n$ satisfies $G=w+wG+xwG^2+xG^3$ [FLZ18].

Theorem (factorial compression). [Zha26] Let $N\ge1$, $0\le\ell\le N$ and $a>0$, and let $p$ be a real-rooted polynomial of degree $N$ with positive leading coefficient and only negative roots, which may be repeated. Then $C_{N,\ell}\,p$ and $C_{N+1,\ell}\,E_ap$ have degrees $\lfloor(N+\ell)/2\rfloor$ and $\lfloor(N+\ell+1)/2\rfloor$ and simple negative roots, and $C_{N,\ell}\,p\ll C_{N+1,\ell}\,E_ap$ with no common root.

The compression is a Schur–Szegő composition with an explicit kernel, $C_{N,\ell}\,p=\frac{N!}{(N+\ell)!}\,h_{N+\ell}*_Np$ with $h_r=\sum_{j\le r/2}\frac{r!}{j!\,(r-2j)!}x^j$, and Schur–Szegő composition with a polynomial with only negative roots preserves interlacing without common roots.

Proof

The enumerators $S_n$ satisfy the cubic recurrence $S_n=(1+t)S_{n-1}+t\sum_{i+j=n-1}S_iS_j+t\sum_{i+j+l=n}S_iS_jS_l$, from the decomposition of a separable permutation into direct and skew sums, and the gamma substitution carries the cubic for $\Gamma_n$, proved by Lagrange inversion, to this one. Interlacing holds for $B_N$ by the derivative-lag recurrence, and the factorial compression theorem with $\ell=1$ and $a=(N+2)/2$ transfers it to $\Gamma_{N+2}$ and $\Gamma_{N+3}$. The gamma substitution then transfers it to $S_n$ and $S_{n+1}$: the two branches of $\rho\mapsto\rho/(1+\rho)^2$ carry a common root of the descent polynomials to a common root of the gamma-polynomials, and the root $-1$ is excluded by evaluating the gamma transform there.

References

  1. [Zha26] Zhanhe Zhang. Strict Interlacing of the Descent Polynomials of Separable Permutations. 2026.
    BibTeX
    @unpublished{Zhang2026SeparableInterlacing,
      author = {Zhang, Zhanhe},
      title = {Strict Interlacing of the Descent Polynomials of Separable Permutations},
      date = {2026-09-10},
      year = {2026},
      note = {SSRN preprint 7510941, posted September 25, 2026},
      doi = {10.2139/ssrn.7510941},
      url = {https://ssrn.com/abstract=7510941}
    }
  2. [FLZ18] Shishuo Fu, Zhicong Lin, & Jiang Zeng. On two unimodal descent polynomials. Discrete Mathematics, 341(9), 2616-2626, 2018.
    BibTeX
    @article{FuLinZeng2018,
      author = {Fu, Shishuo and Lin, Zhicong and Zeng, Jiang},
      title = {On two unimodal descent polynomials},
      year = {2018},
      journal = {Discrete Mathematics},
      volume = {341},
      number = {9},
      pages = {2616--2626},
      publisher = {Elsevier BV},
      doi = {10.1016/j.disc.2018.06.010},
      url = {https://doi.org/10.1016/j.disc.2018.06.010},
      issn = {0012-365X}
    }

Definitions

  • Auxiliary polynomials B_N with B_{N+1} = (x + (N+2)/2) B_N + x B_N'

    RealRooted.SeparablePermutations.compressionSourcePolynomialsource
    def compressionSourcePolynomial : ℕ → ℝ[X]
      | 0 => 1
      | N + 1 =>
          (X + C (((N : ℝ) + 2) / 2)) * compressionSourcePolynomial N +
            X * (compressionSourcePolynomial N).derivative
  • Gamma-polynomials Γ_n through the factorial-compression representation

    RealRooted.SeparablePermutations.gammaPolynomialsource
    def gammaPolynomial : ℕ → ℝ[X]
      | 0 => 0
      | 1 => 1
      | N + 2 =>
          C ((2 : ℝ) ^ N / (N.factorial : ℝ)) *
            compression N 1 (compressionSourcePolynomial N)
  • Descent polynomials S_n = (1 + t)^{n-1} Γ_n(t/(1+t)^2)

    RealRooted.SeparablePermutations.descentPolynomialsource
    def descentPolynomial (n : ℕ) : ℝ[X] :=
      RealRooted.gammaTransform (n - 1) (gammaPolynomial n)
  • Separable permutations: direct and skew sums, equivalently avoiders of 2413 and 3142

    Equiv.Perm.IsSeparablesource
    def IsSeparable {n : ℕ} (σ : Perm (Fin n)) : Prop :=
      σ.Avoids pattern2413 ∧ σ.Avoids pattern3142
    
    instance {n : ℕ} : DecidablePred (IsSeparable (n := n)) := fun σ => by
      simp only [IsSeparable]; infer_instance
  • Descent enumerator of the separable permutations

    RealRooted.SeparablePermutations.descentEnumeratorsource
    def descentEnumerator (n : ℕ) : ℝ[X] :=
      Equiv.Perm.separableDescentEnumerator ℝ (n + 1)
  • Factorial-compression operator

    RealRooted.FactorialCompression.compressionsource
    noncomputable def compression (N ℓ : ℕ) (p : ℝ[X]) : ℝ[X] :=
      ∑ k ∈ Finset.range (N + 1), C (multiplier N ℓ k * p.coeff k) * X ^ k
  • Degree-raising differential step

    RealRooted.FactorialCompression.nextPolynomialsource
    noncomputable def nextPolynomial (a : ℝ) (p : ℝ[X]) : ℝ[X] :=
      (X + C a) * p + X * p.derivative
  • Degree-changing kernel

    RealRooted.FactorialCompression.kernelsource
    noncomputable def kernel (N ℓ : ℕ) (a : ℝ) : ℝ[X] :=
      C (kernelAlpha N ℓ a) * commonKernel (N + ℓ) +
        (C (kernelBeta N ℓ a) * X - C (1 / 4 : ℝ)) * commonKernel (N + ℓ - 1)

Theorems

  • Consecutive descent polynomials S_n, S_{n+1} interlace without common root

    RealRooted.SeparablePermutations.strictInterl_descentPolynomialsource
    theorem strictInterl_descentPolynomial {n : ℕ} (hn : 2 ≤ n) :
        RealRooted.StrictInterl (descentPolynomial n) (descentPolynomial (n + 1)) ∧
          ∀ r : ℝ, ¬ ((descentPolynomial n).IsRoot r ∧ (descentPolynomial (n + 1)).IsRoot r)
  • Consecutive gamma-polynomials Γ_n, Γ_{n+1} interlace without common root

    RealRooted.SeparablePermutations.strictInterl_gammaPolynomialsource
    theorem strictInterl_gammaPolynomial {n : ℕ} (hn : 2 ≤ n) :
        RealRooted.StrictInterl (gammaPolynomial n) (gammaPolynomial (n + 1)) ∧
          ∀ r : ℝ, ¬ ((gammaPolynomial n).IsRoot r ∧ (gammaPolynomial (n + 1)).IsRoot r)
  • Consecutive auxiliary polynomials B_N, B_{N+1} interlace without a common root

    RealRooted.SeparablePermutations.strictInterl_compressionSourcePolynomialsource
    theorem strictInterl_compressionSourcePolynomial (N : ℕ) :
        RealRooted.StrictInterl
            (compressionSourcePolynomial N) (compressionSourcePolynomial (N + 1)) ∧
          ∀ r : ℝ, ¬ ((compressionSourcePolynomial N).IsRoot r ∧
            (compressionSourcePolynomial (N + 1)).IsRoot r)
  • The descent polynomials S_n have simple roots

    RealRooted.SeparablePermutations.hasSimpleRoots_descentPolynomialsource
    theorem hasSimpleRoots_descentPolynomial {n : ℕ} (hn : 2 ≤ n) :
        RealRooted.HasSimpleRoots (descentPolynomial n)
  • All roots of S_n are negative for n ≥ 2

    RealRooted.SeparablePermutations.roots_descentPolynomial_negsource
    theorem roots_descentPolynomial_neg {n : ℕ} (hn : 2 ≤ n) :
        ∀ r ∈ (descentPolynomial n).roots, r < 0
  • S_n has degree n − 1 for n ≥ 1

    RealRooted.SeparablePermutations.natDegree_descentPolynomialsource
    theorem natDegree_descentPolynomial {n : ℕ} (hn : 1 ≤ n) :
        (descentPolynomial n).natDegree = n - 1
  • Zhang: descent polynomials of separable permutations interlaceMain result

    RealRooted.SeparablePermutations.strictInterl_descentEnumeratorsource
    theorem strictInterl_descentEnumerator {n : ℕ} (hn : 1 ≤ n) :
        RealRooted.StrictInterl (descentEnumerator n) (descentEnumerator (n + 1)) ∧
          ∀ r : ℝ, ¬ ((descentEnumerator n).IsRoot r ∧
            (descentEnumerator (n + 1)).IsRoot r)
  • Fu–Lin–Zeng / Zhang: the descent enumerator equals S_{n+1}

    RealRooted.SeparablePermutations.descentEnumerator_eq_descentPolynomialsource
    theorem descentEnumerator_eq_descentPolynomial (n : ℕ) :
        descentEnumerator n = descentPolynomial (n + 1)
  • Fu–Lin–Zeng's cubic for the gamma-polynomials (via Lagrange inversion)

    RealRooted.SeparablePermutations.gammaPolynomial_cubicsource
    theorem gammaPolynomial_cubic {n : ℕ} (hn : 2 ≤ n) :
        gammaPolynomial n = gammaPolynomial (n - 1) +
          X * (∑ i ∈ range n, gammaPolynomial i * gammaPolynomial (n - 1 - i)) +
          X * (∑ i ∈ range (n + 1), ∑ j ∈ range (n + 1 - i),
            gammaPolynomial i * gammaPolynomial j * gammaPolynomial (n - i - j))
  • Compressions of p and (x + a)p + xp' strictly interlace and have simple negative roots

    RealRooted.FactorialCompression.compression_nextPolynomial_strictInterlsource
    theorem compression_nextPolynomial_strictInterl {N ℓ : ℕ} {a : ℝ} {p : ℝ[X]}
        (hN : N ≠ 0) (hℓ : ℓ ≤ N) (ha : 0 < a)
        (hp : p.natDegree = N) (hps : p.Splits) (hppos : HasPosLeadingCoeff p)
        (hneg : ∀ r ∈ p.roots, r < 0) :
        (compression N ℓ p).natDegree = (N + ℓ) / 2 ∧
          (compression (N + 1) ℓ (nextPolynomial a p)).natDegree = (N + ℓ + 1) / 2 ∧
          HasPosLeadingCoeff (compression N ℓ p) ∧
          HasPosLeadingCoeff (compression (N + 1) ℓ (nextPolynomial a p)) ∧
          HasSimpleRoots (compression N ℓ p) ∧
          HasSimpleRoots (compression (N + 1) ℓ (nextPolynomial a p)) ∧
          (∀ r ∈ (compression N ℓ p).roots, r < 0) ∧
          (∀ r ∈ (compression (N + 1) ℓ (nextPolynomial a p)).roots, r < 0) ∧
          StrictInterl (compression N ℓ p) (compression (N + 1) ℓ (nextPolynomial a p)) ∧
          ∀ r, (compression N ℓ p).IsRoot r →
            ¬ (compression (N + 1) ℓ (nextPolynomial a p)).IsRoot r
  • Schur–Szegő composition with a negative-rooted multiplier preserves strict interlacing

    RealRooted.strictInterl_schurSzegoComp_of_roots_negsource
    theorem strictInterl_schurSzegoComp_of_roots_neg {n : ℕ} {f g Q : ℝ[X]} (hn : n ≠ 0)
        (hf : f.natDegree ≤ n) (hg : g.natDegree ≤ n)
        (hfpos : HasPosLeadingCoeff f) (hgpos : HasPosLeadingCoeff g)
        (hfg : StrictInterl f g) (hno : ∀ r, f.IsRoot r → ¬ g.IsRoot r)
        (hQ : Q.natDegree = n) (hQs : Q.Splits) (hQpos : HasPosLeadingCoeff Q)
        (hneg : ∀ b ∈ Q.roots, b < 0) :
        StrictInterl (schurSzegoComp n f Q) (schurSzegoComp n g Q) ∧
          ∀ r, (schurSzegoComp n f Q).IsRoot r → ¬ (schurSzegoComp n g Q).IsRoot r
  • Level one with a = (N + 2)/2: the compressions strictly interlace

    RealRooted.FactorialCompression.compression_one_nextPolynomial_strictInterlsource
    theorem compression_one_nextPolynomial_strictInterl {N : ℕ} {p : ℝ[X]} (hN : N ≠ 0)
        (hp : p.natDegree = N) (hps : p.Splits) (hppos : HasPosLeadingCoeff p)
        (hneg : ∀ r ∈ p.roots, r < 0) :
        (compression N 1 p).natDegree = (N + 1) / 2 ∧
          (compression (N + 1) 1 (nextPolynomial (((N : ℝ) + 2) / 2) p)).natDegree = (N + 2) / 2 ∧
          HasPosLeadingCoeff (compression N 1 p) ∧
          HasPosLeadingCoeff (compression (N + 1) 1 (nextPolynomial (((N : ℝ) + 2) / 2) p)) ∧
          HasSimpleRoots (compression N 1 p) ∧
          HasSimpleRoots (compression (N + 1) 1 (nextPolynomial (((N : ℝ) + 2) / 2) p)) ∧
          (∀ r ∈ (compression N 1 p).roots, r < 0) ∧
          (∀ r ∈ (compression (N + 1) 1 (nextPolynomial (((N : ℝ) + 2) / 2) p)).roots, r < 0) ∧
          StrictInterl (compression N 1 p)
            (compression (N + 1) 1 (nextPolynomial (((N : ℝ) + 2) / 2) p)) ∧
          ∀ r, (compression N 1 p).IsRoot r →
            ¬ (compression (N + 1) 1 (nextPolynomial (((N : ℝ) + 2) / 2) p)).IsRoot r
  • Compression is a Schur–Szegő composition

    RealRooted.FactorialCompression.compression_eq_schurSzegoCompsource
    theorem compression_eq_schurSzegoComp (N ℓ : ℕ) (p : ℝ[X]) :
        compression N ℓ p =
          C ((N.factorial : ℝ) / ((N + ℓ).factorial : ℝ)) *
            schurSzegoComp N (commonKernel (N + ℓ)) p
  • The common kernel strictly interlaces the degree-changing kernel

    RealRooted.FactorialCompression.strictInterl_commonKernel_kernelsource
    theorem strictInterl_commonKernel_kernel {N ℓ : ℕ} {a : ℝ} (hN : N ≠ 0) (hℓ : ℓ ≤ N)
        (ha : 0 < a) (hm : 2 ≤ N + ℓ) :
        StrictInterl (commonKernel (N + ℓ)) (kernel N ℓ a) ∧
          (∀ r, (commonKernel (N + ℓ)).IsRoot r → ¬ (kernel N ℓ a).IsRoot r) ∧
          ∀ r ∈ (kernel N ℓ a).roots, r < 0

Lean source RealRooted/Challenges/Combinatorial/SeparablePermutations.lean at revision d6670742. Formalized 2026-10-09.