Grace's apolarity theorem

If two polynomials of degree $n$ are apolar and all zeros of one lie in a closed disk or closed half-plane, then the other has a zero there. Through polarization this gives the Grace–Walsh–Szegő theorem on symmetric multiaffine polynomials, the basic link between univariate real-rootedness and multivariate stability, and the Lieb–Sokal theorem.

Results

For coefficient sequences $a=(a_k)$ and $b=(b_k)$ and $n\ge0$ put $$ F(z)=\sum_{k=0}^n\binom nk a_kz^k,\qquad G(z)=\sum_{k=0}^n\binom nk b_kz^k , $$ so that $F$ is the binomial lift of $f=\sum_ka_kz^k$. We call $F$ and $G$ apolar if $$ \sum_{k=0}^n(-1)^k\binom nk a_kb_{n-k}=0 . $$ A polynomial in several variables is stable if it does not vanish when all variables lie in the open upper half-plane, and real stable if it has real coefficients and is stable.

Theorem (Grace). [Gra02] Let $F$ and $G$ be apolar polynomials of degree exactly $n$. If all zeros of $F$ lie in a closed disk $\{z:|z-c|\le r\}$ with $r\ge0$, or in a closed half-plane $\{z:\operatorname{Im}z\ge b\}$, then $G$ has a zero in the same set.

The polarization of a polynomial $p(z)=\sum_{k\le n}p_kz^k$ of degree at most $n$ is the symmetric multiaffine polynomial $$ \operatorname{Pol}_n(p)(z_1,\dots,z_n)=\sum_{k=0}^n\binom nk^{-1}p_k\,e_k(z_1,\dots,z_n), $$ where $e_k$ is the elementary symmetric polynomial; its diagonal $z_1=\dots=z_n=z$ is $p(z)$.

Theorem (polarization). If $\deg p\le n$ and $p$ has no zero in the open upper half-plane, then $\operatorname{Pol}_n(p)$ is stable.

Theorem (Grace–Walsh–Szegő). [Wal22]; [Sze22] Let $P\in\mathbb C[z_1,\dots,z_n]$ be symmetric and multiaffine, with diagonal $p(z)=P(z,\dots,z)$. Then $P=\operatorname{Pol}_n(p)$, and $P$ is stable if and only if $p$ has no zero in the open upper half-plane. If $P$ has real coefficients, then $P$ is real stable if and only if $p$ is nonzero and real-rooted.

Theorem (coincidence). Let $P\in\mathbb C[z_1,\dots,z_n]$ be symmetric and multiaffine, and let $C$ be one of the following: an open disk, a closed disk, an open half-plane, a closed half-plane, or the open or closed exterior of a disk, of radius $r>0$ (for a closed disk, $r\ge0$). For an exterior we assume that $P(z,\dots,z)$ has degree $n$. Then for all $\zeta_1,\dots,\zeta_n\in C$ there is $\zeta\in C$ with $$ P(\zeta_1,\dots,\zeta_n)=P(\zeta,\dots,\zeta). $$

Theorem (blockwise polarization). Let $\sigma$ be finite and let $P\in\mathbb C[z_i:i\in\sigma]$ have degree at most $\kappa_i$ in $z_i$. Replace each $z_i$ by a block of $\kappa_i$ new variables and polarize $P$ in each block. The resulting multiaffine polynomial is stable if and only if $P$ is stable.

Theorem (Lieb–Sokal). [LS81] Let $F$ and $G$ be stable polynomials in $\mathbb C[z_1,\dots,z_m]$. Then $F(-\partial)\,G$, obtained by substituting $-\partial/\partial z_i$ for $z_i$ in $F$ and applying the result to $G$, is zero or stable. This holds for multiaffine $F,G$ and, with the blockwise polarization above, for arbitrary degrees.

Proof

We prove Grace's theorem by induction on $n$: by Laguerre's theorem, the polar derivative of $F$ lowers the degree by one and keeps the zeros in the disk or half-plane. For polarization, $\operatorname{Pol}_n(p)(z)=0$ says that $p$ is apolar to $\prod_i(w-z_i)$; since the zeros of $p$ lie in the closed lower half-plane, Grace's theorem puts some $z_i$ there as well. The coincidence theorem for the upper half-plane follows by applying this to $P-P(\zeta)$, and the other regions follow by Möbius maps.

