Gamma transform

The gamma transform $\Gamma_d$ writes a palindromic polynomial in the basis $x^i(1+x)^{d-2i}$. It sends a real-rooted polynomial with nonpositive roots to a real-rooted polynomial with nonpositive roots, and conversely, and gamma transforms of adjacent degrees interlace exactly when the gamma polynomials do. Thus real-rootedness passes in both directions between a palindromic polynomial, such as an Eulerian polynomial, and its gamma polynomial.

Results

For $d\ge0$ and $\gamma=\sum_i\gamma_ix^i$, the gamma transform in ambient degree $d$ is $$ \Gamma_d(\gamma)(x)=\sum_{i=0}^{\lfloor d/2\rfloor}\gamma_i\,x^i(1+x)^{d-2i}. $$ A palindromic polynomial $p$ with center of symmetry $d/2$ is $\Gamma_d(\gamma_p)$ for a unique gamma polynomial $\gamma_p$ of degree at most $d/2$; $p$ is gamma-positive if $\gamma_p$ has nonnegative coefficients.

Theorem (real roots). Let $\deg\gamma\le d/2$. Then $\gamma$ is nonzero and real-rooted with only nonpositive roots if and only if $\Gamma_d(\gamma)$ is. If $\gamma\ne0$ is real-rooted with nonnegative coefficients, then $\Gamma_d(\gamma)$ is nonzero and real-rooted.

Theorem (Hoster–Stump). Let $\deg\gamma\le d/2$ and $\deg\delta\le(d+1)/2$, where $\gamma,\delta$ have nonnegative coefficients and nonzero constant terms. Then $\Gamma_d(\gamma)\ll\Gamma_{d+1}(\delta)$ if and only if $\gamma\ll\delta$.

Theorem (roots). Let $\deg\gamma\le d/2$ with $\gamma\ne0$, and suppose all roots of $\Gamma_d(\gamma)$ are negative. Then the roots of $\Gamma_d(\gamma)$, with multiplicity, are the roots $x\in(-1,0)$, their reciprocals $1/x$, and $-1$ with multiplicity $d-2\deg\gamma$.

Theorem (strict lifting). Let $n\ge2$, and let $A,B$ have positive leading coefficients, only negative roots, and degrees $\lfloor(n-1)/2\rfloor$ and $\lfloor n/2\rfloor$. If $A\ll B$ and $A,B$ have no common root, then $\Gamma_{n-1}(A)$ and $\Gamma_n(B)$ have degrees $n-1$ and $n$, simple negative roots and no common root, and $\Gamma_{n-1}(A)\ll\Gamma_n(B)$.

Theorem (two steps). Let $\gamma\ll\delta$ have nonnegative coefficients and nonzero constant terms, with $\deg\gamma\le n$ and $\deg\delta\le n+1$. Then $$ \Gamma_{2n}(\gamma)\ \ll\ (x+1)\,\Gamma_{2n}(\gamma)\ \ll\ \Gamma_{2n+2}(\delta). $$

Proposition (gamma pencil). For $n\ge2$ let $T_nf=(1+2nx)\,f+x(1-4x)\,f'$, and put $U_2=1$, $V_2=x$, $U_{n+1}=T_nU_n$ and $V_{n+1}=T_nV_n$. Then $T_n$ maps every real-rooted polynomial of degree at most $n/2$ to zero or a real-rooted polynomial. For all real $a,b$, $aU_n+bV_n$ is zero or real-rooted, and $U_n\ll V_n$.

Proof

Since $\Gamma_d(\gamma)(x)=(1+x)^d\gamma\bigl(x/(1+x)^2\bigr)$ and $x/(1+x)^2$ maps $(-\infty,0]\setminus\{-1\}$ onto $(-\infty,0]$, each nonpositive root $y$ of $\gamma$ pulls back to two real roots, which are nonpositive because $y\le0<1/4$. For the pencil, $T_n$ has a stable algebraic symbol, so the finite Borcea–Brändén theorem [Bra15] applies.

