Mesh and finite differences

Operators built from derivatives and finite differences preserve a lower bound on the distance between consecutive roots of a real-rooted polynomial. This mesh condition is the finite difference analogue of real-rootedness, and it leads to a discrete Hermite–Poulain theorem and discrete multiplier sequences.

Results

We write $p\in\mathrm{Mesh}_{\ge\alpha}$ if $p$ is real-rooted and consecutive roots, listed increasingly with multiplicity, differ by at least $\alpha\ge0$. Theorem numbers refer to Brändén, Krasikov and Shapiro.

Theorem 1 (Riesz). If $p\in\mathrm{Mesh}_{\ge\alpha}$ and $c\in\mathbb R$, then $p-c\,p'\in\mathrm{Mesh}_{\ge\alpha}$.

Theorem 2. Let $\alpha,\lambda>0$ and $\beta\ge\alpha$. If $p\in\mathrm{Mesh}_{\ge\beta}$, then $p(x)-\lambda\,p(x-\alpha)\in\mathrm{Mesh}_{\ge\beta}$.

Theorem 3 (discrete Hermite–Poulain). Let $\alpha>0$ and let $Q(t)=\sum_k a_kt^k$ be a real polynomial. The operator $$p(x)\longmapsto\sum_ka_k\,p(x-k\alpha)$$ maps $\mathrm{Mesh}_{\ge\alpha}$ into $\mathrm{Mesh}_{\ge\alpha}$ if and only if $Q$ is zero or has only real nonnegative zeros. For such $Q$ it maps $\mathrm{Mesh}_{\ge\beta}$ into itself for every $\beta\ge\alpha$.

Theorem 5. If $a,b\ge0$, $p\in\mathrm{Mesh}_{\ge1}$ and $p$ has only nonnegative zeros, then $$a\,p(x)+b\,x\,\bigl(p(x)-p(x-1)\bigr)$$ lies in $\mathrm{Mesh}_{\ge1}$ and has only nonnegative zeros.

Lemma 8. Let $q_0,\dots,q_k$ be real polynomials. The operator $$p(x)\longmapsto\sum_jq_j(x)\,p(x-j)$$ maps real-rooted polynomials to real-rooted polynomials or zero if and only if at most one $q_j$ is nonzero, and that $q_j$ is real-rooted.

A sequence $(a_i)$ is a discrete multiplier sequence if the linear operator with $[x]_i\mapsto a_i[x]_i$ on the falling factorials $[x]_i=x(x-1)\cdots(x-i+1)$ maps every $p\in\mathrm{Mesh}_{\ge1}$ with only nonnegative zeros to such a polynomial.

Corollary 2. If $\varphi\ne0$ is real-rooted with only nonpositive zeros, then $(\varphi(i))_{i\ge0}$ is a discrete multiplier sequence. The same holds for $(\operatorname{Re} \varphi(i))_{i\ge0}$ when $\varphi$ is a locally uniform limit of real-rooted polynomials with nonnegative coefficients.

Lemma 10 (Brenti). The linear map $x^i\mapsto[x]_i$ sends every real-rooted polynomial with only nonnegative zeros into $\mathrm{Mesh}_{\ge1}$, with only nonnegative zeros.

Lemma 11 and Corollary 3. If $p=\sum_{i\le n}a_i[x]_i$ lies in $\mathrm{Mesh}_{\ge1}$, has only nonnegative zeros and positive leading coefficient, then $(-1)^{n-i}a_i\ge0$ for $i\le n$. Consequently the entries of a discrete multiplier sequence are all nonnegative or all nonpositive.

Proposition 6. Every discrete multiplier sequence is a multiplier sequence in the classical sense. The converse fails: $(\rho^i)$ with $0<\rho<1$ is not a discrete multiplier sequence (Remark 2).

Proposition 7. A sequence with at most two nonzero entries is a discrete multiplier sequence if and only if its nonzero entries sit at adjacent indices $m,m+1$ and $a_ma_{m+1}\ge0$.

Proposition 12. If $(a_i)$ is a discrete multiplier sequence and $a_{m+2}>0$, then $a_m\le a_{m+1}$.

Proof

For Lemma 8 we apply the operator to $x^m$: two nonzero extreme shifts produce nonreal limits of zeros by the Beraha–Kahane–Weiss theorem. Corollary 2 uses that $\mathrm{Mesh}_{\ge\alpha}$ is closed under coefficientwise limits of bounded degree.

References

