Permanents of random matrices over finite fields

Zach Hunter, Matthew Kwan, Lisa Sauermann · 2026

Read Permanents of random matrices over finite fields by Zach Hunter, Matthew Kwan, Lisa Sauermann (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15856.txt.

Introduction

Hunter, Kwan, and Sauermann compare permanents and determinants of random matrices. The matrices hold entries from a fixed finite field. Determinant spread over the field is well understood by now. Permanent spread has stayed a mystery in contrast. Their result takes a first step toward closing that gap. The permanent lands far more evenly across field values. The determinant piles up in a less uniform way. The proof sets up later work on exact limit laws.

Catalog record

CREATORZach Hunter, Matthew Kwan, Lisa Sauermann
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50941
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.15856

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Permanents of random matrices over finite fields Thanks: Zach Hunter was supported by SNSF grant 200021-228014. Matthew Kwan was supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Lisa Sauermann was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – CRC 1720 – 539309657. Zach Hunter, Matthew Kwan, Lisa Sauermann Abstract . Fix a finite field 𝔽 q \mathbb{F}_{q} and let A ∈ 𝔽 q n × n A\in\mathbb{F}_{q}^{n\times n} be a uniformly random n × n n\times n matrix over 𝔽 q \mathbb{F}_{q} . The asymptotic distribution of the determinant det ( A ) \det(A) is well-understood, but the asymptotic distribution of the permanent per ⁡ ( A ) \operatorname{per}(A) is still something of a mystery. In this paper we make a first step in this direction, proving that per ⁡ ( A ) \operatorname{per}(A) is significantly more uniform than det ⁡ ( A ) \operatorname{det}(A) . 1. Introduction Two important matrix parameters are the determinant and permanent : for an n\times n matrix A=(a_{i,j}) , they are defined as (1.1) \det(A)=\sum_{\pi\in S_{n}}\operatorname{sign}(\pi)\prod_{i=1}^{n}a_{i,\pi(i)}\qquad\text{and}\qquad\operatorname{per}(A)=\sum_{\pi\in S_{n}}\prod_{i=1}^{n}a_{i,\pi(i)}. If we fix a finite field \mathbb{F}_{q} and let A\in\mathbb{F}_{q}^{n\times n} be a uniformly random n\times n matrix over \mathbb{F}_{q} , it is easy to compute the limiting distribution of \det(A) (this is essentially equivalent to computing the number of invertible matrices over \mathbb{F}_{q} , which goes all the way back to Galois [ 30 , p. 280] ). Fact 1.1 . For a prime power q , let \alpha_{q}=1-\prod_{i=1}^{\infty}(1-q^{-i}). Then, for a uniformly random n\times n matrix A\in\mathbb{F}_{q}^{n\times n} and any x\in\mathbb{F}_{q} , we have \lim_{n\to\infty}\Pr[\det(A)=x]=\begin{cases}\alpha_{q}&\text{if }x=0\\ (1-\alpha_{q})/(q-1)&\text{otherwise.}\end{cases} Notably, this limiting distribution is not uniform over \mathbb{F}_{q} : the determinant is significantly more likely to take the value zero than any other value. For example, when q=3 we have \alpha_{q}\approx 0.44 , which is significantly larger than 1/q=1/3 . Roughly speaking, this is because the event \{\det(A)=0\} describes the rows of A being linearly dependent: if we reveal A row-by-row, and at some step we discover that a row lies in the span of the previous rows, this tells us that \det(A)=0 regardless of what happens in future rows. On the other hand, if after revealing the second-last row we still haven’t discovered a linear dependence relation between the rows, then it is easy to see that the conditional distribution of \det(A) is uniform over \mathbb{F}_{q} . Unlike the determinant, the permanent does not seem to have any linear-algebraic meaning (unless our field has characteristic 2, in which case the determinant and permanent are equal). It is tempting to conjecture that, if \mathbb{F}_{q} does not have characteristic 2, then the permanent of a uniformly random matrix over \mathbb{F}_{q} is asymptotically uniform, as follows. Conjecture 1.2 . Fix a finite field \mathbb{F}_{q} of odd characteristic. Then, for a uniformly random n\times n matrix A\in\mathbb{F}_{q}^{n\times n} , and any x\in\mathbb{F}_{q} , we have \lim_{n\to\infty}\Pr[\operatorname{per}(A)=x]=\frac{1}{q}. This conjecture seems to have been floating around the community for a while, but we are not completely sure about its origins. Permanents of random matrices over finite fields have received quite some interest in the computer science community (see e.g. [ 8 , 20 , 9 , 10 , 3 ] ), due to a phenomenon called random self-reducibility , but surprisingly we were not able to find any study of the asymptotic distribution of \operatorname{per}(A) in this literature. The earliest reference we could find was in the open problem session of a 2017 workshop on combinatorics at the Mathematisches Forschungsinstitut Oberwolfach [ 16 ] , in which Swastik Kopparty asked for the limiting distribution of the permanent over \mathbb{F}_{3} . The \mathbb{F}_{3} case of Section 1 also appears explicitly in a recent paper by Scheinerman [ 29 ] (backed by quite convincing computational evidence), and the general case of Section 1 appeared in a very recent paper of Ghasemi, Gross and Kopparty [ 11 ] . See also a related conjecture by Esperet [ 7 ] (motivated by questions in graph theory). Note that, by symmetry (through rescaling any row), \operatorname{per}(A) is equally likely to take any nonzero value. Thus, in order to understand the distribution of \operatorname{per}(A) it suffices to understand \Pr[\operatorname{per}(A)=0] . More specifically, the assertion of Section 1 is equivalent to \lim_{n\to\infty}\Pr[\operatorname{per}(A)=0]=1/q . Although we are not able to prove Section 1 , we are at least able to prove that the permanent is (asymptotically) more uniform than the determinant, as follows (recall that \lim_{n\to\infty}\Pr[\det(A)=0]=\alpha_{q}>1/q and observe that \alpha_{q}-1/q has order of magnitude 1/q^{2} ). Theorem 1.3 . Fix a finite field \mathbb{F}_{q} of odd characteristic. For a uniformly random n\times n matrix A\in\mathbb{F}_{q}^{n\times n} , we have (1.2) \Pr[\operatorname{per}(A)=0]\geq\frac{1}{q} for all n , and we have the strict inequality (1.3) \limsup_{n\to\infty}\Pr[\operatorname{per}(A)=0]<\alpha_{q}. Moreover, for all n\geq 3 we have (1.4) \Pr[\operatorname{per}(A)=0]\leq\frac{1}{q}+\frac{C}{q^{3}} for some absolute constant C . For n=2 one has \Pr[\operatorname{per}(A)=0]=1/q+\Theta(1/q^{2}) , so the assumption n\geq 3 in Equation 1.4 cannot be omitted. We remark that a theorem in a similar spirit was previously proved by Budrevich and Guterman [ 2 ] (see also the simpler proof in [ 1 ] , and the earlier work [ 5 ] ): restated in probabilistic language, their main result was that for any finite field \mathbb{F}_{q} of odd characteristic, and any n\geq 3 , the zero-permanent probability is strictly less than the zero-determinant probability. However, the gap they established between these two probabilities tends to zero very rapidly as n\to\infty . Budrevich and Guterman were motivated by Pólya’s permanent problem (see e.g. [ 27 , 25 , 33 ] ), which asks to what extent it is possible to re-express the permanent of a matrix in terms of a determinant. The gap established in [ 2 ] shows that there is no bijective “converter” f:\mathbb{F}_{q}^{n\times n}\to\mathbb{F}_{q}^{n\times n} such that \operatorname{per}(A)=\det(f(A)) for all A\in\mathbb{F}_{q}^{n\times n} . Note that Theorem 1.3 implies the stronger result that there is no such converter that works for almost all A\in\mathbb{F}_{q}^{n\times n} . 1.1. General distributions It turns out that Section 1 is universal , in the sense that the distribution of the determinant of a random matrix A\in\mathbb{F}_{q}^{n\times n} does not depend very strongly on the distribution of the entries of A . For example, it is known that for any non-constant distribution \mu over a finite field \mathbb{F}_{p} of prime order, if A\in\mathbb{F}_{p}^{n\times n} is a random matrix with independent \mu -distributed entries, then \lim_{n\to\infty}\Pr[\det(A)=0]=\alpha_{p} . This seems to have been first proved in 1990 by Charlap, Rees and Robbins [ 4 ] , though similar theorems with more restrictive assumptions were proved much earlier by Kozlov [ 18 ] and Kovalenko and Levitskaja [ 17 ] , and a very general theorem over arbitrary finite fields (necessarily with a more technical statement) was later proved by Kahn and Komlós [ 15 ] . See also [ 24 , 23 , 36 , 37 , 26 , 6 , 21 ] for some more recent work on universality of various algebraic properties for random matrices over finite fields. We can prove a theorem in the spirit of Theorem 1.3 for arbitrary (non-constant) distributions over finite fields of prime order, as follows. Theorem 1.4 . Fix a finite field \mathbb{F}_{p} of prime order

Read the complete text