Pal’s permanent conjecture: proof for block uniform matrices
Andrea Ottolini, Shannon Starr · 2026
Read Pal’s permanent conjecture: proof for block uniform matrices by Andrea Ottolini, Shannon Starr (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-2605-25274.txt.
Introduction
Andrea Ottolini and Shannon Starr prove a case of a conjecture by Soumik Pal about how the permanent of a special matrix family grows with size. The matrices come from a smooth symmetric function on the unit square, sampled at grid points. Its growth rate was already known from large-deviation theory, while its algebraic factor comes from a formula for doubly stochastic matrices. The pair settles the conjecture when the underlying function stays constant on blocks. They use a known combinatorial splitting of permutations into blocks.
Catalog record
| CREATOR | Andrea Ottolini, Shannon Starr |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35723 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25274
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pal’s permanent conjecture: proof for block uniform matrices Andrea Ottolini, Shannon Starr Abstract Consider a symmetric function 𝒞 ( x , y ) \mathcal{C}(x,y) on [ 0 , 1 ] × [ 0 , 1 ] [0,1]\times[0,1] which is twice continuously differentiable up to the boundary, and which satisfies 𝒞 ( x , y ) = 𝒞 ( 1 − x , 1 − y ) \mathcal{C}(x,y)=\mathcal{C}(1-x,1-y) . Let A ( n ) = ( a i , j ( n ) : i , j ∈ [ n ] ) A^{(n)}=\big(a^{(n)}_{i,j}\,:\,i,j\in[n]\big) be the matrix with entries a i , j ( n ) = exp ( − 𝒞 ( i / n , j / n ) ) a^{(n)}_{i,j}\,=\,\exp(-\mathcal{C}(i/n,j/n)) . Soumik Pal conjectured the asymptotics perm ( A^(n) ) /n!∼exp ( n Λ[ C ] ) / D [ C ] as n → ∞ n\to\infty for known functionals that arise naturally in the context of entropy regularized optimal transport. The functional Λ [ 𝒞 ] \Lambda[\mathcal{C}] is the known large deviation rate function, already proved rigorously by Sumit Mukherjee. It is ∫ 0 1 ∫ 0 1 ( α ( x ) + β ( y ) ) 𝑑 x 𝑑 y \int_{0}^{1}\int_{0}^{1}(\alpha(x)+\beta(y))\,dx\,dy where α ( x ) + β ( y ) \alpha(x)+\beta(y) is chosen such that ρ ( x , y ) := exp ( − 𝒞 ( x , y ) − α ( x ) − β ( y ) ) \rho(x,y):=\exp(-\mathcal{C}(x,y)-\alpha(x)-\beta(y)) has uniform marginals. The algebraic term 𝒟 [ c ] \mathcal{D}[c] is given by Peter McCullagh’s formula for doubly stochastic matrices: det F ( I + J − T ∗ T ) \operatorname{det}_{F}(I+J-T^{*}T) , the Fredholm determinant, where I I is the identity on L 2 ( [ 0 , 1 ] ) L^{2}([0,1]) , J f ( x ) ≡ ∫ 0 1 f ( z ) 𝑑 z Jf(x)\equiv\int_{0}^{1}f(z)\,dz (for all x x ) and T f ( x ) = ∫ 0 1 ρ ( x , y ) f ( y ) 𝑑 y Tf(x)=\int_{0}^{1}\rho(x,y)f(y)\,dy . We prove the conjecture for functions 𝒞 \mathcal{C} that are constant on blocks, exploiting a well-known Ross Pinsky’s combinatorial decomposition of permutations in blocks. 1 Introduction Suppose that A=\big(a_{i,j}\,:\,i,j\in[n]\big) is a matrix where [n]=\{1,\dots,n\} . The permanent is \operatorname{perm}(A)\,=\,\sum_{\pi\in S_{n}}\prod_{i=1}^{n}a_{i,\pi_{i}}\,, which differs from the determinant in the signs of some of the summands \det(A)\,=\,\sum_{\pi\in S_{n}}(-1)^{\sigma(\pi)}\prod_{i=1}^{n}a_{i,\pi_{i}}\,, where \sigma(\pi)=0 for even permutations and \sigma(\pi)=1 for odd permutations. Symmetry properties of the determinant make it easy to compute and approximate. But for the permanent, typical calculations can be quite difficult. For example, Valiant proved that the computational complexity of calculating the permanent of an arbitrary n\times n zero-one matrix, a matrix such that every a_{i,j} is either 0 or 1 , is NP-complete [ 16 ] In the same vein, a more recent conjecture of Aaronson and Archipov is known as the “permanent of Gaussians conjecture.” Suppose that A is a Gaussian random matrix, whose entries are IID \mathcal{N}(0,1) plus i times \mathcal{N}(0,1) complex random variables (so the Ginibre ensemble). Then the problem of determining for each \epsilon>0 and \delta>0 an approximation of \operatorname{perm}(A) that is within \epsilon relative error, with probability at least 1-\delta , is \# P-hard. The reason this conjecture is important is that it provides a key step for Aaronson and Archipov’s quantum supremacy theoretical result based on Boson sampling [ 1 ] . 1.1 Permanents as generalizations of assignments More recently, permanents have been considered as a generalization of the assignment problem from optimal transport theory. One set of applications of optimal transport theory derives from economics. See, for instance [ 3 ] and references, therein. In 2012, Léonard wrote a seminal article [ 7 ] . Suppose that every a_{i,j} is positive. The optimal assignment given A would be the permutation \pi\in S_{n} which maximizes \prod_{i=1}^{n}a_{i,\pi_{i}} or, up to taking logarithms, the cost function \sum_{i=1}^{n}\ln(a_{i,\pi_{i}}) . A regularized version of this problem is to calculate the permanent and randomly sample \pi according to the distribution \prod_{i=1}^{n}a_{i,\pi_{i}}/\operatorname{perm}(A) . Therefore, interest arose in the context of this problem, especially given certain conditions on the matrix entries a_{i,\pi_{i}} beyond just positivity. In [ 9 ] , Mukherjee considered a cost function \mathcal{C}:[0,1]\times[0,1]\to\mathbb{R} satisfying that \mathcal{C} is jointly continuous on its domain and \forall x\in[0,1]\,,\ \text{ we have }\ \int_{0}^{1}\mathcal{C}(x,y)\,dy\,=\,0\ \text{ and }\ \forall y\in[0,1]\,,\ \text{ we have }\ \int_{0}^{1}\mathcal{C}(x,y)\,dx\,=\,0\,. Then, for each n\in\mathbb{N} , defining the matrix A^{(n)}=\big(a^{(n)}_{i,j}\,:\,i,j\in[n]\big) given by a^{(n)}_{i,j}\,=\,\exp\left(-\mathcal{C}(i/n,j/n)\right)\,, one has \lim_{n\to\infty}\frac{1}{n}\,\ln\left(\frac{\operatorname{perm}(A^{(n)})}{n!}\right)\,=\,\Lambda[\mathcal{C}]\,, where \Lambda[\mathcal{C}]\,=\,\int_{0}^{1}\int_{0}^{1}(\alpha(x)+\beta(y))\,dx\,dy\,, for the functions \alpha,\beta:[0,1]\to\mathbb{R} such that \alpha(x)+\beta(y) is uniquely determined by the conditions that \forall x\in[0,1]\,,\ \text{ we have }\ \int_{0}^{1}\exp\left(-\mathcal{C}(x,y)-\alpha(x)-\beta(y)\right)\,dy\,=\,1\, and \forall y\in[0,1]\,,\ \text{ we have }\ \int_{0}^{1}\exp\left(-\mathcal{C}(x,y)-\alpha(x)-\beta(y)\right)\,dx\,=\,1\,. In [ 11 ] , Soumik Pal noted that the determination of the functions \alpha and \beta is known as the Schrodinger bridge problem. The choice of \alpha and \beta is unique up to \alpha\leftarrow\alpha+c , \beta\leftarrow\beta-c , because these two shifts cancel in \alpha(x)+\beta(y) . Pal also posed an interesting conjecture [ 11 ] . Conjecture 1.1 If \mathcal{C}:[0,1]\times[0,1]\to\mathbb{R} is twice continuously differentiable up to the boundary, symmetric in the two variables, zero on the diagonal and also satisfies the symmetry \mathcal{C}(1-x,1-y)=\mathcal{C}(x,y) then \frac{1}{n!}\,\operatorname{perm}\Big(\big(\exp\left(-\mathcal{C}(i/n,j/n)\right)\,:\,i,j\in[n]\big)\Big)\,\sim\,\frac{\exp\left(n\Lambda[\mathcal{C}]\right)}{\sqrt{\mathcal{D}[\mathcal{C}]}}\,, where \mathcal{D}[\mathcal{C}] is the Fredholm determinant \mathcal{D}[\mathcal{C}]\,=\,\det\nolimits_{F}(I+J-T^{*}T)\,, for I the identity operator, J the rank-1 operator on L^{2}([0,1]) given by Jf(x)\equiv\int_{0}^{1}f(y)\,dy (the constant), and T the trace-class operator Tf(x)\,=\,\int_{0}^{1}\rho(x,y)f(y)\,dy\,, for \rho(x,y)=e^{-\mathcal{C}(x,y)-\alpha(x)-\beta(y)} . Pal gave two separate arguments for this. The first argument relies on a previous result by Harchaoui, Liu and himself [ 4 ] . In that paper there was an extra source of randomness, but they were able to obtain precise asymptotics. When Pal considered removing the extra source of randomness, heuristically, it led to his conjecture. One might imagine trying to prove his conjecture that way, using a Tauberian theorem. (See for instance [ 2 ] for an interesting paper, on a different topic, using the Wiener-Ikehara Tauberian theorem among other arguments.) The second argument, which is more direct, is combinatorial. In [ 8 ] , Peter McCullagh had already conjectured something similar to the conjecture above, specifically for doubly stochastic matrices. But then McCullagh did not need to make as many assumptions on \mathcal{C}(x,y) such as regularity, given this. McCullagh gives a similar combinatorial argument as in Pal, but without using the spectral decomposition directly. In Section 4.3 of his article, McCullagh proves that the quantity of interest is a series h_{n}^{(0)}(t)\,=\,\sum_{k=1}^{n}\mathfrak{x}_{n,k}t^{2k}\,, where, for each k\in\{1,\dots,n\} , one has \mathfrak{x}_{n,k}\,=\,\frac{1}{2k}\,\operatorname{Tr}\left[\left(\frac{\left(\mathcal{E}^{(n)}\right)^{*}\mathcal{E}^{(n)}}{n^{\downarrow 2}}\right)^{k}\right]+O(1/n)\,, for \mathcal{E}^{(n)}=n(A^{(n)}-J^{(n)}) . He assumes \mathcal{E}^{(n)} is of moderate deviation, which is a precise version of the assumption that it is order-1. He points out that the leading order terms give the Taylor series for the log of the determinant. So he argues that h_{n}^{(0)}(1)\,=\,\sum_{k=1}^{\infty}\mathfrak{x}_{n,k}\,=\,-\frac{1}{2}\,\ln\left(\det\left(I_{n}-\frac{\left(\mathcal{E}^{(n)}\right)^{*}\mathcal{E}^{(n)}}{n^{\downarrow 2}}\right)\right)+O(n^{-1})\,. But it does seem further analysis is necessary to explicate the remainder term O(n^{-1}) . There is a recent article by Raghavendra Tripathi about Pal’s conjecture [ 15 ] . He cites McCullagh’s paper in a proposition. Our result is