OctoInformBeta

OpenAI preprint, September 2026 · §9. The permanent lower bound and its consequences

Corollary 9.1: The bound applies to complex affine representations of the size-mm permanent when m≥1408m\geq 1408

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 mm and the determinant size nn are separate parameters.

For a finite variable set σ\sigma, the polynomial ring ℂ[𝒙σ]\mathbb C[\mathbf x_\sigma] is the ring of multivariate polynomials over ℂ\mathbb C with one indeterminate xvx_v for each v∈σv\in\sigma.✦ Let Im={0,…,m−1}I_m=\{0,\ldots,m-1\}. The matrix variable indices of size mm form Im×ImI_m\times I_m, with both row and column indices numbered from zero.✦ The permanent perm⁡m∈ℂ[𝒙Im×Im]\operatorname{perm}_m\in\mathbb C[\mathbf x_{I_m\times I_m}] is the polynomial in (1), where SmS_m is the permutation group of ImI_m: perm⁡m(𝒙)=∑τ∈Sm∏i∈Imxi,τ(i).\operatorname{perm}_m(\mathbf x) =\sum_{\tau\in S_m}\prod_{i\in I_m}x_{i,\tau(i)}.(1)✦

For arbitrary matrices A0,Av∈Mat⁡n(ℂ)A_0,A_v\in\operatorname{Mat}_n(\mathbb C), indexed by v∈σv\in\sigma, the determinant polynomial DA0,AD_{A_0,A} of their affine pencil is defined by (2): DA0,A(𝒙)=det⁡(A0+∑v∈σxvAv)∈ℂ[𝒙σ].D_{A_0,A}(\mathbf x) =\det\!\left(A_0+\sum_{v\in\sigma}x_v A_v\right) \in\mathbb C[\mathbf x_\sigma].(2)✦ An exact determinantal representation of size nn of a polynomial p∈ℂ[𝒙σ]p\in\mathbb C[\mathbf x_\sigma] is a choice of matrices A0,Av∈Mat⁡n(ℂ)A_0,A_v\in\operatorname{Mat}_n(\mathbb C), indexed by v∈σv\in\sigma, with n>0n>0, satisfying (3); its existence is denoted by HasExactDeterminant⁡(n,p)\operatorname{HasExactDeterminant}(n,p): DA0,A=p.D_{A_0,A}=p.(3)

The Claim

Theorem 1. Let m,nm,n be natural numbers with m≥1408m\geq 1408, and suppose that HasExactDeterminant⁡(n,perm⁡m)\operatorname{HasExactDeterminant}(n,\operatorname{perm}_m) holds. Then the representation size satisfies (4): m35529600exp⁡(1)≤n.\frac{m^3}{5529600\exp(1)}\leq n.(4)✦

In the paper, the result reads: for every integer m≥1408m\geq 1408, the determinantal complexity satisfies dc⁡(perm⁡m)≥m3/(5529600exp⁡(1))\operatorname{dc}(\operatorname{perm}_m)\geq m^3/(5529600\exp(1)).

What Is Checked

The statement is over the permanent in ℂ[𝒙Im×Im]\mathbb C[\mathbf x_{I_m\times I_m}] and its exact representations by affine matrices of positive size with complex coefficients.