Math-2110 · mathematics · Combinatorics

Math-2110

What is the probability that a random nXn matrix over Z_(p) has zero permanent as n goes to infinity

Status Partially solved · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedPartially solvedOpen

Statement

Definitions and mathematical statement

Fix an odd prime $p$. Let $A_n=(a_{ij})_{1\le i,j\le n}$ be a random matrix over $\mathbb F_p$ whose $n^2$ entries are independent and uniformly distributed in the field, including zero. Its permanent is the field element \[ \operatorname{per}(A_n) =\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}. \] Unlike the determinant, this sum has no permutation signs. Determine the limiting probability of a zero permanent. The proposed answer is \[ \lim_{n\to\infty} \Pr(\operatorname{per}(A_n)=0)=\frac1p. \] The prime is fixed throughout the limit; uniform estimates with $p$ growing are a stronger, separate question.

This model is not a random $0$--$1$ or random sign matrix reduced modulo $p$, and the matrix is not conditioned to be invertible. The conjecture asks for equidistribution at zero, rather than asserting an exact equality for each finite $n$. Characteristic two is excluded because permanent and determinant then coincide, leading to a different limiting singularity probability. Recent work on permanents over finite fields supplies partial distributional information; such information should not be identified with the displayed asymptotic formula unless its hypotheses and limiting conclusion establish this specific law.

Short English statement

For a fixed odd prime, does a uniformly random square matrix over that field have zero permanent with limiting probability1/p?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.