Alec Kriebel

Nonnegative binary rational hafnians: an exact reduction and approximation and sampling consequences

A hafnian adds the weights of every way to pair up a set of objects. This note explains how to turn nonnegative rational pairing weights into an ordinary, unweighted perfect-matching problem. It then transfers the cited general-graph approximation theorem to that rational model and specifies a sampler with a controlled total-variation error.

This is an attributed consequence, exposition and implementation note. Binary rational weight removal and counting self-reduction are established machinery; the approximation breakthrough is credited to OpenAI. The note supplies an explicit Horner construction, proofs, bit bounds, boundary handling and finite reproducibility materials.

Original abstract

We give a self-contained implementation of classical positive-integer weight removal for perfect matchings. A binary directed acyclic graph with W paths gives a simple two-terminal graph with matching signature (W,1,0,0) using 4 bits(W)−2 vertices. Gluing these gadgets and clearing denominators reduces every nonnegative binary rational hafnian to an unweighted simple-graph perfect-matching count with polynomial encoding length. Consequently, the general-graph FPRAS of OpenAI gives a uniform FPRAS for this rational model, with exact zero detection. We specify a bounded-bit counting self-reduction sampler with explicit total-variation and runtime bounds. The approximation breakthrough, logarithmic weight removal, and count-to-sample framework are inherited; this note supplies explicit proofs, bit bounds, boundary cases, and reproducible finite checks. Its approximation conclusions rely on the cited general-graph theorem and do not concern signed or complex hafnians.

Replacing weights with choices

A perfect matching pairs every vertex exactly once. In the weighted problem, each pairing contributes the product of its edge weights. The construction replaces an edge of positive integer weight W by a small graph with exactly W ways to use that pair of endpoints, and one way to leave both endpoints for other edges.

The graph reads the binary digits of W. Each digit doubles the number of directed paths and optionally adds one, just as binary arithmetic does. Splitting the internal path vertices turns those paths into perfect matchings. The graph grows with the number of bits in the weight, rather than with the weight's numerical value.

Clearing rational denominators supplies integer weights. When the small graphs are joined, each original pairing has exactly as many expanded matchings as its scaled weight requires. A uniform choice among expanded matchings therefore projects to the desired weighted pairing law.

The exact reduction and its fibers

Let A be an explicitly given symmetric matrix of order 2m, with nonnegative rational off-diagonal entries encoded in binary. Its diagonal is ignored. Delete zero-weight edges and let L be the matrix's binary encoding length. The hafnian is

ZA = haf(A) = ∑M a perfect matching ∏e∈MAe.

For each positive entry write Ae = pe/qe, and put D = ∏eqe and We = pe(D/qe). The empty product is one. A positive integer W of bit length ℓ = 1+⌊log₂ W⌋ gives a simple two-terminal graph HW with

