betaFeedback

WorksComputer Science

The determinantal complexity of the 4*4 permanent is 15

Abstract

The best known lower bound on the determinantal complexity of the 4x4 permanent is 10. In this short note, I prove that this value is exactly 15: the 4x4 permanent is the determinant of a 15x15 matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size 2^n-1. Hence that construction is optimal at n=4 (and n=3). This now constitutes the first knwon exact value of the determinantal complexity of the permanent at n=4. Only the value at n=3 was exactly known, prior to this note. The general quadratic bound only gives 8 for n=4. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of sie 14 foces the space into any of nine corordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public.

Introduction

The determinantal complexity dc(f)dc(f) of a polynomial ff is the smallest mm for which f=det⁡Af = \det A, where AA is an m×mm \times m matrix whose entries are affine linear forms in the variables of ff. Valiant showed that every polynomial computed by a small formula has small complexity, and that the permanent is complete for the class VNP [7]. His conjecture that dc(per⁡n)dc(\operatorname{per}_{n}) grows faster than any polynomial in nn is the determinant versus permanent form of the VP versus VNP question.

I consider the exact computation of small values of the permanent as revealing of its behavior and of the pattern of growth of the permanent for larger, and asymptotically larger, values of nn. It is my hope that a close study of the techniques that yield these values may one day cast a long enough shadow that at the least, a rough shape of the mathematics behind it may be deduced.

The known bounds are far apart. Mignon and Ressayre proved dc⁡(per⁡n)≥n2/2\operatorname{dc}(\operatorname{per}_n) \ge n^2/2 over C\mathbb{C} by comparing Hessians [5], and Cai, Chen and Li extended this to every characteristic other than 2 [2]. For n=3n = 3, Alper, Bogart and Velasco proved that dc⁡(per⁡3)≥7\operatorname{dc}(\operatorname{per}_3) \ge7 [1]. On the upper bound side, Grenet gave a representation of size 2n−12^n - 1 [3]. These coincide at n=3n = 3. Landsberg and Ressayre showed that 2n−12^n - 1 is optimal among representations that respect a large part of the symmetry group of the permanent [4], which leaves open whether a representation without that symmetry can be smaller. At n=4n = 4 the quadratic bound gives 8 against Grenet’s 15. An earlier stage of the present author’s own analysis had recorded a best lower bound for n=4n = 4 as 10.

To the best of my knowledge, this is the first article that settles the exact case of n=4n = 4 from both directions.

Theorem 1.1. dc⁡(per⁡4)=15\operatorname{dc}(\operatorname{per}_4) = 15 over C\mathbb{C}.

The proof has four parts. Firstly, the singular locus of the permanent hypersurface has dimension 8. This forces every representation to have corank exactly one at every zero of per⁡4\operatorname{per}_4. It gives a normal form at the origin in which per⁡4=bD2c\operatorname{per}_4 = bD^2c, for a row bb, a column cc and a square matrix DD of linear forms.

Secondly, the forms in bb and cc vanish together on a linear space KK, which I call the endpoint kernel. The endpoint kernel lies in the singular locus. Let ρ\rho be the rank of the Hessian of per⁡4\operatorname{per}_4 at a generic point of KK. A short argument with a quadratic form then shows that the size of the matrix is at least 17−dim⁡K+⌈ρ/2⌉17 - \dim K + \lceil\rho/2 \rceil.

Thirdly, at size 14 this inequality leaves nine coordinate kernels up to symmetry. The torus acting on rows and columns degenerates every other surviving kernel to one of them. A local computation near these nine then shows that the forcing is either up to symmetry, or else into a family that degenerates to one of them. The families consist of the hyperplanes of a row, of a 2×32 \times3 block, and of two rows.

Finally, I exclude each surviving kernel at size 14. The hardest case is the kernel spanned by a single row. There the Hessian vanishes, and the inequality gives nothing beyond 13. Table 1 summarizes how each kernel is excluded.

ContainerKernelsMechanismSection
one rowrow less a cell, and every hyperplane of a rowstabilizer of the cubic FzF_z; nilpotence of DD on the kernel; irreducibility of FzF_z4.3
two rowsfull 2×32 \times3 block and its hyperplanesno linear syzygies among 2×22 \times2 superma- nents4.5, 4.6
crosscross with arms of tworank of the quotient map against the Hessian radical4.7
two rows crossrow and two cells K6K_6rank of the specialized Hessian block4.8
equality case of the inequality; irreducibility of per⁡3\operatorname{per}_34.9
two rowstwo rows, two rows less a cell, and every hyperplane of two rowsfive channel factorization of BB; Clifford reduction; odd factor obstruction5
one rowone rowinvariant subspaces of a nilpotent pencil6

