PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond the Bethe Approximation of the Permanent

Nima Anari

arXiv:2608.28031v1cs.DSmath.CO

TL;DR

Deterministic approximation of the permanent remains exponentially weaker than randomized approximation, and the Bethe bound has a tight 2^n/2 worst-case factor. This paper augments the Bethe certificate with paired row certificates and entropy-based structural analysis, obtaining a uniform improvement in the exponential base through a deterministic polynomial-time algorithm. The proof targets near-tight Bethe instances, where approximate K2,2 blocks yield aggregate gains.

  • Problem

    The Bethe permanent is efficiently computable and lower-bounds the permanent, but its universal 2^n/2 factor is attained by block-diagonal 2 × 2 all-ones matrices.

  • Method

    The paper augments the Bethe certificate with paired row certificates and uses slack decomposition, entropy, and stability analysis to identify profitable approximate K2,2 blocks.

  • Results

    The paired certificate gains e^Ω(n) on a linear number of disjoint blocks, supporting a deterministic polynomial-time approximation with a uniformly improved exponential base.

  • Takeaways & Limitations

    The canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent.

  • Takeaways & Limitations

    The paper does not attempt to optimize the improved constant c; optimizing the constants would obscure the argument.

Abstract

from arXiv · show

The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of $(\sqrt{2})^n$. We improve the base of this exponential factor: for some absolute constant $c<\sqrt{2}$, there is a deterministic polynomial-time $c^n$-approximation for the permanent of every nonnegative matrix. This shows that the canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent. The proof augments the Bethe lower bound with a new certificate tailored to matrices on which that lower bound loses nearly the full factor. The author supplied the high-level plan of attack, and the proof was developed in an interaction with ChatGPT 5.6 Sol Pro. The author subsequently verified the results. Codex assisted with proof checking, manuscript assembly, and typesetting.

1 Introduction

The paper improves deterministic approximation of the permanent beyond the Bethe bound by augmenting its certificate with paired row certificates and structural information from near-tight instances. The resulting approach combines stable-polynomial inequalities, entropy-based rigidity, and certified polynomial-time computation.

  • Motivation: Computing the permanent is #P-hard, while randomized approximation is available; general deterministic algorithms remain exponentially worse.The permanent is hard even for 0/1 matrices, and the best general deterministic methods do not match the randomized approximation guarantee.
  • Motivation: The Bethe permanent is efficiently computable and lower-bounds the permanent, but its universal factor 2^n/2 is attained by block-diagonal 2 × 2 all-ones matrices.Therefore, analyzing the Bethe permanent alone cannot improve the exponential base.
  • Paired certificate: The paper augments rather than replaces the Bethe certificate with a lower bound that pairs rows and recovers the factor 2 lost on an exact 2 × 2 all-ones block.Stable-polynomial coefficient inequalities establish one-sidedness of the paired certificate.
  • Structural analysis: Near-tight Bethe instances are analyzed through an exact slack decomposition involving Bethe-program suboptimality, row deficits, and relative entropy.This preserves information discarded in the original sequential-distribution argument.
  • Structural analysis: Small slack forces most rows toward half–half distributions and organizes their large entries into approximate K2,2 blocks rather than many long cycles.The relative-entropy term rules out many long cycles in the maximum-degree-two heavy-edge graph.
  • Algorithm and consequence: A regularized Bethe optimizer transfers these blocks to an algorithmically accessible positive point, where maximum-weight matching aggregates gains over linearly many disjoint blocks.The paired certificate improves the lower bound by e^Ω(n).

2 Preliminaries

This section introduces the Birkhoff-polytope formulation of the Bethe permanent and the polynomial and entropy tools used to construct lower certificates.

  • 2.1 The Bethe permanent: The Birkhoff polytope consists of doubly stochastic matrices, and the Bethe permanent is defined through an optimization over this polytope.The section fixes notation for permutations, entropy, KL divergence, and boundary conventions for zero entries.
  • 2.1 The Bethe permanent: The Bethe objective is concave, and the Bethe permanent is a lower bound on the permanent with a sharp matching upper bound.Both inequalities are tight.
  • 2.2 Capacity and real stability: Real stable polynomials are nonzero when all variables have positive imaginary parts, and products on disjoint variable sets preserve real stability.The section also records a quadratic Hessian criterion for proving stability.
  • 2.2 Capacity and real stability: The quadratic stability criterion follows because a Hessian with at most one positive eigenvalue yields a contradiction if the polynomial vanishes in the upper half-plane.The proof uses the nonnegative coefficients, a positive imaginary vector, and orthogonality in the Hessian quadratic form.
  • 2.2 Capacity and real stability: A multiaffine stable coefficient inequality and an entropy certificate for capacity provide the one-sided tools needed by the proof.The entropy certificate is established using the log-sum inequality and an infimum over positive scaling vectors.

