OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: Border and exact affine determinants for permanent size m≥1408m\geq 1408

Cubic bounds for permanent determinant 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 permanent of an m×mm\times m matrix is compared with determinants of n×nn\times n matrices whose entries are affine linear forms in the permanent’s variables.

For a finite index set Σ\Sigma, let ℂ[𝒙Σ]\mathbb C[\mathbf x_\Sigma] denote the polynomial ring with one variable xvx_v for each v∈Σv\in\Sigma.✦ For m∈ℕm\in\mathbb N, put Im={0,…,m−1}I_m=\{0,\ldots,m-1\} and let SmS_m be its permutation group, with I0=⌀I_0=\varnothing. The permanent perm⁡m∈ℂ[𝒙Im×Im]\operatorname{perm}_m\in\mathbb C[\mathbf x_{I_m\times I_m}] is 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)✦ The matrix variable indices for size mm are the ordered pairs (i,j)∈Im×Im(i,j)\in I_m\times I_m, where ii is the row index and jj is the column index.✦

An affine matrix pencil A0+∑v∈ΣxvAvA_0+\sum_{v\in\Sigma}x_vA_v of size nn in the variables indexed by Σ\Sigma is a matrix whose constant and linear coefficient matrices A0A_0 and AvA_v are arbitrary elements of Mat⁡n(ℂ)\operatorname{Mat}_n(\mathbb C). Writing A=(Av)v∈ΣA=(A_v)_{v\in\Sigma} for the family of linear coefficient matrices, its determinant is the polynomial Dn(A0,A;𝒙)=det⁡(A0+∑v∈ΣxvAv)∈ℂ[𝒙Σ].D_n(A_0,A;\mathbf x) =\det\left(A_0+\sum_{v\in\Sigma}x_vA_v\right) \in\mathbb C[\mathbf x_\Sigma].(2)✦

An exact determinantal representation (A0,(Av)v∈Σ)(A_0,(A_v)_{v\in\Sigma}) of size nn of a polynomial p∈ℂ[𝒙Σ]p\in\mathbb C[\mathbf x_\Sigma] is a family of matrices in Mat⁡n(ℂ)\operatorname{Mat}_n(\mathbb C), with n>0n>0, satisfying (3); its existence is denoted by HasExactDeterminant⁡(n,p)\operatorname{HasExactDeterminant}(n,p).✦ Dn(A0,A;𝒙)=p(𝒙).D_n(A_0,A;\mathbf x)=p(\mathbf x).(3)

For a multi-index d∈ℕΣd\in\mathbb N^\Sigma, write [𝒙d]p[\mathbf x^d]p for the coefficient of ∏v∈Σxvdv\prod_{v\in\Sigma}x_v^{d_v} in pp. A border determinantal representation (A0,j,(Av,j)v∈Σ)j∈ℕ(A_{0,j},(A_{v,j})_{v\in\Sigma})_{j\in\mathbb N} of size nn of a polynomial p∈ℂ[𝒙Σ]p\in\mathbb C[\mathbf x_\Sigma] is a sequence of families of matrices in Mat⁡n(ℂ)\operatorname{Mat}_n(\mathbb C), with n>0n>0, satisfying (4) for every multi-index dd, where Aj=(Av,j)v∈ΣA_j=(A_{v,j})_{v\in\Sigma}; its existence is denoted by HasBorderDeterminant⁡(n,p)\operatorname{HasBorderDeterminant}(n,p).✦ limj→∞[𝒙d]Dn(A0,j,Aj;𝒙)=[𝒙d]p.\lim_{j\to\infty}[\mathbf x^d]D_n(A_{0,j},A_j;\mathbf x) =[\mathbf x^d]p.(4)

The Claim

Theorem 1. Let m,n∈ℕm,n\in\mathbb N with m≥1408m\geq 1408. If HasBorderDeterminant⁡(n,perm⁡m)\operatorname{HasBorderDeterminant}(n,\operatorname{perm}_m) holds, then m35529600exp⁡(1)≤n.\frac{m^3}{5529600\exp(1)}\leq n.(5)✦ If HasExactDeterminant⁡(n,perm⁡m)\operatorname{HasExactDeterminant}(n,\operatorname{perm}_m) holds, then n≥m35529600exp⁡(1).n\geq\frac{m^3}{5529600\exp(1)}.(6)✦

In the paper, the result reads: there exist absolute constants c>0c>0 and m0m_0 such that bdc⁡(perm⁡m)≥cm3\operatorname{bdc}(\operatorname{perm}_m)\geq cm^3 for every integer m≥m0m\geq m_0, where bdc\operatorname{bdc} denotes border determinantal complexity, and one may take c=1/(5529600exp⁡(1))c=1/(5529600\exp(1)) and m0=1408m_0=1408.

What Is Checked

The bounds (5) and (6) are stated over the complex permanent (1), with positive determinant size, exact equality (3) or sequential convergence of every coefficient (4), and unrestricted affine matrix entries.