Asymptotic Uniformity of Permanents of Random Matrices over Finite Fields of Odd Characteristic

Abstract

Let $q$ be an odd prime power, and let $A_n=(a_{ij})\in {\mathbb{F}}_q^{n\times n}$ be a random matrix whose entries are independent and uniformly distributed on ${\mathbb{F}}_q$. The permanent of $A_n$ is defined by $\mathrm{per}(A_n)={\sum }_{\sigma \in S_n}{\prod }_{i=1}^n{a}_{i,\sigma (i)}$, where $S_n$ denotes the symmetric group on $[n]$. Ghasemi, Gross, and Kopparty conjectured the zero-mass asymptotic $\mathrm{Pr}[\mathrm{per}(A_n)=0]=1/q+o(1)$ for every fixed odd prime power $q$, and Hunter, Kwan, and Sauermann subsequently stated its equivalent full-distribution formulation: for every fixed $q$ and every $x\in {\mathbb{F}}_q$, \[ \lim_{n\to\infty}\Pr[\operatorname{per}(A_n)=x]=\frac1q. \] In this paper, we prove this conjecture. More precisely, we prove that there is an absolute constant $C>0$ such that \[\frac12\sum_{x\in\mathbb F_q}\left|\Pr[\operatorname{per}(A_n)=x]-\frac1q\right|\le C\frac{\log n}{n}\] for every odd prime power $q$ and every $n\ge 7$. The estimate is uniform in $q$, so the conclusion remains valid for every sequence $q=q(n)$ of odd prime powers.

13 pages. Comments welcome. This version adds a Declaration on the Use of AI; the mathematical content is unchanged