References

  1. [Pet15] T. Kyle Petersen. Eulerian Numbers. Birkhäuser Advanced Texts Basler Lehrbücher, Birkhäuser, 2015.
    BibTeX
    @book{Petersen2015EulerianNumbers,
      author = {T. Kyle Petersen},
      title = {Eulerian Numbers},
      series = {Birkhäuser Advanced Texts Basler Lehrbücher},
      publisher = {Birkhäuser},
      address = {New York},
      year = {2015},
      isbn = {978-1-4939-3091-3},
      doi = {10.1007/978-1-4939-3091-3},
      url = {https://doi.org/10.1007/978-1-4939-3091-3}
    }
  2. [HS25] Elena Hoster & Christian Stump. Chow polynomials of simplicial posets with positive $h$-vector are real-rooted. arXiv e-prints, 2025.
    BibTeX
    @article{HosterStump2025x,
      author = {Elena Hoster and Christian Stump},
      title = {Chow polynomials of simplicial posets with positive $h$-vector are
        real-rooted},
      year = {2025},
      eprint = {2508.15538},
      url = {https://arxiv.org/abs/2508.15538},
      journal = {arXiv e-prints}
    }
  3. [Bra15] Petter Brändén. Unimodality, Log-Concavity, Real-Rootedness and Beyond. Handbook of enumerative combinatorics, 437-483, 2015.
    BibTeX
    @incollection{Branden2015,
      doi = {10.1201/b18255-10},
      year = {2015},
      month = mar,
      publisher = {Chapman and Hall/{CRC}},
      pages = {437--483},
      author = {Petter Br{\"{a}}nd{\'{e}}n},
      title = {Unimodality, Log-Concavity, Real-Rootedness and Beyond},
      booktitle = {Handbook of Enumerative Combinatorics}
    }
  4. [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}
    }

Definitions

  • Gamma transform

    RealRooted.gammaTransformsource
    def gammaTransform (d : ℕ) (γ : ℝ[X]) : ℝ[X] :=
      ∑ i ∈ Finset.range (d / 2 + 1), C (γ.coeff i) * gammaBasisTerm d i
  • Gamma-pencil operator

    RealRooted.gammaOperatorsource
    def gammaOperator (n : ℕ) : ℝ[X] →ₗ[ℝ] ℝ[X] :=
      oreAffineDerivativeLinearMap
        (1 + C (2 * n : ℝ) * X) (X * (1 - C (4 : ℝ) * X))
  • Constant component of the gamma pencil

    RealRooted.gammaUsource
    def gammaU : ℕ → ℝ[X]
      | 0 => 0
      | 1 => 0
      | 2 => 1
      | n + 3 => gammaOperator (n + 2) (gammaU (n + 2))
  • Parameter component of the gamma pencil

    RealRooted.gammaVsource
    def gammaV : ℕ → ℝ[X]
      | 0 => 0
      | 1 => 0
      | 2 => X
      | n + 3 => gammaOperator (n + 2) (gammaV (n + 2))
  • The polynomial γ is the gamma polynomial of p in ambient degree d

    RealRooted.IsGammaExpansionsource
    def IsGammaExpansion (d : ℕ) (p γ : ℝ[X]) : Prop :=
      p = gammaTransform d γ

Theorems

  • Real roots transfer through the gamma transformMain result

    RealRooted.GammaTransform.isRealRooted_and_roots_nonpos_iffsource
    theorem GammaTransform.isRealRooted_and_roots_nonpos_iff {d : ℕ} {γ : ℝ[X]}
        (hγdeg : γ.natDegree ≤ d / 2) :
        ((γ ≠ 0 ∧ γ.Splits) ∧ ∀ r ∈ γ.roots, r ≤ 0) ↔
          ((gammaTransform d γ ≠ 0 ∧ (gammaTransform d γ).Splits) ∧
            ∀ r ∈ (gammaTransform d γ).roots, r ≤ 0)
  • The gamma-pencil components interlace

    RealRooted.gammaU_strictInterl_gammaVsource
    theorem gammaU_strictInterl_gammaV (n : ℕ) (hn : 2 ≤ n) :
        StrictInterl (gammaU n) (gammaV n)
  • Gamma transforms of real-rooted nonnegative polynomials

    RealRooted.GammaTransform.isRealRooted_gammaTransform_of_hasNonnegCoeffssource
    theorem GammaTransform.isRealRooted_gammaTransform_of_hasNonnegCoeffs {d : ℕ} {γ : ℝ[X]}
        (hγdeg : γ.natDegree ≤ d / 2) (hγ_ne : γ ≠ 0) (hγ_splits : γ.Splits)
        (hγ_nonneg : HasNonnegCoeffs γ) :
        gammaTransform d γ ≠ 0 ∧ (gammaTransform d γ).Splits
  • Gamma transforms of adjacent degree preserve interlacing

    RealRooted.strictInterl_gammaTransform_succ_iffsource
    theorem strictInterl_gammaTransform_succ_iff
        {d : ℕ} {γ δ : ℝ[X]}
        (hγdeg : γ.natDegree ≤ d / 2)
        (hδdeg : δ.natDegree ≤ (d + 1) / 2)
        (hγnn : HasNonnegCoeffs γ)
        (hδnn : HasNonnegCoeffs δ)
        (hγ0 : γ.coeff 0 ≠ 0)
        (hδ0 : δ.coeff 0 ≠ 0) :
        StrictInterl (gammaTransform d γ) (gammaTransform (d + 1) δ) ↔
          StrictInterl γ δ
  • Every real combination of the gamma-pencil components is real-rooted

    RealRooted.gammaUV_allComboRealRootedsource
    theorem gammaUV_allComboRealRooted (n : ℕ) (hn : 2 ≤ n) :
        AllComboRealRooted (gammaU n) (gammaV n)
  • The gamma-pencil operator preserves real-rootedness

    RealRooted.gammaOperator_splits_or_zerosource
    theorem gammaOperator_splits_or_zero
        {n : ℕ} (hn : 2 ≤ n) {p : ℝ[X]}
        (hdeg : p.natDegree ≤ n / 2) (hp : p.Splits) :
        gammaOperator n p = 0 ∨ (gammaOperator n p).Splits
  • A gamma expansion is real-rooted with nonpositive roots iff its gamma polynomial is

    RealRooted.IsGammaExpansion.isRealRooted_and_hasRootsNonpos_iffsource
    theorem IsGammaExpansion.isRealRooted_and_hasRootsNonpos_iff {d : ℕ} {p γ : ℝ[X]}
        (hγdeg : γ.natDegree ≤ d / 2) (hGamma : IsGammaExpansion d p γ) :
        ((γ ≠ 0 ∧ γ.Splits) ∧ HasRootsNonpos γ) ↔
          ((p ≠ 0 ∧ p.Splits) ∧ HasRootsNonpos p)
  • The roots of a gamma transform are reciprocal pairs together with roots at −1

    RealRooted.roots_gammaTransform_eq_reciprocal_add_neg_one_addsource
    theorem roots_gammaTransform_eq_reciprocal_add_neg_one_add
        {d : Nat} {γ : Real[X]} (hγdeg : γ.natDegree ≤ d / 2)
        (hγ : γ ≠ 0)
        (hneg : ∀ x ∈ (gammaTransform d γ).roots, x < 0) :
        (gammaTransform d γ).roots =
          ((gammaTransform d γ).roots.filter
              (fun x => x ∈ Set.Ioo (-1 : Real) 0)).map (fun x => x⁻¹) +
            Multiset.replicate (d - 2 * γ.natDegree) (-1 : Real) +
              (gammaTransform d γ).roots.filter
                (fun x => x ∈ Set.Ioo (-1 : Real) 0)
  • Strict interlacing of gamma polynomials lifts to simple-rooted gamma transforms

    RealRooted.GammaTransform.strictInterl_succ_of_no_commonsource
    theorem GammaTransform.strictInterl_succ_of_no_common {n : ℕ} {A B : ℝ[X]}
        (hn : 2 ≤ n) (hA : A.natDegree = (n - 1) / 2) (hB : B.natDegree = n / 2)
        (hApos : HasPosLeadingCoeff A) (hBpos : HasPosLeadingCoeff B)
        (hAneg : ∀ r ∈ A.roots, r < 0) (hBneg : ∀ r ∈ B.roots, r < 0)
        (hpair : StrictInterl A B) (hno : ∀ r, ¬ (A.IsRoot r ∧ B.IsRoot r)) :
        (gammaTransform (n - 1) A).natDegree = n - 1 ∧ (gammaTransform n B).natDegree = n ∧
        HasSimpleRoots (gammaTransform (n - 1) A) ∧ HasSimpleRoots (gammaTransform n B) ∧
        (∀ r ∈ (gammaTransform (n - 1) A).roots, r < 0) ∧
        (∀ r ∈ (gammaTransform n B).roots, r < 0) ∧
        StrictInterl (gammaTransform (n - 1) A) (gammaTransform n B) ∧
        ∀ r, (gammaTransform (n - 1) A).IsRoot r → ¬ (gammaTransform n B).IsRoot r
  • Two successive gamma-transform steps preserve proper position

    RealRooted.strictInterl_gammaTransform_two_stepsource
    theorem strictInterl_gammaTransform_two_step
        {n : ℕ} {γ δ : ℝ[X]}
        (hγdeg : γ.natDegree ≤ n) (hδdeg : δ.natDegree ≤ n + 1)
        (hγnn : HasNonnegCoeffs γ) (hδnn : HasNonnegCoeffs δ)
        (hγ0 : γ.coeff 0 ≠ 0) (hδ0 : δ.coeff 0 ≠ 0)
        (hpair : StrictInterl γ δ) :
        StrictInterl (gammaTransform (2 * n) γ)
            ((X + 1) * gammaTransform (2 * n) γ) ∧
          StrictInterl ((X + 1) * gammaTransform (2 * n) γ)
            (gammaTransform (2 * n + 2) δ)

Lean source RealRooted/Challenges/Preservers/GammaTransform.lean at revision d6670742. Formalized 2026-10-06.