A proof of hyperbolic van der Waerden conjecture: the right generalization is the ultimate simplification

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables. Assume that this polynomial satisfies the property: \\ $|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n): Re(z_i) \geq 0, 1 \leq i \leq n \}$. \\ We prove that $|\frac{\partial^n}{\partial z_1...\partial z_n} p | \geq \frac{n!}{n^n}$. Our proof is relatively short and self-contained (i.e. we only use basic properties of hyperbolic polynomials). As the van der Waerden conjecture for permanents, proved by D.I. Falikman and G.P. Egorychev, as well Bapat's conjecture for mixed discriminants, proved by the author, are particular cases of this result. We also prove so called "small rank" lower bound (in the permanents context it corresponds to sparse doubly-stochastic matrices, i.e. with small number of non-zero entries in each column). The later lower bound generalizes (with simpler proofs) recent lower bounds by A.Schrijver for the number of perfect matchings of $k$-regular bipartite graphs. 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 multiplicative factor $\frac{e^n}{n^m}$ for any fixed positive $m$.

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.