Definitions

  • Mesh at least α

    Polynomial.MeshGEsource
    def MeshGE (p : ℝ[X]) (α : ℝ) : Prop :=
      p.Splits ∧ 0 ≤ α ∧
        ∀ i, i + 1 < (p.roots.sort (· ≤ ·)).length →
          (p.roots.sort (· ≤ ·)).getD i 0 + α ≤
            (p.roots.sort (· ≤ ·)).getD (i + 1) 0
  • The finite difference p(x) − λ p(x − α)

    RealRooted.meshDifferencesource
    def meshDifference (α lam : ℝ) (p : ℝ[X]) : ℝ[X] :=
      p - C lam * p.comp (X - C α)
  • The finite-difference operator with symbol Q

    RealRooted.finiteDifferenceOpsource
    def finiteDifferenceOp (α : ℝ) (Q p : ℝ[X]) : ℝ[X] :=
      Q.sum fun k a => C a * p.comp (X - C ((k : ℝ) * α))
  • Discrete multiplier sequence

    RealRooted.IsDiscreteMultiplierSequencesource
    def IsDiscreteMultiplierSequence (a : ℕ → ℝ) : Prop :=
      ∀ T : ℝ[X] →ₗ[ℝ] ℝ[X],
        (∀ i, T (descPochhammer ℝ i) = a i • descPochhammer ℝ i) →
          ∀ p : ℝ[X], p.MeshGE 1 → HasOnlyNonnegRoots p →
            (T p).MeshGE 1 ∧ HasOnlyNonnegRoots (T p)

