betaFeedback

WorksMathematics

A cubic lower bound for border determinantal complexity of the permanent

Abstract

We prove that the complex border determinantal complexity of the m×mm\times m permanent is Ω(m3)\Omega(m^3), allowing arbitrary affine-linear determinant representations and coefficientwise limits. It also gives cubic lower bounds for exact determinantal complexity and for the numbers of vertices and edges in affine-linear algebraic branching programs, including coefficientwise limits with a fixed vertex or edge budget.

Introduction

For a matrix X=(xij)X=(x_{ij}) of independent variables, the permanent is

perm⁡m(X)=∑σ∈Sm∏i=1mxi,σ(i).\operatorname{perm}_m(X)=\sum_{\sigma\in S_m}\prod_{i=1}^{m}x_{i,\sigma(i)}.

The permanent–determinant problem asks how large a determinant of affine-linear forms is needed to express perm⁡m\operatorname{perm}_m. Valiant connected determinant projections to arithmetic formulas: his construction represents a polynomial computed by a formula with ss addition or multiplication operations as a determinant of order s+2s+2 [24], Theorem 1. His algebraic completeness theorem shows that, in characteristic different from two, polynomial families defined by summing polynomial-size formulas over Boolean strings of polynomial length are projections of polynomial-size permanents [24], Theorem 2. Valiant’s projections substitute individual variables or field constants. The exact model below allows every matrix entry to be an arbitrary affine-linear form.

For f∈C[x1,…,xN]f\in\mathbb{C}[x_1,\ldots,x_N], its determinantal complexity dc⁡(f)\operatorname{dc}(f) is the least positive integer nn for which

f=det⁡(A0+∑j=1NxjAj),A0,…,AN∈Mat⁡n(C).f=\det\left(A_0+\sum_{j=1}^{N}x_jA_j\right),\qquad A_0,\ldots,A_N\in\operatorname{Mat}_n(\mathbb{C}).

Its border determinantal complexity dc⁡‾(f)\overline{\operatorname{dc}}(f) is the least positive integer nn such that ff lies in the coefficientwise closure of

{det⁡(A0+∑j=1NxjAj):A0,…,AN∈Mat⁡n(C)}.(1)\left\{\det\left(A_0+\sum_{j=1}^{N}x_jA_j\right):A_0,\ldots,A_N\in\operatorname{Mat}_n(\mathbb{C})\right\}. \tag*{(1)}

The closure is taken in the finite-dimensional space of polynomials of degree at most nn; a polynomial of larger degree cannot belong to it. We allow ff to be constant or zero. Coefficientwise closure agrees with Zariski closure here, as explained in Section 2. The size nn stays fixed along an approximating sequence, while the complex coefficients of its matrix entries are unrestricted.

Theorem 1.1. There exist absolute constants c>0c>0 and m0m_0 such that, for every integer m≥m0m\ge m_0,

dc⁡‾(perm⁡m)≥cm3.\overline{\operatorname{dc}}(\operatorname{perm}_m)\ge cm^3.

One may take c=1/(5 529 600e)c=1/(5\,529\,600e) and m0=1408m_0=1408.

The constants are not optimized. Proposition 2.2 identifies this coefficientwise model with the projective determinant-orbit closure formulation, including equal permanent and determinant orders. The same numerical lower bound holds for exact determinantal complexity. There is also a consequence for algebraic branching programs. An affine-linear algebraic branching program is a finite directed acyclic graph with a source and a sink and an affine-linear form on each edge; it computes the sum of products of edge labels along all source-to-sink paths. Over C\mathbb{C}, computing perm⁡m\operatorname{perm}_m requires Ω(m3)\Omega(m^3) vertices and Ω(m3)\Omega(m^3) edges. The same bounds hold for coefficientwise limits when the relevant vertex or edge budget remains fixed along the approximation, even if the graph varies. Section 9 gives the precise statements and determinant reductions.

Earlier bounds and geometric methods

The early matrix-order lower bounds were linear in the permanent order mm. For the variable-or-constant projection model, von zur Gathen published a bound due to Babai and Seress with leading term 2m\sqrt{2}m and a loss of 6m6\sqrt{m} [26], Theorem 4.4]. For arbitrary affine representations over C\mathbb{C}, Meshulam’s final theorem [15], pp. 270–271] and Cai’s dimension argument [4], Theorem 1.5 and Section 2.2] give the scale 2m−O(1)\sqrt{2}m-O(1). Their arguments compare the dimension of the affine matrix image with the minimum rank that an exact permanent representation must have.

