Metraipolis › archive › dc_64bb9bc5b601

Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries — arXiv:2610.40484

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.40484
License (as archived)
CC0-1.0
Archived
2026-11-01T02:48:00.833Z
SHA-256 of the archived text
20851a402d21856c0bd9bf887ffcd463b52c1665dd21f99bf44561e3fbc2a5d5
Stable URL of this page
https://metraipolis.com/documento/dc_64bb9bc5b601

How to cite

Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries — arXiv:2610.40484 — arXiv (en), https://arxiv.org/abs/2610.40484 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_64bb9bc5b601 (Metraipolis archive dc_64bb9bc5b601, sha256 20851a402d21856c0bd9bf887ffcd463b52c1665dd21f99bf44561e3fbc2a5d5)
BibTeX
@misc{dc64bb9bc5b601,
  title = {Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries — arXiv:2610.40484},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40484},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_64bb9bc5b601; sha256 20851a402d21856c0bd9bf887ffcd463b52c1665dd21f99bf44561e3fbc2a5d5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40484. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The determinantal complexity of a polynomial is the order of the smallest matrix whose entries are polynomials of degree at most one and whose determinant equals the polynomial. A lower bound for the permanent in this measure is the algebraic form of the question whether the permanent is harder to compute than the determinant. Over the complex numbers, the best known lower bound grows cubically in the size of the permanent. It holds even when the permanent only has to be a limit of such determinants. I prove that the cubic lower bound holds over every algebraically closed field of odd characteristic $p$, with a constant that depends on $p$. Hence the cubic bound does not depend on characteristic zero. I also prove the bound for Pfaffians, which are square roots of determinants of skew symmetric matrices. Lower bounds for Pfaffians imply the same bounds for determinants. Further, I prove the bound, divided by $a$, for matrices whose entries are polynomials of degree at most $a$. All three results come from one lower bound for smooth hypersurfaces. I prove it in every characteristic by counting intersection points together with their multiplicities.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Commutative Algebra (math.AC).
Pagina del lavoro: https://arxiv.org/abs/2610.40484 — 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-01T02:18:28.503Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).