Table 1. How each admissible kernel is excluded at size 14. Kernels inside a container include the noncoordinate ones.

The argument depends on the characteristic. In characteristic 2 the permanent equals the determinant and dc⁡(per⁡4)=4\operatorname{dc}(\operatorname{per}_4) = 4. The step that fails there is the first one, because the singular locus of det⁡4\det_4 has dimension 12. The first version of this paper, which also appeared as ECCC report TR26-309, condensed several of these steps and referred to the certificate archives for them. In this version every step is argued in full. The computer still enters, but only through finite exact calculations: an enumeration of coordinate subspaces, ranks of explicit integer matrices, and polynomial identities. Each of them is specified in the text, and the two largest are printed in the appendices.

The remainder of this paper is organized as follows. § 2 gives the upper bound and derives the normal form and the endpoint inequality. § 3 classifies the kernels that survive the inequality. § 4, § 5 and § 6 exclude them, and § 7 lists the certificates. Appendices § 9 and § 10 contain the data of the two largest computations.

The upper bound and the endpoint inequality

This section proves the upper bound, reduces any representation of per⁡4\operatorname{per}_4 to a normal form at the origin, and proves the inequality that the rest of the paper uses. We write X=(xij)1≤i,j≤4X=(x_{ij})_{1\leq i,j\leq4} for the 4×44\times4 matrix of variables, and put

f(X)=per⁡4(X)=∑σ∈S4∏i=14xi,σ(i).f(X)=\operatorname{per}_4(X)=\sum_{\sigma\in S_4}\prod_{i=1}^{4}x_{i,\sigma(i)}.

A representation of size mm is an m×mm\times m matrix A(X)A(X) of affine linear forms in the sixteen variables with det⁡A=f\det A=f. All vector spaces, polynomial rings and varieties are over C\mathbb{C}. The rank of a polynomial matrix means its rank over the fraction field, which is also its rank on a nonempty Zariski open subset of its parameter space.

The upper bound

The upper bound is Grenet’s construction [3], which we recall for n=4n=4. Index fourteen states by the nonempty proper subsets SS of {1,2,3,4}\{1,2,3,4\}. Order the states first by their cardinality. There are four states of size one, six of size two, and four of size three. Define a row bb, a column cc, and a 14×1414\times14 matrix DD by

