An arXiv preprint claims a deterministic, polynomial-time way to approximate the permanent of every nonnegative rational square matrix. Its construction would return a lower-bound certificate that never exceeds the permanent, while the permanent would be no more than an exponential factor times that certificate, with the factor's base below the canonical Bethe base.
The Bethe approximation is the theoretical baseline in this work. The proposed gain is therefore a better exponential guarantee, not an exact value for the permanent. The claim is uniform over the stated class of matrices rather than limited to a selected input family.
The proof turns a gap into structure
The proposed lower certificate adds paired information to the Bethe construction. It uses a stable-polynomial encoding to track clusters of rows and the requirement that every column be used once. For any matching, meaning a set of non-overlapping row pairs, the certificate remains one-sided, and the method searches for pairs whose gain is greater than one.
The proof's central move is to treat the gap in the Bethe bound as information. For positive matrices, it gives an exact decomposition of that slack into three nonnegative parts: the loss from using the assignment-marginal matrix instead of the optimizer, the sum of row deficits, and an averaged sequential KL divergence, a measure of difference between probability distributions. Since none can be negative, the identity gives the argument separate quantities to control.
That bookkeeping leads to a stability result for individual rows. A probability row with a small deficit lies close, in L1 distance, to a half-half vector that puts equal weight on two columns. In plain terms, rows with small deficits must look approximately like two-column splits. The distance is bounded by a universal finite constant times the fourth root of the deficit, independently of the dimension.
At the structural level, the argument then guarantees many vertex-disjoint clean pairs in the relevant regime. Each clean pair is a K2,2 component formed by two good rows. Because the pairs do not share vertices, the proof can use their gains together without reusing a row.
From structure to an executable certificate
A maximum-weight matching on the row pairs performs that selection. The analysis says it collects at least the gain of the clean pairs identified in the proof, and that the matching is computable in polynomial time. This is the bridge from a structural existence argument to an algorithm.
To organize the calculation, the paper uses a regularized Bethe objective. It has a unique optimizer in the interior, and its value is within the stated regularization loss of the unregularized Bethe value. The optimizer also yields positive row and column scalings satisfying the paper's KKT factorization, its stated optimality condition.
An exact transfer identity connects that optimizer to the true assignment marginals. It says that regularized suboptimality together with row-entropy terms equals the total logarithmic transfer cost across matrix entries. Entropy here captures how spread a row's probability mass is, while the identity supplies the accounting used in the transfer analysis.
For positive matrices, the result reaches its cleanest form. The constructed certificate is a lower bound on the permanent, and the upper ratio has an absolute positive improvement in its exponential base over the Bethe baseline. The proposition covers every positive matrix of order at least two, but the improvement constant is existential rather than numerically optimized or reported.
Zero entries require a separate passage. For a nonnegative rational matrix whose nonzero pattern contains a perfect matching, and after scaling so its largest entry is at most one, polynomial-time smoothing produces a positive matrix whose permanent stays between the original permanent and the paper's stated multiplicative factor times it. If the nonzero pattern has no perfect matching, the final procedure returns zero; otherwise it scales the matrix and continues.
Finite precision is treated explicitly for positive rational inputs. Given a rational numerical tolerance, the certified algorithm outputs a rational lower-bound certificate with an explicit error guarantee. Its running time is polynomial in the input bit length, the matrix order, and the logarithm of two plus the inverse of the requested tolerance. The supplied analysis does not report independent implementation results or benchmarks, so this is an algorithmic guarantee rather than an observed performance result.
Why the result still needs checking
The work remains a preprint. The supplied front matter identifies it as arXiv version 2, dated 1 September 2026. This is a theoretical proof and algorithm analysis over mathematical inputs, not an empirical validation. The numerical improvement constant is not optimized or reported, so the paper does not say how large the gain is.
The preprint also discloses its production process. The author says they supplied the high-level plan, developed the proof in interaction with ChatGPT 5.6 Sol Pro, later verified the results, and used Codex for proof checking, manuscript assembly and typesetting. That records assistance and authorship workflow; it does not by itself establish that an AI system independently authored or verified the proof.
The reported Lean 4 formalization covers convex optimization, finite-precision error analysis, support and boundary cases, an executable rational algorithm, and a proof of ordinary deterministic polynomial time under binary encoding. Its axiom audit reports only standard Lean and Mathlib axioms, although the supplied review did not independently assess the artifact's contents. The open questions are whether the constant can be made explicit or improved, whether the proof and implementation can be independently checked, and how the paired certificate compares computationally with other methods across matrix families.
Paper data and sources
Original title: Beyond the Bethe Approximation of the Permanent
Authors: Nima Anari
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text