Abstract:
Let $p(x_1,...,x_n) = p(X) , X \in R^{n}$ be a homogeneous polynomial of degree $n$ in $n$ real variables , $e = (1,1,..,1) \in R^n$ be a vector of all ones . Such polynomial $p$ is called $e$-hyperbolic if for all real vectors $X \in R^{n}$ the univariate polynomial equation $p(te - X) = 0$ has all real roots $\lambda_{1}(X) \geq ... \geq \lambda_{n}(X)$ . The number of nonzero roots $|\{i :\lambda_{i}(X) \neq 0 \}|$ is called $Rank_{p}(X)$ . A $e$-hyperbolic polynomial $p$ is called $POS$-hyperbolic if roots of vectors $X \in R^{n}_{+}$ with nonnegative coordinates are also nonnegative (the orthant $R^{n}_{+}$ belongs to the hyperbolic cone) and $p(e) > 0$ . Below $\{e_1,...,e_n\}$ stands for the canonical orthogonal basis in $R^{n}$. \\ The main results states that if $p(x_1,x_2,...,x_n)$ is a $POS$-hyperbolic (homogeneous) polynomial of degree $n$ , $Rank_{p} (e_{i}) = R_i$ and $ p(x_1,x_2,...,x_n) \geq \prod_{1 \leq i \leq n} x_i ; x_i > 0 , 1 \leq i \leq n , $ \\ then the following inequality holds $$ \frac{\partial^n}{\partial x_1...\partial x_n} p(0,...,0) \geq \prod_{1 \leq i \leq n} (\frac{G_{i} -1}{G_{i}})^{G_{i} -1} (G_i = \min(R_{i} , n+1-i)) . $$ This theorem is a vast (and unifying) generalization of the van der Waerden conjecture on the permanents of doubly stochastic matrices as well as the Schrijver-Valiant conjecture on the number of perfect matchings in $k$-regular bipartite graphs . These two famous results correspond to the $POS$-hyperbolic polynomials being products of linear forms. Section 2.2 provides the extension of the main result to so called AF-polynomials , the class which is larger than the class of $POS$-hyperbolic polynomial and includes volume polynomials $Vol(x_1 C_1 +...+x_n C_n)$ , where $C_i , 1 \leq i \leq n$ are convex compact subsets of R^n . This extension leads to a randomized poly-time algorithm to approximate the mixed volume of $n$ convex compact subsets of R^n within multiplicative factor $e^n$ . Our proof is relatively simple and "noncomputational" ; it actually slightly improves Schrijver's lower bound , and uses very basic ( more or less centered around Rolle's theorem ) properties of hyperbolic polynomials . \\ We present some important algorithmic applications of the result, including a polynomial time deterministic algorithm approximating the permanent of $n \times n$ nonnegative entry-wise matrices within a multiplicative factor $\frac{e^n}{n^m}$ for any fixed positive $m$ . This paper introduces a new powerful "polynomial" technique , which allows as to simplify/unify famous and hard known results as well to prove new important theorems . The paper is (almost) entirely self-contained , most of the proofs can be found in the {\bf Appendices}.