PaperlayerView exact revision on arXiv

Source-linked AI summary

On the ranks and border ranks of symmetric tensors

J. M. Landsberg, Zach Teitler

arXiv:0901.0487v3math.AG

TL;DR

The paper addresses open questions about explicitly computing ranks and border ranks of polynomials, motivated by applications in signal processing and algebraic complexity. It uses geometric methods, including singularities and differential geometry, to derive rank lower bounds, normal forms for border rank at most five, and rank results for several polynomial classes.

  • Problem

    Explicit computation of polynomial ranks and border ranks remains difficult, and equations for border-rank varieties would help address this problem in applications and algebraic complexity theory.

  • Method

    The paper combines equations for border rank with differential-geometric methods, including analysis of hypersurface singularities, to study symmetric tensor ranks.

  • Results

    The paper improves rank lower bounds, obtains normal forms for polynomials of border rank at most five, and computes or bounds ranks for monomials, the determinant, the permanent, and other classes.

  • Takeaways & Limitations

    Singularity-based geometric analysis provides improved lower bounds and supports rank and border-rank computations across several important polynomial families.

  • Takeaways & Limitations

    The singularity-based bounds are not yet presented as fully general degree- and variable-sensitive bounds, which the authors expect further study to strengthen.

Abstract

from arXiv · show

Motivated by questions arising in signal processing, computational complexity, and other areas, we study the ranks and border ranks of symmetric tensors using geometric methods. We provide improved lower bounds for the rank of a symmetric tensor (i.e., a homogeneous polynomial) obtained by considering the singularities of the hypersurface defined by the polynomial. We obtain normal forms for polynomials of border rank up to five, and compute or bound the ranks of several classes of polynomials, including monomials, the determinant, and the permanent.

1. Introduction

The paper studies symmetric tensor rank and border rank geometrically, using hypersurface singularities for rank lower bounds and classifying low-border-rank polynomials. It develops results for monomials, determinant and permanent polynomials, and polynomials of border rank at most five.

  • Motivation and framework: Symmetric tensor rank is defined through sums of d-th powers, while border rank uses the Zariski closure of rank-r polynomials.The geometric viewpoint connects these notions to secant varieties and makes border rank algebraically tractable.
  • Motivation and framework: Catalecticant minors, or symmetric flattenings, provide equations for varieties of polynomials with bounded border rank.A polarized polynomial is viewed as a linear map φ_s,d−s, whose minors supply such equations.
  • Main results: Monomials receive new upper and lower border-rank bounds by combining these equations with differential-geometric techniques.The result is stated for nonnegative exponents satisfying a0 ≥ a1 + ··· + am.
  • Main results: Polynomials of border rank three admit explicit normal forms, including x^d + y^d + z^d, with additional linearly dependent cases normalized separately.The paper extends normal-form and rank analyses to border rank at most five.
  • Main results: Singularities of the hypersurface defined by φ yield a new general lower bound on rank, described by the authors as the first such bound in about 100 years.The bound is formulated for φ ∈ S^d C^n and 1 ≤ s ≤ d; its right-hand side is typically maximized at s = ⌊d/2⌋.
  • Main results: The singularity-based bound is applied to determinant and permanent polynomials, while further rank estimates cover plane cubics and other specific classes.The authors expect further singularity study to produce stronger bounds involving degree as well as number of variables.

2. Geometric definitions

The paper places polynomial rank and border rank in the geometry of secant varieties, with the Veronese variety representing d-th powers. This framework also relates rank gaps to singularity stratifications and extends naturally to arbitrary projective varieties.

  • Secant varieties: For a projective variety X, X-rank is the smallest secant order containing a point, while X-border rank uses the corresponding Zariski-closed secant variety.Border rank is geometrically natural because points of border rank at most r form an algebraic variety.
  • Secant varieties: For homogeneous polynomials, the Veronese variety consists of projectivized d-th powers, so polynomial rank and border rank are instances of X-rank and X-border rank.The general formulation simultaneously treats polynomials, tensors, and related geometric objects.
  • Secant varieties: The tangential variety τ(X), consisting of embedded tangent lines, is contained in the second secant variety σ2(X).This inclusion provides a basic geometric relation used in the paper’s broader rank framework.
  • Singularity stratification: Within a fixed border-rank class, singularities can distinguish polynomials whose rank exceeds their border rank.The paper proposes that deeper positions in a singularity stratification correspond to higher rank, while presenting this as an expectation beyond its first bound.