Mignon and Ressayre raised the exact lower bound to dc⁡(perm⁡m)≥m2/2\operatorname{dc}(\operatorname{perm}_m) \ge m^2/2 in characteristic zero [16]. Their proof compares Hessians at a zero: affine pullback cannot increase Hessian rank, the Hessian of an order-nn determinant has rank at most 2n2n at a noninvertible matrix, and, for m≥2m \ge2, the permanent has a zero where its Hessian has full rank m2m^2. Cai, Chen and Li extended the quadratic scale to positive characteristic different from two by constructing sparse zeros that avoid the large factorial factors in the earlier Hessian calculation [5], Theorem 2.3].

On the upper side, Grenet’s construction realizes perm⁡m\operatorname{perm}_m as a determinant of order 2m−12^m-1, using a branching program indexed by the subsets of {1,…,m}\{1,\ldots,m\} [10], unnumbered Theorem, p. 3]. Its determinant entries are individual variables and constants, so it is also an upper bound in the unrestricted exact model.

Mulmuley and Sohoni’s geometric complexity theory program studies permanent–determinant separation through orbit closures of determinants and padded permanents, seeking equations or representation-theoretic obstructions to containment [17, 18]. Landsberg, Manivel and Ressayre proved the unrestricted complex border bound dc⁡‾(perm⁡m)≥m2/2\overline{\operatorname{dc}}(\operatorname{perm}_m) \ge m^2/2 by studying hypersurfaces with degenerate duals and the effect of padding [13], Theorem 1.1.1]. Theorem 1.1 raises the lower-bound exponent from two to three in that same model. It remains a fixed polynomial bound. Whether the permanent has superpolynomial determinantal complexity, or superpolynomial border determinantal complexity, remains open.

Landsberg and Ressayre later proved exponential optima for exact representations with symmetry requirements. Each specified projective symmetry of the input must lift to a projective symmetry of the determinant that fixes the pencil’s constant matrix, preserves the image of its linear part, and induces the given input action there. Over C\mathbb{C}, for m≥3m \ge3, requiring this for left multiplication by invertible diagonal and permutation matrices gives minimum order 2m−12^m-1. Lifting the full projective symmetry group of the permanent gives minimum order (2mm)−1\binom{2m}{m}-1 in the same range [14], Theorems 2.1 and 2.8; Propositions 2.9 and 2.10]. These hypotheses specify exact representation classes; the border model of Theorem 1.1 allows arbitrary affine determinant approximations of fixed order.

Singularities also give geometric lower bounds for exact representations. For a homogeneous polynomial of degree greater than two whose affine singular locus has codimension greater than four, Alper, Bogart and Velasco prove dc⁡(f)≥codim⁡Sing⁡(f)+1\operatorname{dc}(f) \ge\operatorname{codim}\operatorname{Sing}(f)+1 [2], Theorem 1.2]. For the permanent, matrices with two zero columns show that this codimension is at most 2m2m, so this obstruction alone has only a linear scale [2], Remark 1.5]. Our construction instead obtains a coefficient polynomial from a permanent and finds a linear subspace on which its zero hypersurface is smooth. Its degree is linear and the subspace dimension is quadratic in an auxiliary matrix size.

For a smooth complex form of degree r≥2r \ge2 in d≥2d \ge2 variables, the classical top polar degree is r(r−1)d−2r(r-1)^{d-2} [19], Corollary 3.7]. The left and right kernel equations for the determinant matrix and the Schur-complement reduction used below also appear in Sheshadri’s June 2026 preprint [21], Theorem 3 and Section 3.1], as part of its proposed conormal approach to border bounds for diagonal power sums. Kumar and Volk’s September 2026 preprint uses such kernel equations and a multihomogeneous count to obtain a quadratic exact lower bound for ∑i=1nxin\sum_{i=1}^{n}x_i^n [12], Theorem 1.1 and Section 3]. Theorem 2.3 proves the version needed here, including persistence of finitely many simple polar intersections in one sufficiently close determinant under an arbitrary coefficientwise approximation. Its lower bound is proportional to the product (r−1)(d−1)(r-1)(d-1).

The coefficient construction and the proof

