OctoInformBeta

A cubic permanent–determinant lower bound

For a positive integer mm, let SmS_m be the permutation group on {1,…,m}\{1,\ldots,m\}. The permanent of a matrix X=(xij)1≤i,j≤mX=(x_{ij})_{1\le i,j\le m} of independent variables is per⁡m(X)=∑σ∈Sm∏i=1mxi,σ(i)\operatorname{per}_m(X)=\sum_{\sigma\in S_m}\prod_{i=1}^m x_{i,\sigma(i)}. For a complex polynomial ff in NN variables, an affine determinant representation of size nn is an identity f(x)=det⁡(A0+∑j=1NxjAj)f(x)=\det(A_0+\sum_{j=1}^N x_jA_j) with A0,…,AN∈Mat⁡n(ℂ)A_0,\ldots,A_N\in\operatorname{Mat}_n(\mathbb C). Its determinantal complexity dc⁡(f)\operatorname{dc}(f) is the least positive size of such a representation. Its border determinantal complexity dc_(f)\underline{\operatorname{dc}}(f) is the least positive nn for which ff is a coefficientwise limit of determinants of affine-linear matrices of size nn. An affine-linear algebraic branching program computes the sum of products of affine-linear edge labels along all directed paths from a source to a sink in a finite acyclic graph. The permanent versus determinant problem asks how dc⁡(per⁡m)\operatorname{dc}(\operatorname{per}_m) and dc_(per⁡m)\underline{\operatorname{dc}}(\operatorname{per}_m) grow with mm.

Mignon and Ressayre proved the characteristic-zero bound dc⁡(per⁡m)≥m2/2\operatorname{dc}(\operatorname{per}_m)\ge m^2/2. Landsberg, Manivel and Ressayre proved the unrestricted complex border bound dc_(per⁡m)≥m2/2\underline{\operatorname{dc}}(\operatorname{per}_m)\ge m^2/2.

The preprint proves dc_(per⁡m)≥m3/(5529600exp⁡(1))\underline{\operatorname{dc}}(\operatorname{per}_m)\ge m^3/(5529600\exp(1)) for every m≥1408m\ge1408. The preprint also derives a lower bound of Ω(m3)\Omega(m^3) for the fixed vertex budget in any coefficientwise approximation of per⁡m\operatorname{per}_m by affine-linear algebraic branching programs.

The Lean library Determinantal formalizes the determinant lower bounds and the coefficient and plane-curve results supporting them. For a nonzero homogeneous complex form GG of degree r≥2r\ge2 in d≥2d\ge2 variables, the Lean library proves dc_(G)≥(r−1)(d−1)/(4exp⁡(1))\underline{\operatorname{dc}}(G)\ge(r-1)(d-1)/(4\exp(1)) under the hypothesis that the only common zero of GG and all its first partial derivatives is the origin. Lean has checked every result of the Lean library, so the Lean library is the reference for these pages. Each page states the Lean library’s result and links to the corresponding declaration. Where the preprint gives a different statement, its statement appears beside the Lean library’s. The preprint serves only as a guide to the order and names of the results.

The Lean library: Determinantal

Determinantal is a Lean library: 30 items, in nine groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): exact and border determinant representations Exact and border models at fixed size.
  2. Theorem 1.1 Cubic bounds for permanent determinant representations.
§2. Border models and smooth homogeneous forms 2 items
  1. Lemma 2.1 Affine changes preserve border determinant size.
  2. Theorem 2.3 Projectively smooth forms constrain border determinant size.
§3. Selecting a coefficient by a permanent projection 3 items
  1. §3 (setting): the integral coefficient polynomial An integral family of coefficient polynomials.
  2. Proposition 3.1 Selecting diagonal permanent coefficients by projection.
  3. Corollary 3.2 A border size bound for permanent coefficients.
§4. The adjugate scheme in characteristic two 4 items
  1. §4 (setting): spectral pencils and adjugate ideals Spectral pencils and their selector gradients.
  2. Lemma 4.1 Distinct slopes give separable spectral pencils.
  3. Lemma 4.2 Adjugate entries span the cofactor ideal’s low-degree part.
  4. Proposition 4.3 A length bound from cofactor coefficient vanishing.
§5. The conductor and the normalization defect 3 items
  1. §5 (setting): normalization and conductor Conductors and the affine normalization defect.
  2. Lemma 5.1 Separable spectral algebras satisfy conductor bounds.
  3. Proposition 5.2 Normalization defect bounds affine adjugate colength.
§6. From curve defects to matrix codimension 6 items
  1. Proposition 6.1 A dimension bound for diagonal permanent coefficient critical loci.
  2. §6 (proof setting): the effective spectral-curve parameter bound Normalization defect limits spectral parameters.
  3. §6 (setting): the row subscheme on a fixed curve Column sums define the row ideal.
  4. Lemma 6.3 Row ideals and determinants recover spectral pencils.
  5. Lemma 6.4 Finite curve charts have bounded parameter fields.
  6. Proposition 6.5 Fixing a spectral determinant limits matrix parameters.
§7. Characteristic transfer and smooth linear sections 4 items
  1. §7 (setting): algebraic certificates for smooth restrictions Linear restrictions and their Macaulay matrices.
  2. Lemma 7.1 Integer polynomial rank certificates transfer to characteristic zero.
  3. Proposition 7.2 A gradient dimension bound gives smooth sections.
  4. Proposition 7.3 Critical dimensions constrain border determinantal representations.
§8. Counting polars of a smooth hypersurface 4 items
  1. §8 (setting): directional derivatives and simple polar zeros Affine sections and simple polar zeros.
  2. Lemma 8.1 Counting smooth hypersurface polar intersections.
  3. Lemma 8.2 Counting simple zeros across projective charts.
  4. Proposition 8.3 Simple polar zeros constrain determinant size.
§9. The permanent lower bound and its consequences 2 items
  1. Corollary 9.1 A cubic size bound for exact permanent representations.
  2. Corollary 9.3 Smooth initial forms constrain determinant sizes.

No item matches.