3 A paired lower certificate

The paper augments the Bethe lower bound by pairing disjoint rows and certifies the resulting improvement through stable polynomials and capacity inequalities.

  • 3 A paired lower certificate: The singleton factors reproduce the Bethe objective, whereas each pair contributes a ratio Γ_rs measuring the gain over treating the rows separately.The pair ratio compares paired treatment with two singleton-row certificates.
  • 3 A paired lower certificate: For every matching of disjoint row pairs, the paired construction supplies a lower certificate combining singleton and pair factors.The construction is valid at every interior Birkhoff point and is later evaluated at a regularized Bethe optimizer.
  • 3 A paired lower certificate: The stable coefficient inequality is one-sided for every matching, allowing the row pairs to be selected algorithmically.The proof encodes row clusters and the all-columns-used condition in two stable polynomials.
  • 3 A paired lower certificate: The cluster polynomial uses singleton linear forms and pair polynomials, while a column-selector polynomial enforces that every column is used exactly once.Their coefficient inner product equals the permanent because common squarefree monomials enumerate weighted permutations.
  • 3 A paired lower certificate: The pair polynomials are real stable because their Hessians have at most one positive eigenvalue after diagonal scaling and subtracting 2I.Stability then extends to the full cluster polynomial through products in disjoint variables.

4 An exact identity for the Bethe slack

The section retains the exact relative-entropy term discarded in the Bethe upper-bound proof, decomposing the slack into nonnegative structural contributions.

  • 4 An exact identity for the Bethe slack: The analysis compares the Gibbs distribution on permutations with a sequential distribution that samples unused columns according to assignment marginals.The marginal matrix P records each row’s probability distribution over assigned columns.
  • 4 An exact identity for the Bethe slack: The sequential identity preserves the full KL divergence rather than using only its nonnegativity.This retained quantity supplies structural information beyond the standard Bethe upper-bound argument.
  • 4 An exact identity for the Bethe slack: Δ(A) measures the gap in the upper half of the Bethe sandwich, while E measures the loss from evaluating the Bethe objective at P instead of its maximizer.These quantities separate sandwich slack from Bethe-suboptimality.
  • 4 An exact identity for the Bethe slack: The exact slack decomposition expresses the relevant gap as a sum of nonnegative terms, including row deficits and a KL-divergence contribution.Nonnegativity follows from the Bethe optimum, the one-row inequality, and Gibbs’ inequality.

5 Dimension-free stability of the row inequality

The section establishes dimension-free stability for the row inequality: small defect forces a probability vector close to a half–half vector. The proof identifies equality cases and derives quantitative control from a separable defect.

  • Quantitative stability: Dimension-free stability bounds the distance of every probability vector from the half–half set using a universal constant.The modulus is independent of the ambient dimension.
  • Proof strategy: The proof first lower-bounds the sequential divergence by a separable coordinate function, then converts that bound into control of the two largest coordinates.This strategy avoids dependence on the number of coordinates.
  • Equality structure: The half–half vectors are exactly the equality cases of the separable defect lower bound.The defect is nonnegative and vanishes only at a half–half vector.
  • Equality structure: The separable defect grows quartically when one coordinate exceeds 1/2.For a largest coordinate a > 1/2, the defect is expressed through 2(artanh u − u).
  • Quantitative stability: Small defect forces the two largest coordinates to carry nearly all mass and each to be bounded below by 1/4.The proof controls both coordinates and the remaining tail mass using absolute constants.

6 Robust four-cycle structure