To use this product at cubic scale, we seek an affine restriction of a permanent of size proportional to kk that has degree proportional to kk in quadratically many variables and has a smooth projective zero set. Let k≥1k \ge1 and 0≤q≤⌊k/2⌋0 \le q \le\lfloor k/2 \rfloor be integers. With indeterminates θ1,…,θk\theta_1,\ldots,\theta_k, put D=diag⁡(θ1,…,θk)D=\operatorname{diag}(\theta_1,\ldots,\theta_k) and define

GD(X)=[sqtq]per⁡k(X+sI+tD)∈Z[θ1,…,θk][Xij].G_D(X)=[s^q t^q]\operatorname{per}_k(X+sI+tD)\in\mathbb{Z}[\theta_1,\ldots,\theta_k][X_{ij}].

This polynomial is homogeneous of degree r=k−2qr=k-2q in the k2k^2 entries of XX. We use the same notation after specializing the parameters in a field. For the main construction we assume k≥128k\ge128 and take q=⌊(k−1)/3⌋q=\lfloor(k-1)/3\rfloor; then rr is linear in kk and T=(q+22)T=\binom{q+2}{2} is quadratic in kk.

The integral formula has two uses. Over C\mathbb{C}, two count gates and a cancellation gadget realize GDG_D, up to a fixed nonzero scalar, as an affine restriction of a permanent of size 11k−2q11k-2q (Proposition 3.1). This holds for every complex choice of the parameters. The scalar vanishes in characteristic two, so the geometric argument specializes the integral coefficient formula itself. We will use the complex projection at the complex parameter choice that geometry eventually supplies.

Let K=F2K=\mathbb{F}_2, choose pairwise distinct θˉ1,…,θˉk∈K\bar{\theta}_1,\ldots,\bar{\theta}_k\in K, and write Dˉ=diag⁡(θˉ1,…,θˉk)\bar{D}=\operatorname{diag}(\bar{\theta}_1,\ldots,\bar{\theta}_k). Since permanent and determinant agree over KK, every matrix XX defines a plane curve

CX=V(det⁡(sI+tDˉ+uX))⊂PK2.C_X=V(\det(sI+t\bar{D}+uX))\subset\mathbb{P}^2_K.

Its fiber on u=0u=0 consists of the distinct points [−θˉi:1:0][-\bar{\theta}_i:1:0]. This fixed fiber makes the curve reduced and its projection to [t:u][t:u] finite and generically separable, and it controls the adjugate of sI+tDˉ+uXsI+t\bar{D}+uX on the curve. The full adjugate defines a finite subscheme Z⊂CXZ\subset C_X. If all entrywise derivatives of GDˉG_{\bar{D}} vanish at XX, the coefficient [sqtqur−1][s^q t^q u^{r-1}] of every adjugate entry vanishes. We prove that these entries span all degree-(k−1)(k-1) forms vanishing on ZZ, so the same coefficient vanishes on every such form. For a degree-qq monomial sitjuℓs^i t^j u^\ell, multiplication by sq−itq−jur−1−ℓs^{q-i}t^{q-j}u^{r-1-\ell} lets this functional recover its coefficient in any degree-qq form. These exponents are nonnegative because r−1≥qr-1\ge q. Thus restriction of degree-qq forms to ZZ is injective, giving the length bound in Proposition 4.3:

K[s,t,u]q↪H0(Z,OZ(q)),length⁡Z≥dim⁡KK[s,t,u]q=T.K[s,t,u]_q\hookrightarrow H^0(Z,\mathcal{O}_Z(q)),\qquad\operatorname{length} Z\ge\dim_K K[s,t,u]_q=T.

The length of ZZ is bounded above by the normalization defect δ(CX)\delta(C_X), the length of the quotient between the normalization’s structure sheaf and the curve’s structure sheaf. The comparison follows the evaluation-ideal argument of Fantechi, Göttsche and van Straten over C\mathbb{C} [8, Proposition C.2 and Corollary C.3]; Section 5 proves the needed conductor inclusion and colength identity for our generically separable pencils in arbitrary characteristic. Thus every critical matrix lies over a curve with δ(CX)≥T\delta(C_X)\ge T.