3. Review of known facts about rank and border rank of polynomials

This section reviews geometric descriptions of rank and border rank, emphasizing secant varieties, symmetric flattenings, subspace varieties, and known special cases.

  • Geometric framework: Secant varieties σr(vd(PW)) encode border rank, while generic rank and border rank are known from the expected dimensions of Veronese secant varieties.Alexander–Hirschowitz established the expected dimensions except for a short list of exceptions.
  • Flattenings: Symmetric flattenings φs,d−s provide equations for secant varieties through minors and yield left and right kernel spaces.The discussion restricts to 1 ≤ s ≤ ⌊d/2⌋ to avoid redundant flattenings.
  • Flattening behavior: For dim W ≤3, the ranks of symmetric flattenings are nondecreasing with s, although an example has rank φ1,3 = 13 and rank φ2,2 = 12.The example demonstrates that monotonicity can fail in larger dimension.
  • Known cases: Special equations extend beyond flattenings: σ3(v3(P2)) is defined by the Aronhold invariant, and few other cases are fully understood.
  • Rank bounds: 108?
  • Known cases: When dim W = 2, rank and border rank coincide with symmetric-matrix rank for quadratics, while binary forms have classified possible ranks and border ranks.For S3C3, possible ranks and border ranks were also determined, with normal forms assigned ranks explicitly.

4. The theorem of Comas and Seiguer

For binary forms, the Comas–Seiguer theorem completely characterizes secant varieties through a two-part rank condition, giving an explicit description of their rank strata.

  • Theorem 4.1: σr(vd(P1)) consists exactly of forms with rank at most r or rank at least d − r + 2.
  • Rank strata: The successive secant difference σr(vd(P1)) \ σr−1(vd(P1)) contains precisely forms of rank r and forms of rank d − r + 2.
  • Geometric criterion: Rank greater than r is characterized by the right kernel lying inside the variety of degree-r forms with a multiple root.For W = C2, this singularity variety is the locus of binary forms having a repeated root.
  • Theorem 4.1: For φ ∈ SdC2, membership in σr(vd(P1)) is equivalent to rank φs,d−s ≤ r at s = ⌊d/2⌋, rank φr,d−r ≤ r, or a nonzero left kernel.These equivalent conditions apply for 1 ≤ r ≤ ⌊d/2⌋.
  • Proof strategy: The proof uses a nonzero kernel polynomial: a decomposition with at most d − r + 1 distinct summands forces all summand points to be roots of a degree-r polynomial, hence at most r summands.
  • Applications: For a binary monomial, R(x^a y^b) = max(a + 1, b + 1) when a,b > 0.The proof combines symmetric-flattening lower bounds with kernel analysis.

5. Maximum rank of arbitrary varieties

The section proves a dimension-based upper bound for the rank of points relative to an arbitrary irreducible projective variety and derives consequences for smooth curves.

  • Maximum rank: For an irreducible n-dimensional variety X ⊂ PN not contained in a hyperplane, every point has X-rank at most N + 1 − n.The proof proceeds by induction on the dimension, intersecting X with a general hyperplane through the point.
  • Proof: The bound is obtained by choosing a general hyperplane through p whose intersection with X spans the hyperplane and remains irreducible.Induction then applies to the intersection, whose dimension is n−1.
  • Curves: For a smooth nondegenerate curve C ⊂ PN, the maximum C-rank is at most N.
  • Border rank versus rank: Points on a secant variety can have rank exceeding their border rank; for a rational normal curve, tangent-variety points can have the maximum rank d.The rank of a point on the tangent variety can also be arbitrarily large in the broader discussion.

6. Proof and variants of Theorem 1.3

