Source-linked AI summary
Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
Leonid Gurvits
TL;DR
The paper addresses the limited known application of inequality (5) by using it to derive a new bound and prove the Asymptotic Lower Matching Conjecture. The proof covers the full density range t in [0, 1].
Problem
The known application of inequality (5) was limited to bound (4), motivating the paper to demonstrate its broader power.
Source: §1.1 · p. 3Method
The proof derives its target inequality by combining a new inequality with a known identity.
Source: §6.2 · p. 20Results
The proof of the Asymptotic Lower Matching Conjecture covers the full density range t in [0, 1].
Source: §6.2 · p. 21Takeaways & Limitations
A deterministic polynomial-time algorithm approximates the permanent within relative factor UB(n), and proving UB < e is described as algorithmically important.
Source: §3 · p. 6The proof applies only to m-permanents, and whether it extends to general H-stable polynomials remains open.
Source: §6.2 · p. 21
Abstract
from arXiv · showhide
Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n. We use the above Shrijver's inequality to prove the following lower bound: \frac{per(A)}{F(A)} \geq 1; F(A) =: \prod_{1 \leq i,j \leq n} (1- A(i,j))^{1- A(i,j)}. We use this new lower bound to prove S.Friedland's Asymptotic Lower Matching Conjecture(LAMC) on monomer-dimer problem. We use some ideas of our proof of (LAMC) to disprove [Lu,Mohr,Szekely] positive correlation conjecture. We present explicit doubly-stochastic $n \times n$ matrices $A$ with the ratio $\frac{per(A)}{F(A)} = \sqrt{2}^{n}$; conjecture that \max_{A \in \Omega_n}\frac{per(A)}{F(A)} \approx (\sqrt{2})^{n} and give some examples supporting the conjecture. If true, the conjecture (and other ones stated in the paper) would imply a deterministic poly-time algorithm to approximate the permanent of $n \times n$ nonnegative matrices within the relative factor $(\sqrt{2})^{n}$. The best current such factor is $e^n$.
1 The permanent
The section recalls the permanent and doubly stochastic matrices, then introduces Schrijver’s permanental inequality as the key result motivating the paper’s further use of it.
1 The permanent
- A doubly stochastic matrix is nonnegative with every row and column summing to one, and Ω_n denotes the set of such matrices.The section also introduces Λ(k,n), integer matrices with all row and column sums k, and Ω_k,n as their scaling by k^-1.Source: §1 · p. 2
1.1 Schrijver-Valiant Conjecture and (main) Schrijver’s permanental inequality
- Schrijver’s 1998 result settled the conjecture that θ(k) = G(k), and its main result is the Schrijver-bound for doubly stochastic matrices.The paper presents the bound as a remarkable consequence of that resolution.Source: §1.1 · p. 2
- The bound (4) follows from a more general inequality involving the entrywise transform A(i,j)(1−A(i,j)) and a product of (1−A(i,j)) terms.The paper says the proof of this general inequality in was highly complicated and that its known application was limited to very rational doubly stochastic matrices.Source: §1.1 · pp. 2–3
2 A Generalization of Schrijver’s permanental inequality
This section generalizes Schrijver’s inequality through a functional on pairs of nonnegative matrices. Its proof uses scaling and the original inequality to obtain the stated conclusion.
2 A Generalization of Schrijver’s permanental inequality
- Theorem 2.2 states that for nonnegative P with Per(P)>0, the maximum of CW(P,Q) over doubly stochastic Q is attained.The section says the functional is concave in P and, surprisingly, in Q over Ω_n.Source: §2 · p. 3
- For positive P, CW(P,Q) is bounded and continuous on Ω_n, so its maximum exists.The proof proceeds by choosing a maximizer V and deriving first-order conditions.Source: §2 · p. 4
- At an indecomposable doubly stochastic block, the proof uses Lagrange multipliers on matrices restricted to the block’s support.The resulting conditions yield a diagonal scaling inequality for the block’s entrywise transform V(i,j)(1−V(i,j)).Source: §2 · pp. 4–5
- The proof combines the new inequality with a known identity and then applies Schrijver’s permanental inequality.The paper notes that this proof does not use concavity of CW(P,V) in V.Source: §2 · p. 5
3 Corollaries
The corollaries emphasize an entry-dependent lower bound for the permanent and connect it to approximation guarantees and a counterexample to a positive-correlation conjecture.
3 Corollaries
- 1 ≤ UB ≤ e, and a deterministic polynomial-time algorithm approximates the permanent of nonnegative matrices within relative factor UB(n).The passage states that the current best rate is e^n and that proving UB < e is of major algorithmic importance.Source: §3 · p. 6
- The lower bound (14) depends explicitly on the entries of P, unlike earlier lower bounds for permanents of doubly stochastic matrices, which depend only on dimension and support.The paper uses it in Section 5 to settle a conjecture on monomer-dimer entropy.Source: §3 · p. 6
- The paper gives a class of matrices for which max_Q CW(P_2n,Q)=log(F(P_2n)), and identifies it as a counterexample to the non-trivial part of Conjecture 15 in.The passage then asks whether the bound (18) is sharp.Source: §3 · p. 7
- The paper presents a non-regular real-valued version of the Schrijver-bound and a slightly weaker version of the Falikman-Egorychev-van der Waerden lower bound.It also notes that the bound from is better in the worst case.Source: §3 · p. 7
4 Some historical remarks
This section recalls earlier permanent-related bounds and definitions, then states a broader conjecture for H-stable polynomials.
4 Some historical remarks
- The section recalls the polynomial classes HomR(m,n), HomC(m,n), and Hom+(m,n), with Hom+ comprising homogeneous real polynomials with nonnegative coefficients.It also defines capacity and an associated product polynomial for a matrix P, relating the permanent to a mixed derivative of that polynomial.Source: §4 · p. 8
- A lower bound for all doubly stochastic P is attributed to, while a different version is obtained by combining results from with (27).The section frames a broader conjecture beyond doubly stochastic matrices and permanental settings.Source: §4 · pp. 8–9
- Conjecture 4.2 proposes the inequality for H-stable homogeneous polynomials with nonnegative coefficients, defined here by having no roots when every variable has positive real part.The conjecture is presented as a general version beyond doubly stochastic matrices and permanental polynomials.Source: §4 · p. 9
5 Some Partial Results Towards the Main Conjecture(s)
This section develops partial results around conjectured bounds for doubly stochastic matrices and their implications for approximating the permanent. It establishes simplex-convexity properties and gives cases where the conjectures hold.
5 Some Partial Results Towards the Main Conjecture(s)
- The paper poses a main conjecture for doubly stochastic P and distinguishes it from the optimization, strong, and mild conjectures.The optimization conjecture is described as yielding a polynomial-time but not strongly-polynomial algorithm; the strong and mild conjectures are linked to strongly-polynomial algorithms.Source: §5 · pp. 9–10
- The optimization conjecture is associated with a deterministic polynomial-time approximation algorithm, while the strong conjecture gives a deterministic strongly-polynomial algorithm.The text also states that the mild conjecture would give a strongly-polynomial approximation factor below e^n.Source: §5 · pp. 9–10
5.1 Some Basic Properties of CW(P, Q)
- Odd entropy is not convex on [0, 1], but its lift to the simplex is convex, and the paper gives a simpler, more general proof of this result.The authors use the convex odd-entropy functional to define the Bethe Divergence; they identify statistical or learning applications as a direction for future investigation.Source: §5.1 · pp. 10, 12
5.2 Some easy exact computations of maxQ∈Ωn CW(P, Q)
- For n ≥ 3, the maximum of OD(q, p) is at an extreme point when a unique dominant index exists, and otherwise is attained in the simplex interior.The paper contrasts this with Kullback–Leibler divergence minimization, where the extremum has largest possible support.Source: §5.2 · p. 13
- The section gives a corollary for diagonally dominant nonnegative P over row-stochastic matrices and considers matrices made diagonally dominant by diagonal scaling.The scaling case assumes P = D1AD2 is diagonally dominant.Source: §5.2 · p. 13
5.3 Regular Bipartite Graphs
- The Strong Conjecture holds for regular bipartite graph matrices and for their convex hull, with the latter conclusion following from linearity of the permanent in individual rows.The text also invokes Bregman’s upper bound in this section.Source: §5.3 · p. 14
5.4 Diagonally Dominant Matrices
- Corollary 5.15 states that the Optimizational Conjecture holds when A is diagonally dominant.The proof is attributed to linearity of the permanent in individual rows and a generalized Hölder inequality.Source: §5.4 · p. 15
6 A proof of Friedland’s Asymptotic Lower Matching Conjecture
The paper proves Friedland’s Asymptotic Lower Matching Conjecture using lower bounds for permanents, including a stronger result for integer matrices with fixed row and column sums. It also compares two random models for regular bipartite graphs and derives asymptotic properties of their probabilities.
6.1 Two models for random regular bipartite graphs with multiple edges
- The two models considered are a pairing model built from a uniform permutation of length rn and a sum of r independent uniform permutations.The resulting matrices have row and column sums r.Source: §6.1 · pp. 15–16
- For fixed r, the paper gives an asymptotic expression for the probability that the sum-of-permutations model is boolean.The passage identifies this as the asymptotic for prob2(r, n).Source: §6.1 · p. 17
- For the sum of independent random permutations, events that pairs of permutations do not overlap are asymptotically independent.The paper interprets the probability in (44) as the probability that all such pairwise non-overlap events occur.Source: §6.1 · p. 17
6.2 Monomer-Dimer Problem
- The paper proves Friedland’s Asymptotic Lower Matching Conjecture by combining its lower bounds with inequalities (46, 47).It states a stronger result for matrices in RI(r, n), not only the boolean case.Source: §6.2 · pp. 18, 20
7 A disproof of a positive correlation conjecture due to [Lu,Mohr,Szekely]
The paper disproves the Lu, Mohr, and Székely positive-correlation conjecture by constructing doubly-stochastic matrices for which the conjectured lower bound exceeds a weighted average of permanents. It also shows that a related Sidak-like conjecture fails outside the regular case and gives an explicit counterexample.
7 A disproof of a positive correlation conjecture due to [Lu,Mohr,Szekely]
- Finite families of doubly-stochastic matrices have constant LMS(A), while a weighted average of their permanents is exponentially smaller, disproving the conjecture.The paper reports a concrete 135 × 135 counterexample.Source: §7 · p. 23, §7.3 · p. 27
7.2 A disproof of Sidak-like positive correlation conjecture (67)
- The Sidak-like inequality holds in the regular case but fails in general, where SD(A) is at least F(A).In the regular case, SD(A), LMS(A), and F(A) are equal.Source: §7 · p. 24
7 A disproof of a positive correlation conjecture due to [Lu,Mohr,Szekely]
- The paper proves the Lu, Mohr, and Székely conjecture for regular H-Stable polynomials.For regular doubly-stochastic matrices, LMS(A) equals F(A), and the conjectured inequality is equivalent to Schrijver’s bound.Source: §7 · pp. 23, 25
7.1 The Construction
- The construction seeks matrices for which F(A) is close to the permanent while LMS(A) and SD(A) are much greater than F(A).The paper first establishes existence for sufficiently large n by a probabilistic method, then gives a concrete example.Source: §7.1 · p. 25
7.3 A Concrete Counter-Example
- The smallest n for which LMS(K_n) exceeds per(K_n) is 90, giving a 135 × 135 counterexample to the conjecture.The construction considers even n in the stated family of doubly-stochastic matrices.Source: §7.3 · p. 27
8 Credits and Conclusion
The conclusion credits the Bethe approximation and Schrijver’s inequality as important to the paper’s approach. It also identifies generalizing the proof beyond m-permanents as an open problem.
8 Credits and Conclusion
- The conclusion suggests higher-order approximations as a possible direction, but says they will likely require new lower bounds involving subpermanents.The Bethe approximation is described there as an order-two approximation involving pairwise marginals.Source: §8 · pp. 27–28
- The proof of the monomer-dimer entropy conjecture illustrates the power of Theorem 2.2, and the author credits Schrijver’s inequality as essential to settling it.The conclusion connects the problem to classical statistical physics and the history of the Bethe approximation.Source: §8 · pp. 27–28