OctoInformBeta

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

Corollary 9.3: The degree and number of variables give a common numerical bound for exact and border representations

Smooth initial forms constrain determinant sizes.

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

Let g∈ℂ[x1,…,xd]g\in\mathbb C[x_1,\ldots,x_d] and a∈ℂda\in\mathbb C^d. The object of interest is the lowest nonzero homogeneous term of g(a+x)g(a+x), together with its projective smoothness.

For a finite variable set σ\sigma, the ring ℂ[xv:v∈σ]\mathbb C[x_v:v\in\sigma] is the ring of multivariate polynomials over ℂ\mathbb C.✦ An affine matrix pencil of size nn is a matrix LA0,A(x)=A0+∑v∈σxvAvL_{A_0,A}(x)=A_0+\sum_{v\in\sigma}x_vA_v, where A0A_0 and each AvA_v belong to Mat⁡n(ℂ)\operatorname{Mat}_n(\mathbb C) and have unrestricted entries. Its determinant is the polynomial Dn(A0,A)(x)=det⁡(A0+∑v∈σxvAv).D_n(A_0,A)(x) =\det\left(A_0+\sum_{v\in\sigma}x_vA_v\right).(1)✦

An exact determinantal representation LA0,AL_{A_0,A} of p∈ℂ[xv:v∈σ]p\in\mathbb C[x_v:v\in\sigma] is an affine pencil of positive size whose determinant (1) equals pp. For n∈ℕn\in\mathbb N, its existence is the predicate HasExactDeterminant⁡(n,p)⇔n>0 and p=Dn(A0,A)for some A0,(Av)v∈σ.\operatorname{HasExactDeterminant}(n,p) \quad\Longleftrightarrow\quad n>0\ \text{ and }\ p=D_n(A_0,A)\ \text{for some }A_0,(A_v)_{v\in\sigma}.(2)✦

A border determinantal representation (L(j))j∈ℕ(L^{(j)})_{j\in\mathbb N} of p∈ℂ[xv:v∈σ]p\in\mathbb C[x_v:v\in\sigma] of positive size nn is a sequence of affine pencils of size nn whose determinants converge to pp in every coefficient. For an exponent vector α∈ℕσ\alpha\in\mathbb N^\sigma, write [xα]p[x^\alpha]p for the coefficient of xαx^\alpha in pp. The corresponding predicate is HasBorderDeterminant⁡(n,p)⇔n>0 and there exist (A0(j),A(j))j∈ℕsuch that[xα]Dn(A0(j),A(j))→[xα]pfor every α∈ℕσ.\begin{split} \operatorname{HasBorderDeterminant}(n,p) \quad\Longleftrightarrow\quad &n>0\ \text{ and there exist } (A_0^{(j)},A^{(j)})_{j\in\mathbb N}\ \text{such that}\\ &[x^\alpha]D_n(A_0^{(j)},A^{(j)}) \longrightarrow [x^\alpha]p \quad\text{for every }\alpha\in\mathbb N^\sigma. \end{split}(3)✦

Translation and Homogeneous Terms

For finite variable sets σ\sigma and τ\tau, an affine substitution with constants b∈ℂσb\in\mathbb C^\sigma and coefficients B∈ℂσ×τB\in\mathbb C^{\sigma\times\tau} is the ℂ\mathbb C-algebra homomorphism Sb,B:ℂ[xv:v∈σ]→ℂ[yw:w∈τ]S_{b,B}:\mathbb C[x_v:v\in\sigma]\to \mathbb C[y_w:w\in\tau] determined by Sb,B(xv)=bv+∑w∈τBvwyw.S_{b,B}(x_v)=b_v+\sum_{w\in\tau}B_{vw}y_w.(4) Translation by aa is Sa,Idg=g(a+x)S_{a,I_d}g=g(a+x) in (4), where IdI_d is the identity matrix.

