Limits of zeros of recursive families

The zeros of $f_n=\sum_k\alpha_k\beta_k^n$ accumulate where two dominant bases have equal modulus or where the dominant coefficient vanishes. For polynomials defined by a linear recurrence, a nonreal accumulation point shows that the late members are not real-rooted, so this is a standard tool for proving that real-rootedness fails.

Results

A point $z_0\in\mathbb C$ is a limit of zeros of functions $(F_n)_{n\ge0}$ if every ball around $z_0$ contains a zero of $F_n$ for all sufficiently large $n$ (the liminf notion of Sokal). In the next three theorems let $f_n(z)=\sum_{k\in s}\alpha_k(z)\,\beta_k(z)^n$ with $s$ a finite index set.

Theorem (two dominant bases). Let $\alpha_k,\beta_k$ be analytic at $z_0$. Suppose there are distinct $i,j\in s$ with $\alpha_i(z_0)\ne0$, $\alpha_j(z_0)\ne0$, $\beta_j(z_0)\ne0$ and $|\beta_i(z_0)|=|\beta_j(z_0)|$, that $|\beta_k(z_0)|<|\beta_j(z_0)|$ for every other $k\in s$, and that $\beta_i/\beta_j$ is not constant near $z_0$. Then $z_0$ is a limit of zeros of $(f_n)$.

Theorem (unique dominant base). Let $\alpha_k,\beta_k$ be analytic at $z_0$. Suppose $\beta_i(z_0)\ne0$ and $|\beta_k(z_0)|<|\beta_i(z_0)|$ for every $k\ne i$, and that $\alpha_i(z_0)=0$ while $\alpha_i$ does not vanish identically near $z_0$. Then $z_0$ is a limit of zeros of $(f_n)$.

Theorem (necessary condition). Let $\alpha_k,\beta_k$ be continuous at $z_0$. If $z_0$ is a limit of zeros of $(f_n)$, then at $z_0$ one of the following holds: two distinct bases $\beta_i,\beta_j$ have equal modulus, at least that of every $\beta_k$; or there is $i$ with $\alpha_i(z_0)=0$ and $|\beta_k(z_0)|<|\beta_i(z_0)|$ for all $k\ne i$; or every $\beta_k(z_0)$ vanishes.

Theorem (order-two recurrences). Let $W_{n+2}=A\,W_{n+1}+B\,W_n$ with $W_0=U$, $W_1=V$, and suppose $U,V$ and functions $u,v$ are analytic at $z_0$, where on a ball around $z_0$ we have $u+v=A$, $uv=-B$ and $u\ne v$.

Theorem (Wang–Zhang). Let $a,b,c,d>0$ and $W_0=1$, $W_1=x$, $$W_{n+2}=(a x+b)\,W_{n+1}+(c x+d)\,W_n.$$ Then every $W_n$ is real-rooted if and only if $ad\le bc$.

Use

For $ad>bc$, the order-two theorem gives a nonreal limit of zeros of the Wang–Zhang recurrence, so $W_n$ is not real-rooted for all large $n$.

