Eulerian operators and interlacing

The Euler step $p\mapsto(c+ax)p+(x-x^2)p'$, which generates the Eulerian polynomials, maps a polynomial with simple negative roots to one of the same kind that it interlaces. Variants cover coupled and scaled steps, lag-two corrections, perturbed Eulerian rows and second-order steps.

Results

A polynomial is negative-simple if it has positive leading coefficient, simple roots, and only real negative roots. Write $\theta=x\,d/dx$. For real $c$ and $a$, the Euler step is $$ E_{c,a}\,p=(c+ax)\,p+(x-x^2)\,p'. $$ For $c=1$ and $a=n-1$ this is the Eulerian operator $T_n$ of [Ale26].

Theorem (Euler step). Let $c>0$ and let $p$ be real-rooted with simple roots, positive leading coefficient, nonnegative coefficients, $p(0)>0$ and $\deg p<a$. Then $E_{c,a}\,p$ has degree $\deg p+1$, positive leading coefficient, nonnegative coefficients, positive value at $0$ and only simple negative roots. Moreover $p\ll E_{c,a}\,p$, and the two polynomials have no common root.

Theorem (coupled families). Let $c>0$, and let $\lambda_n\ge0$ and $b_n>n$ be real numbers such that $t_n=b_n+\lambda_n$ satisfies $t_{n+1}-t_n\ge1$. Put $P_0=Q_0=1$ and $$ P_{n+1}=(c+\lambda_n+b_nx)\,P_n+(x-x^2)\,P_n',\qquad Q_{n+1}=(c+t_nx)\,P_n+(x-x^2)\,P_n'. $$ Then $P_n$ and $Q_n$ have degree $n$, positive leading coefficient, nonnegative coefficients and simple negative roots, and $P_n\ll P_{n+1}$, $P_n\ll Q_{n+1}$, $Q_n\ll Q_{n+1}$. Moreover $$ Q_{n+2}=\bigl(c+\lambda_n+(b_n+t_{n+1}-t_n)\,x\bigr)Q_{n+1}+(x-x^2)\,Q_{n+1}' +\lambda_n\,(t_{n+1}-t_n-1)\,(x-x^2)\,P_n . $$

Further variants:

Use

The power series identities turn an Euler differential equation for a generating function into a recurrence for its coefficients.

Proof

Both $P_{n+1}$ and $Q_{n+1}$ are Euler steps of $P_n$, namely $E_{c+\lambda_n,b_n}P_n$ and $E_{c,t_n}P_n$, so the first two interlacings follow from the Euler step theorem. The third follows from the critical-sign criterion [LW07]; [MW08] applied to the second-order form, whose lag term has nonnegative coefficient. The scaled step is $\gamma_n E_{\sigma,\beta_n/\gamma_n}$, and the perturbed Eulerian step is $s\,E_{1/s,\,n+1/s}$.

References

