VibeMathedMath problems solved with AI
Sign in

Anari's Bethe permanent conjecture

For an n×nn\times n nonnegative matrix AA, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparisonBethe⁡(A)≤per⁡(A)≤2n/2Bethe⁡(A).\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{n/2}\operatorname{Bethe}(A).The lower bound, due to Gurvits, is attained on forests. The upper bound, due to Anari and Rezaei, is attained by the adjacency matrix of a disjoint union of 44-cycles. Confirming a conjecture of Anari, we provide an optimal girth-dependent refinement of the above comparison. More precisely, we show that if the bipartite support graph of AA has girth at least an even integer g≥4g \geq 4, thenBethe⁡(A)≤per⁡(A)≤22n/gBethe⁡(A).\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{2n/g}\operatorname{Bethe}(A).The upper bound is attained by the adjacency matrix of a disjoint union of gg-cycles.

Result
Proved(see note)
Status
Resolved
AI contribution
AI co-developed
Method
Argument
Field
Permanent approximation
Posed by
Nima Anari
Year posed
—
Years open
—
Solved
2026-09-02
Model
ChatGPT 5.6 Sol Ultra
Vendor
OpenAI
Collaborators
Dingding Dong, Vishesh Jain
Verification
Unreviewed
Publication
Preprint
Significance
22 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

For every nonnegative n×nn\times n matrix AA whose bipartite support graph has girth at least an even integer g≥4g\ge4, Dong and Jain prove the sharp inequalityBethe⁡(A)≤per⁡(A)≤22n/gBethe⁡(A).\operatorname{Bethe}(A)\le\operatorname{per}(A)\le2^{2n/g}\operatorname{Bethe}(A).The factor 22n/g2^{2n/g} is optimal whenever g∣2ng\mid2n, attained by matrices whose support graphs are disjoint unions of gg-cycles. Thus the result confirms Anari's conjecture, recovers the sharp 2n/22^{n/2} universal Anari--Rezaei bound when g=4g=4, and approaches exactness as the support-graph girth tends to infinity.

What the AI did

The authors had already developed a strategy proving a weaker girth-dependent bound of the form exp⁡(n/f(g))\exp(n/f(g)), with f(g)→∞f(g)\to\infty. GPT-5.6 Sol Pro developed this strategy into a proof with f(g)=Θ(g/log⁡g)f(g)=\Theta(g/\log g). Subsequent interactions with GPT-5.6 Sol Ultra, focused on understanding the source of the logarithmic loss and its relation to the Anari--Rezaei argument, led to the development of the final optimal 22n/g2^{2n/g} proof. Codex also assisted with manuscript preparation.

Verification

Unreviewed. A 21-page preprint two days old, no peer review, no formal verification. The optimality half is checkable by anyone: the paper exhibits the equality cases explicitly. The upper-bound argument is conventional and the authors take responsibility for it. Nobody independent has read it on the record.

Source

Submitted by VibeGene on

Changelog2 changes

Discussion