Pal's permanent conjecture: proof for block uniform matrices

This paper proves Soumik Pal's conjecture regarding the asymptotic behavior of the permanent of block-uniform matrices, confirming that the normalized permanent converges to an expression involving a large deviation rate functional and a Fredholm determinant derived from Peter McCullagh's formula.

The Gist

The Big Picture: Counting Impossible Ways to Sit at a Table

Imagine you have a massive dinner party with $N$ guests and $N$ seats. You want to know: How many different ways can you seat everyone so that everyone is happy?

In mathematics, this is called calculating the Permanent of a matrix.

• The Matrix: Think of this as a giant "happiness chart." Each number in the chart tells you how happy Guest $i$ would be sitting in Seat $j$.
• The Permanent: This is the sum of the "happiness scores" for every possible seating arrangement.

The problem is that for a large party, the number of seating arrangements is astronomical (it's $N!$, or $N$ factorial). Calculating this sum is famously difficult—so difficult that computers can't do it efficiently for large groups. It's like trying to count every single grain of sand on a beach by picking them up one by one.

The Mystery: What Happens When the Party Gets Huge?

The authors are investigating what happens when the party size ($N$) becomes infinitely large.

A mathematician named Soumik Pal made a bold guess (a "conjecture") about the answer. He suggested that even though the number of ways to seat people is huge, the answer follows a very specific, predictable pattern. He claimed the answer is made of two parts:

1. The "Main Engine": A massive exponential number (like a rocket ship blasting off). This part depends on the overall "cost" or "energy" of the seating arrangement.
2. The "Fine-Tuning": A smaller correction factor (like a speed bump or a steering adjustment). This part depends on the subtle fluctuations and randomness in the system.

Pal's formula for this "Fine-Tuning" involves a complex mathematical object called a Fredholm Determinant. It's a bit like a "complexity meter" that measures how much the guests' preferences wiggle and fluctuate around the average.

The Challenge: The Formula Was Unproven

Pal's guess was based on strong intuition and partial arguments, but no one had actually proven it was true for all cases. The math involved is incredibly slippery, like trying to catch smoke with your bare hands.

The Authors' Solution: Building a Lego City

Andrea Ottolini and Shannon Starr decided to prove Pal's conjecture, but they took a clever shortcut. Instead of trying to solve the problem for a smooth, continuous world (where every seat and guest is unique and fluid), they simplified the world into blocks.

The Analogy: The Lego City
Imagine the dinner party isn't a chaotic mix of individuals, but a city built out of Lego bricks.

• The guests are divided into $m$ distinct neighborhoods (blocks).
• Everyone in Neighborhood A likes sitting in Neighborhood B's seats exactly the same way.
• The "happiness chart" is no longer a smooth curve; it's a grid of solid, uniform blocks.

By forcing the problem into these rigid "blocks," the authors turned a slippery, continuous math problem into a discrete, combinatorial puzzle. It's like turning a flowing river into a series of connected buckets. This makes the math much easier to handle.

The Secret Weapon: Ross Pinsky's "Combinatorial Decomposition"

To solve the puzzle of counting the ways to arrange these blocks, the authors used a tool discovered by a mathematician named Ross Pinsky.

The Analogy: The Sorting Hat
Pinsky's method is like a magical sorting hat that breaks a giant, messy permutation (a seating chart) into smaller, manageable pieces.

1. It counts how many people from Neighborhood A sit in Neighborhood A, how many from A sit in B, etc.
2. It realizes that once you decide how many people move between blocks, the problem splits into smaller, independent problems.
3. It uses a famous formula (Stirling's approximation) to estimate the number of ways to arrange people within those smaller blocks.

The Result: The Conjecture is True (For Blocks)

The authors proved that for these "block-uniform" matrices:

1. Pal's Main Engine works exactly as he predicted.
2. Pal's Fine-Tuning (the Fredholm Determinant) is also exactly correct.

They showed that the "complexity meter" (the determinant) perfectly captures the "Gaussian fluctuations" (the random wiggles) of the system.

A Special Note on the "Zero" Case:
The paper also explores what happens if a block is completely empty (a guest has zero chance of sitting in a specific seat). They found that if a block is empty, the "complexity meter" breaks (the determinant becomes zero). This is like a bridge collapsing because a key support beam is missing. This confirms that the formula only works when every connection has a non-zero chance of happening.

Summary in a Nutshell

• The Problem: Counting the number of ways to arrange a massive group of people is too hard to calculate directly.
• The Guess: A previous mathematician guessed a formula for the answer that includes a "main term" and a "correction term."
• The Proof: The authors proved this guess is correct, but only for a simplified version of the problem where people are grouped into rigid "blocks" (like Lego bricks).
• The Method: They used a clever counting trick (Pinsky's lemma) to break the giant problem into small, solvable pieces, showing that the "correction term" is indeed a measure of the system's natural fluctuations.

They didn't solve the problem for every possible matrix, but they proved the formula works for a very important class of "blocky" matrices, giving strong evidence that Pal's conjecture is likely true in the general case.

Technical Summary

Technical Summary: Proof of Pal's Permanent Conjecture for Block Uniform Matrices

Problem Statement
The paper addresses a conjecture proposed by Soumik Pal regarding the asymptotic behavior of the permanent of matrices derived from a symmetric, twice continuously differentiable function $C(x, y)$ on $[0, 1] \times [0, 1]$. Specifically, for a matrix $A(n)$ with entries $a_{i,j}^{(n)} = \exp(-C(i/n, j/n))$, Pal conjectured that as $n \to \infty$:
$$\frac{\text{perm}(A(n))}{n!} \sim \frac{\exp(n\Lambda[C])}{\sqrt{D[C]}}$$
Here, $\Lambda[C]$ is the large deviation rate function associated with the Schrödinger bridge problem (the entropy-regularized optimal transport cost), and $D[C]$ is a Fredholm determinant involving the identity operator $I$, a rank-1 operator $J$, and a trace-class operator $T$ derived from the optimal coupling density $\rho(x, y)$.

While the leading order term $\exp(n\Lambda[C])$ was rigorously established by Sumit Mukherjee, the algebraic prefactor $D[C]^{-1/2}$ remained a conjecture. Previous heuristic arguments by Pal and combinatorial approaches by Peter McCullagh suggested this form, but a rigorous proof for general smooth functions was lacking.

Methodology
The authors, Andrea Ottolini and Shannon Starr, prove the conjecture for a specific, albeit non-smooth, class of functions: block uniform matrices. In this setting, the function $C$ is piecewise constant on an $m \times m$ grid of blocks, meaning the matrix $A(n)$ consists of $m^2$ constant blocks, each of size roughly $(n/m) \times (n/m)$.

The methodology relies on three primary components:

1. Ross Pinsky's Combinatorial Decomposition: The authors utilize a lemma by Pinsky which counts the number of permutations $\pi$ that map specific subsets of indices to specific subsets of indices with fixed cardinalities. This allows the permanent to be expressed as a sum over "block count" matrices $Q$, where $Q_{r,s}$ represents the number of times the permutation maps the $r$-th row-block to the $s$-th column-block.
2. Stirling's Approximation and Large Deviations: The sum over permutations is converted into a sum over integer matrices $Q$. Using Stirling's formula, the authors approximate the factorial terms to derive a leading order exponential term and a Gaussian fluctuation term.
3. Gaussian Integration and Spectral Analysis: The sum is approximated by a Gaussian integral over the space of matrices with zero row and column sums. The authors rigorously evaluate the determinant of the quadratic form governing these fluctuations. They relate this determinant to the spectrum of the operator $T^*T$ using properties of the adjugate matrix and the Matrix Determinant Lemma, effectively bridging the discrete combinatorial sum to the continuous Fredholm determinant.

Key Contributions and Results
The paper establishes Theorem 2.1, which proves Pal's conjecture for block uniform matrices. Specifically, for a block matrix defined by a base matrix $B$ and scaling vectors $v, w$ satisfying specific doubly stochastic conditions, the asymptotic formula holds:
$$\frac{\text{perm}(A^{(m,n)})}{(mn)!} \sim \frac{m^{-mn} (\prod v_r)^{-n} (\prod w_s)^{-n}}{\sqrt{\det(I^{(m)} + J^{(m)} - (T^{(m)})^* T^{(m)})}}$$
where $T^{(m)}$ is the normalized block matrix.

The authors provide two detailed examples to illustrate the result:

• Uniform Case: When the base matrix is uniform, the formula correctly recovers the known asymptotics for the all-ones matrix.
• Two-Block Case ($m=2$): The authors explicitly calculate the sum for a $2 \times 2$ block structure with a parameter $\delta$. They demonstrate that the Gaussian fluctuations around the optimal block counts yield a prefactor of $(1-\delta^2)^{-1/2}$, which matches the Fredholm determinant calculation $\sqrt{\det(I + J - T^*T)}$.

A critical technical insight is the handling of the spectral gap. The authors note that if the block matrix $B$ contains zero entries (e.g., $\delta=1$ in the example), the spectral gap collapses, the Fredholm determinant becomes zero, and the asymptotic formula fails. This aligns with the requirement in the original conjecture that the kernel be strictly positive (ensuring the existence of a spectral gap via the Perron-Frobenius or Krein-Rutman theorems).

Significance and Claims
The paper claims to provide the first rigorous proof of Pal's conjecture for a non-trivial class of functions, albeit restricted to piecewise constant (block) functions. The authors explicitly state that their function $C$ is not continuous, let alone twice continuously differentiable, and thus they do not prove the conjecture for the general smooth case proposed by Pal.

However, the significance lies in the combinatorial mechanism. By exploiting Pinsky's decomposition, the authors bypass the need for the spectral decomposition arguments used in previous heuristic proofs or the Tauberian theorem approaches. They demonstrate that the "1-loop correction" (the algebraic prefactor arising from Gaussian fluctuations) in the discrete combinatorial setting exactly matches the Fredholm determinant predicted by the continuous theory.

The authors position their work as an independent verification of the conjecture's structure, distinct from recent related work by Raghavendra Tripathi. They suggest that while the smooth case remains open, the block uniform case provides a concrete combinatorial foundation for the relationship between the permanent's asymptotics and the Schrödinger bridge problem's spectral properties.