Real stability

Real stability is the multivariate generalization of real-rootedness. A multiaffine real polynomial is real stable if and only if it is Rayleigh; determinantal pencils are real stable; real stability is preserved by homogenization, specialization and inversion; and it gives hyperbolicity, matroid supports, Lorentzian polynomials and the root bound for mixed characteristic polynomials.

Results

A polynomial $P\in\mathbb C[z_1,\dotsc,z_n]$ is stable if $P(z)\ne0$ whenever $\operatorname{Im}z_i>0$ for all $i$; in particular $P\ne0$. A polynomial with real coefficients is real stable if it is stable as a complex polynomial. It is multiaffine if it has degree at most one in each variable, and Rayleigh if $$ \partial_iP\,\partial_jP-P\,\partial_i\partial_jP\ge0 $$ at every $x\in\mathbb R^n$ and for all $i,j$. A real polynomial $P$ is hyperbolic in the direction $e\in\mathbb R^n$ if $P(e)\ne0$ and $t\mapsto P(x+te)$ is real-rooted for every $x\in\mathbb R^n$.

Theorem (Brändén) [Bra07]. A multiaffine $P\in\mathbb R[z_1,\dotsc,z_n]$ is real stable if and only if $P\ne0$ and $P$ is Rayleigh.

Corollary (Borcea–Brändén–Liggett) [BBL08]. Let $\mu$ be a weight function on the subsets of $\{1,\dotsc,n\}$ whose generating polynomial $\sum_S\mu(S)\prod_{i\in S}z_i$ is real stable. Then for $i\ne j$, $$ \mu(\Omega)\,\mu(i,j\in S)\le\mu(i\in S)\,\mu(j\in S). $$ For a probability measure this is pairwise negative correlation; it is the Rayleigh inequality at the all-ones point.

Theorem (Borcea–Brändén) [BB08]. Let $A$ be a Hermitian $m\times m$ matrix and $B_1,\dotsc,B_n$ positive semidefinite $m\times m$ matrices. Then $\det(A+z_1B_1+\dotsb+z_nB_n)$ is stable or identically zero. If all matrices are real and the determinant is not identically zero, it is real stable.

Corollary (Choe–Oxley–Sokal–Wagner) [COSW04]. If a finite graph $G$ has a spanning tree, its spanning-tree polynomial $\sum_T\prod_{e\in T}z_e$ is real stable. By Kirchhoff's weighted matrix-tree theorem it equals the determinant of the reduced Laplacian $\sum_ez_eb_eb_e^{T}$, a pencil of positive semidefinite rank-one matrices.

Theorem (hyperbolicity). A homogeneous $P\in\mathbb R[z_1,\dotsc,z_n]$ is real stable if and only if it is hyperbolic in every direction $e$ with all $e_i>0$. If a homogeneous $P$ is hyperbolic in the direction $e$, then it is hyperbolic in every direction $u$ joined to $e$ by a path in $\{x:P(x)\ne0\}$.

Theorem (Gårding) [Gar59]. If a homogeneous $P$ is hyperbolic in the direction $e$, its hyperbolicity cone, the path component of $e$ in $\{x:P(x)\ne0\}$, is convex.

Theorem (homogenization). Let $P\ne0$ be real stable with nonnegative coefficients and total degree $d$. Then $z_0^dP(z_1/z_0,\dotsc,z_n/z_0)$ and the top homogeneous component of $P$ are real stable. The homogenization in any degree at least $d$ is also real stable.

Theorem (top component). If $P$ is real stable, then its top homogeneous component is real stable, and the homogenization $z_0^dP(z_1/z_0,\dotsc,z_n/z_0)$, with $d$ the total degree of $P$, is hyperbolic in the direction $(0,b)$ for every $b\in\mathbb R^n$ with all $b_i>0$. In particular the top component does not vanish at such $b$.

Theorem (same-phase stability). If $P$ is real stable, then for every $w\in\mathbb R^n$ with all $w_i\ge0$ the polynomial $P(w_1t,\dotsc,w_nt)$ is real-rooted.

Theorem (line restrictions). $P$ is real stable if and only if, for all $a\in\mathbb R^n$ and $b\in\mathbb R_{>0}^n$, the restriction $t\mapsto P(a+tb)$ is nonzero and real-rooted.

Theorem (inversion). Let $P$ be a stable polynomial in a variable $z_0$ and further variables, of degree at most $d$ in $z_0$. Then $z_0^dP(-1/z_0,\dotsc)$ is stable, and real stable if $P$ is. For one variable: if $p$ has no zeros in the open upper half-plane and $\deg p\le d$, then $z^dp(-1/z)$ has none.