The section derives rank lower bounds from singularities of the hypersurface defined by a polynomial, then applies them to reducible and repeated-factor polynomials.

  • Singularity bound: The rank satisfies R(φ) ≥ rank φs,d−s + dim Σs, where Σs is the locus of zeros of φ having multiplicity at least s + 1.Taking r = R(φ) and comparing dimensions yields the inequality.
  • Kernel construction: For a decomposition φ = η1^d + ··· + ηr^d, the linear system of degree-(d−s) forms vanishing at the ηi lies in the right kernel of the symmetric flattening.Its codimension is at most r, and under ⟨φ⟩ = W it avoids the Veronese variety.
  • Consequences: If ⟨φ⟩ = W and R(φ) = dim W, then the hypersurface has no singular points of multiplicity at least two.This follows because a minimal decomposition gives a basis of W.
  • Scope: The assumption ⟨φ⟩ = W is equivalent to the absence of a first-order kernel and means the hypersurface is not a cone over a lower-dimensional variety.A geometric characterization for higher-order kernel triviality remains open in the remark.
  • Applications: For reducible φ in n variables, R(φ) ≥ 2n − 2; if φ has a repeated factor, R(φ) ≥ 2n − 1.The bounds combine flattening rank n with singular loci of codimension two or one, respectively.
  • Variants: The singularity-based method extends through derivatives and deeper singular strata, using inclusions between the corresponding Σs loci.

7. Ranks and border ranks of some cubic polynomials

The section determines exact ranks or bounds for several cubic polynomials, using flattenings, singular loci, explicit decompositions, and border-rank degenerations.

  • Cubic polynomials: R(φ) = 4m for φ = x1y1z1 + ··· + xmymzm.The lower bound comes from the singular set and flattening, while the upper bound sums the rank-4 decompositions of each xiyizi.
  • Cubic polynomials: R(x(y1^2 + ··· + ym^2)) = 2m and R(x(y1^2 + ··· + ym^2) + x^3) = 2m.The lower bound follows from Corollary 6.8, and explicit decompositions provide matching upper bounds.
  • Cubic polynomials: The section leaves the border ranks of x(y1^2 + ··· + ym^2) and x(y1^2 + ··· + ym^2) + x^3 as open questions.The text explicitly identifies these border ranks as interesting to determine.
  • Cubic polynomials: The rank of x(y1^2 + y2^2 + y3^2) is exactly 6, exceeding the generic rank 5 of cubic forms in four variables.This example illustrates that a cubic can have rank strictly above the generic rank in the same ambient dimension.
  • Cubic polynomials: R(x^2u + y^2v + xyz) = 5 and 8 ≤ R(φ) ≤ 9 for border rank.The rank lower bound uses surjectivity of φ1,2 and the singular set, while five curves give a border-rank-5 degeneration.

8. Plane cubic curves

For plane cubic curves, the paper presents rank and border-rank classifications and derives rank bounds by combining secant-variety equations with Hessian geometry and singularity arguments.

  • Classification: Theorem 8.1 gives the possible ranks and border ranks of plane cubic curves in Table 1.The classification is stated as a table of ranks and border ranks for the plane-cubic normal forms.
  • Method: Secant-variety equations determine the border ranks, while Hessian geometry distinguishes ranks of nongeneric points within secant varieties.For k = 2,3, the third secant variety is defined by the Aronhold invariant rather than a symmetric flattening.
  • Hessian method: The Hessian of a sum of three cubes of linearly independent forms is a union of three nonconcurrent lines with three distinct singular points.This contrasts with the smooth or less singular Hessians of other listed cubic curves and supports their rank lower bounds.
  • Hessian method: The cubic y(x^2 + yz) has rank 5, established by showing that a four-point decomposition would force an impossible pencil of conics.The argument uses the triple-line Hessian and the fact that a pencil of conics through four points contains at least three reducible conics.
  • Results: The listed cubic curves receive matching lower and upper rank bounds, completing the rank calculations.Upper bounds come from explicit expressions, while lower bounds use flattenings, singularities, and Hessian geometry.

9. Determinants and permanents

