Perron root of permanental compounds

What Lean checks

Written FPRAS proof for every nonnegative rational matrix and every compound degree, with deterministic zero detection. Exact finite checks supplement the argument. This is the randomized approximation formulation of Minc Problem 18; exact polynomial-time eigenvalue computation and the characteristic-polynomial problem are outside its scope.

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 A∈ℚ≥0n×nA\in\mathbb Q_{\ge0}^{n\times n}, every 0≤k≤n0\le k\le n, and rational accuracy and failure parameters in (0,1)(0,1), the algorithm returns a rational RR with

Pr[(1−ε)ρ(Pk(A))≤R≤(1+ε)ρ(Pk(A))]≥1−δ.\Pr\!\left[ (1-\varepsilon)\rho(P_k(A)) \le R\le (1+\varepsilon)\rho(P_k(A)) \right]\ge1-\delta.

The running time is polynomial in the binary input length, 1/ε1/\varepsilon, and log(1/δ)\log(1/\delta). 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 t≥1t\ge1, is

n!nnmax0≤j≤nρ(Pj(A))t≤∑j=0ntr(Pj(A)t)≤2nmax0≤j≤nρ(Pj(A))t.\frac{n!}{n^n}\max_{0\le j\le n}\rho(P_j(A))^t \le \sum_{j=0}^n\mathop{\mathrm{tr}}(P_j(A)^t) \le 2^n\max_{0\le j\le n}\rho(P_j(A))^t.

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.

Reproducible checks

Run from the repository root with ordinary Python 3.10 or later:

python3 results/perron-root-permanental-compounds/verify.py

The 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