Theorem (specialization). Let $P$ be stable and $c$ real. Then $P$ with the variable $z_i$ replaced by $c$ is stable or identically zero. The same holds for repeated specialization of several variables at real values, and for setting a finite block of variables to zero.

Theorem (differentiation). Let $P$ be stable in $z_0,z_1,\dotsc,z_n$, of degree at most $m\ge1$ in $z_0$, and suppose the coefficient of $z_0^m$ is a nonzero constant. Then $\partial P/\partial z_0$ is stable.

Theorem (common-rotation criterion). Call a complex polynomial $Q$ common-rotation stable if $Q(z)\ne0$ whenever some single $c$ with $\operatorname{Im}c>0$ satisfies $\operatorname{Im}(cz_i)>0$ for all $i$. A homogeneous polynomial $P$ in $z_0,z_1,\dotsc,z_n$ is stable if and only if $P(1,z_1,\dotsc,z_n)$ is common-rotation stable; for a homogeneous real polynomial the same holds for real stability. The ordinary homogenization of $p$ in any degree at least $\deg p$ is stable if and only if $p$ is common-rotation stable.

Theorem (affine extensions). Let $P$ and $Q$ be multiaffine polynomials not involving $z_k$. Write $W_i(Q,P)=Q\,\partial_iP-P\,\partial_iQ$ for the coordinate Wronskian, $R_{ij}(F)=\partial_iF\,\partial_jF-F\,\partial_i\partial_jF$ for the Rayleigh difference, and $M_{ij}=\partial_iP\,\partial_jQ+\partial_iQ\,\partial_jP -P\,\partial_i\partial_jQ-Q\,\partial_i\partial_jP$. Then $P+z_kQ$ is Rayleigh if and only if

The Wronskians satisfy the Plücker relation $W_i(P,A)\,W_i(Q,B)=W_i(P,Q)\,W_i(A,B)+W_i(P,B)\,W_i(Q,A)$. If $P\in\mathbb C[z_1,\dotsc,z_n]$ is multiaffine and stable, so is $z\mapsto\prod_iz_i\,P(-1/z_1,\dotsc,-1/z_n)$. If $P$ is Rayleigh, $a\in\mathbb R^n$ and $b\in\mathbb R^n$ has nonnegative entries, then $p(t)=P(a+tb)$ satisfies $p'(t)^2-p(t)\,p''(t)\ge0$ for all real $t$.

Theorem (Brändén) [Bra07]. The support of a real stable polynomial is a jump system: for support points $\alpha,\beta$ and a unit step $s=\pm e_i$ from $\alpha$ towards $\beta$, either $\alpha+s$ is in the support, or some further unit step $t$ towards $\beta$ has $\alpha+s+t$ in the support.

Corollary (Brändén). If $P$ is homogeneous, multiaffine and real stable, its support is the set of bases of a matroid: $B$ is a basis exactly when its indicator vector lies in the support of $P$.

Theorem (Brändén–Huh) [BH20]. A homogeneous real stable polynomial with nonnegative coefficients is Lorentzian.

Theorem (mixed characteristic polynomials). For real positive semidefinite matrices $A_i$, the mixed characteristic polynomial $$ \mu[A](x)=\prod_i(1-\partial_{z_i})\det\Bigl(xI+\sum_iz_iA_i\Bigr)\Big|_{z=0} $$ is nonzero and real-rooted.

Theorem (Marcus–Spielman–Srivastava) [MSS15]. Let $A_1,\dotsc,A_m$ be real positive semidefinite $n\times n$ matrices with $\sum_iA_i=I$ and $\operatorname{tr}A_i\le\varepsilon$, where $\varepsilon>0$. Then every root of $\mu[A]$ is at most $(1+\sqrt\varepsilon)^2$. This is the root bound behind the solution of the Kadison–Singer problem.

Theorem (MSS, Thm. 4.1) [MSS15, Thm. 4.1]. The expected characteristic polynomial of a sum of independent random rank-one matrices equals the mixed characteristic polynomial of their second-moment matrices.

Proof

For determinantal pencils, if $v\ne0$ lies in the kernel of $M=A+\sum_iz_iB_i$ with all $\operatorname{Im}z_i>0$, then $\operatorname{Im}(v^*Mv)=\sum_i\operatorname{Im}(z_i)\,v^*B_iv=0$ forces $B_iv=0$ and $Av=0$, so the pencil is singular everywhere. Inversion uses that $z\mapsto-1/z$ maps the open upper half-plane to itself. For $P+z_kQ$ and $i,j\ne k$, the Rayleigh difference is a quadratic in $z_k$ with coefficients $R_{ij}(P)$, $M_{ij}$ and $R_{ij}(Q)$, and for $i=k$ it equals $W_j(Q,P)$. The root bound for $\mu[A]$ follows the barrier argument of Marcus, Spielman and Srivastava, with the Helton–Vinnikov step replaced by an elementary Pick-function lemma.