The section converts row stability into a robust graph structure and an entropy comparison. Good rows form heavy-edge cycles, whose ambiguity is outweighed by their entropy contribution except for controlled exceptional structure.

  • Heavy-edge structure: Row stability makes most rows close to half–half, so their two large coordinates form a graph of maximum degree two.Every good row has exactly two heavy neighbors, while the column constraints preserve degree at most two.
  • Entropy comparison: Each surviving cycle contributes at most one bit of matching ambiguity, while a good row contributes almost (log 2)/2 to the entropy calculation.Cycles with at least three rows create a surplus that must be paid for by the sequential divergence.
  • Heavy-edge structure: The heavy-edge graph can be completed to a spanning bipartite two-regular multigraph whose components are even cycles, including doubled one-row edges.The completion uses stubs and permits parallel edges.
  • Entropy comparison: The core encoding bounds the number of permutations consistent with the encoded outside assignments by 2^m(K).Intact cycles have two perfect matchings, whereas paths and doubled edges contribute at most one.
  • Robust cycle structure: Clean two-row components form K2,2 pairs, and their abundance is controlled by the number of bad rows and good rows in larger components.There are at least (n−2b−N)/2 vertex-disjoint clean pairs.

7 Transfer to a computable Bethe point

The section transfers structural facts from the inaccessible true marginal matrix to a computable regularized Bethe optimizer. Strict concavity, interiority, and KKT factorization make the transfer analyzable.

  • Transfer framework: The computable optimizer replaces the unavailable true marginal matrix while preserving the structural conclusions needed for the analysis.The transfer is made through concave optimization.
  • Regularized optimization: A regularized Bethe objective has a unique maximizer in the interior of the Birkhoff polytope.Strict concavity gives uniqueness, while the entropy regularizer rules out boundary maximizers.
  • KKT factorization: The KKT conditions factor the optimizer into row and column potentials, and normalization produces bounded compatible variables Uij.This factorization exposes the coordinates used in the paired certificate.
  • Leakage control: Subtracting excursion costs isolates the contribution of heavy edges, with good-row leakage bounded by η and bad rows handled by a coarser entropy estimate.The outside mass ρi is the probability that row i uses an edge outside K.
  • Transfer identity: An exact global transfer identity expresses the regularized suboptimality through the nonnegative transfer costs of U.Row and column scaling terms cancel in the identity.

8 A constant gain from a clean four-cycle

The section constructs a constant gain from clean four-cycles using KKT factorization and a capacity witness concentrated on core columns. The same witness yields a polynomial-time certificate-selection procedure.

  • Pair factorization: KKT factorization reduces the paired certificate to row, column, and normalization factors that cancel in the pair ratio.The resulting expression depends on the summed pair marginals.
  • Clean-pair gain: A clean K2,2 pair with sufficiently small core transfer costs yields a constant gain in the certificate.The gain uses rational absolute constants κ0, γ0, and ξ0.
  • Capacity witness: Small total core cost forces all four core entries of U to be at least e^-κ, which in turn concentrates both rows of X on the two core columns.Nonnegativity of every summand in the cost decomposition is used.
  • Capacity witness: A feasible capacity-dual distribution places most of its mass on the core monomial z_a z_b and supplies the required coefficient lower bounds.Its inclusion marginals match the pair marginal vector, making it feasible for the capacity lemma.
  • Algorithmic construction: Maximum-weight matching over row pairs selects at least the total gain of the analytically constructed clean pairs in polynomial time.Zero-weight edges are omitted from the final certificate.

9 Completing the approximation bound

The proof combines Bethe-bound stability with a paired lower-bound certificate, handling either substantial Bethe slack or a nearly tight bound. This dichotomy establishes the positive-matrix proposition, with computation and positivity deferred to the appendix.

  • 9 Completing the approximation bound: The constants η, δ0, and ξ are chosen sequentially to control structural errors, define the near-equality regime, and bound regularization loss.No numerical optimization of these constants is required.
  • 9 Completing the approximation bound: A maximum-weight matching on row pairs supplies the paired gains while preserving the lower-bound direction L_X(A) ≤ per(A).Each positive-weight edge receives witness columns attaining its pair weight.
  • 9 Completing the approximation bound: A positive-matrix proposition follows from a dichotomy between slack in the Bethe bound and gain from a paired certificate.The proof tracks bad rows, long components, sequential divergence, and transfer cost on the component graph.
  • 9 Completing the approximation bound: When Δ(A) ≥ δ0n, the nonnegative matching gain combines with the Bethe estimate to yield the required approximation bound.This is the nonnegligible-slack case.
  • 9 Completing the approximation bound: When Δ(A) < δ0n, many vertex-disjoint clean pairs satisfy the local-cost condition, so matching gains recover the needed improvement.At least 3n/8 clean pairs satisfy the hypothesis of Lemma 20 after excluding pairs with excessive transfer cost.
  • 9 Completing the approximation bound: Equations (95) and (100) prove Eq. (94), completing the conceptual core before positivity and finite-precision issues are handled separately.The remaining issues are addressed in the appendix.

