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).