References

  1. [Sok04, Theorems 1.5(b), 1.5(a) and 1.5] Alan D. Sokal. Chromatic roots are dense in the whole complex plane. Combinatorics, Probability and Computing, 13(2), 221-261, 2004.
    BibTeX
    @article{Sokal2004ChromaticRoots,
      author = {Alan D. Sokal},
      title = {Chromatic roots are dense in the whole complex plane},
      year = {2004},
      journal = {Combinatorics, Probability and Computing},
      volume = {13},
      number = {2},
      pages = {221--261},
      doi = {10.1017/S0963548303006023},
      url = {https://doi.org/10.1017/S0963548303006023},
      eprint = {cond-mat/0012369}
    }
  2. [WZ17, Theorem 2.1] David G. L. Wang & Jiarui Zhang. Root geometry of polynomial sequences III: Type $(1,1)$ with positive coefficients. arXiv e-prints, 2017.
    BibTeX
    @article{WangZhang2017RootGeometryIII,
      author = {David G. L. Wang and Jiarui Zhang},
      title = {Root geometry of polynomial sequences {{I}{I}{I}}: {T}ype $(1,1)$ with positive coefficients},
      year = {2017},
      eprint = {1712.06105v1},
      url = {https://arxiv.org/abs/1712.06105v1},
      journal = {arXiv e-prints}
    }

Definitions

  • Limit of zeros of a sequence of functions

    Complex.IsLimitOfZerossource
    def IsLimitOfZeros (F : ℕ → ℂ → ℂ) (z : ℂ) : Prop :=
      ∀ ε > 0, ∀ᶠ n in atTop, ∃ w ∈ ball z ε, F n w = 0

Theorems

  • Two equimodular dominant bases give a limit of zerosMain result

    Complex.isLimitOfZeros_finset_two_dominantsource
    theorem isLimitOfZeros_finset_two_dominant {κ : Type*}
        (s : Finset κ) (α β : κ → ℂ → ℂ) (i j : κ) {z₀ : ℂ}
        (hi : i ∈ s) (hj : j ∈ s) (hij : i ≠ j)
        (hα : ∀ k ∈ s, AnalyticAt ℂ (α k) z₀)
        (hβ : ∀ k ∈ s, AnalyticAt ℂ (β k) z₀)
        (hαi0 : α i z₀ ≠ 0) (hαj0 : α j z₀ ≠ 0)
        (hβj0 : β j z₀ ≠ 0) (heq : ‖β i z₀‖ = ‖β j z₀‖)
        (hsmall : ∀ k ∈ s, k ≠ i → k ≠ j → ‖β k z₀‖ < ‖β j z₀‖)
        (hnconst : ¬∀ᶠ z in 𝓝 z₀, β i z / β j z = β i z₀ / β j z₀) :
        IsLimitOfZeros (fun n z => ∑ k ∈ s, α k z * β k z ^ n) z₀
  • A unique dominant base with vanishing coefficient gives a limit of zeros

    Complex.isLimitOfZeros_finset_unique_dominantsource
    theorem isLimitOfZeros_finset_unique_dominant {κ : Type*}
        (s : Finset κ) (α β : κ → ℂ → ℂ) (i : κ) {z₀ : ℂ} (hi : i ∈ s)
        (hα : ∀ k ∈ s, AnalyticAt ℂ (α k) z₀)
        (hβ : ∀ k ∈ s, AnalyticAt ℂ (β k) z₀)
        (hβi0 : β i z₀ ≠ 0)
        (hsmall : ∀ k ∈ s, k ≠ i → ‖β k z₀‖ < ‖β i z₀‖)
        (hαi0 : α i z₀ = 0) (hnconst : ¬∀ᶠ z in 𝓝 z₀, α i z = 0) :
        IsLimitOfZeros (fun n z => ∑ k ∈ s, α k z * β k z ^ n) z₀
  • Limits of zeros occur only at two dominant bases or a vanishing dominant coefficient

    Complex.isLimitOfZeros_imp_dominant_or_coeff_zerosource
    theorem isLimitOfZeros_imp_dominant_or_coeff_zero {κ : Type*}
        (s : Finset κ) (α β : κ → ℂ → ℂ) {z₀ : ℂ}
        (hα : ∀ k ∈ s, ContinuousAt (α k) z₀)
        (hβ : ∀ k ∈ s, ContinuousAt (β k) z₀)
        (hlim : IsLimitOfZeros (fun n z => ∑ k ∈ s, α k z * β k z ^ n) z₀) :
        (∃ i ∈ s, ∃ j ∈ s, i ≠ j ∧ ‖β i z₀‖ = ‖β j z₀‖ ∧
          ∀ k ∈ s, ‖β k z₀‖ ≤ ‖β i z₀‖) ∨
        (∃ i ∈ s, α i z₀ = 0 ∧
          ∀ k ∈ s, k ≠ i → ‖β k z₀‖ < ‖β i z₀‖) ∨
        (∀ k ∈ s, β k z₀ = 0)
  • Limits of zeros of an order-two recurrence

    RealRooted.isLimitOfZeros_two_step_of_rootssource
    theorem isLimitOfZeros_two_step_of_roots {A B U V u v : ℂ → ℂ}
        {W : ℕ → ℂ → ℂ} {z₀ : ℂ} {ρ : ℝ} (hρ : 0 < ρ)
        (h0 : W 0 = U) (h1 : W 1 = V)
        (hrec : ∀ n z, W (n + 2) z = A z * W (n + 1) z + B z * W n z)
        (hroots : ∀ z ∈ ball z₀ ρ, u z + v z = A z ∧ u z * v z = -B z ∧ u z ≠ v z)
        (hU : AnalyticAt ℂ U z₀) (hV : AnalyticAt ℂ V z₀)
        (hu : AnalyticAt ℂ u z₀) (hv : AnalyticAt ℂ v z₀)
        (hunu : u z₀ ≠ v z₀) (hv0 : v z₀ ≠ 0)
        (hcoeffu : V z₀ - v z₀ * U z₀ ≠ 0)
        (hcoeffv : u z₀ * U z₀ - V z₀ ≠ 0)
        (heq : ‖u z₀‖ = ‖v z₀‖)
        (hnconst : ¬∀ᶠ z in 𝓝 z₀, u z / v z = u z₀ / v z₀) :
        Complex.IsLimitOfZeros W z₀
  • Unequal characteristic roots exclude limits of zeros

    RealRooted.not_isLimitOfZeros_two_step_of_rootssource
    theorem not_isLimitOfZeros_two_step_of_roots {A B U V u v : ℂ → ℂ}
        {W : ℕ → ℂ → ℂ} {z₀ : ℂ} {ρ : ℝ} (hρ : 0 < ρ)
        (h0 : W 0 = U) (h1 : W 1 = V)
        (hrec : ∀ n z, W (n + 2) z = A z * W (n + 1) z + B z * W n z)
        (hroots : ∀ z ∈ ball z₀ ρ, u z + v z = A z ∧ u z * v z = -B z ∧ u z ≠ v z)
        (hU : AnalyticAt ℂ U z₀) (hV : AnalyticAt ℂ V z₀)
        (hu : AnalyticAt ℂ u z₀) (hv : AnalyticAt ℂ v z₀)
        (hunu : u z₀ ≠ v z₀) (hnorm : ‖u z₀‖ ≠ ‖v z₀‖)
        (hcoeffu : ‖v z₀‖ < ‖u z₀‖ → V z₀ - v z₀ * U z₀ ≠ 0)
        (hcoeffv : ‖u z₀‖ < ‖v z₀‖ → u z₀ * U z₀ - V z₀ ≠ 0) :
        ¬Complex.IsLimitOfZeros W z₀
  • A nonreal limit of zeros forces late polynomials to be not real-rooted

    RealRooted.eventually_not_splits_of_nonreal_limitsource
    theorem eventually_not_splits_of_nonreal_limit {W : ℕ → ℝ[X]} {z₀ : ℂ}
        (hz₀ : z₀.im ≠ 0)
        (hW : ∀ᶠ n in atTop, W n ≠ 0)
        (hlim : Complex.IsLimitOfZeros
          (fun n z => ((W n).map Complex.ofRealHom).eval z) z₀) :
        ∀ᶠ n in atTop, ¬(W n).Splits
  • Wang–Zhang criterion for an affine three-term recurrence

    RealRooted.WangZhang.forall_splits_iffsource
    theorem forall_splits_iff {a b c d : ℝ} (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) (hd : 0 < d)
        (W : ℕ → ℝ[X]) (h0 : W 0 = 1) (h1 : W 1 = X)
        (hrec : ∀ n, W (n + 2) = (C a * X + C b) * W (n + 1) + (C c * X + C d) * W n) :
        (∀ n, (W n).Splits) ↔ a * d ≤ b * c

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