Metraipolis › archive › dc_d5ffd46ac452
The determinantal complexity of the 4*4 permanent is 15 — arXiv:2611.06658
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06658
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:32:04.582Z
- SHA-256 of the archived text
ea8768ddb6327275f82a3d20d93867324897a489e4fe03148815ff21ca377068- Stable URL of this page
https://metraipolis.com/documento/dc_d5ffd46ac452
How to cite
The determinantal complexity of the 4*4 permanent is 15 — arXiv:2611.06658 — arXiv (en), https://arxiv.org/abs/2611.06658 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d5ffd46ac452 (Metraipolis archive dc_d5ffd46ac452, sha256 ea8768ddb6327275f82a3d20d93867324897a489e4fe03148815ff21ca377068)
BibTeX
@misc{dcd5ffd46ac452,
title = {The determinantal complexity of the 4*4 permanent is 15 — arXiv:2611.06658},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06658},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d5ffd46ac452; sha256 ea8768ddb6327275f82a3d20d93867324897a489e4fe03148815ff21ca377068},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06658. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The best known lower bound on the determinantal complexity of the 4x4 permanent is 10. In this short note, I prove that this value is exactly 15: the 4x4 permanent is the determinant of a 15x15 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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2611.06658 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-05T18:21:34.065Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).