An Analysis upon Various Applications of Zeros of Complex Univariate and Multivariate Polynomials: A Review

---------------------------♦-----------------------------

Consider the following results relevant in theoretical computer science: 1. The permanent of an n x n stochastic matrix is at least . (This has been used to show that every d-regular graph on n vertices has a traveling salesman tour of length at most. 2. The polynomial time approximation algorithm for the Traveling Salesman Problem on undi-rected. unweighted graphs with approximation ratio , for some constant , USD. 3. The seminal result by Lee and Yang in statistical physics that shows the lack of phase transition in the Ising model, and the mean magnetization of the Ising model and the average size of a matching in the monomer-dimer model are both #P-hard to compute. 4. For every d, there is an infinite sequence of d-regular bipartite Ramanujan graphs, whose adjacency matrices have all nontrivial eigenvalues bounded by . Every transitive graph with m edges and n vertices can be partitioned into edge- disjoint subgraphs of size , each of which approximates the cuts of the original graph up to a constant factor. This is a special case of a spectral discrepancy theorem about par- titioning sets of vectors in, which also resolves the Kadison-Singer problem in operator theory. While the above problems and results seem unrelated, their solutions share a common thread: they all rely on showing, at some level, that a certain univariate or multivariate polynomial has no zeros in a region of (e.g., the upper complex half-plane, or the unit disk). This is achieved by inductively constructing the relevant polynomial via a sequence of operations which preserve the property of not having roots in the required region. For instance, when the coefficients of the polynomial are real and the region of no zeros is the upper complex-half plane, the polynomial is called real stable and this property is preserved under operations such as multiplication, taking derivatives and specialization to real values. While there are extensive and difficult characterizations of real stable polynomials. the above properties of real stable polynomials are rather simple to prove and, surprisingly, are sufficient for the applications listed above. Moreover, when the polynomials are of combinatorial origin, these operations have clear algebraic and combinatorial interpretations. Thus, there is a robust way to encode many kinds of combinatorial objects as polynomials, and to draw useful conclusions from their analytic properties. More generally, this serves as evidence against the stereotype that the roots of polynomials are brittle and ill-behaved (which is the case under unnatural

Roughly, these principles are evident in the applications listed above as follows: In this paper, closure of real stability under taking derivatives allows one to lower bound the value of the permanent of a doubly stochastic matrix. In this study, using the fact that the polynomials corresponding to the max-entropy probability distributions on spanning trees are real-stable, robust and novel negative correlation and anti-concentration properties of them are established. The result in EU relies on a stability result for derivatives of the partition function of the Ising model and extends the famous Lee-Yang theorem, real stability allows one to relate the behavior of one polynomial to the behavior of a sum of polynomials leading to a new existence argument. Lastly, this theory allows the authors to control the evolution of roots of a polynomial under the application of differential operators. One may argue that some of the applications above have alternative proofs that do not require this machinery. However, the fact remains that understanding the zeros of the relevant polynomials is important, and. in certain cases, has led to major progress in problems of interest. Moreover, with dramatic progress in the mathematics of this area, such techniques have recently reached a certain maturity which makes them ripe for applications. Thus, we feel that there is need to communicate the essential techniques underlying these results, in a largely self-contained manner, to a broad theory audience, and that is the goal of this article. For more in depth exposition of techniques.

Recall that is said to be real stable if and no root of it lies in It seems harder to show that a multivariate polynomial is real stable. The first lemma reduces the problem of checking real stability of a multivariate polynomial to checking real-rootedness of a set of univariate polynomials, and turns out to be quite effective. Lemma. A multivariate polynomial is stable if and only if for all and all , the univariate polynomial is real-rooted. Proof. Suppose that is real-rooted for all and all , but f is not real stable. The latter implies that there is an such that. Let and . Since for all i. But then and, For the other direction, suppose that there are and and a such that Since complex roots of a univariate polynomial appear in conjugates, we may assume that Thus, the imaginary part of each component ofis strictly positive contradicting the fact that is real stable. Using the lemma above, several multivariate polynomials can be shown to be real stable. Perhaps the simplest such polynomial (which can be seen to be real stable without appealing to the lemma above) is when for all i. Since a root of a polynomial that is a product of two polynomials is a root of at least one of those two polynomials, the polynomial is also real stable. A bit more non-trivially, the following important class of polynomials arising from determinants can be shown to be real stable. Lemma. Let be positive definite matrices0 and B be a symmetric m x m real matrix. Then the polynomial is real stable. Proof. By Lemma it is sufficient to prove that for all and . is real-rooted. This is the same as showing that is real-rooted. Since and for all . Thus, letting , we need to show that This latter is true because is symmetric and every real-symmetric has all real eigenvalues. To see this, if A is a real symmetric matrix and isan eigenvalue with an eigenvectorthen ‗Conjugating both sides we obtain that , where is the conjugate transpose of Hence, since A is symmetric. Thus, which implies that Thus, The above lemma can be proved in the setting whenare positive semi-definite (PSD) as opposed to being positive-definite. This is quite useful for applications. However, extending Lemma requires the

is beyond the scope of the current article. Theorem (Hurwitz). Let be a sequence of -stable polynomials over for a connected and open set that uniformly converge to a polynomial over compact subsets of . Then is -stable. To use this theorem for a matrix which is just guaranteed to be PSD one approximates each by a sequence of matrices which are positive definite and converge to ask goes to infinity. One can ask if all real stable polynomials arise from such determinants. This is the content of the Lax Conjecture and the interested reader is referred to.

As a simple but powerful application of the closure properties we show how, starting with simple polynomials, we can argue about non-trivial (and computationally intractable) objects such as the permanent of a matrix. For a matrix with real entries, its permanent is defined to be Consider the polynomial and note that is clearly real stable. Moreover, it follows from a repeated application of Lemma that, for any the polynomial is real stable. Note that . If all entries of A are nonnegative, then it follows from Lemma that, for any fixed positive Where is the degree of the polynomial . Fixing , let be defined to be Thus, applying the above inequality fortoand letting we obtain that which is at least It turns out that when A is a doubly stochastic matrix, then this quantity can be lower bounded by 1. Recall that a matrix A is said to be doubly stochastic matrix, i.e., and, for all and for all f. To see the claim, observe that for any positive Thus, when A is doubly stochastic,. Noting that we have proved the van der Waerden conjecture. Theorem. For a doubly stochastic matrix A, As a corollary, let be a k-regular bipartite graph with Let A be the matrix with rows indexed by columns by W, and if . Then, is doubly stochastic and, hence, . Note that per(A) counts exactly the number of perfect matchings in G.

In this section we study probability distributions over by looking at their generating function. For a distributionthe generating function is the multivariate affine polynomial If is real stable, then one can derive a host of properties ofby appealing to the closure properties enjoyed by real stable polynomials. In this case, is said to be strongly Rayleigh. Definition . A measureover is said to be strongly Rayleigh if its generating function is real stable. Strongly Rayleigh measures satisfy the strongest forms of negative dependence, a consequence of which is the concentration of measure for a sum of random variables drawn from a such a measure. As a starting point, we prove the pairwise negative correlation property of strongly Rayleigh measures.

negatively correlated if for all In terms of polynomials, this condition is equivalent to In fact, for strongly Rayleigh measures, one can show something stronger: the condition holds for all rather than just the vector . This property, in fact, implies the strong Rayleigh measures but we just prove the forward direction. Lemma. If is affine and stable, then for all Thus, the lemma implies that strongly Rayleigh measures are pair wise negatively correlated. Proof Fix and . It follows from Lemma along with Theorem that is stable. On the other hand, since is affine, Since is stable, for any such that If then (dropping for the easy of reading). Multiplying the first equation by and the second by and adding them, we obtain Since, this implies that completing the proof.

In this section we show how real stability can be used to show that a bound on the largest root of a sum of a certain family of polynomials implies the same bound on the largest root of one polynomial in the family. This novel technique is central to the proof of the existence of Ramanujan graphs of all degrees [OS], and the resolution of the Kadison-Singer problem. the same degree and has a positive leading coefficient. For we define a random polynomial where is an independent Bernoulli random variable which is 1 with probability and -1 with probability Assume, the seemingly strong hypothesis, that this family polynomials satisfies, for every the polynomial is real-rooted. Such a family is shown to have the property that if the largest root of is bounded by , then there is a such that the largest root of is also bounded by . This is captured in the following theorem. Theorem .Suppose is a family of real-rooted polynomials with positive leading coefficients where all have the same degree. Then, there is a such that the largest root of is at most the largest root of While we do not go into the the proof of the hypothesis for any specific family in this article, we mention that the real-rootedness of is shown by constructing a suitable starting multivariate polynomial that is real stable and then applying a carefully chosen sequence of closure properties such as the ones presented in paper We start the proof of Theorem for a family which satisfies the above hypothesis by observing the following implication of the hypothesis. Lemma . Under the hypothesis, for any fixing any convex combination of and are real-rooted. Proof. For a parameter set and and for k. It follows that which is real-rooted by the hypothesis.

The conclusion of the above lemma is interesting because if any convex combination of two univariate polynomials with leading positive coefficients is real-rooted, then they have a common interlacing. Two real-rooted polynomials and of the same degree (d) are said to interlace if their roots alternate. More formally, if are roots of and are the roots of g, then or

both and , we say that they have a common interlacing. The following lemma can be proved by showing that, if one looks at the intervals corresponding to the successive roots of each polynomial and order them from left to right, the corresponding intervals have non-empty intersection. This is a consequence of the fact that two interlacing polynomials with positive leading coefficients cannot differ in the number of roots they have in any interval of the form by more than 1. We omit the elementary but somewhat tedious proof.

Adam Marcus, Daniel A. Spielman, and Nikhil Srivastava (2013). Interlacing families I: Bipartite Ramanujan graphs of all degrees. arXiv preprint arXiv:1304.4132. Adam Marcus, Daniel A. Spielman and Nikhil Srivastava (2013). Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem. arXiv preprint arXiv:1306.3969. Adrian Lewis, Pablo Parrilo, and Motakuri Ramana (2005). The lax conjecture is true. Proceedings of the American Mathematical Society, 133(9): pp. 2495–2499. C. N. Yang and T. D. Lee (1952). Statistical theory of equations of state and phase transitions. I. Theory of condensation. Physical Review, 87(3): pp. 404–409. Julius Borcea and Petter Br¨and´en (2009). The Lee-Yang and P´olya-Schur programs. I. linear operators preserving stability. Inventiones mathematicae, 177(3): pp. 541–569. Julius Borcea and Petter Br¨and´en (2009). The Lee-Yang and P´olya-Schur programs. II. theory of stable polynomials and applications. Communications on Pure and Applied Mathematics, 62(12): pp. 1595–1631. Julius Borcea, Petter Br¨and´en, and Thomas Liggett (2009). Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22(2): pp. 521 567. Leonid Gurvits (2006). Hyperbolic polynomials approach to van der Waerden/Schrijver-valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. In Proceedings of the thirty-eighth annual ACM

426. ACM.

Maria Chudnovsky and Paul Seymour (2007). The roots of the independence polynomial of a clawfree graph. Journal of Combinatorial Theory, Series B, 97(3): pp. 350–357. Robin Pemantle (2012). Hyperbolicity and stable polynomials in combinatorics and probability. arXiv preprint arXiv:1210.3231. Shayan Oveis Gharan, Amin Saberi, and Mohit Singh (2011). A randomized rounding approach to the traveling salesman problem. In FOCS, pp. 550–559. Steve Fisk (2006). Polynomials, roots, and interlacing. arXiv preprint math/0612833. Tobias M¨omke and Ola Svensson (2011). Approximating graphic TSP by matchings. In FOCS, pages 560–569. Tom´as Feder and Milena Mihail (1992). Balanced matroids. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 26–38. ACM.

Research Scholar, OPJS University, Rajasthan E-Mail – rohitkumarjangra1@gmail.com