Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries
Abstract
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.
Related
- Non-canonical Oscillator Representations of Orthogonal Lie Algebras and Pfaffian Varieties
- Subexponential Approximation of the Permanent in Deterministic Polynomial Time
- Counting Integral Matrices with Given Cubic Characteristic Polynomial
- Appendix: The representations of the Lie superalgebra p(3) in characteristic 3
- Counting matrices with given characteristic polynomial
BibTeX
@misc{sheshadri2026cubic,
title = {{Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries}},
author = {Karthik Sheshadri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40484},
eprint = {2610.40484},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40484},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries
AU - Karthik Sheshadri
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40484
UR - https://arxiv.org/abs/2610.40484
AB - 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.
ER -