OpenAI preprint, September 2026 · §9. The permanent lower bound and its consequences
Corollary9.1:The bound applies to complex affine representations of the
size-
permanent when
A cubic size bound for exact permanent representations.
Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its
declaration both in Lean and in words.
The Setting
The question is how large an affine matrix must be if its determinant equals the permanent. The permanent size and the determinant size are separate parameters.
For a finite variable set , the polynomial ring is the ring of multivariate polynomials over with one indeterminate for each .✦ Let .The matrix variable indices of size form , with both row and column indices numbered from zero.✦The permanent is the polynomial in (1), where is the permutation group of :(1)✦
For arbitrary matrices , indexed by , the determinant polynomial of their affine pencil is defined by (2): (2)✦ An exact determinantal representation of size of a polynomial is a choice of matrices , indexed by , with , satisfying (3); its existence is denoted by :(3)
The Claim
Theorem 1. Let be natural numbers with , and suppose that holds. Then the representation size satisfies (4): (4)✦
In the paper, the result reads: for every integer , the determinantal complexity satisfies .
What Is Checked
The statement is over the permanent in and its exact representations by affine matrices of positive size with complex coefficients.