The paper compares rank and border-rank bounds for determinants and permanents, using flattenings and geometric descriptions of their higher-singularity loci.

  • Border rank: Flattenings yield lower bounds for the border ranks of det_n and per_n through independent minors and permanents of a × a submatrices.Gurvits applies the flattening equations for each 1 ≤ a ≤ n − 1.
  • Rank upper bounds: Rank upper bounds arise from expressing determinants as sums of n! monomials and permanents through a Ryser-type formula with 2^(n−1) terms.Each monomial term is bounded using the rank estimate for products of independent linear forms.
  • Determinant: The determinant’s higher-singularity locus consists of matrices of rank at most n − a − 1 and has dimension n^2 − 1 − (a + 1)^2.This geometric description supplies the improved rank lower bound through Theorem 1.3.
  • Permanent: For the permanent, matrices with a + 1 identically zero columns lie in its higher-singularity locus, giving a crude dimension-based lower bound.The resulting bound is maximized at a = ⌊n/2⌋.
  • Bounds: Table 3 collects upper bounds for rank and lower bounds for border rank from Gurvits alongside the paper’s lower bounds for rank.The table is the section’s consolidated comparison of determinant and permanent bounds.

10. Limits of secant planes for Veronese varieties

The section analyzes limiting secant planes for Veronese varieties through Taylor expansions and Grassmannian limits, yielding classifications of low-border-rank forms. It gives normal forms and rank consequences for border ranks two through five.

  • Limiting secant planes: Limiting secant planes are represented in the Grassmannian by wedges of curves on the Veronese variety, whose limits are studied via Taylor coefficients.The first nonzero coefficient determines the limiting plane containing the border-rank point.
  • Border rank two: For border rank two, every point has rank 1, 2, or d, with normal forms xd, xd + yd, and xd−1y.The tangent-line case gives the form xd−1y and rank d.
  • Border rank three: For border rank three with three-dimensional span, there are three normal-form types, including xd + yd + zd.The classification uses degenerations of limiting points and excludes three distinct limiting points on a trisecant line.
  • Rank consequences: The rank bounds are obtained by summing ranks for upper bounds and specializing to SdC2 for lower bounds; for d = 3, both upper bounds are attained.A dimension count suggests normal forms should exist when r ≤ n.
  • Border rank four: For d > 2, border rank four and four-dimensional span yield six normal-form types, represented by configurations of four d-th powers and their degenerations.The listed types include distinct points, paired tangencies, higher-order degenerations, and a four-step curve.
  • Border rank five: Border rank five has seven types when d > 3 and eight when d = 3; the extra cubic type is x2u + y2v + xyz.Six types extend border-rank-four forms by adding ud, while two further types have explicit normal forms.

11. Monomials

The monomial section develops rank and border-rank bounds using degenerations, coefficient determinants, and symmetric flattenings. It proves an exact product formula under a dominance condition and gives explicit bounds and examples for squarefree and nonsquarefree monomials.

  • Degeneration method: A family of degenerating d-th powers produces a limiting plane containing the monomial x0^b0 ··· x_n^bn, establishing an upper bound on its rank.The surviving lowest-order wedge term is uniquely the monomial indexed by exponent bounds.
  • Degeneration method: The coefficient analysis uses determinants of tensor-product matrices; Vandermonde nonsingularity ensures the target term appears, while other terms vanish or occur at higher t-order.Terms with excessive exponents force dependent columns and zero determinants.
  • Exact monomial ranks: If b0 ≥ b1 + ··· + bn, then the monomial rank satisfies R(x0^b0x1^b1 ··· x_n^bn) = T(b1,...,bn).The matching lower bound follows from the symmetric flattening and the Hilbert-function count Sb,δ.
  • Squarefree monomials: The rank of x1x2x3x4 is exactly 8.This is the next explicit case after the range where the general upper and lower bounds agree.
  • Examples: For x2yz, the paper establishes border rank 4 and rank 5 ≤ R(x2yz) ≤ 6, then proves the upper endpoint by ruling out a five-term decomposition.The contradiction uses the symmetric flattening lower bound R(x2y2 − Ax4) ≥ 3.
Loading 0901.0487v3…