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].

  1. [Gur08] Leonid Gurvits. 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}
    }
  2. [Ego81] G. P Egorychev. 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}
    }
  3. [Fal81] D. I. Falikman. 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}
    }

Definitions

  • Capacity of a multivariate polynomial

    RealRooted.Gurvits.capacitysource
    noncomputable def capacity (p : MvPolynomial σ ℝ) : ℝ :=
      ⨅ x : {x : σ → ℝ // ∀ i, 0 < x i}, eval x.1 p / ∏ i, x.1 i

Theorems

  • Van der Waerden: the permanent of a doubly stochastic matrix is at least n!/nⁿMain result

    RealRooted.Gurvits.factorial_div_pow_le_permanentsource
    theorem factorial_div_pow_le_permanent {n : ℕ} {A : Matrix (Fin n) (Fin n) ℝ}
        (hA : A ∈ doublyStochastic ℝ (Fin n)) : (n.factorial : ℝ) / n ^ n ≤ A.permanent
  • Gurvits: capacity drops by at most ((d−1)/d)^(d−1) per variable

    RealRooted.Gurvits.gurvitsFactor_mul_capacity_le_capacity_stepsource
    theorem gurvitsFactor_mul_capacity_le_capacity_step {k : ℕ}
        {p : MvPolynomial (Fin (k + 1)) ℝ} (hp : MvRealStableOrZero p) (hnn : ∀ m, 0 ≤ p.coeff m)
        (hdeg : p.totalDegree ≤ k + 1) :
        gurvitsFactor (k + 1) * capacity p ≤ capacity (step p)
  • Gurvits' univariate coefficient inequality

    RealRooted.Gurvits.mul_le_coeff_one_of_splitssource
    theorem mul_le_coeff_one_of_splits {q : ℝ[X]} (hs : q.Splits) (hq : ∀ n, 0 ≤ q.coeff n)
        {d : ℕ} (hdeg : q.natDegree ≤ d) (hd : 1 ≤ d) {c : ℝ}
        (h : ∀ t > 0, c * t ≤ q.eval t) :
        c * (((d : ℝ) - 1) / d) ^ (d - 1) ≤ q.coeff 1

Lean source RealRooted/Challenges/Matrices/VanDerWaerden.lean at revision d6670742. Formalized 2026-10-07.