Van der Waerden permanent bound
The permanent of an $n\times n$ doubly stochastic matrix is at least $n!/n^n$.
Results
Theorem (Egorychev, Falikman). [Ego81]; [Fal81] If $A$ is an $n\times n$ doubly stochastic matrix, then $$ \operatorname{per}A\ge\frac{n!}{n^n}. $$
Proof
The proof follows Gurvits [Gur08]. The capacity of a polynomial $p(x_1,\dots,x_n)$ with nonnegative coefficients is $\inf_{x>0}p(x)/(x_1\cdots x_n)$. Let $p$ be a real stable polynomial in $k$ variables of total degree at most $k$. Differentiating in one variable and setting it to zero gives a real stable polynomial whose capacity is at least $((k-1)/k)^{k-1}$ times that of $p$. This rests on a univariate inequality: if $q$ is real-rooted with nonnegative coefficients and degree at most $d$, and $c\,t\le q(t)$ for all $t>0$, then $c\,((d-1)/d)^{d-1}\le q'(0)$. The polynomial $\prod_i\sum_ja_{ij}x_j$ is real stable with capacity at least $1$ and coefficient $\operatorname{per}A$ at $x_1\cdots x_n$; the $n$ steps extract this coefficient and the factors multiply to $n!/n^n$.
References
[Ego81]; [Fal81]; the proof above is that of [Gur08].
- [Gur08] Van der Waerden/Schrijver--Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: One theorem for all. The Electronic Journal of Combinatorics, 15(1), Research Paper 66, 2008.
BibTeX
@article{Gurvits2008, author = {Leonid Gurvits}, title = {Van der {W}aerden/{S}chrijver--{V}aliant like conjectures and stable (aka hyperbolic) homogeneous polynomials: One theorem for all}, year = {2008}, journal = {The Electronic Journal of Combinatorics}, volume = {15}, number = {1}, pages = {Research Paper 66}, doi = {10.37236/790}, url = {https://doi.org/10.37236/790}, eprint = {0711.3496} } - [Ego81] The solution of van der Waerden's problem for permanents. Advances in Mathematics, 42(3), 299-305, 1981.
BibTeX
@article{Egorychev1981, author = {Egorychev, G.P}, title = {The solution of van der {W}aerden's problem for permanents}, year = {1981}, journal = {Advances in Mathematics}, volume = {42}, number = {3}, pages = {299--305}, doi = {10.1016/0001-8708(81)90044-X}, url = {https://doi.org/10.1016/0001-8708(81)90044-X} } - [Fal81] Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix. Mathematical Notes of the Academy of Sciences of the USSR, 29(6), 475-479, 1981.
BibTeX
@article{Falikman1981, author = {Falikman, D. I.}, title = {Proof of the van der {W}aerden conjecture regarding the permanent of a doubly stochastic matrix}, year = {1981}, journal = {Mathematical Notes of the Academy of Sciences of the USSR}, volume = {29}, number = {6}, pages = {475--479}, doi = {10.1007/BF01163285}, url = {https://doi.org/10.1007/BF01163285} }