The determinantal complexity of the $4\times 4$ permanent is 15

The best known lower bound on the determinantal complexity of the $4\times4$ permanent is 10. In this short note, I prove that this value is exactly 15: the $4\times4$ permanent is the determinant of a $15\times15$ matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size $2^n-1$. Hence that construction is optimal at $n=4$ (and $n=3$). This now constitutes the first knwon exact value of the determinantal complexity of the permanent at $n=4$. Only the value at $n=3$ was exactly known, prior to this note. The general quadratic bound only gives 8 for $n=4$. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of sie 14 foces the space into any of nine corordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public. The proof is short and easy to follow. This note is hand-written by the human author.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-04
DOI
https://doi.org/10.5281/zenodo.23936888
Primary Topic
Complexity and Algorithms in Graphs
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

The determinantal complexity of the $4\times 4$ permanent is 15

Karthik Sheshadri
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
article

The determinantal complexity of the $4\times 4$ permanent is 15

Karthik Sheshadri
article en

Abstract

The best known lower bound on the determinantal complexity of the $4\times4$ permanent is 10. In this short note, I prove that this value is exactly 15: the $4\times4$ permanent is the determinant of a $15\times15$ matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size $2^n-1$. Hence that construction is optimal at $n=4$ (and $n=3$). This now constitutes the first knwon exact value of the determinantal complexity of the permanent at $n=4$. Only the value at $n=3$ was exactly known, prior to this note. The general quadratic bound only gives 8 for $n=4$. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of sie 14 foces the space into any of nine corordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public. The proof is short and easy to follow. This note is hand-written by the human author.

Zenodo (CERN European Organization for Nuclear Research)
Openalex Percentile: Top 16%
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon