Comon's conjecture

In mathematics, Comon's conjecture was a conjecture in multilinear algebra asserting that the rank and the symmetric rank of a symmetric tensor are always equal. The conjecture is named after the French engineer and mathematician Pierre Comon, who raised the question in the context of signal processing; it was studied systematically by Comon, Gene H. Golub, Lek-Heng Lim and Bernard Mourrain in 2008. The statement generalizes the elementary fact that the rank of a symmetric matrix can always be realized by a symmetric decomposition, as in the eigendecomposition of a real symmetric matrix.

The conjecture was disproved by Yaroslav Shitov, who in 2018 published a symmetric tensor of size 800 × 800 × 800 whose rank and symmetric rank over the complex numbers differ. All known counterexamples are of very large size and exhibit a gap of exactly one between the two ranks; the problem of finding a counterexample of minimal size or minimal rank remains open, as does the analogous conjecture for border rank.

Statement

Let V be a finite-dimensional vector space over a field F. A tensor $T\in V^{\otimes d}$ is called decomposable (or simple, or of rank at most one) if it can be written as $T=v_{1}\otimes \cdots \otimes v_{d}$ for vectors $v_{i}\in V$. The rank of T is the smallest number r such that T is a sum of r decomposable tensors; this is the notion of rank underlying the tensor rank decomposition. If T is symmetric—invariant under permutations of its tensor factors—then one may also ask for decompositions into symmetric decomposable tensors $\lambda _{i}\,v_{i}^{\otimes d}$, and the smallest number of terms in such a decomposition is the symmetric rank of T. Since every symmetric decomposition is in particular a decomposition, the rank of a symmetric tensor never exceeds its symmetric rank.

Comon's conjecture. The symmetric rank of a symmetric tensor equals its rank.

Under the standard correspondence between symmetric tensors of order d and homogeneous polynomials of degree d, the symmetric rank of a tensor is the Waring rank of the corresponding polynomial (the minimal number of d-th powers of linear forms needed to express it). In geometric language, the conjecture asserts that the rank of a homogeneous polynomial with respect to the Veronese variety equals its rank with respect to the Segre variety into which the Veronese variety is diagonally embedded.

For d = 2 the statement is a classical fact of linear algebra: the rank and symmetric rank of a symmetric matrix coincide. The conjecture concerned the case d ≥ 3, where computing either rank is difficult in general; deciding tensor rank is NP-hard.

Partial results

Before it was disproved in general, the conjecture was verified in a number of special cases, and these results delimit where a minimal counterexample could live. First cases were established by Comon, Golub, Lim and Mourrain, including tensors of sufficiently small rank relative to their dimension. Zhang, Huang and Qi proved the conjecture under the assumption that the rank of the tensor does not exceed its order, and studied when rank decompositions of symmetric tensors are automatically symmetric. Further special cases were proved by Friedland, and Casarotti, Massarenti and Mella improved the rank bounds under which the conjecture holds by producing new equations for secant varieties of Veronese and Segre varieties. Seigal showed that rank and symmetric rank agree for symmetric tensors of small format, including the 4 × 4 × 4 symmetric tensors corresponding to cubic surfaces.

An analogue of the conjecture is known to be true for at least one other notion of rank: the symmetric G-stable rank of a symmetric tensor equals its G-stable rank, a notion introduced by Harm Derksen and defined via geometric invariant theory.

A structural obstacle to settling the conjecture for small tensors is that the standard general-purpose lower bounds for tensor rank—ranks of flattenings and related constructions—bound the rank and the symmetric rank in the same way, and therefore cannot certify that the two ranks of a given tensor differ. The known counterexamples instead rely on variants of the substitution method.

Counterexamples

Complex counterexample

In a preprint posted in 2017 and published in 2018, Shitov constructed a symmetric tensor of size 800 × 800 × 800 that can be written as a sum of 903 decomposable tensors with complex entries but not as a sum of 903 symmetric decomposable tensors, so that its complex rank is 903 while its complex symmetric rank is at least 904. The construction builds the tensor from a structured family of blocks (called clones by Shitov) engineered so that the substitution method yields a lower bound on the symmetric rank that exceeds the exhibited rank decomposition by one.

In 2024, SIAM Journal on Applied Algebra and Geometry published an erratum to the paper, authored by Jan Draisma, concerning a gap in the published proof. Shitov had earlier circulated a note discussing a repaired construction, which he called the "Rosh Hashanah" counterexample.

Real counterexamples

Rank and symmetric rank depend on the underlying field, and the complex counterexample left open the real case of the conjecture, which attracted independent interest. In a 2020 preprint, Shitov constructed a symmetric tensor in $\mathbb {R} ^{208}\otimes \mathbb {R} ^{208}\otimes \mathbb {R} ^{208}\otimes \mathbb {R} ^{208}$ with real rank 761 and real symmetric rank 762, resolving the real case in the negative.

Wang and Seigal reorganized this construction into three modular steps, developed new lower bounds on rank and symmetric rank based on Sylvester-type inequalities for the unfoldings of a tensor, and used the framework to construct a real symmetric tensor of order six whose real rank and real symmetric rank differ.

Other fields

The conjecture has also been studied over arbitrary fields, where counterexamples of much smaller size are known; over the two-element field, symmetric tensors of small order and dimension already exhibit a gap between rank and symmetric rank.

Open problems

All known counterexamples over the real and complex numbers are of large size, and in each of them the symmetric rank exceeds the rank by exactly one. The problem of finding a counterexample of minimal size, or of minimal rank, is open, as is the question of how large the gap between the two ranks can be. The border-rank analogue of Comon's conjecture—that the border rank and symmetric border rank of a symmetric tensor coincide—also remains open.

Related conjectures

Comon's conjecture is frequently studied alongside Strassen's direct sum conjecture, which asserted that the rank of a direct sum of tensors equals the sum of the ranks of the summands. Strassen's conjecture was likewise disproved by Shitov, in 2019. Versions of Comon's conjecture have also been formulated for partially symmetric decompositions of partially symmetric tensors.

See also

• Symmetric tensor
• Tensor rank decomposition
• Waring's problem
• Segre embedding
• Veronese variety
• List of conjectures § Disproved (no longer conjectures)