Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials : One Theorem for all

1 The permanent, the mixed discriminant, the Van Der Waerden conjecture(s) and homogeneous polynomials

• A doubly stochastic matrix has nonnegative entries and every row and column sums to one.The set of such n × n matrices is denoted Ω_n.Source: §1 · p. 2
• The mixed discriminant is a name for the 3-dimensional Pascal hyperdeterminant, and the permanent is its diagonal case.The mixed discriminant of an n-tuple of matrices is defined using the coefficient of the associated homogeneous polynomial.Source: §1 · pp. 2–3
• The Van der Waerden conjecture was posed in 1926; Falikman proved its lower bound in 1981, and Egorychev proved the uniqueness part.The cited passages identify Falikman's proof as and Egorychev's as.Source: §1 · p. 3

2. Schrijver-Valiant Conjecture Define

• Voorhoeve proved the k = 3 case in 1979, while the conjecture was settled in 1998.The cited passage describes the settlement as 17 years after the published proof of the Van der Waerden conjecture.Source: §2 · p. 3
• The proof of the Schrijver bound in was described by its author as “highly complicated.”The section also recalls that the Voorhoeve bound was asymptotically sharp and that Schrijver and Valiant found probabilistic distributions on Λ(k,n).Source: §2 · p. 4
• The k = 2 case has minimum permanent 2 for matrices in Λ(2,n).This is stated as part of the historical discussion leading to the Schrijver–Valiant conjecture.Source: §2 · p. 4

3. Bapat’s Conjecture (Van der Waerden Conjecture for mixed discriminants)

• Bapat conjectured that the minimum mixed discriminant over D_n is n! / n^n, attained uniquely at the tuple with every matrix equal to I/n.The author reports proving the bound even for complex positive-semidefinite matrices.Source: §3 · p. 5

1.1 The Ultimate Unification (and Simplification)

• The paper's main theorem unifies and generalizes the earlier results and improves the Schrijver bound.The theorem is formulated using the mixed derivative of H-stable homogeneous polynomials.Source: §1.1 · p. 5
• The main theorem is described as easily stated and proved by easy induction.The sections that follow introduce stable homogeneous polynomials and prove the theorem and its corollaries.Source: §1.1 · p. 5
• The uniqueness proof for the generalized Van der Waerden conjecture uses Gårding’s result on convexity of the hyperbolic cone.Source: §1.1 · p. 6

2 Homogeneous Polynomials

• Hom_R(m,n) and Hom_C(m,n) denote spaces of degree-n homogeneous polynomials in m variables with real and complex coefficients, respectively.Hom+(m,n) denotes the closed convex cone of real polynomials in Hom_R(m,n) with nonnegative coefficients.Source: §2 · p. 6
• A homogeneous polynomial with nonnegative coefficients is called doubly stochastic when it satisfies the stated normalization condition.The passage gives p(1,1,...,1) = 1 as that condition.Source: §2 · p. 6
• A polynomial in Hom_C(m,n) is H-Stable when it is nonzero whenever every variable has positive real part.The passage also names H-SStable for the condition with nonnegative real parts and an additional constraint.Source: §2 · p. 7

6. We define

• For an H-Stable polynomial p in Hom+(n, n), Theorem 2.4 states an inequality, which gives the generalized Van Der Waerden inequality; Corollary 2.5 is also stated.Source: §6 · p. 8

2.1 Three Conjectures/Inequalities

• For doubly stochastic matrices and tuples, the associated product and determinantal polynomials have capacity 1, yielding the Falikman and Bapat bounds.The product polynomial is H-Stable for a doubly stochastic matrix; the determinantal polynomial is H-Stable for a doubly stochastic tuple.Source: §6 · p. 7, §2.1 · p. 9
• A product polynomial’s degree in a variable equals the number of nonzero entries in the corresponding matrix column, enabling degree-based bounds.For matrices in Λ(k, n), the theorem yields an improved Schrijver bound when k < n; for k = 3, it recovers Voorhoeve’s inequality.Source: §2.1 · pp. 9–10
• For k ≥ n, the stated comparison gives min_{A∈Λ(k,n)} per(A) ≥ k^n vdw(n) > k^n G(k)^n.The section notes that the inequality under discussion is interesting only when k < n.Source: §2.1 · p. 10

2.2 The Main Idea

• The induction reduces variables while preserving H-Stability, using Gauss–Lucas to show each resulting polynomial is either zero or H-Stable.The argument applies Gauss–Lucas to a univariate polynomial obtained from the original polynomial.Source: §2.2 · p. 13
• The capacity step proves a lower bound for the reduced polynomial using AM/GM and real-rootedness; the induction then yields generalized Van der Waerden inequalities.The first reduced polynomial in the permanental case generally is not a product of nonnegative linear forms, so the proof leaves the matrix or graph representation.Source: §2.2 · pp. 12–13

