A general fully polynomial randomized approximation scheme for the Perron root of a permanental compound of a nonnegative rational matrix.
Statement
For every nonnegative rational matrix , every , and rational accuracy and failure parameters in , the algorithm returns a rational with
The running time is polynomial in the binary input length, , and . A zero root is detected exactly in polynomial time. The theorem covers all compound degrees, reducible inputs, zero diagonal entries and periodic compounds. It does not form the exponentially large compound matrix.
Mathematical argument
The central estimate, valid for every integer , is
The lower bound follows by applying Gurvits's coefficient-capacity theorem to the stable symbol of an iterated transfer operator. The sum of traces is the permanent of a cyclic layered matrix. Log-concavity across compound degrees allows one degree to be selected by a rational scaling parameter. A finite grid and the Jerrum–Sinclair–Vigoda permanent FPRAS then give the claimed accuracy and running time.
The proof includes stability preservation, the trace estimate, the counting identity, zero detection, an explicit rational grid, all error constants, and bit-complexity bounds.
Scope and review
This answers the general randomized approximation formulation of Minc Problem 18. The historical wording asks for an algorithm without specifying a complexity threshold. The theorem does not assert exact polynomial-time computation of an algebraic eigenvalue or of the permanent. It does not solve Minc Problem 17 on characteristic polynomials.
The proof is unrefereed. Two independent internal reviews found no remaining gap after a correction to the positive-support argument. The source audit found no previous full-domain FPRAS under permanental-compound, zeon, transfer-matrix or stable-operator terminology; that search does not certify priority. Known ingredients are credited explicitly.
- Independent mathematical review
- Independent inequality and complexity review
- Coordination and review discussion
Reproducible checks
Run from the repository root with ordinary Python 3.10 or later:
python3 results/perron-root-permanental-compounds/verify.pyThe standard-library verifier checks 126 exact cyclic trace identities, 81 Newton inequalities and 2,048 exact support/degree cases. The checks test the finite reductions. The general theorem depends on the written proof and its cited theorems. The Jerrum–Sinclair–Vigoda sampler is not implemented here; no practical runtime claim is made.
No Lean formalization is included.
Files
| File | Contents |
|---|---|
| proof.md | Complete mathematical proof and explicit algorithm |
| source-audit.md | Prior-art search, overlaps and access limits |
| verify.py | Exact finite checks for the reductions |
| permanent_helpers.py | Exact small-matrix permanent and compound routines |
| review-sign-matrices.md | Independent proof review and additional prior-art checks |
| review-inequalities.md | Independent review of the main estimate, edge cases and complexity |