Central limit theorems for real-rooted coefficient distributions

The coefficients of a real-rooted polynomial with nonnegative coefficients are asymptotically normal as soon as their variance diverges; the Eulerian, type $B$ Eulerian, Narayana, second-order Eulerian and derangement excedance numbers and the Stirling numbers of the first kind are examples.

Results

For a polynomial $p$ with nonnegative coefficients and $p(1)\ne0$, the coefficient distribution puts mass $p_k/p(1)$ at $k$. Its mean and variance are $$ \mu(p)=\frac{p'(1)}{p(1)},\qquad \sigma^2(p)=\frac{p''(1)}{p(1)}+\mu(p)-\mu(p)^2 . $$ If $p$ is real-rooted with roots $-r_i\le0$, then $p(x)/p(1)=\prod_i(1-q_i+q_ix)$ with $q_i=1/(1+r_i)$. The coefficient distribution is that of a sum of independent Bernoulli variables, with $\mu=\sum_iq_i$ and $\sigma^2=\sum_iq_i(1-q_i)$.

Theorem (Harper; Bender). Let $P_n$ be real-rooted polynomials with nonnegative coefficients and $\sigma^2(P_n)\to\infty$. Then the laws of $(K_n-\mu_n)/\sigma_n$, where $K_n$ has the coefficient distribution of $P_n$, converge weakly to the standard normal distribution [Har67]; [Ben73].

Theorem (Bender, local limit). Let $P_n$ be nonzero real-rooted polynomials with nonnegative coefficients and $\sigma^2(P_n)\to\infty$. Let $\mu_n,\sigma_n$ be the mean and standard deviation of the coefficient distribution, and $\varphi$ the standard Gaussian density. Then $$ \sup_{k\ge0}\left|\sigma_n\,\frac{[x^k]P_n(x)}{P_n(1)} -\varphi\!\left(\frac{k-\mu_n}{\sigma_n}\right)\right|\longrightarrow0 \qquad(n\to\infty). $$ More generally, the same holds for nonzero polynomials $P_n$ with nonnegative log-concave coefficients without internal zeros, with $\sigma^2(P_n)\to\infty$, whose standardized coefficient distributions converge weakly to the standard normal distribution [Ben73, Thm. 2].

Theorem (products). Let $L_i$ be real-rooted with nonnegative coefficients and $L_i(1)\ne0$. If $\sum_{i<n}\sigma^2(L_i)\to\infty$, the standardized coefficient distributions of $\prod_{i<n}L_i$ converge weakly to the standard normal distribution. For $(1+x)^n$ this is the de Moivre–Laplace theorem. For $\prod_{i<n}(x+i)$, whose coefficients are the unsigned Stirling numbers of the first kind, the factor $x+i$ has variance $i/(i+1)^2\ge1/(2(i+1))$ for $i\ge1$, and the harmonic series diverges; this is Goncharov's theorem.

Theorem (three-term recurrences). Let $P_{n+2}=a\,P_{n+1}+b\,P_n$ with polynomials $a,b$ independent of $n$. Let $\lambda\ne\nu$ be the roots of $t^2=a(1)t+b(1)$ with $\lambda>|\nu|$ and $\nu\ne0$, and assume that $\bigl(P_1(1)-\nu P_0(1)\bigr)/(\lambda-\nu)\ne0$. Let $\lambda(x)$ be the root branch of $t^2=a(x)t+b(x)$ through $\lambda$. Then $$ \frac{\mu(P_n)}n\to\frac{\lambda'(1)}{\lambda(1)},\qquad \frac{\sigma^2(P_n)}n\to\frac{\lambda''}{\lambda}+\frac{\lambda'}{\lambda}- \Bigl(\frac{\lambda'}{\lambda}\Bigr)^2\quad\text{at }x=1, $$ where the limits are expressed algebraically in $a(1)$, $b(1)$ and their derivatives (Bender's formulas).

Examples. Each family below has nonnegative real-rooted rows with variance tending to infinity, so its coefficients are asymptotically normal.

Proof

The characteristic function of the standardized distribution is a product of centred Bernoulli factors, and the product is within $2|t|^3/\sigma$ of $e^{-t^2/2}$; Lévy's continuity theorem gives weak convergence. For the local limit theorem, log-concavity without internal zeros makes the coefficients quasi-concave, and weak convergence with Pólya's theorem makes window sums of coefficients uniformly close to Gaussian integrals.

References

  1. [Ben73] Edward A Bender. Central and local limit theorems applied to asymptotic enumeration. Journal of Combinatorial Theory, Series A, 15(1), 91--111, 1973.
    BibTeX
    @article{Bender1973,
      title = {Central and local limit theorems applied to asymptotic enumeration},
      volume = {15},
      ISSN = {0097-3165},
      url = {http://dx.doi.org/10.1016/0097-3165(73)90038-1},
      DOI = {10.1016/0097-3165(73)90038-1},
      number = {1},
      journal = {Journal of Combinatorial Theory,  Series A},
      publisher = {Elsevier BV},
      author = {Bender,  Edward A},
      year = {1973},
      month = jul,
      pages = {91–-111}
    }
  2. [Bon09] Miklós Bóna. Real Zeros and Normal Distribution for Statistics on Stirling Permutations Defined by Gessel and Stanley. SIAM Journal on Discrete Mathematics, 23(1), 401-406, 2009.
    BibTeX
    @article{Bona2009,
      doi = {10.1137/070702254},
      url = {https://doi.org/10.1137/070702254},
      year = {2009},
      month = jan,
      publisher = {Society for Industrial \& Applied Mathematics ({SIAM})},
      volume = {23},
      number = {1},
      pages = {401--406},
      author = {Mikl{\'{o}}s B{\'{o}}na},
      title = {Real Zeros and Normal Distribution for Statistics on {S}tirling Permutations Defined by {G}essel and {S}tanley},
      journal = {{SIAM} Journal on Discrete Mathematics}
    }
  3. [Har67] L. H. Harper. Stirling Behavior is Asymptotically Normal. The Annals of Mathematical Statistics, 38(2), 410-414, 1967.
    BibTeX
    @article{Harper1967,
      author = {Harper, L. H.},
      title = {Stirling {B}ehavior is {A}symptotically {N}ormal},
      year = {1967},
      journal = {The Annals of Mathematical Statistics},
      volume = {38},
      number = {2},
      pages = {410--414},
      doi = {10.1214/aoms/1177698956},
      url = {https://doi.org/10.1214/aoms/1177698956}
    }

Definitions

  • Standardized coefficient distribution of a polynomial

    Polynomial.standardizedCoeffDistributionsource
    def standardizedCoeffDistribution (p : ℝ[X]) : ProbabilityMeasure ℝ :=
      p.coeffDistribution.map fun x => (x - p.coeffMean) / p.coeffStdDev

Theorems

  • Variance of a real-rooted coefficient distribution is Σᵢ qᵢ(1 − qᵢ)

    Polynomial.coeffVariance_eq_sumsource
    theorem coeffVariance_eq_sum {p : ℝ[X]} (hs : p.Splits) (hnn : ∀ k, 0 ≤ p.coeff k)
        (hp : p ≠ 0) :
        p.coeffVariance = (p.roots.map fun a => (1 - a)⁻¹ * (1 - (1 - a)⁻¹)).sum
  • Harper: real-rooted coefficient distributions are asymptotically normal

    Polynomial.tendsto_standardizedCoeffDistributionsource
    theorem tendsto_standardizedCoeffDistribution {P : ℕ → ℝ[X]} (hs : ∀ n, (P n).Splits)
        (hnn : ∀ n k, 0 ≤ (P n).coeff k)
        (hvar : Tendsto (fun n => (P n).coeffVariance) atTop atTop) :
        Tendsto (fun n => (P n).standardizedCoeffDistribution) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • Bender: real-rooted coefficient rows satisfy a local limit theoremMain result

    Polynomial.tendsto_localLimit_of_splitssource
    theorem tendsto_localLimit_of_splits {P : ℕ → ℝ[X]}
        (hne : ∀ n, P n ≠ 0) (hs : ∀ n, (P n).Splits)
        (hnn : ∀ n k, 0 ≤ (P n).coeff k)
        (hvar : Tendsto (fun n => (P n).coeffVariance) atTop atTop) :
        ∀ ε > 0, ∀ᶠ n in atTop, ∀ k : ℕ,
          |(P n).coeffStdDev * ((P n).coeff k / (P n).eval 1) -
            gaussianPDFReal 0 1 (((k : ℝ) - (P n).coeffMean) / (P n).coeffStdDev)| < ε
  • Bender: log-concave rows satisfying a CLT satisfy a local limit theorem

    Polynomial.tendsto_localLimit_of_logConcavesource
    theorem tendsto_localLimit_of_logConcave {P : ℕ → ℝ[X]}
        (hnn : ∀ n k, 0 ≤ (P n).coeff k) (hne : ∀ n, P n ≠ 0)
        (hlc : ∀ n k, 0 < k → (P n).coeff (k - 1) * (P n).coeff (k + 1) ≤ (P n).coeff k ^ 2)
        (hnz : ∀ n i j k, i < j → j < k → (P n).coeff i ≠ 0 → (P n).coeff k ≠ 0 →
          (P n).coeff j ≠ 0)
        (hvar : Tendsto (fun n => coeffVariance (P n)) atTop atTop)
        (hclt : Tendsto (fun n => standardizedCoeffDistribution (P n)) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)) :
        ∀ ε > 0, ∀ᶠ n in atTop, ∀ k : ℕ,
          |coeffStdDev (P n) * ((P n).coeff k / (P n).eval 1) -
            gaussianPDFReal 0 1 (((k : ℝ) - coeffMean (P n)) / coeffStdDev (P n))| < ε
  • De Moivre–Laplace: the binomial distribution is asymptotically normal

    Polynomial.tendsto_standardizedCoeffDistribution_one_add_X_powsource
    theorem tendsto_standardizedCoeffDistribution_one_add_X_pow :
        Tendsto (fun n : ℕ => ((1 + X : ℝ[X]) ^ n).standardizedCoeffDistribution) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • Products of real-rooted factors with divergent total variance are asymptotically normal

    Polynomial.tendsto_standardizedCoeffDistribution_prod_rangesource
    theorem tendsto_standardizedCoeffDistribution_prod_range {L : ℕ → ℝ[X]}
        (hs : ∀ i, (L i).Splits) (hnn : ∀ i k, 0 ≤ (L i).coeff k) (h1 : ∀ i, (L i).eval 1 ≠ 0)
        (hvar : Tendsto (fun n => ∑ i ∈ Finset.range n, (L i).coeffVariance) atTop atTop) :
        Tendsto (fun n => (∏ i ∈ Finset.range n, L i).standardizedCoeffDistribution) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • Goncharov: Stirling numbers of the first kind are asymptotically normal

    Polynomial.tendsto_standardizedCoeffDistribution_prod_X_add_natCastsource
    theorem tendsto_standardizedCoeffDistribution_prod_X_add_natCast :
        Tendsto (fun n => (∏ i ∈ Finset.range n, (X + C (i : ℝ))).standardizedCoeffDistribution)
          atTop (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • The Eulerian numbers are asymptotically normal

    RealRooted.tendsto_standardizedCoeffDistribution_eulerianTildesource
    theorem tendsto_standardizedCoeffDistribution_eulerianTilde :
        Tendsto (fun n => (eulerianTilde n).standardizedCoeffDistribution) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • The type B Eulerian numbers are asymptotically normal

    RealRooted.GeneralizedEulerian.tendsto_standardizedCoeffDistribution_twosource
    theorem GeneralizedEulerian.tendsto_standardizedCoeffDistribution_two :
        Tendsto (fun n => (generalizedEulerian 2 n).standardizedCoeffDistribution) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • The Narayana numbers are asymptotically normal

    RealRooted.tendsto_standardizedCoeffDistribution_narayanasource
    theorem tendsto_standardizedCoeffDistribution_narayana :
        Tendsto (fun n => (narayana n).standardizedCoeffDistribution) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • The second-order Eulerian numbers are asymptotically normal

    RealRooted.tendsto_standardizedCoeffDistribution_stirlingPermutationssource
    theorem tendsto_standardizedCoeffDistribution_stirlingPermutations :
        Tendsto (fun n => (stirlingPermutations n).standardizedCoeffDistribution) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • Excedances of derangements are asymptotically normal

    RealRooted.tendsto_standardizedCoeffDistribution_sturmDerangementsExcsource
    theorem tendsto_standardizedCoeffDistribution_sturmDerangementsExc :
        Tendsto (fun n => (sturmDerangementsExc n).standardizedCoeffDistribution) atTop
          (𝓝 ⟨gaussianReal 0 1, inferInstance⟩)
  • Three-term recurrences: the mean grows like n λ'/λ

    RealRooted.ThreeTermRecurrence.tendsto_derivative_eval_div_nat_mul_evalsource
    theorem tendsto_derivative_eval_div_nat_mul_eval
        {P : ℕ → ℝ[X]} {a b : ℝ[X]} {lam nu : ℝ}
        (hP : ∀ n, P (n + 2) = a * P (n + 1) + b * P n)
        (hLam : lam ^ 2 = a.eval 1 * lam + b.eval 1)
        (hNu : nu ^ 2 = a.eval 1 * nu + b.eval 1)
        (hDistinct : lam ≠ nu) (hDominant : 0 < lam) (hModulus : |nu| < lam) (hNuNe : nu ≠ 0)
        (hA : ((P 1).eval 1 - nu * (P 0).eval 1) / (lam - nu) ≠ 0) :
        Tendsto (fun n => (P n).derivative.eval 1 /
          ((n : ℝ) * (P n).eval 1)) atTop
          (𝓝 (meanSlope a b lam))
  • Three-term recurrences: the variance grows linearly

    RealRooted.ThreeTermRecurrence.tendsto_variance_eval_div_natsource
    theorem tendsto_variance_eval_div_nat
        {P : ℕ → ℝ[X]} {a b : ℝ[X]} {lam nu : ℝ}
        (hP : ∀ n, P (n + 2) = a * P (n + 1) + b * P n)
        (hLam : lam ^ 2 = a.eval 1 * lam + b.eval 1)
        (hNu : nu ^ 2 = a.eval 1 * nu + b.eval 1)
        (hDistinct : lam ≠ nu) (hDominant : 0 < lam) (hModulus : |nu| < lam) (hNuNe : nu ≠ 0)
        (hA : ((P 1).eval 1 - nu * (P 0).eval 1) / (lam - nu) ≠ 0) :
        Tendsto (fun n =>
          ((P n).derivative.derivative.eval 1 / (P n).eval 1 +
              (P n).derivative.eval 1 / (P n).eval 1 -
              ((P n).derivative.eval 1 / (P n).eval 1) ^ 2) / (n : ℝ)) atTop
          (𝓝 (varianceSlope a b lam))

Lean source RealRooted/Challenges/Combinatorial/HarperCLT.lean at revision d6670742. Formalized 2026-10-12.