Schedule for: 21w5117 - Real Polynomials: Counting and Stability (Online)

I will give a panoramic talk on stable polynomials and related families of polynomials, such as hyperbolic and Lorentzian polynomials. Over the past two decades stable polynomials and their relatives have been applied in different areas such as optimization, real algebraic geometry, combinatorics, statistical mechanics, quantum mechanics and computer science. I will review some remarkable properties of this class of polynomials as well as point to applications. I will also talk about a recent generalization called Lorentzian polynomials. 

In 1980, A. Khovanskii gave a bound for the number of non-degenerate positive solutions of any square sparse polynomial system. His bound depends only on the number of monomials of the system and is smaller than all classical bounds (Bézout or mixed volume bounds) when the number of monomials is small. Such bounds are called fewnomial bounds. In the univariate case, the classical Descartes’ rule of signs, going back from 1637, produces a bound for the number of positive roots which takes care of the signs of the coefficients, which is sharp and which implies a sharp fewnomial bound. In this talk, I will describe several improvements of Khovanskii bound, which in some cases provide sharp fewnomial bounds. I will also describe recent multivariate generalisations of Descartes’ rule of signs. This talk is mainly based on joint works with several collaborators including A. Dickenstein, B. El Hilany, J. Forsgard, M. Rojas and F. Sottile.

A multivariate polynomial $p$ in ${\mathbb C}[z_1, \ldots, z_n]$ is called stable if every root $z$ has at least one component $z_j$ with imaginary part $\le 0$. In this expository talk, we discuss the naturally generalized viewpoint of conic stability. Its origin is in the study of imaginary projections, and the usual stability refers to the specific polyhedral cone ${\mathbb R}_+^n$. As a prominent case, we consider conic stability with respect to the positive semidefinite cone ("psd stability"). Criteria for psd stability are tightly linked to the containment problem for spectrahedra, to positive maps and to determinantal representations. The own results in this talk are based on various joint works with Giulia Codenotti, Papri Dey, Stephan Gardoll, Thorsten Jörgens, Mahsa Sayyary and Timo de Wolff.

We consider the evolutes of plane real-algebraic curves and discuss some of their complex and real-algebraic properties. In particular, for a given degree d ≥ 2, we provide lower bounds for the following four numerical invariants: 1) the maximal number of times a real line can intersect the evolute of a real-algebraic curve of degree d; 2) the maximal number of real cusps which can occur on the evolute of a real-algebraic curve of degree d; 3) the maximal number of (cru)nodes which can occur on the dual curve to the evolute of a real-algebraic curve of degree d; 4) the maximal number of (cru)nodes which can occur on the evolute of a real-algebraic curve of degree d (joint with R.Piene and C.Riener).

We explore the inflectionary behavior of linear series on families of marked superelliptic curves (i.e., cyclic covers of $\mathbb{P}^1$). The inflection of these linear series supported away from the superelliptic ramification locus is parameterized by the inflection polynomials, a certain family of polynomials generalizing the division polynomials (which are used to compute the torsion points of elliptic curves). These polynomials are remarkable since their properties reflect aspects of the underlying family of superelliptic curves. We also obtain inflectionary varieties, which describe the global behaviour of the inflection points on the family. In this talk we will introduce these inflection polynomials and some of their properties. Although this story is valid over fields of arbitrary characteristic, we will focus on the real case. We report on joint work with Ethan Cotterill, Ignacio Darago, Changho Han, and Tony Shaska.

Understanding the real zeros of polynomials is a research subject of intrinsic interest with a long and rich history and is especially useful for polynomials with specific properties like nonnegativity. In this talk, I provide a complete and explicit characterization of the real zeros of both homogeneous and inhomogeneous sums of nonnegative circuit (SONC) polynomials, a recent certificate for nonnegative polynomials independent of sums of squares. As an interesting consequence, I show that the supremum of the number of zeros of all homogeneous n-variate polynomials of degree 2d in the SONC cone can be determined exactly. Note that in strong contrast, the determination of this number for both the nonnegativity cone and the cone of sums of squares for general n and d is still an open question.

Matroids are combinatorial objects designed to capture independence relations on collections of objects, such as linear independence of vectors in a vector space or cyclic independence of edges in a graph. Recent work by several independent authors shows that the multivariate basis-generating polynomial of a matroid is log-concave as a function on the positive orthant. In this talk, I will describe some of the underlying combinatorial and geometric structure of such log-concave polynomials and applications to the problems of approximately counting and approximately sampling the bases of a matroid. This is based on joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.