Related Eulerian results are on the Eulerian compendium page.

  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. [LW07] Lily L. Liu & Yi Wang. A unified approach to polynomial sequences with only real zeros. Advances in Applied Mathematics, 38(4), 542-560, 2007.
    BibTeX
    @article{LiuWang2007,
      doi = {10.1016/j.aam.2006.02.003},
      url2 = {https://doi.org/10.1016/j.aam.2006.02.003},
      year = {2007},
      month = may,
      publisher = {Elsevier {BV}},
      volume = {38},
      number = {4},
      pages = {542--560},
      author = {Lily L. Liu and Yi Wang},
      title = {A unified approach to polynomial sequences with only real zeros},
      journal = {Advances in Applied Mathematics}
    }
  3. [MW08] Shi-Mei Ma & Yi Wang. $q$-Eulerian polynomials and polynomials with only real zeros. The Electronic Journal of Combinatorics, 15(1), Research Paper 17, 2008.
    BibTeX
    @article{MaWang2008,
      doi = {10.37236/741},
      url2 = {https://doi.org/10.37236/741},
      year = {2008},
      month = jan,
      publisher = {The Electronic Journal of Combinatorics},
      volume = {15},
      number = {1},
      author = {Shi-Mei Ma and Yi Wang},
      title = {$q$-{E}ulerian Polynomials and Polynomials with Only Real Zeros},
      pages = {Research Paper 17},
      journal = {The Electronic Journal of Combinatorics}
    }

Definitions

  • The Euler step p ↦ (c + aX) p + (X - X²) p'

    RealRooted.realEulerInsertionStepsource
    @[expose] def realEulerInsertionStep (c a : ℝ) (p : ℝ[X]) : ℝ[X] :=
      (C c + C a * X) * p + (X - X ^ 2) * p.derivative
  • The scaled Euler step p ↦ (σγ + βX) p + γ (1 - X) X p'

    RealRooted.scaledEulerInsertionStepsource
    def scaledEulerInsertionStep (sigma gamma beta : ℝ) (p : ℝ[X]) : ℝ[X] :=
      (C (sigma * gamma) + C beta * X) * p +
        C gamma * (1 - X) * (X * p.derivative)
  • Rows of an Euler recurrence with a lag-two correction

    RealRooted.lagTwoEulerPolynomialsource
    def lagTwoEulerPolynomial (m : ℝ) (lambda : ℕ → ℝ) : ℕ → ℝ[X]
      | 0 => 1
      | 1 => 1 + X
      | n + 2 =>
          lagTwoEulerStep (n + 1) 1 m (lagTwoEulerPolynomial m lambda (n + 1)) +
            C (m * lambda (n + 2)) * X *
              lagTwoEulerCore n (lagTwoEulerPolynomial m lambda n)
  • The centered Euler orbit of the constant polynomial 1

    RealRooted.centeredEulerOrbitsource
    def centeredEulerOrbit (α : ℝ) : ℕ → ℝ[X]
      | 0 => 1
      | n + 1 => centeredEulerStep α (centeredEulerOrbit α n)
  • The second-order step X + (θ + a)(θ + b)

    RealRooted.EulerBidiagonal.stepsource
    def step (a b : ℝ) (p : ℝ[X]) : ℝ[X] :=
      X * p + (theta (theta p) + C (a + b) * theta p + C (a * b) * p)
  • The second-order step κ(θ + a)(θ + b) + X(u + vθ)

    RealRooted.EulerBidiagonal.generalStepsource
    def generalStep (κ a b u v : ℝ) (p : ℝ[X]) : ℝ[X] :=
      C κ * (theta (theta p) + C (a + b) * theta p + C (a * b) * p) +
        X * (C u * p + C v * theta p)
  • The Euler operator X d/dX on formal power series

    RealRooted.powerSeriesEulersource
    def powerSeriesEuler {R : Type*} [CommSemiring R]
        (f : PowerSeries R) : PowerSeries R :=
      PowerSeries.X * PowerSeries.derivative f

Theorems

  • An Euler step with c > 0 gives simple negative roots and interlacingMain resultRealRooted original

    RealRooted.realEulerInsertionStep_simple_roots_strictInterlsource
    theorem realEulerInsertionStep_simple_roots_strictInterl
        {c a : ℝ} {p : ℝ[X]}
        (hc : 0 < c) (ha : (p.natDegree : ℝ) < a)
        (hp_pos : HasPosLeadingCoeff p) (hp_nn : HasNonnegCoeffs p)
        (hp_splits : p.Splits) (hp_simple : HasSimpleRoots p)
        (hp_zero : 0 < p.eval 0) :
        let q
  • Coupled Euler families: simple negative roots and interlacingRealRooted original

    RealRooted.coupledEuler_simple_roots_strictInterlsource
    theorem coupledEuler_simple_roots_strictInterl
        {P Q : ℕ → ℝ[X]} {c : ℝ} {lam b t : ℕ → ℝ}
        (hc : 0 < c) (hlam : ∀ n, 0 ≤ lam n)
        (hb : ∀ n : ℕ, (n : ℝ) < b n)
        (ht : ∀ n, t n = b n + lam n)
        (ht_step : ∀ n, 1 ≤ t (n + 1) - t n)
        (hP0 : P 0 = 1) (hQ0 : Q 0 = 1)
        (hP : ∀ n, P (n + 1) =
          (C (c + lam n) + C (b n) * X) * P n +
            (X - X ^ 2) * (P n).derivative)
        (hQ : ∀ n, Q (n + 1) =
          (C c + C (t n) * X) * P n +
            (X - X ^ 2) * (P n).derivative) :
        (∀ n, (P n).natDegree = n ∧ HasPosLeadingCoeff (P n) ∧
          HasNonnegCoeffs (P n) ∧ (P n).Splits ∧ HasSimpleRoots (P n) ∧
          (∀ r, (P n).IsRoot r → r < 0)) ∧
        (∀ n, (Q n).natDegree = n ∧ HasPosLeadingCoeff (Q n) ∧
          HasNonnegCoeffs (Q n) ∧ (Q n).Splits ∧ HasSimpleRoots (Q n) ∧
          (∀ r, (Q n).IsRoot r → r < 0)) ∧
        (∀ n, StrictInterl (P n) (P (n + 1))) ∧
        (∀ n, StrictInterl (P n) (Q (n + 1))) ∧
        (∀ n, StrictInterl (Q n) (Q (n + 1)))
  • Second-order recurrence for Q_{n+2} in terms of Q_{n+1} and P_nRealRooted original

    RealRooted.coupledEuler_secondOrdersource
    theorem coupledEuler_secondOrder
        {P Q : ℕ → ℝ[X]} {c : ℝ} {lam b t : ℕ → ℝ}
        (ht : ∀ n, t n = b n + lam n)
        (hP : ∀ n, P (n + 1) =
          (C (c + lam n) + C (b n) * X) * P n +
            (X - X ^ 2) * (P n).derivative)
        (hQ : ∀ n, Q (n + 1) =
          (C c + C (t n) * X) * P n +
            (X - X ^ 2) * (P n).derivative) :
        ∀ n, Q (n + 2) =
          (C (c + lam n) + C (b n + (t (n + 1) - t n)) * X) * Q (n + 1) +
            (X - X ^ 2) * (Q (n + 1)).derivative +
              C (lam n * (t (n + 1) - t n - 1)) * (X - X ^ 2) * P n
  • Scaled Euler steps: simple negative roots of F_n and (θ + σ) F_n, interlacingRealRooted original

    RealRooted.eulerMultiplier_simpleNegRooted_and_strictInterlsource
    theorem eulerMultiplier_simpleNegRooted_and_strictInterl
        {F : ℕ → ℝ[X]} {sigma : ℝ} {gamma beta : ℕ → ℝ}
        (hsigma : 0 < sigma)
        (hgamma : ∀ n, 0 < gamma (n + 1))
        (hbeta : ∀ n, gamma (n + 1) * n < beta (n + 1))
        (hFzero : F 0 = 1)
        (hFsucc : ∀ n, F (n + 1) =
          scaledEulerInsertionStep sigma (gamma (n + 1)) (beta (n + 1)) (F n)) :
        (∀ n, SimpleNegRooted (F n) n) ∧
          (∀ n, SimpleNegRooted (eulerShift sigma (F n)) n) ∧
          (∀ n, StrictInterl (eulerShift sigma (F n))
            (eulerShift sigma (F (n + 1))))
  • A nonnegative lag-two correction preserves simple negative roots and interlacingRealRooted original

    RealRooted.lagTwoEulerPolynomial_certificatesource
    theorem lagTwoEulerPolynomial_certificate
        {m : ℝ} {lambda : ℕ → ℝ} (hm : 1 ≤ m)
        (hlambda : ∀ n, 0 ≤ lambda n) (n : ℕ) :
        LagTwoEulerPairCertificate (lagTwoEulerPolynomial m lambda) n
  • Monomial perturbations of the centered Euler orbit interlaceRealRooted original

    RealRooted.centeredEulerOrbit_add_monomialsource
    theorem centeredEulerOrbit_add_monomial {α b : ℝ} (hα : 1 / 2 ≤ α) (hb : -1 < b) (hb1 : b ≤ 1)
        {n : ℕ} (hn : 0 < n) :
        (centeredEulerOrbit α n + C b * X ^ n).natDegree = n ∧
          HasPosLeadingCoeff (centeredEulerOrbit α n + C b * X ^ n) ∧
          IsRealRootedIn (Ioo (-1 : ℝ) 1) (centeredEulerOrbit α n + C b * X ^ n) ∧
          HasSimpleRoots (centeredEulerOrbit α n + C b * X ^ n) ∧
          StrictInterl (centeredEulerOrbit α n + C b * X ^ n)
            (centeredEulerOrbit α (n + 1) + C b * X ^ (n + 1))
  • A three-term θ-recurrence with perturbed seeds has interlacing rowsRealRooted original

    RealRooted.strictInterl_of_orbitPerturbation_recurrencesource
    theorem strictInterl_of_orbitPerturbation_recurrence {s κ : ℝ} (hs : 1 ≤ s) (hκ : s + 4 ≤ κ)
        {Q : ℕ → ℝ[X]} (h0 : Q 0 = 1) (h1 : Q 1 = C 2 * X + 1)
        (h2 : Q 2 = C κ * X ^ 2 + C κ * X + 1)
        (hrec : ∀ n : ℕ, ((n : ℝ[X]) + 1) * Q (n + 3) =
          (2 * (n : ℝ[X]) + 3) * (C 2 * X + 1) * Q (n + 2) +
            ((n : ℝ[X]) + 1) * C s * (X + 1) * (X * (Q (n + 2)).derivative) -
            ((n : ℝ[X]) + 2) * (C 2 * X + 1) *
              ((C 2 * X + 1) * Q (n + 1) + C s * (X + 1) * (X * (Q (n + 1)).derivative))) (n : ℕ) :
        IsRealRootedIn (Ioo (-1 : ℝ) 0) (Q n) ∧ HasSimpleRoots (Q n) ∧
          StrictInterl (Q n) (Q (n + 1))
  • Perturbed generalized Eulerian polynomials interlaceRealRooted original

    RealRooted.strictInterl_C_mul_generalizedEulerian_addsource
    theorem strictInterl_C_mul_generalizedEulerian_add {s c : ℝ} (hs : 1 ≤ s) (hc : 1 / 2 ≤ c)
        (n : ℕ) :
        StrictInterl (C c * generalizedEulerian s n + C (1 - c) * (1 + X) ^ n)
          (C c * generalizedEulerian s (n + 1) + C (1 - c) * (1 + X) ^ (n + 1))
  • The step X + (θ + a)(θ + b) preserves interlacing of negative-simple pairsRealRooted original

    RealRooted.EulerBidiagonal.strictInterl_step_of_strictInterlsource
    theorem strictInterl_step_of_strictInterl {a b : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b)
        (hab : 0 < a * b) {f g : ℝ[X]} (hfg : StrictInterl f g)
        (hdeg : g.natDegree = f.natDegree + 1)
        (hcop : ∀ r, ¬ (f.IsRoot r ∧ g.IsRoot r))
        (hf : IsNegativeSimple f) (hg : IsNegativeSimple g) :
        StrictInterl (step a b f) (step a b g) ∧
          ∀ r, ¬ ((step a b f).IsRoot r ∧ (step a b g).IsRoot r)
  • Consecutive iterates of X + (θ + a)(θ + b) interlaceRealRooted original

    RealRooted.EulerBidiagonal.strictInterl_rowssource
    theorem strictInterl_rows {a b : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b)
        (hab : 0 < a * b) :
        ∀ n, StrictInterl (rows a b n) (rows a b (n + 1)) ∧
          ∀ r, ¬ ((rows a b n).IsRoot r ∧ (rows a b (n + 1)).IsRoot r)
  • The step κ(θ + a)(θ + b) + X(u + vθ) preserves interlacing of negative-simple pairsRealRooted original

    RealRooted.EulerBidiagonal.strictInterl_generalStep_of_strictInterlsource
    theorem strictInterl_generalStep_of_strictInterl
        (κ a b u v : ℝ) (f g : ℝ[X]) (d : ℕ) (hf : IsNegativeSimple f) (hg : IsNegativeSimple g)
        (hfd : f.natDegree = d) (hgd : g.natDegree = d + 1) (hfg : StrictInterl f g)
        (hno : ∀ s, f.IsRoot s → ¬ g.IsRoot s) (hκ : 0 < κ) (ha : 0 < a) (hb : 0 < b)
        (hell : ∀ k ≤ d + 1, 0 < u + v * k) (hQ : ∀ t ≤ 0, comparisonDefect κ a b u v t < 0) :
        StrictInterl (generalStep κ a b u v f) (generalStep κ a b u v g) ∧
          ∀ x, (generalStep κ a b u v f).IsRoot x → ¬ (generalStep κ a b u v g).IsRoot x
  • θ^k multiplies the coefficient of X^n by n^kRealRooted original

    RealRooted.coeff_powerSeriesEuler_iteratesource
    @[simp] theorem coeff_powerSeriesEuler_iterate {R : Type*} [CommSemiring R]
        (f : PowerSeries R) (k n : ℕ) :
        PowerSeries.coeff n ((powerSeriesEuler^[k]) f) =
          (n : R) ^ k * PowerSeries.coeff n f
  • M D^k F = (D - c)^k N when D M = c M and M F = NRealRooted original

    RealRooted.mul_iterate_derivation_eq_iterate_derivationShift_of_mul_eqsource
    theorem mul_iterate_derivation_eq_iterate_derivationShift_of_mul_eq
        {R A : Type*} [CommRing R] [CommRing A] [Algebra R A]
        (D : Derivation R A A) (c : R) {M F N : A}
        (hM : D M = algebraMap R A c * M) (hN : M * F = N) (k : ℕ) :
        M * (D^[k]) F = ((derivationShift D c)^[k]) N

Lean source RealRooted/Challenges/Combinatorial/EulerianOperators.lean at revision d6670742. Formalized 2026-11-01.