A Zero entries and finite-precision computation

The appendix extends the positive-matrix argument to nonnegative matrices by one-sided smoothing. The construction preserves a lower-bound certificate and has polynomial bit complexity.

  • A Zero entries and finite-precision computation: Zero entries are removed by one-sided smoothing, and finite-precision computation is treated separately without changing the structural argument.The appendix identifies these as the two implementation issues in passing to the algorithm.
  • A Zero entries and finite-precision computation: The smoothing parameter uses a fixed positive rational constant χ and is selected to preserve a one-sided certificate.The construction also controls the resulting geometric-series estimate.
  • A Zero entries and finite-precision computation: For a nonnegative rational matrix whose positive support contains a perfect matching, smoothing constructs a positive rational matrix in polynomial time.The matrix is assumed to have largest entry at most one.
  • A Zero entries and finite-precision computation: The positive support’s perfect matching ensures per(A) ≥ m^n, while the smoothing parameter has polynomial bit length.This establishes the lower-bound relation needed for the smoothing argument.

A.2 Certified finite-precision computation

Certified computation approximates the regularized optimizer and paired certificate with polynomially bounded precision. Interior bounds, weak optimization, KKT reconstruction, and exactification preserve the lower-bound direction and polynomial running time.

  • A.2 Certified finite-precision computation: The computation first bounds the regularized optimizer away from the boundary, then solves a bounded epigraph problem using weak optimization.Approximate KKT potentials are recovered and interpreted through a nearby positive matrix.
  • A.2 Certified finite-precision computation: Every optimizer coordinate and its complement are at least 2^-poly(n,B,1/τ) for rational input matrices.This interior bound permits finite-precision evaluation of the objective and gradient.
  • A.2 Certified finite-precision computation: The gradient has an explicit logarithmic form, and Lipschitz bounds give polynomial-size control parameters for the epigraph computation.The affine coordinate map converts Euclidean coordinate errors into Frobenius errors.
  • A.2 Certified finite-precision computation: Weak optimization returns a rational doubly stochastic point with certified interior margins, despite the optimizer potentially lying outside the input body.Exact row and column sums are preserved by the affine reconstruction.
  • A.2 Certified finite-precision computation: Strong convexity controls objective error, while approximate gradients are reconstructed as row-plus-column potentials and exactified using a nearby positive matrix.The nearby matrix makes the computed point an exact regularized optimizer for the perturbed instance.
  • A.2 Certified finite-precision computation: The resulting certificate remains one-sided, and all arithmetic, optimization, elementary-function evaluation, matching, and certificate routines run in deterministic polynomial time.The output and rational intermediates have polynomial bit length.

A.3 Proof of the main theorem

The main algorithm tests support, scales and smooths the input, computes a certified lower bound, and rescales the result. The proof concludes a deterministic polynomial-time approximation, with an accompanying Lean 4 formalization covering the algorithm and proof components.

  • A.3 Proof of the main theorem: If the positive support lacks a perfect matching, the algorithm returns zero; otherwise it scales the matrix and applies smoothing and certified computation.The n = 1 case is exact.
  • A.3 Proof of the main theorem: The smoothed permanent is bounded by a computed certificate with an approximation base strictly below the canonical Bethe base.The final exponent retains at least ε+/2 after smoothing and numerical losses.
  • A.3 Proof of the main theorem: Undoing the initial scaling multiplies both the output and the permanent by the same factor to the nth power.This preserves the approximation guarantee.
  • B Provenance: The proof originated from an interaction in which the author supplied the high-level plan, while ChatGPT proposed key certificate and transfer components; the author verified the results.Codex assisted with proof checking, literature verification, assembly, and typesetting.
  • B Provenance: A Lean 4 development formalizes the proof and complete algorithm, including convex optimization, finite-precision analysis, boundary cases, and polynomial-time execution.Its main theorem has no project-specific hypotheses, and the axiom audit reports only standard Lean and Mathlib axioms.
Loading 2608.28031v1…