(#PM(HW), #PM(HW−{u,v}), #PM(HW−u), #PM(HW−v)) = (W,1,0,0).

It has exactly 4ℓ−2 vertices, including 4ℓ−4 internal vertices, and at most 6ℓ−5 edges. After gluing one fresh gadget per positive support edge, the resulting simple graph H satisfies

#PM(H) = Dmhaf(A),   |π−1(M)| = Dm∏e∈MAe.

Here π projects an expanded perfect matching to the original edges whose gadgets use both endpoints. The fibers can have different sizes; their exact sizes give the weighted law. Even internal vertex counts force a gadget to cover either both original endpoints or neither. Acyclicity rules out extra directed cycles inside a gadget.

The construction takes polynomial bit time. Both the number of vertices and the number of edges are O(L²); the explicit graph encoding has length O(L² log(L+2)). The scale Dm has O(mL+1) bits. No weight is expanded into that many copies. Individual gadgets are bipartite; the glued graph need not be bipartite.

Approximation with exact zero detection

The approximation input is OpenAI's pinned general-graph perfect-matching theorem, Theorem 1.1. A fully polynomial randomized approximation scheme, or FPRAS, estimates a count to relative error ε with failure probability at most δ in time polynomial in the input size, ε−1 and log δ−1.

Using that theorem, the note obtains a uniform FPRAS for ZA for rational 0 < ε, δ < 1. Its bit time on every execution is polynomial in the full input encoding length, ε−1 and log δ−1. This full input includes the rational accuracy parameters.

An exact support-matching feasibility test handles zero separately. On infeasible support the algorithm returns zero; on feasible support it returns a positive rational on every execution, even when the estimate is inaccurate. It calls the unweighted theorem with failure parameter min(δ,1/4), replaces a failed zero estimate by one, and divides by Dm. This replacement changes no successful estimate. The output is therefore zero if and only if the hafnian is zero on every execution.

A finite-bit weighted sampler

For ZA > 0 and rational 0 < η < 1, the sampler approximates

μA(M) = ∏e∈MAe/ZA

within total-variation distance η. Total variation bounds the difference in probability assigned to any event. Every output is a support perfect matching. Infeasibility is reported exactly; the order-zero case returns the empty matching.

For the expanded graph of order N = 2s ≥ 2, put C = s² and choose

α = η/(4s),   γ = η/(4C),   b = ⌈log₂(4C/η)⌉.

The wrapper makes at most C counting calls, each with relative error α and failure parameter γ, and at most C+1 exact feasibility/witness checks. Its categorical choices use at most sb additional fair bits; the counting algorithms' own randomness is additional. If T(B,a−1,log d−1) bounds every execution of the unweighted counter, its counting-time budget is

C T(B′, 4s/η, log(4C/η)),

with polynomially bounded input length B′, plus polynomial witness work and exact rational arithmetic. The resulting every-execution bit time is polynomial in the full original input length and η−1.

At each step, exact witnesses remove infeasible children. Fresh count estimates choose among the remaining completions. Cumulative probabilities are rounded to a fixed dyadic grid, without rejection. If every estimate is zero, a stored witness supplies a feasible completion. A coupling over adaptive histories accounts for estimate failures and rounding without conditioning the final output on universal success:

TV ≤ sα/(1−α) + Cγ + C2−b ≤ η/3 + η/4 + η/4 = 5η/6 < η.

The proved fiber sizes turn the uniform expanded matching law into μA, and projection cannot increase total variation.

Scope and limitations

The input is an explicit nonnegative rational matrix. Disconnected support, weights below one, large denominators and arbitrarily small positive hafnians are covered. No density, connectivity or minimum positive-weight promise is needed. The empty hafnian is one, and the diagonal has no effect.

The conclusions do not extend to signed or complex hafnians or unrestricted Gaussian boson sampling. Sampling is approximate in total variation; exact sampling, pointwise relative sampling error and polynomial dependence on log η−1 are not asserted.

The approximation and efficient sampling consequences use the cited unweighted FPRAS and polynomial matching-witness algorithm. The supplied code contains exponential reference enumeration and finite synthetic-oracle tests; it includes no practical implementation or benchmark of the upstream FPRAS. Finite checks support the construction and wrapper rather than certify that external theorem.

This follow-on theorem is not formally verified. An independent upstream Lean kernel rebuild was not reproduced. The note makes no first-publication or new complexity-classification claim; its role is an attributed consequence, explicit exposition and implementation package.

Original files and manuscript

  1. Source and verification package (ZIP, 183,748 bytes) · Zenodo original ZIP
  2. README.md (6,238 bytes) · Zenodo original README
  3. Manuscript (PDF, 75,751 bytes) · Zenodo original PDF

Open the six-page PDF · Download PDF · Zenodo record

These are unchanged copies of the current published files, in the record's order. The manuscript and declared publication date are 6 October 2026; the record reports creation on 7 October 2026 UTC and updates on 10 October 2026. The record version is 1.0.0. The README describes the package and its reproduction assumptions.

Attribution and dependencies

The Horner gadget is a transparent variant of established machinery. The rational approximation consequence follows by combining the classical equivalence with the cited general-graph theorem. The manuscript includes its broader bibliography and source-comparison limitations.

Citation and rights

Kriebel, Alec. (2026). Nonnegative binary rational hafnians: an exact reduction and approximation and sampling consequences (Version 1.0.0) [Unrefereed preprint]. Zenodo. doi:10.5281/zenodo.23205294. Download BibTeX.

Newly authored prose, proofs, explanatory documents and data are licensed CC BY 4.0; newly authored Python code is MIT-licensed, as stated in the archive's LICENSES.md and LICENSE_CODE.txt. Cited works retain their authorship and rights.

Status and collaboration

AI tools were used extensively in research, drafting, implementation and automated adversarial verification. This is an unrefereed, AI-assisted preprint; automated reviews are not conventional human peer review. The author is responsible for the claims.

Independent verification of the exact construction or quantitative sampler, substantive improvements to the exposition or implementation, and development of a journal version would be useful contributions. Collaboration and authorship would be based on actual contributions.