Applying the arbitrary-characteristic Severi dimension theorem of Christ, He and Tyomkin [6, Lemma 2.6, Proposition 2.7, and Remark 2.8] to the integral components bounds the locus of curves with this defect. Their result builds on Tyomkin’s dimension bound for toric pairs [23, Theorem 1.2(1)]. The sum RX=(1,…,1)adj⁡(sI+tDˉ+uX)R_X=(1,\ldots,1)\operatorname{adj}(sI+t\bar{D}+uX) of the adjugate rows controls the matrices over one fixed curve: its zero subscheme has length k(k−1)/2k(k-1)/2, and the common boundary frame makes that subscheme determine the matrix uniquely. A Hilbert-scheme estimate and an algebraic incidence then bound the dimension of each matrix fiber. Combining the curve and matrix bounds gives

dim⁡{X:∇G‾D(X)=0}≤k2+k−T,codim⁡{X:∇G‾D(X)=0}≥T−k.\dim\{X:\nabla\overline{G}_{D}(X)=0\}\le k^{2}+k-T,\qquad\operatorname{codim}\{X:\nabla\overline{G}_{D}(X)=0\}\ge T-k.

The projective zero scheme of the raw partial derivatives forms a proper family over the integral parameter space. Specialization transfers the dimension bound to a nonempty open set of complex parameters. Over C\mathbb{C}, Euler’s identity identifies these gradient zeros with the hypersurface’s singular scheme, and a general linear section avoids that scheme and meets the smooth locus transversely. Proposition 7.3 then supplies, for k≥128k\ge128 and the stated choice of qq, a nonzero form GG of degree rr in d=⌊k2/100⌋d=\lfloor k^{2}/100\rfloor variables whose projective zero set is smooth. For each m≥11k−2qm\ge11k-2q, it also supplies a fixed affine map Φm\Phi_m satisfying G=per⁡m∘ΦmG=\operatorname{per}_m\circ\Phi_m.

Figure 1 shows how the two uses of the coefficient formula meet and how the polar bound converts their output into the cubic estimate.

Diagram showing the two uses of the integral coefficient formula, permanent projection, plane-curve geometry, a smooth affine restriction over $\mathbb{C}$, and the resulting polar bound

Figure 1. The two uses of the integral coefficient formula meet over C\mathbb{C}. The graph projection applies to every complex parameter choice; the characteristic-two branch supplies a suitable complex choice through the proper parameter family. The displayed scale bounds use q=⌊(k−1)/3⌋q=\lfloor(k-1)/3\rfloor, k≥128k\ge128, and m≥11k−2qm\ge11k-2q.

Sections 3–7 establish this construction. Section 8 then proves the smooth-form bound stated in Section 2, using selected simple polar intersections and the left and right kernels of one nearby determinant. Section 9 combines the two results and gives the exact, branching-program, and smooth-initial-form consequences.

Border models and smooth homogeneous forms

We first identify the two border models precisely. All closures in this section are over C\mathbb{C}. In a finite-dimensional polynomial space, coefficientwise convergence means ordinary convergence of the coefficients of every monomial. The image of a polynomial map is constructible [22], and a complex constructible set has the same Euclidean and Zariski closures. For the latter fact, decompose the set into finitely many locally closed subsets: each contains a Zariski open dense subset of its closure, which is also Euclidean dense. These facts apply both to the polynomial map taking an affine matrix to its determinant and to the action map defining a linear-group orbit. Thus coefficientwise sequences can be used for either closure below.

Lemma 2.1 (Affine substitution). Let ff be a complex polynomial, let AA be an affine map into its variable space, and let a≠0a \ne0 be a complex scalar. Then

dc⁡‾(af∘A)≤dc⁡‾(f).\overline{\operatorname{dc}}(af \circ A) \le\overline{\operatorname{dc}}(f).