• A Hurwitz polynomial with complex coefficients has a Hurwitz derivative, while a real-coefficient Hurwitz polynomial with positive leading coefficient has all positive coefficients.Source: §3 · pp. 13–14
• For a nonnegative-coefficient polynomial Q with real non-positive roots, the section derives a lower bound involving its capacity; equality holds exactly when all roots coincide.In that case, Q(t) = b(t + a)^k for a, b > 0.Source: §3 · p. 14
• The capacity bound follows by normalizing Q(0), expressing Q′(0) through its roots, and applying AM/GM and basic calculus.Source: §3 · pp. 14–15
• Equality in the intermediate AM/GM step requires equal positive parameters, and the bound also holds for certain functions whose kth root is concave.The stated relaxation includes log-concave functions.Source: §3 · p. 15
• The section notes that the univariate inequality is equivalent to the Van der Waerden bound for doubly stochastic matrices with two distinct columns.Source: §3 · p. 15

• H-stability means a homogeneous polynomial is nonzero whenever every variable has positive real part.Source: §4.1 · p. 15
• If A has nonnegative entries and no zero rows, composing an H-stable polynomial with A preserves H-stability; positive entries yield the stronger H-SStable property.Source: §4.1 · p. 16
• An H-stable polynomial is characterized by nonvanishing on positive real vectors and real positive roots of the univariate restrictions p(tX − Y).Source: §4.1 · p. 16
• For H-stable p, the roots of p(tX + Y) are real when X and X + Y are positive, and H-stability also implies nonnegative real values on real vectors.Source: §4.1 · p. 17
• A limit of H-stable polynomials with nonnegative coefficients is either zero or H-stable, and setting a variable to zero preserves stability unless the resulting polynomial is zero.Source: §4.1 · p. 18
• Specializing one variable to zero gives a capacity lower bound involving its degree, derived using real roots and the capacity definition.Source: §4.1 · pp. 19–20

5.1 Hyperbolic Polynomials

• An H-stable polynomial is hyperbolic in a positive direction, with hyperbolicity defined through real roots of univariate restrictions.Source: §5.1 · p. 20
• The hyperbolic cone is convex, and changing the hyperbolicity direction within that cone preserves the cone and its closure.Source: §5.1 · p. 21
• The null space consists of directions that leave the polynomial unchanged under translation, and it is a linear subspace.Source: §5.1 · p. 21

5.2 Uniqueness

• An H-stable polynomial is extremal exactly when it is a positive nth power of a linear form; equivalently, its null space has dimension n − 1.Source: §5.2 · p. 23
• Positive coordinate scaling preserves extremality, with capacity scaling by the product of the coordinate factors.Source: §5.2 · pp. 23–24
• For polynomials with positive coefficients, the capacity infimum is attained at a positive vector under the product-one normalization.Source: §5.2 · pp. 24–25

• The argument assumes a positive-coefficient, doubly stochastic H-SStable polynomial satisfying the equality condition and seeks to establish null-space dimension n − 1.Source: §1 · pp. 25–26
• It constructs a column-stochastic matrix with zero diagonal and positive off-diagonal entries as part of the null-space analysis.Source: §1 · p. 26
• The constructed matrix satisfies Rank(I − A) = n − 1, since each principal (n − 1) × (n − 1) submatrix is strictly diagonally dominant and nonsingular.Source: §1 · p. 26

• Papers and connected Alexandrov inequalities for mixed discriminants with homogeneous hyperbolic polynomials; also implicitly introduced Bapat’s conjecture.Falikman and Egorychev ’s publications prompted expository papers clarifying and popularizing their proofs.Source: §6 · pp. 26–27
• The author reports no previously published connection between the Schrijver-Valiant conjecture and stable or hyperbolic polynomials.Source: §6 · p. 27
• Capacity and Lemma (3.2) enable a simple induction by partial differentiation.The induction resembles proofs of hyperbolic-polynomial analogues of Alexandrov inequalities for mixed discriminants in and.Source: §6 · p. 27
• Capacity was implicit in permanent work and was crucial to algorithmic results in and.For nonnegative-coefficient polynomials, log(Cap(p)) is an infimum of a convex functional over vectors whose entries sum to zero.Source: §6 · p. 27
• An earlier inductive approach in used a determinantal representation for three-variable hyperbolic homogeneous polynomials and proved positivity of the full mixed derivative for H-Stable polynomials.It also established a functional involving Rank_p(S), though the passage does not give its full definition.Source: §6 · pp. 27–28
• The characterization (43) generalizes the Hall-Rado theorem, and gives strongly polynomial deterministic algorithms for support and Newton-polytope membership problems.The algorithms apply to oracle-given H-Stable polynomials in Hom+(m, n).Source: §6 · p. 28