bS={x1jS={j},0otherwise,cS={x4jS={1,2,3,4}∖{j},0otherwise.b_S= \begin{cases} x_{1j} & S=\{j\},\\ 0 & \text{otherwise}, \end{cases} \qquad c_S= \begin{cases} x_{4j} & S=\{1,2,3,4\}\setminus\{j\},\\ 0 & \text{otherwise}. \end{cases}

and

DS,T={x∣S∣+1,jT=S∪{j}, j∉S, ∣S∣=1 or 2,0otherwise.D_{S,T}= \begin{cases} x_{|S|+1,j} & T=S\cup\{j\},\ j\notin S,\ |S|=1\text{ or }2,\\ 0 & \text{otherwise}. \end{cases}

Every nonzero entry of DD increases subset cardinality by one. Thus D3=0D^3=0, I−DI-D is upper triangular with diagonal entries one, and

det⁡(I−D)=1,(I−D)−1=I+D+D2.\det(I-D)=1,\qquad(I-D)^{-1}=I+D+D^2.

The product bcbc is zero because bb is supported on states of size one and cc on states of size three. The product bDcbDc is also zero because one step does not connect these two layers. A term of bD2cbD^2c corresponds to an ordering (j1,j2,j3,j4)(j_1,j_2,j_3,j_4) of the four columns, and its weight is

x1j1x2j2x3j3x4j4.x_{1j_1}x_{2j_2}x_{3j_3}x_{4j_4}.

Each ordering occurs exactly once, so bD2c=fbD^{2}c=f. The Schur complement now gives

det⁡(0−bcI−D)=det⁡(I−D)b(I−D)−1c=bD2c=f.\det\begin{pmatrix} 0 & -b \\ c & I-D \end{pmatrix}=\det(I-D)b(I-D)^{-1}c=bD^{2}c=f.

This proves dc⁡(f)≤15\operatorname{dc}(f)\le15.

Polynomials attached to the permanent

For u,v∈C4u,v\in\mathbb{C}^{4}, define the symmetric 4×44\times4 matrix B(u,v)B(u,v) by

B(u,v)ii=0,B(u,v)ij=ukvl+ulvk({i,j,k,l}={1,2,3,4}).B(u,v)_{ii}=0,\qquad B(u,v)_{ij}=u_{k}v_{l}+u_{l}v_{k}\quad(\{i,j,k,l\}=\{1,2,3,4\}).

Then, for four row vectors a,u,v,ca,u,v,c,

per⁡4(a,u,v,c)=aTB(u,v)c.\operatorname{per}_{4}(a,u,v,c)=a^{T}B(u,v)c.

For a single vector a∈C4a\in\mathbb{C}^{4}, write

B1(a)=B(1,a),B1(a)ij=∑k∉{i,j}ak(i≠j).B_{1}(a)=B(1,a),\qquad B_{1}(a)_{ij}=\sum_{k\notin\{i,j\}}a_{k}\quad(i\ne j).

The subscript distinguishes this linear matrix from the bilinear matrix B(u,v)B(u,v). The trilinear cubic obtained by setting one permanent row to 11 is

F(a,b,c)=per⁡4(1,a,b,c)=∑i,j,kpairwise distinctaibjck=bTB1(a)c.F(a,b,c)=\operatorname{per}_{4}(1,a,b,c)=\sum_{\substack{i,j,k\\\text{pairwise distinct}}}a_{i}b_{j}c_{k}=b^{T}B_{1}(a)c.

For d=(d1,d2,d3)d=(d_{1},d_{2},d_{3}) we also use

C(d)=(0d3d2d30d1d2d10),det⁡C(d)=2d1d2d3.(1)C(d)=\begin{pmatrix} 0 & d_{3} & d_{2} \\ d_{3} & 0 & d_{1} \\ d_{2} & d_{1} & 0 \end{pmatrix},\qquad\det C(d)=2d_{1}d_{2}d_{3}. \tag*{(1)}

Lemma 2.1. For every nonzero z∈C4z\in\mathbb{C}^{4}, the cubic

Fz(a,b,c)=per⁡4(z,a,b,c)F_{z}(a,b,c)=\operatorname{per}_{4}(z,a,b,c)

is irreducible. The ordinary 3×33\times3 permanent is irreducible as well.

Proof. A polynomial homogeneous of degree one in each of three disjoint groups of variables can factor only into multihomogeneous factors. To see this, fix one group and compare the highest and lowest degrees in that group in a product. In an integral domain the highest degrees add and the lowest degrees add. The width between them therefore adds. A product of width zero has factors of width zero. Apply this argument to each group.

A nontrivial factorization of a polynomial of multidegree (1,1,1)(1,1,1) partitions the three row groups between its factors. At least one factor must consequently be a linear form in a single row, independent of the other rows. Such a factor makes all partial derivatives in that row constant multiples of one polynomial.

For per⁡3\operatorname{per}_{3}, the three derivatives in any row are the three distinct 2×22\times2 permanents in the other two rows. They are linearly independent: each contains a monomial not contained in the other two. Hence the required proportionality cannot occur.

For FzF_{z}, choose jj with zj≠0z_{j}\ne0 and set column jj of all three lower rows to zero. Every term using zlz_{l} for l≠jl\ne j then vanishes, because a lower row would have to use column jj. The remaining polynomial is zjper⁡3z_{j}\operatorname{per}_{3} on the other three columns. Consequently the derivatives in each lower row have span of dimension at least three before this specialization. They cannot all be proportional. The multigrading argument therefore excludes every nontrivial factorization.

References

  1. [1]J. Alper, T. Bogart, and M. Velasco. A lower bound for the determinantal complexity of a hypersurface. Found. Comput. Math., 17(3):829–836, 2017.
  2. [2]J.-Y. Cai, X. Chen, and D. Li. Quadratic lower bound for permanent vs. determinant in any characteristic. Comput. Complexity, 19(1):37–56, 2010.DOI
  3. [3]B. Grenet. An upper bound for the permanent versus determinant problem. Manuscript, 2011.
  4. [4]J. M. Landsberg and N. Ressayre. Permanent v. determinant: an exponential lower bound assuming symmetry. In Proc. ITCS, 2016.DOI
  5. [5]T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent problem. Int. Math. Res. Not., 2004(79):4241–4253, 2004.
  6. [6]W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 4.3.2 — A computer algebra system for polynomial computations, 2023.
  7. [7]L. G. Valiant. Completeness classes in algebra. In Proc. 11th STOC, 249–261, 1979.DOI
  8. [8]J. von zur Gathen. Permanent and determinant. Linear Algebra Appl., 96:87–100, 1987.

Paper details

vlnc:W_3kpt4f7p
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

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

  • Computer Science

ChatGPT Pro, Claude Opus 5.5, Claude Fable 5.1 (bare)

View statement
Looking for related papers…
Contents