References

  1. [COSW04] Young-Bin Choe, James G. Oxley, Alan D. Sokal, & David G. Wagner. Homogeneous multivariate polynomials with the half-plane property. Advances in Applied Mathematics, 32(1-2), 88-187, 2004.
    BibTeX
    @article{ChoeOxleySokalWagner2004,
      doi = {10.1016/s0196-8858(03)00078-2},
      url2 = {https://doi.org/10.1016/s0196-8858(03)00078-2},
      year = {2004},
      month = jan,
      publisher = {Elsevier {BV}},
      volume = {32},
      number = {1-2},
      pages = {88--187},
      author = {Young-Bin Choe and James G. Oxley and Alan D. Sokal and David G. Wagner},
      title = {Homogeneous multivariate polynomials with the half-plane property},
      journal = {Advances in Applied Mathematics}
    }
  2. [Bra07] Petter Brändén. Polynomials with the half-plane property and matroid theory. Advances in Mathematics, 216(1), 302-320, 2007.
    BibTeX
    @article{Branden2007,
      title={Polynomials with the half-plane property and matroid theory},
      author={Br{\"{a}}nd{\'{e}}n, Petter},
      journal={Advances in Mathematics},
      volume={216},
      number={1},
      pages={302--320},
      year={2007},
      doi={10.1016/j.aim.2007.05.011},
      publisher={Elsevier}
    }
  3. [BB08] Julius Borcea & Petter Brändén. Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products. Duke Mathematical Journal, 143(2), 205-223, 2008.
    BibTeX
    @article{BorceaBranden2008MixedDeterminants,
      doi = {10.1215/00127094-2008-018},
      url2 = {https://doi.org/10.1215/00127094-2008-018},
      year = {2008},
      month = jun,
      publisher = {Duke University Press},
      volume = {143},
      number = {2},
      pages = {205--223},
      author = {Julius Borcea and Petter Br{\"{a}}nd{\'{e}}n},
      title = {Applications of stable polynomials to mixed determinants: {J}ohnson's conjectures, unimodality, and symmetrized {F}ischer products},
      journal = {Duke Mathematical Journal}
    }
  4. [BBL08] Julius Borcea, Petter Brändén, & Thomas Liggett. Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22(2), 521-567, 2008.
    BibTeX
    @article{BorceaBrandenLiggett2008,
      title = {Negative dependence and the geometry of polynomials},
      volume = {22},
      ISSN = {1088-6834},
      url = {http://dx.doi.org/10.1090/S0894-0347-08-00618-8},
      DOI = {10.1090/s0894-0347-08-00618-8},
      number = {2},
      journal = {Journal of the American Mathematical Society},
      publisher = {American Mathematical Society (AMS)},
      author = {Borcea,  Julius and Br{\"{a}}nd{\'{e}}n,  Petter and Liggett,  Thomas},
      year = {2008},
      month = sep,
      pages = {521–567}
    }
  5. [MSS15] Adam Marcus, Daniel A. Spielman, & Nikhil Srivastava. Interlacing families II: Mixed characteristic polynomials and the Kadison--Singer problem. Annals of Mathematics, 182(1), 327-350, 2015.
    BibTeX
    @article{MarcusSpielmanSrivastava2015II,
      author = {Adam Marcus and Daniel A. Spielman and Nikhil Srivastava},
      title = {Interlacing families {II}: Mixed characteristic polynomials and the
        {K}adison--{S}inger problem},
      year = {2015},
      journal = {Annals of Mathematics},
      volume = {182},
      number = {1},
      pages = {327--350},
      doi = {10.4007/annals.2015.182.1.8},
      url = {https://doi.org/10.4007/annals.2015.182.1.8},
      eprint = {1306.3969}
    }
  6. [BH20] Petter Brändén & June Huh. Lorentzian polynomials. Annals of Mathematics, 192(3), 2020.
    BibTeX
    @article{BrandenHuh2020,
      title = {Lorentzian polynomials},
      volume = {192},
      ISSN = {0003-486X},
      url = {http://dx.doi.org/10.4007/annals.2020.192.3.4},
      DOI = {10.4007/annals.2020.192.3.4},
      number = {3},
      journal = {Annals of Mathematics},
      publisher = {Annals of Mathematics},
      author = {Br{\"{a}}nd{\'{e}}n,  Petter and Huh,  June},
      year = {2020},
      month = nov
    }
  7. [Gar59] Lars Gårding. An Inequality for Hyperbolic Polynomials. Indiana University Mathematics Journal, 8(6), 957-965, 1959.
    BibTeX
    @article{Garding1959,
      author = {Gårding, Lars},
      title = {An {I}nequality for {H}yperbolic {P}olynomials},
      year = {1959},
      journal = {Indiana University Mathematics Journal},
      volume = {8},
      number = {6},
      pages = {957--965},
      doi = {10.1512/iumj.1959.8.58061},
      url = {https://doi.org/10.1512/iumj.1959.8.58061}
    }

Definitions

  • Stable multivariate polynomial

    RealRooted.MvUpperHalfPlaneStablesource
    def MvUpperHalfPlaneStable {sigma : Type*}
        (P : MvPolynomial sigma ℂ) : Prop :=
      MvStableIn (fun _ => {z | 0 < z.im}) P
  • Real stable multivariate polynomial

    RealRooted.MvRealStablesource
    def MvRealStable {sigma : Type*} (P : MvPolynomial sigma ℝ) : Prop :=
      MvUpperHalfPlaneStable (complexifyMv P)
  • Multiaffine polynomial

    MvPolynomial.IsMultiaffinesource
    def IsMultiaffine {R σ : Type*} [CommSemiring R] (p : MvPolynomial σ R) : Prop :=
      ∀ i, p.degreeOf i ≤ 1
  • Rayleigh property

    MvPolynomial.IsRayleighsource
    def IsRayleigh {σ : Type*} (P : MvPolynomial σ ℝ) : Prop :=
      ∀ i j x, 0 ≤ eval x (rayleighDifference P i j)
  • Hyperbolic in a direction

    MvPolynomial.HyperbolicAtsource
    def HyperbolicAt {σ R : Type*} [CommSemiring R]
        (P : MvPolynomial σ R) (e : σ → R) : Prop :=
      MvPolynomial.eval e P ≠ 0 ∧
        ∀ x : σ → R, (affineLineRestriction x e P).Splits
    
    end
  • Inversion z^d P(−1/z) in one variable

    RealRooted.invertVariablesource
    def invertVariable {R τ : Type*} [CommRing R] (d : ℕ) (P : MvPolynomial (Option τ) R) :
        MvPolynomial (Option τ) R :=
      (MvPolynomial.optionEquivLeft R τ).symm
        (reflect d ((MvPolynomial.optionEquivLeft R τ P).comp (-X)))
  • Determinant of a linear matrix pencil

    RealRooted.mvDetPencilsource
    def mvDetPencil {R : Type*} [CommRing R]
        (A : Matrix m m R) (B : sigma → Matrix m m R) : MvPolynomial sigma R :=
      Matrix.det fun i j => C (A i j) + ∑ k : sigma, X k * C (B k i j)
  • Stable or zero

    RealRooted.MvUpperHalfPlaneStableOrZerosource
    def MvUpperHalfPlaneStableOrZero {sigma : Type*}
        (P : MvPolynomial sigma ℂ) : Prop :=
      P = 0 ∨ MvUpperHalfPlaneStable P
  • Coordinate Wronskian

    MvPolynomial.coordinateWronskiansource
    def coordinateWronskian {R σ : Type*} [CommRing R]
        (P Q : MvPolynomial σ R) (i : σ) : MvPolynomial σ R :=
      P * pderiv i Q - pderiv i P * Q
  • Common-rotation stability

    RealRooted.MvCommonRotationStablesource
    def MvCommonRotationStable {σ : Type*} (P : MvPolynomial σ ℂ) : Prop :=
      ∀ z : σ → ℂ,
        (∃ c : ℂ, 0 < c.im ∧ ∀ i, 0 < (c * z i).im) →
          MvPolynomial.eval z P ≠ 0

Theorems

  • A multiaffine polynomial is real stable iff it is RayleighMain result

    RealRooted.MvPolynomial.IsMultiaffine.mvRealStable_iff_isRayleigh_and_ne_zerosource
    theorem MvPolynomial.IsMultiaffine.mvRealStable_iff_isRayleigh_and_ne_zero
        {σ : Type*} {P : MvPolynomial σ ℝ} (hma : P.IsMultiaffine) :
        MvRealStable P ↔ P.IsRayleigh ∧ P ≠ 0
  • Strongly Rayleigh measures are negatively correlated

    RealRooted.sum_mul_sum_le_of_mvRealStable_subsetGenPolysource
    theorem sum_mul_sum_le_of_mvRealStable_subsetGenPoly [DecidableEq σ] {μ : Finset σ → ℝ}
        (hμ : MvRealStable (subsetGenPoly μ)) {i j : σ} (hij : i ≠ j) :
        (∑ S, μ S) * ∑ S with i ∈ S ∧ j ∈ S, μ S ≤
          (∑ S with i ∈ S, μ S) * ∑ S with j ∈ S, μ S
  • Determinantal pencils are stable or zero

    RealRooted.mvUpperHalfPlaneStableOrZero_detPencilsource
    theorem mvUpperHalfPlaneStableOrZero_detPencil
        (A : Matrix m m ℂ) (B : sigma → Matrix m m ℂ)
        (hA : A.IsHermitian) (hB : ∀ k, (B k).PosSemidef) :
        MvUpperHalfPlaneStableOrZero (detPencil A B)
  • A homogeneous polynomial is real stable iff it is hyperbolic in every positive direction

    RealRooted.MvPolynomial.IsHomogeneous.mvRealStable_iff_forall_hyperbolicAt_possource
    theorem MvPolynomial.IsHomogeneous.mvRealStable_iff_forall_hyperbolicAt_pos
        {σ : Type*} {P : MvPolynomial σ ℝ} {d : ℕ}
        (hhom : P.IsHomogeneous d) :
        MvRealStable P ↔
          ∀ e : σ → ℝ, (∀ i, 0 < e i) → P.HyperbolicAt e
  • Gårding: hyperbolicity cones are convex

    RealRooted.convex_hyperbolicityConesource
    theorem convex_hyperbolicityCone {σ : Type*} {P : MvPolynomial σ ℝ} {d : ℕ} {e : σ → ℝ}
        (he : P.HyperbolicAt e) (hhom : P.IsHomogeneous d) :
        Convex ℝ (hyperbolicityCone P e)
  • Real determinantal pencils are real stable

    RealRooted.mvRealStable_realDetPencil_of_nesource
    theorem mvRealStable_realDetPencil_of_ne
        (A : Matrix m m ℝ) (B : sigma → Matrix m m ℝ)
        (hA : A.IsHermitian) (hB : ∀ k, (B k).PosSemidef)
        (hne : realDetPencil A B ≠ 0) :
        MvRealStable (realDetPencil A B)
  • Choe–Oxley–Sokal–Wagner: spanning-tree polynomials are real stable

    RealRooted.mvRealStable_spanningTreePolysource
    theorem mvRealStable_spanningTreePoly (hG : G.spanningTrees.Nonempty) :
        MvRealStable (spanningTreePoly G)
  • Kirchhoff's weighted matrix-tree theorem

    SimpleGraph.det_weightedLapMatrix_submatrixsource
    theorem det_weightedLapMatrix_submatrix [CommRing R] (w : Sym2 V → R) (r : V) :
        ((G.weightedLapMatrix w).submatrix (Subtype.val : {v // v ≠ r} → V) Subtype.val).det =
          ∑ T ∈ G.spanningTrees, ∏ e ∈ T, w e
  • Homogenization preserves real stability

    RealRooted.MvRealStable.ordinaryHomogenizationsource
    theorem MvRealStable.ordinaryHomogenization
        {σ : Type*} {P : MvPolynomial σ ℝ} (hst : MvRealStable P)
        (hnn : MvPolynomial.HasNonnegCoeffs P) (hP : P ≠ 0) :
        MvRealStable
          (MvPolynomial.ordinaryHomogenization P P.totalDegree)
  • The top homogeneous component of a real stable polynomial is real stable

    RealRooted.MvRealStable.homogeneousComponent_totalDegree_of_hasNonnegCoeffssource
    theorem MvRealStable.homogeneousComponent_totalDegree_of_hasNonnegCoeffs
        {σ : Type*} {P : MvPolynomial σ ℝ} (hst : MvRealStable P)
        (hnn : MvPolynomial.HasNonnegCoeffs P) (hP : P ≠ 0) :
        MvRealStable
          (MvPolynomial.homogeneousComponent P.totalDegree P)
  • Real stable polynomials are same-phase stable

    RealRooted.MvRealStable.samePhaseStablesource
    theorem MvRealStable.samePhaseStable {σ : Type*}
        {P : MvPolynomial σ ℝ} (hP : MvRealStable P) :
        SamePhaseStable P
  • Inversion preserves stability of univariate polynomials

    RealRooted.IsUpperHalfPlaneStable.reflect_comp_neg_Xsource
    theorem IsUpperHalfPlaneStable.reflect_comp_neg_X {p : ℂ[X]} {d : ℕ}
        (hd : p.natDegree ≤ d) (hp : IsUpperHalfPlaneStable p) :
        IsUpperHalfPlaneStable (reflect d (p.comp (-X)))
  • Inversion in one variable preserves stability

    RealRooted.MvUpperHalfPlaneStable.invertVariablesource
    theorem MvUpperHalfPlaneStable.invertVariable {τ : Type*} {P : MvPolynomial (Option τ) ℂ}
        {d : ℕ} (hd : P.degreeOf none ≤ d) (hP : MvUpperHalfPlaneStable P) :
        MvUpperHalfPlaneStable (invertVariable d P)
  • Inversion in one variable preserves real stability

    RealRooted.MvRealStable.invertVariablesource
    theorem MvRealStable.invertVariable {τ : Type*} {P : MvPolynomial (Option τ) ℝ} {d : ℕ}
        (hd : P.degreeOf none ≤ d) (hP : MvRealStable P) :
        MvRealStable (invertVariable d P)
  • Real stability from real-rootedness of all positive-direction line restrictions

    RealRooted.mvRealStable_of_forall_realAffineLineRestrictionsource
    theorem mvRealStable_of_forall_realAffineLineRestriction
        {σ : Type*} {P : MvPolynomial σ ℝ}
        (hP : ∀ a b : σ → ℝ, (∀ i, 0 < b i) →
          (realAffineLineRestriction a b P).Splits ∧
            realAffineLineRestriction a b P ≠ 0) :
        MvRealStable P
  • Line restrictions of a real stable polynomial in positive directions are real-rooted

    RealRooted.MvRealStable.realAffineLineRestriction_splits_ne_zerosource
    theorem MvRealStable.realAffineLineRestriction_splits_ne_zero
        {σ : Type*} {P : MvPolynomial σ ℝ} (hP : MvRealStable P)
        (a b : σ → ℝ) (hb : ∀ i, 0 < b i) :
        (realAffineLineRestriction a b P).Splits ∧
          realAffineLineRestriction a b P ≠ 0
  • Brändén: the support of a real stable polynomial is a jump system

    RealRooted.MvRealStable.isJumpSystem_supportIntsource
    theorem MvRealStable.isJumpSystem_supportInt {p : MvPolynomial (Fin n) ℝ}
        (hp : MvRealStable p) : IsJumpSystem (JumpSystem.supportInt p)
  • Brändén: supports of a homogeneous multi-affine real stable polynomial are matroid bases

    RealRooted.MvRealStable.isBase_supportMatroid_iffsource
    theorem MvRealStable.isBase_supportMatroid_iff {p : MvPolynomial (Fin n) ℝ}
        (hp : MvRealStable p) {r : ℕ} (hhom : MvPolynomial.IsHomogeneous p r)
        (haff : ∀ d ∈ p.support, ∀ i, d i ≤ 1) (B : Set (Fin n)) :
        (hp.supportMatroid hhom haff).IsBase B ↔ JumpSystem.indicator B ∈ JumpSystem.supportInt p
  • Brändén–Huh: nonnegative homogeneous real stable polynomials are Lorentzian

    RealRooted.MvRealStable.isLorentziansource
    theorem MvRealStable.isLorentzian {n : ℕ} {p : MvPolynomial (Fin n) ℝ} (hp : MvRealStable p)
        {d : ℕ} (hhom : p.IsHomogeneous d) (hnn : ∀ m, 0 ≤ p.coeff m) :
        Lorentzian.IsLorentzian d p
  • Marcus–Spielman–Srivastava: mixed characteristic polynomials are real-rooted

    RealRooted.MixedCharacteristic.isRealRooted_mixedCharacteristicsource
    theorem isRealRooted_mixedCharacteristic
        (As : Fin m → Matrix (Fin n) (Fin n) ℝ)
        (hAs : ∀ i, (As i).PosSemidef) :
        mixedCharacteristic As ≠ 0 ∧ (mixedCharacteristic As).Splits
  • Marcus–Spielman–Srivastava: the roots of μ[A] are at most (1 + √ε)²

    RealRooted.MixedCharacteristic.mixedCharacteristic_roots_le_one_add_sqrt_sqsource
    theorem mixedCharacteristic_roots_le_one_add_sqrt_sq {n m : ℕ}
        (As : Fin m → Matrix (Fin n) (Fin n) ℝ)
        (hAs : ∀ i, (As i).PosSemidef) (hsum : ∑ i, As i = 1)
        {ε : ℝ} (hε : 0 < ε) (htrace : ∀ i, (As i).trace ≤ ε)
        :
        ∀ r ∈ (mixedCharacteristic As).roots,
          r ≤ (1 + Real.sqrt ε) ^ 2
  • MSS: expected characteristic polynomials are mixed characteristic

    RealRooted.MixedCharacteristic.expectedCharpoly_eq_mixedCharacteristicsource
    theorem expectedCharpoly_eq_mixedCharacteristic {m n : ℕ}
        (ι : Fin m → Type) [∀ i, Fintype (ι i)]
        (v : ∀ i, ι i → Fin n → ℝ) (p : ∀ i, ι i → ℝ)
        (hp1 : ∀ i, ∑ j, p i j = 1) :
        expectedCharpoly ι v p = mixedCharacteristic (fun i => secondMoment (v i) (p i))
  • Hyperbolicity is constant on path components of the nonvanishing locus

    RealRooted.MvPolynomial.HyperbolicAt.of_joinedInsource
    theorem MvPolynomial.HyperbolicAt.of_joinedIn
        {σ : Type*} {P : MvPolynomial σ ℝ} {d : ℕ} {e u : σ → ℝ}
        (he : P.HyperbolicAt e) (hhom : P.IsHomogeneous d)
        (hjoin : JoinedIn {x | MvPolynomial.eval x P ≠ 0} e u) :
        P.HyperbolicAt u
  • The top homogeneous component of any real stable polynomial is real stable

    RealRooted.MvRealStable.homogeneousComponent_totalDegreesource
    theorem MvRealStable.homogeneousComponent_totalDegree
        {σ : Type*} {P : MvPolynomial σ ℝ} (hst : MvRealStable P) :
        MvRealStable (MvPolynomial.homogeneousComponent P.totalDegree P)
  • Ordinary homogenization is hyperbolic in every boundary direction

    RealRooted.MvRealStable.ordinaryHomogenization_hyperbolicAt_boundarysource
    theorem MvRealStable.ordinaryHomogenization_hyperbolicAt_boundary
        {σ : Type*} {P : MvPolynomial σ ℝ} (hst : MvRealStable P)
        (b : σ → ℝ) (hb : ∀ i, 0 < b i) :
        (MvPolynomial.ordinaryHomogenization P P.totalDegree).HyperbolicAt
          (fun o => Option.elim o 0 b)
  • Homogenization in any degree at least the total degree preserves real stability

    RealRooted.MvRealStable.ordinaryHomogenization_of_totalDegree_lesource
    theorem MvRealStable.ordinaryHomogenization_of_totalDegree_le
        {σ : Type*} {P : MvPolynomial σ ℝ} {d : ℕ}
        (hst : MvRealStable P) (hnn : MvPolynomial.HasNonnegCoeffs P)
        (hP : P ≠ 0) (hdeg : P.totalDegree ≤ d) :
        MvRealStable (MvPolynomial.ordinaryHomogenization P d)
  • Specializing a coordinate at a real value gives a stable polynomial or zero

    RealRooted.MvUpperHalfPlaneStable.specializeAt_real_zero_or_generalsource
    theorem MvUpperHalfPlaneStable.specializeAt_real_zero_or_general
        {alpha : Type*} {P : MvPolynomial alpha ℂ}
        (hP : MvUpperHalfPlaneStable P) (i : alpha) (c : ℝ) :
        MvUpperHalfPlaneStableOrZero
          (MvPolynomial.specializeAt i (c : ℂ) P)
  • Specializing several coordinates at real values preserves stability or zero

    RealRooted.MvUpperHalfPlaneStableOrZero.specializeAtList_real_generalsource
    theorem MvUpperHalfPlaneStableOrZero.specializeAtList_real_general
        {alpha : Type*} {P : MvPolynomial alpha ℂ}
        (hP : MvUpperHalfPlaneStableOrZero P) (c : alpha → ℝ) (l : List alpha) :
        MvUpperHalfPlaneStableOrZero
          (MvPolynomial.specializeAtList (fun i => (c i : ℂ)) l P)
  • Setting a finite block of variables to zero gives a stable polynomial or zero

    RealRooted.MvUpperHalfPlaneStable.specializeRight_zero_or_generalsource
    theorem MvUpperHalfPlaneStable.specializeRight_zero_or_general
        {tau sigma : Type*} [Finite sigma]
        {P : MvPolynomial (Sum tau sigma) ℂ}
        (hP : MvUpperHalfPlaneStable P) :
        MvUpperHalfPlaneStableOrZero
          (_root_.RealRooted.specializeRight (fun _ : sigma => 0) P)
  • Exact Rayleigh criterion for a fresh affine extension

    MvPolynomial.isRayleigh_add_X_mul_iff_of_freshsource
    theorem isRayleigh_add_X_mul_iff_of_fresh
        {σ : Type*} {P Q : MvPolynomial σ ℝ} {k : σ}
        (hPma : IsMultiaffine P) (hQma : IsMultiaffine Q)
        (hkP : k ∉ P.vars) (hkQ : k ∉ Q.vars) :
        IsRayleigh (P + X k * Q) ↔
          IsRayleigh P ∧ IsRayleigh Q ∧
            (∀ i x, 0 ≤ eval x (coordinateWronskian Q P i)) ∧
            (∀ i j x, i ≠ k → j ≠ k →
              eval x (affineRayleighDiscriminant P Q i j) ≤ 0)
  • The signed multiaffine reciprocal preserves stability

    RealRooted.MvUpperHalfPlaneStable.signedMultiaffineReciprocalsource
    theorem MvUpperHalfPlaneStable.signedMultiaffineReciprocal
        {sigma : Type*} [Fintype sigma] {P : MvPolynomial sigma ℂ}
        (hstable : MvUpperHalfPlaneStable P)
        (hP : MvPolynomial.IsMultiaffine P) :
        MvUpperHalfPlaneStable (signedMultiaffineReciprocal P)
  • Plücker relation for coordinate Wronskians

    MvPolynomial.coordinateWronskian_pluckersource
    theorem coordinateWronskian_plucker
        {R σ : Type*} [CommRing R]
        (P Q A B : MvPolynomial σ R) (i : σ) :
        coordinateWronskian P A i * coordinateWronskian Q B i =
          coordinateWronskian P Q i * coordinateWronskian A B i +
            coordinateWronskian P B i * coordinateWronskian Q A i
  • Laguerre's inequality for line restrictions of Rayleigh polynomials

    RealRooted.MvPolynomial.IsRayleigh.laguerre_realAffineLineRestrictionsource
    theorem MvPolynomial.IsRayleigh.laguerre_realAffineLineRestriction
        {σ : Type*} [Finite σ] {P : MvPolynomial σ ℝ}
        (hP : P.IsRayleigh) (a b : σ → ℝ) (hb : ∀ i, 0 ≤ b i)
        (t : ℝ) :
        0 ≤ (realAffineLineRestriction a b P).derivative.eval t ^ 2 -
          (realAffineLineRestriction a b P).eval t *
            (realAffineLineRestriction a b P).derivative.derivative.eval t
  • A homogeneous polynomial is stable iff its dehomogenization is common-rotation stable

    RealRooted.mvUpperHalfPlaneStable_iff_commonRotation_dehomogenizesource
    theorem mvUpperHalfPlaneStable_iff_commonRotation_dehomogenize
        {σ : Type*} {P : MvPolynomial (Option σ) ℂ} {d : ℕ}
        (hhom : P.IsHomogeneous d) :
        MvUpperHalfPlaneStable P ↔
          MvCommonRotationStable (MvPolynomial.dehomogenize P)
  • Real-stable analogue of the common-rotation criterion

    RealRooted.mvRealStable_iff_commonRotation_dehomogenizesource
    theorem mvRealStable_iff_commonRotation_dehomogenize
        {σ : Type*} {P : MvPolynomial (Option σ) ℝ} {d : ℕ}
        (hhom : P.IsHomogeneous d) :
        MvRealStable P ↔
          MvCommonRotationStable
            (complexifyMv (MvPolynomial.dehomogenize P))
  • Ordinary homogenization is stable iff the source is common-rotation stable

    RealRooted.mvUpperHalfPlaneStable_ordinaryHomogenization_iffsource
    theorem mvUpperHalfPlaneStable_ordinaryHomogenization_iff
        {σ : Type*} {p : MvPolynomial σ ℂ} {d : ℕ}
        (hdeg : p.totalDegree ≤ d) :
        MvUpperHalfPlaneStable (MvPolynomial.ordinaryHomogenization p d) ↔
          MvCommonRotationStable p
  • Differentiation in a variable with constant leading coefficient preserves stability

    RealRooted.MvUpperHalfPlaneStable.pderiv_none_of_top_coeff_Csource
    theorem MvUpperHalfPlaneStable.pderiv_none_of_top_coeff_C
        {σ : Type*} {P : MvPolynomial (Option σ) ℂ} {m : ℕ} {c : ℂ}
        (hP : MvUpperHalfPlaneStable P) (hm : m ≠ 0) (hc : c ≠ 0)
        (hdeg : P.degreeOf none ≤ m)
        (htop : (MvPolynomial.optionEquivLeft ℂ σ P).coeff m =
          MvPolynomial.C c) :
        MvUpperHalfPlaneStable (MvPolynomial.pderiv none P)

Lean source RealRooted/Challenges/Stability/RealStability.lean at revision d6670742. Formalized 2026-10-12.