References

  1. [1]M. R. Adams, J. Harnad, and J. Hurtubise. Darboux coordinates and Liouville-Arnold integration in loop algebras. Communications in Mathematical Physics, 155(2):385–413, 1993. Preprint: arXiv:hep-th/9210089v1; numbered locators in the text refer to this version.DOI
  2. [2]Jarod Alper, Tristram Bogart, and Mauricio Velasco. A lower bound for the determinantal complexity of a hypersurface. Foundations of Computational Mathematics, 17(3):829–836, 2017.
  3. [3]Vladimir Baranovsky. On punctual Quot schemes for algebraic surfaces. arXiv:alg-geom/9703038v3, 1998. Version of 18 July 1998; first submitted 28 March 1997.arxiv.org/abs/alg-geom/9703038
  4. [4]Jin-yi Cai. A note on the determinant and permanent problem. Information and Computation, 84(1):119–127, 1990.DOI
  5. [5]Jin-Yi Cai, Xi Chen, and Dong Li. Quadratic lower bound for permanent vs. determinant in any characteristic. Computational Complexity, 19(1):37–56, 2010.DOI
  6. [6]Karl Christ, Xiang He, and Ilya Tyomkin. On the Severi problem in arbitrary characteristic. Publications Mathématiques de l’IHÉS, 137:1–45, 2023.DOI
  7. [7]Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms, 10(4):21:1–21:32, 2014. Preprint: arXiv:1206.1775v1; numbered locators in the text refer to this version.DOI
  8. [8]Barbara Fantechi, Lothar Göttsche, and Duco van Straten. Euler number of the compactified Jacobian and multiplicity of rational curves. Journal of Algebraic Geometry, 8(1):115–133, 1999.
  9. [9]Maciej Gałązka. Vector bundles give equations of cactus varieties. Linear Algebra and its Applications, 521:254–262, 2017. Preprint: arXiv:1605.08005v1; numbered locators in the text refer to this version.
  10. [10]Bruno Grenet. An upper bound for the permanent versus determinant problem. Author preprint, 2012. 25 May 2012.
  11. [11]Steven L. Kleiman. The transversality of a general translate. Compositio Mathematica, 28(3):287–297, 1974.
  12. [12]Mrinal Kumar and Ben Lee Volk. A quadratic lower bound on determinantal complexity. arXiv:2609.34462v1, 2026. 28 September 2026.arxiv.org/abs/2609.34462
  13. [13]Joseph M. Landsberg, Laurent Manivel, and Nicolas Ressayre. Hypersurfaces with degenerate duals and the Geometric Complexity Theory Program. Commentarii Mathematici Helvetici, 88(2):469–484, 2013.arxiv.org/abs/1004.4802
  14. [14]Joseph M. Landsberg and Nicolas Ressayre. Permanent v. determinant: An exponential lower bound assuming symmetry and a potential path towards Valiant’s conjecture. Differential Geometry and its Applications, 55:146–166, 2017.DOI
  15. [15]Roy Meshulam. On two extremal matrix problems. Linear Algebra and its Applications, 114/115:261–271, 1989.DOI
  16. [16]Thierry Mignon and Nicolas Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices, 2004(79):4241–4253, 2004.
  17. [17]Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory I: An approach to the P vs. NP and related problems. SIAM Journal on Computing, 31(2):496–526, 2001.DOI
  18. [18]Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory II: Towards explicit obstructions for embeddings among class varieties. SIAM Journal on Computing, 38(3):1175–1206, 2008.arxiv.org/abs/cs/0612134
  19. [19]Ragni Piene. Polar classes of singular varieties. Annales scientifiques de l’École Normale Supérieure, 11(2):247–276, 1978.DOI
  20. [20]Alexander Premet. Nilpotent commuting varieties of reductive Lie algebras. Inventiones Mathematicae, 154(3):653–683, 2003. Author manuscript, Corollary 4.1.
  21. [21]Karthik Sheshadri. A near-quadratic lower bound on the border determinantal complexity of Σᵢ xᵢⁿ via conormal specialization. arXiv:2606.13628v1, 2026. 11 June 2026.arxiv.org/abs/2606.13628
  22. [22]The Stacks Project Authors. The Stacks project. https://stacks.math.columbia.edu, 2026. Tags 032L, 00PD, 0D4I, and 054K; accessed 24 September 2026.
  23. [24]L. G. Valiant. Completeness classes in algebra. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC ’79, pages 249–261. Association for Computing Machinery, 1979.DOI
  24. [25]L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189–201, 1979.DOI
  25. [26]Joachim von zur Gathen. Permanent and determinant. Linear Algebra and its Applications, 96:87–100, 1987.
  26. [27]Charles W. Wampler. Isotropic coordinates, circularity, and Bezout numbers: Planar kinematics from a new perspective. In ASME 1996 Design Engineering Technical Conferences, 1996. Paper 96-DETC/MECH-1210.DOI

Paper details

vlnc:W_jy7u9k7r
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 25

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents