A cubic permanent–determinant lower bound

The explanation

Take a small grid of numbers: 1 and 2 on top, 3 and 4 below. Its determinant multiplies along the two diagonals and subtracts: 1×4 − 2×3 = −2. Its permanent does the same but adds: 1×4 + 2×3 = 10. Bigger grids follow one recipe. Pick one entry from each row and each column, and multiply them. The permanent adds up every such product. The determinant gives exactly half of them a minus sign.

A small permanent can wear a determinant's disguise. Flip the sign of the 2, and the determinant becomes 1×4 − (−2)×3 = 10. The trick works for any four numbers, not just these. For bigger grids, the disguise needs a bigger determinant. Each of its entries may be a constant plus a weighted sum of the original entries. Such entries are called affine-linear. The smallest determinant size that works is the permanent's determinantal complexity.

Why care about one formula? In 1979, Leslie Valiant showed that many polynomial families built from small formulas are pieces of small permanents. So the permanent stands in for a whole class of polynomial sums. The central open question is whether its disguise must grow faster than any fixed power of the grid size.

The known gap is wide. In 2012, Bruno Grenet built a disguise of size 2^m − 1 for an m-by-m permanent. That is 7 for a 3-by-3 grid and 1,023 for a 10-by-10 grid. Lower bounds grew slowly. Around 1989 and 1990, Roy Meshulam and Jin-yi Cai showed the size must be about 1.41 times m. In 2004, Thierry Mignon and Nicolas Ressayre raised this to m²/2. For a 10-by-10 grid, the true answer lay somewhere from 50 to 1,023.

There is also a looser kind of disguise. A sequence of same-size determinants may approach the permanent, coefficient by coefficient, without ever reaching it. The smallest size that allows this is the border determinantal complexity. It is never larger than the exact one. So a lower bound on it is the stronger statement. Joseph Landsberg, Laurent Manivel and Ressayre proved the same m²/2 bound for this looser model.

This paper proves that the looser size grows like the cube of mSource 1. For every m of at least 1,408, the size is at least m³/(5,529,600·e)Source 2. Here e is about 2.718. The same bound then holds for exact disguisesSource 3. The power of m rises from two to three. The constant is tiny, and the paper says it is not optimizedSource 4. At m = 1,408 the new bound gives about 186, while m²/2 gives 991,232. The cube overtakes the square only beyond about 7.5 million rows. So the gain is in how fast the bound grows, not in any size you could write down today.

Why were the old methods stuck at squares? Mignon and Ressayre compared Hessians, the grids of second derivatives at one point. At a suitable point, a determinant of size n has Hessian rank at most 2n. The permanent has a point where its Hessian rank is m², the most possible. Rank cannot pass the m² entries, so this comparison stops at about m²/2.

The paper uses a different measure. Each partial derivative measures how fast the polynomial changes along one variable. The zero set is smooth when no point on it makes every partial derivative zero at once. The all-zero point is the one allowed exception. Roughly, it has no creases or pinch points. Take a polynomial with a smooth zero set, of degree r in d variables. The paper shows it needs size at least (r − 1)(d − 1)/(4e)Source 5. That bound survives the looser, approximate disguises tooSource 6. The permanent's own zero set is far from smooth, which gives only a linear boundSource 7. So the paper digs a smooth polynomial out of a larger permanent. Its degree grows like k and its number of variables like k², from a permanent of size about 11kSource 8. Degree times variables gives the cubeSource 9.

The result still leaves the main question open. A cubic bound is a fixed power of m. Whether the permanent needs a disguise beyond every fixed power remains unknown. The paper also draws cubic bounds for algebraic branching programs, networks that compute a polynomial by summing products along pathsSource 10.

How sure is this? A computer proof checker called Lean has checked formal versions of two statements. One is the cubic bound, exact and approximate, for m of at least 1,408 with the stated constant. The other is the general bound for smooth polynomials. The branching-program consequences are outside that check. No specialist review has been published yet.

What it doesn't show. This does not show that the permanent needs determinants larger than every fixed power of m, which remains open.