Let $C\subseteq{\mathbb R}^n$ be a (piecewise) real algebraic curve, let $K$ be its closed convex hull. To allow efficient semidefinite optimization over $K$, one would like to have a low-complexity semidefinite representation of $K$. As a measure for complexity, we use the semidefinite extension degree ${\rm sxdeg}(K)$ introduced by Averkov. Our main result says that ${\rm sxdeg}(K)\le 1+\lfloor\frac n2\rfloor=:k$. This means that $K$ is a linear image of the solution set of a linear matrix inequality that is a block-diagonal sum of $k\times k$ matrices. In this talk we will mainly consider the case where $C$ is a monomial curve, which is completely explicit and where Schur polynomials play a key role. (Joint work with Gennadiy Averkov)

Let $K$ be the field of either real or complex numbers, and let $S_f$ denote the set of points in $K^n$ at which a polynomial map $f: K^n\to K^n$ is not proper. Jelonek proved that $S_f$ is an algebraic hypersurface in the complex case and semi-algebraic in the real case. He furthermore showed that $S_f$ is ruled by polynomial curves, and provided a method for computing its equations for complex maps. However, such methods do not extend to real polynomial maps. In this talk, I will establish a description of $S_f$ for a large family of non-proper polynomial maps f using their Newton polytopes. I will furthermore highlight the interplay between the combinatorics of the polytopes and the topology of $S_f$. The resulting method computes $S_f$ for complex polynomial maps as well as the real ones. As an application, some of Jelonek's results are recovered.  I will furthermore report on a joint work with Elias Tsigaridas in which we provided a more elaborate method for computing the non-properness set for degenerate real polynomial maps on the plane.

We will study several properties of bases generating polynomials of matroids that are related to stability. This includes the half-plane property or determinantal representability. We will further present a classification of all matroids on up to eight elements whose bases generating polynomial is stable. This is joint work with Büşra Sert.

This talk has two parts. In the first part, I shall talk about real degeneracy loci of matrices and its correspondence with symmetroids. Let $\mathcal{A}:=\{A_1 \dots,A_{m+1}\}$ be a collection of linear operators on ${\mathbb R}^{m}$. The degeneracy locus (DL) of $\mathcal{A}$ is defined as the set of the points $x$ for which rank$([A_1x\dots A_{m+1}x])\leq m-1$. We show that the DL is an $m-3$ dimensional sub-scheme of degree ${m+1 \choose 2}$ in ${\mathbb P}^{m-1}({\mathbb C})$. In particular, when $m=3$, the DL consists of six rational points in ${\mathbb P}^{2}({\mathbb R})$ with quadrilateral configuration if and only if $A_{i},i=1\dots,4$ are in the linear span of four fixed rank-one operators. Moreover, we show that if $A_{i},i=1\dots,m+1$ are in the linear span of $m+1$ fixed rank-one matrices, the DL of $m+1$ matrices satisfies generalized Desargues configuration, and it has correspondence with a Special type of symmetroid, call it Sylvester symmetroid. This part is based on joint work with Dan Edidin. In the second part, I shall focus on the hyperbolicity cones of the elementary symmetric polynomials and real polynomials which define symmetroids (work in progress).

Given a complex multivariate polynomial ${p\in\mathbb{C}[z_1,\ldots,z_n]}$, the imaginary projection $\mathcal{I}(p)$ of $p$ is defined as the projection of the variety $\mathcal{V}(p)$ onto its imaginary part. We give a full characterization of the imaginary projections of conic sections with complex coefficients, which generalizes a classification for the case of real conics. More precisely, given a bivariate complex polynomial $p\in\mathbb{C}[z_1,z_2]$ of total degree two, we describe the number and the boundedness of the components in the complement of $\mathcal{I}(p)$ as well as their boundary curves and the spectrahedral structure of the components. We further study the imaginary projections of some families of higher degree complex polynomials.

The cone of nonnegative forms of a given degree is a convex set of remarkable beauty and usefulness. In this talk we will discuss some recent ideas for approximating this set through polyhedra and spectrahedra. We call the resulting approximations harmonic hierarchies since they arise naturally from harmonic analysis on spheres (or equivalently from the representation theory of $SO(n)$). We will describe theoretical results leading to sharp estimates for the quality of these approximations and will also show a brief demo of our Julia implementation of harmonic hierarchies. These results are joint work with Sergio Cristancho (UniAndes).