For j∈ℕj\in\mathbb N, the degree jj homogeneous component qj∈ℂ[xv:v∈σ]q_j\in\mathbb C[x_v:v\in\sigma] of a polynomial q∈ℂ[xv:v∈σ]q\in\mathbb C[x_v:v\in\sigma] is the sum of its monomials of total degree jj: qj=∑|α|=j[xα]qxα,|α|=∑v∈σαv.q_j=\sum_{|\alpha|=j}[x^\alpha]q\,x^\alpha, \qquad |\alpha|=\sum_{v\in\sigma}\alpha_v.(5) Write Gj=(g(a+x))jG_j=(g(a+x))_j, using (5).

A homogeneous polynomial H∈ℂ[x1,…,xd]H\in\mathbb C[x_1,\ldots,x_d] of degree at least two is projectively smooth when it and its first partial derivatives have only the zero common affine zero: {y∈ℂd:H(y)=0,∂iH(y)=0for every 1≤i≤d}={0}.\left\{y\in\mathbb C^d: H(y)=0,\quad \partial_iH(y)=0\ \text{for every }1\le i\le d\right\} =\{0\}.(6)

The Claim

Theorem 1. Let d,r≥2d,r\ge2, let g∈ℂ[x1,…,xd]g\in\mathbb C[x_1,\ldots,x_d], and let a∈ℂda\in\mathbb C^d. Suppose Gj=0G_j=0 for every j<rj<r, Gr≠0G_r\ne0, and GrG_r is projectively smooth in the sense of (6). Every n∈ℕn\in\mathbb N for which HasBorderDeterminant⁡(n,g)\operatorname{HasBorderDeterminant}(n,g) or HasExactDeterminant⁡(n,g)\operatorname{HasExactDeterminant}(n,g) holds satisfies n≥(r−1)(d−1)4exp⁡(1).n\ge \frac{(r-1)(d-1)}{4\exp(1)}.(7)✦

In the paper, the result reads: if g∈ℂ[x1,…,xd]g\in\mathbb C[x_1,\ldots,x_d], d≥2d\ge2, and a∈ℂda\in\mathbb C^d are such that the lowest nonzero homogeneous term GrG_r of g(a+x)g(a+x) has degree r≥2r\ge2 and defines a smooth hypersurface in ℙd−1\mathbb P^{d-1}, then both the border determinantal complexity bdc⁡(g)\operatorname{bdc}(g) and the determinantal complexity dc⁡(g)\operatorname{dc}(g) are at least (r−1)(d−1)/(4exp⁡(1))(r-1)(d-1)/(4\exp(1)).

What Is Checked

The bound (7) is stated over complex polynomials with the exact and border predicates (2) and (3); the fixed-size statements (8) and (9) allow any finite variable set σ\sigma.

Theorem 2 (Lowest Homogeneous Component). Let q∈ℂ[xv:v∈σ]q\in\mathbb C[x_v:v\in\sigma] and n,r∈ℕn,r\in\mathbb N. Suppose HasBorderDeterminant⁡(n,q)\operatorname{HasBorderDeterminant}(n,q) holds and qj=0q_j=0 for every j<rj<r. Then HasBorderDeterminant⁡(n,qr).\operatorname{HasBorderDeterminant}(n,q_r).(8)✦

Theorem 3 (Closure At Fixed Size). Let (Pj)j∈ℕ(P_j)_{j\in\mathbb N} be a sequence in ℂ[xv:v∈σ]\mathbb C[x_v:v\in\sigma] and let pp belong to the same ring. Suppose HasBorderDeterminant⁡(n,Pj)\operatorname{HasBorderDeterminant}(n,P_j) holds for every jj, and [xα]Pj→[xα]p[x^\alpha]P_j\to[x^\alpha]p for every α∈ℕσ\alpha\in\mathbb N^\sigma. Then HasBorderDeterminant⁡(n,p).\operatorname{HasBorderDeterminant}(n,p).(9)✦