References

The classical sources are [Gra02]; [Wal22]; [Sze22] and [RS02]. See also [LS81]; [BB09]; [GM22, Thm. 2.4], as well as apolar polynomials and polarization on symmetricfunctions.com.

  1. [Gra02] J. H. Grace. The zeros of a polynomial. Proceedings of the Cambridge Philosophical Society, 11, 352-357, 1902.
    BibTeX
    @article{Grace1902,
      author  = {J. H. Grace},
      title   = {The zeros of a polynomial},
      journal = {Proceedings of the Cambridge Philosophical Society},
      volume  = {11},
      pages   = {352--357},
      year    = {1902}
    }
  2. [Wal22] J. L. Walsh. On the location of the roots of certain types of polynomials. Transactions of the American Mathematical Society, 24(3), 163-180, 1922.
    BibTeX
    @article{Walsh1922,
      doi     = {10.1090/S0002-9947-1922-1501220-0},
      url2    = {https://doi.org/10.1090/S0002-9947-1922-1501220-0},
      author  = {J. L. Walsh},
      title   = {On the location of the roots of certain types of polynomials},
      journal = {Transactions of the American Mathematical Society},
      volume  = {24},
      number  = {3},
      pages   = {163--180},
      year    = {1922}
    }
  3. [Sze22] G. Szegö. Bemerkungen zu einem Satz von J. H. Grace über die Wurzeln algebraischer Gleichungen. Mathematische Zeitschrift, 13, 28-55, 1922.
    BibTeX
    @article{Szego1922,
      doi     = {10.1007/BF01485280},
      url2    = {https://doi.org/10.1007/BF01485280},
      author  = {G. Szeg{\"{o}}},
      title   = {Bemerkungen zu einem {S}atz von {J}. {H}. {G}race {\"{u}}ber die {W}urzeln algebraischer {G}leichungen},
      journal = {Mathematische Zeitschrift},
      volume  = {13},
      pages   = {28--55},
      year    = {1922}
    }
  4. [RS02] Q. I. Rahman & G. Schmeisser. Analytic Theory of Polynomials. London Mathematical Society Monographs, Oxford University Press, 2002.
    BibTeX
    @book{RahmanSchmeisser2002,
      author    = {Rahman, Q. I. and Schmeisser, G.},
      title     = {Analytic Theory of Polynomials},
      publisher = {Oxford University Press},
      series    = {London Mathematical Society Monographs},
      year      = {2002}
    }
  5. [BB09] Julius Borcea & Petter Brändén. The Lee–Yang and Pólya–Schur programs. II. Theory of stable polynomials and applications. Communications on Pure and Applied Mathematics, 62(12), 1595-1631, 2009.
    BibTeX
    @article{BorceaBranden2009II,
    	doi = {10.1002/cpa.20295},
    	url2 = {https://doi.org/10.1002%2Fcpa.20295},
    	year = 2009,
    	month = {dec},
    	publisher = {Wiley},
    	volume = {62},
    	number = {12},
    	pages = {1595--1631},
    	author = {Julius Borcea and Petter Br{\"{a}}nd{\'{e}}n},
    	title = {The {L}ee--{Y}ang and {P}{\'{o}}lya--{S}chur programs. {II}. Theory of stable polynomials and applications},
    	journal = {Communications on Pure and Applied Mathematics}
    }
  6. [LS81] Elliott H. Lieb & Alan D. Sokal. A general Lee-Yang theorem for one-component and multicomponent ferromagnets. Communications in Mathematical Physics, 80(2), 153-179, 1981.
    BibTeX
    @article{LiebSokal1981,
      author = {Lieb, Elliott H. and Sokal, Alan D.},
      title = {A general {L}ee-{Y}ang theorem for one-component and multicomponent ferromagnets},
      year = {1981},
      journal = {Communications in Mathematical Physics},
      volume = {80},
      number = {2},
      pages = {153--179},
      doi = {10.1007/bf01213009},
      url = {https://doi.org/10.1007/bf01213009}
    }
  7. [GM22] Aurelien Gribinski & Adam W. Marcus. A rectangular additive convolution for polynomials. Combinatorial Theory, 2(1), 2022.
    BibTeX
    @article{GribinskiMarcus2022,
      author = {Gribinski, Aurelien and Marcus, Adam W.},
      title = {A rectangular additive convolution for polynomials},
      year = {2022},
      journal = {Combinatorial Theory},
      volume = {2},
      number = {1},
      doi = {10.5070/c62156888},
      url = {https://doi.org/10.5070/c62156888}
    }

Definitions

  • Polynomial with binomial-weighted coefficients

    RealRooted.binomialLiftsource
    def binomialLift {R : Type*} [CommRing R] (n : Nat) (f : R[X]) : R[X] :=
      Finset.sum (Finset.range (n + 1)) fun k =>
        monomial k ((Nat.choose n k : R) * f.coeff k)
  • Apolar polynomials

    RealRooted.AreApolarsource
    def AreApolar {R : Type*} [CommRing R] (n : Nat) (f g : R[X]) : Prop :=
      apolarPairing n f g = 0
  • Polarization

    RealRooted.polarizationsource
    def polarization (n : ℕ) (p : ℂ[X]) : MvPolynomial (Fin n) ℂ :=
      reducedPolarization n (binomialUnlift n p)
  • Diagonal of a multivariate polynomial

    RealRooted.diagonalProjectionsource
    noncomputable def diagonalProjection (n : ℕ) :
        MvPolynomial (Fin n) ℂ →ₗ[ℂ] ℂ[X] where
      toFun q :=
        MvPolynomial.uniqueAlgEquiv ℂ (Fin 1)
          (MvPolynomial.rename (fun _ : Fin n => (0 : Fin 1)) q)
      map_add' q r := by simp
      map_smul' c q := by simp [MvPolynomial.smul_eq_C_mul, Polynomial.smul_eq_C_mul]
  • Blockwise polarization in a degree box

    RealRooted.BorceaBranden.blockwisePolarizationDegreeBoxGeneralsource
    noncomputable def blockwisePolarizationDegreeBoxGeneral
        {σ : Type*} [Fintype σ] (κ : σ → ℕ) :
        MvPolynomial.degreeOfLE σ ℂ κ →ₗ[ℂ]
          MvPolynomial.degreeOfLE (PolarizedSource κ) ℂ (fun _ => 1) :=
      (MvPolynomial.basisDegreeOfLE (R := ℂ) κ).constr ℂ fun m =>
        ⟨blockwisePolarizationBasis κ m,
          (MvPolynomial.mem_degreeOfLE_iff_degreeOf _).2
            (isMultiaffine_blockwisePolarizationBasis κ m)⟩
  • Differential action F(−∂)G

    RealRooted.applyNegDifferentialsource
    def applyNegDifferential
        {R sigma : Type*} [CommRing R] [Fintype sigma]
        (F G : MvPolynomial sigma R) : MvPolynomial sigma R :=
      F.coeff.sum fun d c =>
        MvPolynomial.C ((-1 : R) ^ (d.sum fun _ n => n) * c) *
          applyMonomialDifferential d G

Theorems

  • Grace's apolarity theorem for closed disksMain result

    RealRooted.exists_isRoot_mem_closedBall_of_areApolarsource
    theorem exists_isRoot_mem_closedBall_of_areApolar {n : ℕ} {c : ℂ} {r : ℝ}
        (hr : 0 ≤ r) {f g : ℂ[X]} (hf : (binomialLift n f).natDegree = n)
        (hg : (binomialLift n g).natDegree = n) (hap : AreApolar n f g)
        (hroots : ∀ z, (binomialLift n f).IsRoot z → z ∈ Metric.closedBall c r) :
        ∃ z ∈ Metric.closedBall c r, (binomialLift n g).IsRoot z
  • Polarization preserves stability

    RealRooted.mvUpperHalfPlaneStable_polarizationsource
    theorem mvUpperHalfPlaneStable_polarization {n : ℕ} {p : ℂ[X]}
        (hdeg : p.natDegree ≤ n)
        (hstable : ∀ w : ℂ, 0 < w.im → p.eval w ≠ 0) :
        MvUpperHalfPlaneStable (polarization n p)
  • Grace–Walsh–Szegő: a symmetric multiaffine polynomial is stable iff its diagonal is

    RealRooted.mvUpperHalfPlaneStable_iff_eval_diagonalProjection_ne_zerosource
    theorem mvUpperHalfPlaneStable_iff_eval_diagonalProjection_ne_zero {n : ℕ}
        {P : MvPolynomial (Fin n) ℂ} (hsym : P.IsSymmetric)
        (hma : MvPolynomial.IsMultiaffine P) :
        MvUpperHalfPlaneStable P ↔
          ∀ w : ℂ, 0 < w.im → (diagonalProjection n P).eval w ≠ 0
  • Grace–Walsh–Szegő coincidence theorem for closed disks

    RealRooted.exists_eval_const_eq_of_mem_closedBallsource
    theorem exists_eval_const_eq_of_mem_closedBall {n : ℕ} {P : MvPolynomial (Fin n) ℂ}
        (hsym : P.IsSymmetric) (hma : P.IsMultiaffine) {c : ℂ} {r : ℝ} (hr : 0 ≤ r)
        {ζ : Fin n → ℂ} (hζ : ∀ i, ζ i ∈ Metric.closedBall c r) :
        ∃ w ∈ Metric.closedBall c r, MvPolynomial.eval (fun _ => w) P = MvPolynomial.eval ζ P
  • Coincidence theorem for open disks

    RealRooted.exists_eval_const_eq_of_mem_ballsource
    theorem exists_eval_const_eq_of_mem_ball {n : ℕ} {P : MvPolynomial (Fin n) ℂ}
        (hsym : P.IsSymmetric) (hma : P.IsMultiaffine) {c : ℂ} {r : ℝ} (hr : 0 < r)
        {ζ : Fin n → ℂ} (hζ : ∀ i, ζ i ∈ Metric.ball c r) :
        ∃ w ∈ Metric.ball c r, MvPolynomial.eval (fun _ => w) P = MvPolynomial.eval ζ P
  • Coincidence theorem for open half-planes

    RealRooted.exists_eval_const_eq_of_im_div_possource
    theorem exists_eval_const_eq_of_im_div_pos {n : ℕ} {P : MvPolynomial (Fin n) ℂ}
        (hsym : P.IsSymmetric) (hma : P.IsMultiaffine) {a : ℂ} (ha : a ≠ 0) (b : ℂ)
        {ζ : Fin n → ℂ} (hζ : ∀ i, 0 < ((ζ i - b) / a).im) :
        ∃ w : ℂ, 0 < ((w - b) / a).im ∧
          MvPolynomial.eval (fun _ => w) P = MvPolynomial.eval ζ P
  • Coincidence theorem for closed half-planes

    RealRooted.exists_eval_const_eq_of_im_div_nonnegsource
    theorem exists_eval_const_eq_of_im_div_nonneg {n : ℕ} {P : MvPolynomial (Fin n) ℂ}
        (hsym : P.IsSymmetric) (hma : P.IsMultiaffine) {a : ℂ} (ha : a ≠ 0) (b : ℂ)
        {ζ : Fin n → ℂ} (hζ : ∀ i, 0 ≤ ((ζ i - b) / a).im) :
        ∃ w : ℂ, 0 ≤ ((w - b) / a).im ∧
          MvPolynomial.eval (fun _ => w) P = MvPolynomial.eval ζ P
  • Coincidence theorem for the exterior of a disk, when the diagonal has degree n

    RealRooted.exists_eval_const_eq_of_lt_distsource
    theorem exists_eval_const_eq_of_lt_dist {n : ℕ} {P : MvPolynomial (Fin n) ℂ}
        (hsym : P.IsSymmetric) (hma : P.IsMultiaffine)
        (hdeg : (diagonalProjection n P).natDegree = n) {c : ℂ} {r : ℝ} (hr : 0 < r)
        {ζ : Fin n → ℂ} (hζ : ∀ i, r < dist (ζ i) c) :
        ∃ w, r < dist w c ∧ MvPolynomial.eval (fun _ => w) P = MvPolynomial.eval ζ P
  • Coincidence theorem for the closed exterior of a disk

    RealRooted.exists_eval_const_eq_of_le_distsource
    theorem exists_eval_const_eq_of_le_dist {n : ℕ} {P : MvPolynomial (Fin n) ℂ}
        (hsym : P.IsSymmetric) (hma : P.IsMultiaffine)
        (hdeg : (diagonalProjection n P).natDegree = n) {c : ℂ} {r : ℝ} (hr : 0 < r)
        {ζ : Fin n → ℂ} (hζ : ∀ i, r ≤ dist (ζ i) c) :
        ∃ w, r ≤ dist w c ∧ MvPolynomial.eval (fun _ => w) P = MvPolynomial.eval ζ P
  • Grace–Walsh–Szegő, real form: real stable iff the diagonal is real-rooted

    RealRooted.mvRealStable_iff_aeval_X_ne_zero_and_splitssource
    theorem mvRealStable_iff_aeval_X_ne_zero_and_splits {n : ℕ}
        {P : MvPolynomial (Fin n) ℝ} (hsym : P.IsSymmetric) (hma : MvPolynomial.IsMultiaffine P) :
        MvRealStable P ↔
          MvPolynomial.aeval (fun _ => (X : ℝ[X])) P ≠ 0 ∧
            (MvPolynomial.aeval (fun _ => (X : ℝ[X])) P).Splits
  • A symmetric multiaffine polynomial is the polarization of its diagonal

    RealRooted.polarization_diagonalProjectionsource
    theorem polarization_diagonalProjection {n : ℕ} {P : MvPolynomial (Fin n) ℂ}
        (hsym : P.IsSymmetric) (hma : MvPolynomial.IsMultiaffine P) :
        polarization n (diagonalProjection n P) = P
  • Blockwise polarization preserves and reflects stability

    RealRooted.GraceApolarity.polarization_stable_iffsource
    theorem GraceApolarity.polarization_stable_iff {σ : Type*}
        [Fintype σ] (κ : σ → ℕ) (p : MvPolynomial.degreeOfLE σ ℂ κ) :
        MvUpperHalfPlaneStable (BorceaBranden.blockwisePolarizationDegreeBoxGeneral κ p).1 ↔
          MvUpperHalfPlaneStable p.1
  • Grace's apolarity theorem for closed half-planes

    RealRooted.exists_isRoot_le_im_of_areApolarsource
    theorem exists_isRoot_le_im_of_areApolar {n : ℕ} {b : ℝ} {f g : ℂ[X]}
        (hf : (binomialLift n f).natDegree = n) (hg : (binomialLift n g).natDegree = n)
        (hap : AreApolar n f g) (hroots : ∀ z, (binomialLift n f).IsRoot z → b ≤ z.im) :
        ∃ z, b ≤ z.im ∧ (binomialLift n g).IsRoot z
  • Lieb–Sokal theorem for multiaffine polynomials

    RealRooted.MvUpperHalfPlaneStable.liebSokal_multiaffinesource
    theorem MvUpperHalfPlaneStable.liebSokal_multiaffine
        {sigma : Type*} [Fintype sigma]
        {F G : MvPolynomial sigma ℂ}
        (hF : MvUpperHalfPlaneStable F)
        (hG : MvUpperHalfPlaneStable G)
        (hFma : MvPolynomial.IsMultiaffine F)
        (hGma : MvPolynomial.IsMultiaffine G) :
        applyNegDifferential F G = 0 ∨
          MvUpperHalfPlaneStable (applyNegDifferential F G)
  • Lieb–Sokal theorem without the multiaffine hypothesis

    RealRooted.MvUpperHalfPlaneStable.liebSokalsource
    theorem MvUpperHalfPlaneStable.liebSokal
        {sigma : Type*} [Fintype sigma]
        {F G : MvPolynomial sigma ℂ} (hF : MvUpperHalfPlaneStable F)
        (hG : MvUpperHalfPlaneStable G) :
        applyNegDifferential F G = 0 ∨
          MvUpperHalfPlaneStable (applyNegDifferential F G)

Lean source RealRooted/Challenges/Roots/GraceApolarity.lean at revision d6670742. Formalized 2026-10-06.