Theorems

  • Riesz: subtracting c p′ does not decrease the mesh

    Polynomial.MeshGE.sub_C_mul_derivativesource
    theorem sub_C_mul_derivative {p : ℝ[X]} {α : ℝ} (h : p.MeshGE α) (c : ℝ) :
        (p - C c * derivative p).MeshGE α
  • Positive finite differences preserve mesh bounds at least their step

    RealRooted.meshDifference_meshGEsource
    theorem meshDifference_meshGE {p : ℝ[X]} {α β lam : ℝ}
        (hα : 0 < α) (hlam : 0 < lam) (hp : p.MeshGE β) (hαβ : α ≤ β) :
        (meshDifference α lam p).MeshGE β
  • Discrete Hermite–Poulain theoremMain result

    RealRooted.forall_finiteDifferenceOp_meshGE_iffsource
    theorem forall_finiteDifferenceOp_meshGE_iff {α : ℝ} {Q : ℝ[X]} (hα : 0 < α) :
        (∀ p : ℝ[X], p.MeshGE α → (finiteDifferenceOp α Q p).MeshGE α) ↔
          HasOnlyNonnegRoots Q
  • The operator a p + b x (p(x) − p(x − 1)) preserves mesh at least one

    RealRooted.meshGE_one_add_X_mul_meshDifferencesource
    theorem meshGE_one_add_X_mul_meshDifference {p : ℝ[X]} {a b : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b)
        (hp : p.MeshGE 1) (hpnn : HasOnlyNonnegRoots p) :
        (C a * p + C b * (X * meshDifference 1 1 p)).MeshGE 1 ∧
          HasOnlyNonnegRoots (C a * p + C b * (X * meshDifference 1 1 p))
  • φ(0), φ(1), … is a discrete multiplier sequence for φ with nonpositive zeros

    RealRooted.isDiscreteMultiplierSequence_evalsource
    theorem isDiscreteMultiplierSequence_eval {φ : ℝ[X]} (hφ : φ ≠ 0) (hs : φ.Splits)
        (hroots : ∀ r ∈ φ.roots, r ≤ 0) :
        IsDiscreteMultiplierSequence fun i : ℕ => φ.eval (i : ℝ)
  • Discrete multiplier sequences increase where they are positive

    RealRooted.IsDiscreteMultiplierSequence.le_succsource
    theorem IsDiscreteMultiplierSequence.le_succ {a : ℕ → ℝ} (ha : IsDiscreteMultiplierSequence a)
        (m : ℕ) (hpos : 0 < a (m + 2)) : a m ≤ a (m + 1)
  • Brenti: x^i ↦ [x]_i sends nonnegative zeros to mesh at least one

    RealRooted.fallingFactorialMap_meshGE_onesource
    theorem fallingFactorialMap_meshGE_one {p : ℝ[X]} (hp : HasOnlyNonnegRoots p) :
        (fallingFactorialMap p).MeshGE 1 ∧ HasOnlyNonnegRoots (fallingFactorialMap p)
  • Falling-factorial coefficients alternate in sign

    RealRooted.neg_one_pow_mul_descPochhammerBasis_repr_nonnegsource
    theorem neg_one_pow_mul_descPochhammerBasis_repr_nonneg {p : ℝ[X]} (hpos : HasPosLeadingCoeff p)
        (hmesh : p.MeshGE 1) (hnn : HasOnlyNonnegRoots p) {i : ℕ} (hi : i ≤ p.natDegree) :
        0 ≤ (-1 : ℝ) ^ (p.natDegree - i) * (descPochhammerBasis ℝ).repr p i
  • Nonzero entries of a discrete multiplier sequence share a sign

    RealRooted.IsDiscreteMultiplierSequence.nonneg_or_nonpossource
    theorem IsDiscreteMultiplierSequence.nonneg_or_nonpos {a : ℕ → ℝ}
        (ha : IsDiscreteMultiplierSequence a) : (∀ i, 0 ≤ a i) ∨ (∀ i, a i ≤ 0)
  • Trivial discrete multiplier sequences

    RealRooted.isDiscreteMultiplierSequence_iff_adjacent_of_two_nonzerosource
    theorem isDiscreteMultiplierSequence_iff_adjacent_of_two_nonzero {a : ℕ → ℝ}
        (h2 : ∃ i j, ∀ k, k ≠ i → k ≠ j → a k = 0) :
        IsDiscreteMultiplierSequence a ↔
          ∃ m, 0 ≤ a m * a (m + 1) ∧ ∀ i, i ≠ m → i ≠ m + 1 → a i = 0
  • Discrete multiplier sequences are multiplier sequences

    RealRooted.IsDiscreteMultiplierSequence.isMultiplierSequencesource
    theorem IsDiscreteMultiplierSequence.isMultiplierSequence {a : ℕ → ℝ}
        (ha : IsDiscreteMultiplierSequence a) : IsMultiplierSequence a
  • ρ^i with 0 < ρ < 1 is not a discrete multiplier sequence

    RealRooted.not_isDiscreteMultiplierSequence_geometricsource
    theorem not_isDiscreteMultiplierSequence_geometric {ρ : ℝ} (h0 : 0 < ρ) (h1 : ρ < 1) :
        ¬ IsDiscreteMultiplierSequence fun i : ℕ => ρ ^ i
  • φ(0), φ(1), … is a discrete multiplier sequence for φ in the Laguerre–Pólya class

    RealRooted.isDiscreteMultiplierSequence_of_isLaguerrePolyaTypeIsource
    theorem isDiscreteMultiplierSequence_of_isLaguerrePolyaTypeI {f : ℂ → ℂ}
        (hf : IsLaguerrePolyaTypeI f) : IsDiscreteMultiplierSequence fun i : ℕ => (f i).re
  • p ↦ ∑ q_j(x) p(x − j) preserves real-rootedness iff at most one q_j is nonzero

    RealRooted.PreservesRealRootedOrZero.polyFiniteDifferenceOp_iffsource
    theorem _root_.RealRooted.PreservesRealRootedOrZero.polyFiniteDifferenceOp_iff
        {n : ℕ} {q : Fin n → ℝ[X]} :
        PreservesRealRootedOrZero (polyFiniteDifferenceOp q) ↔
          Set.Subsingleton {j | q j ≠ 0} ∧ ∀ j, q j ≠ 0 → (q j).Splits
  • Symbols with nonnegative real zeros preserve Mesh ≥ β for every β ≥ α

    RealRooted.finiteDifferenceOp_meshGEsource
    theorem finiteDifferenceOp_meshGE {β : ℝ} (hα : 0 < α)
        (hQ : HasOnlyNonnegRoots Q) (hp : p.MeshGE β) (hαβ : α ≤ β) :
        (finiteDifferenceOp α Q p).MeshGE β
  • Only nonnegative roots is closed under coefficientwise limits of bounded degree

    RealRooted.HasOnlyNonnegRoots.of_tendsto_coeffsource
    theorem HasOnlyNonnegRoots.of_tendsto_coeff {q : ℕ → ℝ[X]} {q₀ : ℝ[X]} {N : ℕ}
        (hnn : ∀ k, HasOnlyNonnegRoots (q k)) (hdeg : ∀ k, (q k).natDegree ≤ N)
        (hcoeff : ∀ i, Tendsto (fun k => (q k).coeff i) atTop (𝓝 (q₀.coeff i))) :
        HasOnlyNonnegRoots q₀

Lean source RealRooted/Challenges/Roots/MeshFiniteDifference.lean at revision d6670742. Formalized 2026-10-27.