We will discuss a generalization of stable polynomials to complex algebraic varieties of codimension larger than one and study their combinatorial structure using tropical geometry. We show that their tropicalization are closely related to type-A braid arrangements and positroids (matroid arising from the nonnegative part of the Grassmannian) and that their Chow polytopes are generalized permutohedra. This is based on joint work with Felipe Rincón and Cynthia Vinzant.

We provide upper bounds on the number of connected components of the complement of a hypersurface in the positive orthant and phrase our results as partial generalizations of the classical Descartes’ rule of signs to multivariate polynomials (with real exponents). In particular, we give conditions based on the geometrical configuration of the exponents and the sign of the coefficients that guarantee that the number of connected components of the complement of the hypersurface where the defining polynomial attains a negative value is at most one or two. Furthermore, we briefly present an application for chemical reaction networks that motivated us to consider this problem.

The principal minor map takes an $n$ by  $n$ square matrix to the length-$2^n$ vector of its principal minors. A basic question is to give necessary and sufficient conditions that characterize the image of various spaces of matrices under this map. In this talk I will describe the image of the space of complex matrices using a characterization of determinantal representations of multiaffine polynomials, based on the factorization of their Rayleigh differences. Using these techniques I will give equations and inequalities characterizing the images of the spaces of real and complex symmetric, Hermitian, and general complex matrices. For complex symmetric matrices this recovers a result of Oeding from $2011$. This is based on a joint work with Cynthia Vinzant.

We develop tools of real tropical intersection theory in order to determine necessary and sufficient conditions for real algebraic curves near the non-singular tropical limit to be hyperbolic with respect to a point, in terms of real phase structure and twisted edges on a tropical curve, generalising Speyer's classification of stable curves near the tropical limit.

A well-known fact in real algebraic geometry is that crossing the discriminant changes the number of real zeros. However, can the size of a discriminant chamber influence the number of zeros of the polynomial systems in it? In this talk, we show some novel results showing that this is the case. More concretely, we show that we can bound the number of real zeros in terms of the logarithm of the inverse distance to the discriminant—also known as the condition number—. We also demonstrate that this bound has important consequences regarding random real polynomial systems. This is joint work with Elias Tsigaridas.

The capacity of a polynomial p with non-negative coefficients is a certain function on its support that interpolates between coefficients of p and its value at the vector (1,...,1). This concept has a lot of remarkable applications including bounds on the mixed volume of convex bodies and bounds on some combinatorial quantities like the number of matchings in bipartite graphs. I will discuss relation of capacity to relative entropy of measures as well as its appearances in the theory of non-negative polynomials and in the theory of A-discriminants. The talk is based on a joint work in progress with Jonathan Leake and Timo de Wolff.

A key question in the theory of hyperbolic polynomials is how to test hyperbolicity. This is classically done by computing a symmetric determinantal representation of the given polynomial. In the case of curves this is always possible, whereas in high dimension one should look at such representations for multiples of the given polynomial (according to the Generalized Lax Conjecture). In the talk I will discuss a recent variant of the classical Dixon method, for the computation of spectrahedral representations of curves. The talk is based on a recent work joint with Mario Kummer and Daniel Plaumann.

Randomization has proved instrumental in efficiently solving geometric problems where the best deterministic methods are impractical. An important recent example is a recent singly exponential algorithm of Burgisser, Cucker, and Tonelli-Cueto for computing the homology of real algebraic sets for ``most'' inputs. We approach an analogous speed-up in a different direction: Computing the isotopy type of real zero sets defined by certain n-variate sparse polynomials of degree d with coefficients of maximum bit-length h. We show how, for ``most'' inputs, we can compute the number of connected components of the positive zero set in time $(h log d)^O(n)$, whereas the fastest previous algorithms had complexity $(hd)^{O(n)}$. A key tool is a new way to metrically approximate certain A-discriminant varieties. We'll aslo see how reducing the dependence on the number of variables n is related to diophantine approximation. Parts of this work are joint with Frederic Bihan, Jens Forsgard, Mounir Nisse, Kaitlyn Phillipson, and Lisa Soule.

In this talk we will focus on the distribution of real inflection points among the ovals of a real non-singular hyperbolic curve of even degree. Using Hilbert’s method we show that for any integers $d$ and $r$ such that $4 ≤ r ≤ 2d^2 −2d$, there is a non-singular hyperbolic curve of degree $2d$ in $\mathbb R^2$ with exactly $r$ line segments in the boundary of its convex hull. We also give a complete classification of possible distributions of inflection points among the ovals of a maximally inflected non-singular hyperbolic curve of degree 6. This is a joint work with Aubin Arroyo and Erwan Brugallé.