Strassen's direct sum conjecture

In mathematics, Strassen's direct sum conjecture, also called Strassen's additivity conjecture, was a conjecture in multilinear algebra and algebraic complexity theory asserting that the rank of a direct sum of two tensors equals the sum of their ranks. It was formulated by Volker Strassen in 1973 in the context of the computational complexity of bilinear maps. After remaining open for more than four decades, the conjecture was disproved by Yaroslav Shitov, who showed in 2019 that tensor rank fails to be additive over every infinite field.

Statement

Let T1∈A1⊗B1⊗C1 and T2∈A2⊗B2⊗C2 be tensors of order three over a field F. Their direct sum T1⊕T2 is a tensor in (A1⊕A2)⊗(B1⊕B2)⊗(C1⊕C2), obtained by placing the two tensors in disjoint blocks. The rank of a tensor is the smallest number of decomposable (rank-one) tensors summing to it, as in the tensor rank decomposition. Since decompositions of the two summands can be concatenated, the rank of a direct sum never exceeds the sum of the ranks.

Strassen's direct sum conjecture. For all tensors T1 and T2, rank⁡(T1⊕T2)=rank⁡(T1)+rank⁡(T2).

The conjecture originated in the study of bilinear complexity: the rank of a tensor measures the number of multiplications needed to evaluate the associated bilinear map, and taking the union of two bilinear systems depending on disjoint sets of variables corresponds to the direct sum of the associated tensors. The conjecture thus asserted that two independent bilinear problems cannot be solved with fewer multiplications jointly than separately. For order-two tensors the statement is the elementary fact that matrix rank is additive on block-diagonal matrices.

Partial results

Several special cases were established before the conjecture was disproved, and they constrain where counterexamples can occur. In 1986, Ja'Ja' and Takche proved the conjecture in the case where one of the summands has one of its three dimensions at most two. Buczyński, Postinghel and Rupniewski proved additivity when one of the summands is contained in ℂ3⊗ℂ3⊗ℂ3, and more generally when one summand is a concise tensor of rank at most two more than one of its dimensions. A symmetric analogue for Waring rank was proved in the case of sums of pairwise coprime monomials by Carlini, Catalisano and Geramita. Further sufficient conditions, for mixed as well as symmetric tensors, were given by Casarotti, Massarenti and Mella.

Border rank

The analogous statement for the border rank of complex tensors was already known to be false in 1981, when Arnold Schönhage constructed tensors whose direct sum has border rank strictly smaller than the sum of the border ranks; his counterexample consists of summands of formats 2 × 3 × 6 and 2 × 2 × 1, so that it lives in ℂ4⊗ℂ5⊗ℂ7. The subadditivity of border rank under direct sums is a key ingredient of Schönhage's asymptotic sum inequality (his "τ-theorem"), which underlies modern upper bounds on the exponent of matrix multiplication. Buczyński, Postinghel and Rupniewski showed that no border-rank counterexample exists when all three ambient spaces have dimension at most four, and the question of finding the smallest counterexample to border-rank additivity, posed by J. M. Landsberg, remains open. Analogues of Schönhage's construction have also been given for tensors of order four and higher. Schönhage's examples were long regarded as evidence against the rank version of the conjecture, although an explicit rank counterexample was expected to be difficult to find.

Disproof

In a preprint posted in December 2017 and published in Acta Mathematica in 2019, Shitov proved that over every infinite field there exist tensors of order three whose direct sum has rank strictly smaller than the sum of their ranks. The argument is an existence proof based on the substitution method and genericity considerations rather than an explicit pair of tensors, and the tensors it produces are of very large size; subsequent expository work has revisited the construction in detail. Shitov has since also disproved the symmetric version of the conjecture, exhibiting a failure of Waring rank additivity involving tensors of order up to 10888.

Shitov is also known for disproving two other long-standing conjectures: Comon's conjecture, on the equality of the rank and symmetric rank of a symmetric tensor, and Hedetniemi's conjecture in graph theory. The problem of finding explicit or minimal counterexamples to the direct sum conjecture, and of determining the largest possible deficit between rank⁡(T1⊕T2) and rank⁡(T1)+rank⁡(T2), remains open.

See also