Polynomial Bounds on Degeneration Order from Commutativity Properties of Tensor Slices

Technical Summary: Polynomial Bounds on Degeneration Order from Commutativity Properties of Tensor Slices

Problem Statement
The paper investigates the relationship between the border rank and the tensor rank of 3-tensors, specifically focusing on the quantitative measures of approximation known as the error degree ($e\text{-deg}(T)$) and the order of degeneration ($\text{ord}(T)$).

For a tensor $T$ with border rank $r$, there exists a polynomial map $\varepsilon \mapsto T(\varepsilon)$ such that $\lim_{\varepsilon \to 0} T(\varepsilon) = T$ and $\text{rank}(T(\varepsilon)) \leq r$ for small $\varepsilon$. The error degree is the minimal degree of such a polynomial map, while the order of degeneration is the smallest integer $q$ such that $\sum_{i=1}^r u_i(\varepsilon) \otimes v_i(\varepsilon) \otimes w_i(\varepsilon) = \varepsilon^q T + \varepsilon^{q+1}Q(\varepsilon)$.

These quantities are critical for "debordering": via polynomial interpolation, a bound on the error degree $k$ implies $\text{rank}(T) \leq (k+1)r$. While standard interpolation yields $\text{rank}(T) \leq (2\cdot\text{ord}(T)+1)r$, the best known general bound for $\text{ord}(T)$ in the literature (Lehmkuhl and Lickteig [LL89]) is exponential in the tensor dimensions. This paper seeks to improve these bounds for specific classes of 3-tensors, potentially yielding non-trivial debordering results (e.g., $\text{rank}(T) \leq 2r$).

Methodology
The authors' approach diverges from previous work that relied on global upper bounds on the degree of the algebraic variety of tensors with border rank $r$. Instead, they exploit specific algebraic properties of the tensor slices, particularly commutativity.

1. Reduction to Matrix Commutativity: For a tensor $T \in \mathbb{C}^{m \times n \times p}$ with an invertible first slice $T_1$, the problem reduces to analyzing the matrices $A_i = T_i T_1^{-1}$. The border rank of $T$ is closely linked to whether these matrices are Approximately Simultaneously Diagonalizable (ASD).
2. Motzkin-Taussky Theorem: The paper leverages the Motzkin-Taussky Theorem, which states that a pair of complex matrices is ASD if and only if they commute. This allows the authors to translate the geometric problem of tensor degeneration into the algebraic problem of constructing perturbations for commuting matrices.
3. Perturbation Techniques:
   • En,1 Perturbation: For a single Jordan block, the authors utilize a specific perturbation $A + \varepsilon E_{n,1}$ (where $E_{n,1}$ is the elementary matrix with a 1 in the $(n,1)$ entry). This perturbation preserves commutativity relations in a way that keeps the error degree low (linear in $\varepsilon$).
   • Weyr Form and Regularity: To handle general matrices with complex Jordan structures, the authors employ the Weyr form, a normal form better suited for commuting matrices than the Jordan form. They introduce the concept of $k$-regularity (where every eigenspace has dimension at most $k$). Specifically, they utilize 1-regular matrices (where all eigenspaces are 1-dimensional) to construct simultaneous diagonalizations.
4. Commuting Extensions: For the overcomplete setting ($r \geq \min(m,n)$), the authors use a characterization of border rank via commuting extensions, generalizing results from [Koi25].

Key Contributions and Results

The paper establishes polynomial upper bounds on the error degree and degeneration order for two main classes of tensors, significantly improving upon the exponential bounds of [LL89].

1. The 1-Regular Case (Theorem 1.7)
For $(r, 3)$-generic tensors $T \in \mathbb{C}^{m \times n \times p}$ where the slices satisfy specific commutativity conditions and one slice ($Z_2 Z_1^{-1}$) is 1-regular:

• Rank: $\text{rank}(T) = r$.
• Error Degree: $e\text{-deg}(T) \leq 1$.
• Degeneration Order: $\text{ord}(T) \leq r - 1$.
• Significance: Since $e\text{-deg}(T) \leq 1$, standard interpolation implies $\text{rank}(T) \leq 2r$. This provides a non-trivial debordering result for this class of tensors.

2. The General Commuting Case (Theorem 1.6)
For $(r, 3)$-generic tensors with format $m \times n \times 3$ where the slices $Z_2 Z_1^{-1}$ and $Z_3 Z_1^{-1}$ commute (without the 1-regularity assumption):

• Rank: $\text{rank}(T) = r$.
• Error Degree: $e\text{-deg}(T) \leq (r-1)^3 + (r-1)^2$.
• Degeneration Order: $\text{ord}(T) \leq 2(r-1)^3 + 3(r-1)^2 + 3(r-1)$.
• Significance: While the error degree is cubic rather than linear, it is still a polynomial improvement over the exponential bounds previously known.

3. Overcomplete Setting (Theorems 4.10, 4.11)
The authors extend these results to the overcomplete case ($r \geq \min(m,n)$) using commuting extensions. The bounds on error degree and degeneration order retain the same polynomial shape as the undercomplete case, provided the commuting extension exists.

Significance and Claims
The paper claims that these results represent an exponential improvement over the bounds established by Lehmkuhl and Lickteig [LL89] for the specific classes of tensors discussed.

• Debordering: The primary motivation is the "debordering" question. By showing that $e\text{-deg}(T)$ can be bounded by a small constant (specifically 1) under the 1-regularity assumption, the authors demonstrate that for these tensors, the tensor rank is at most twice the border rank.
• Methodological Shift: The work highlights that specific algebraic properties (commutativity and regularity of slices) can yield tighter bounds than general geometric degree arguments.
• Limitations: The authors are modest about the scope. They note that their results for 3-slice tensors rely on the Motzkin-Taussky theorem, which does not generalize easily to more than two matrices. Consequently, extending these results to tensors with $p > 3$ slices remains an open problem, as commutativity alone is insufficient to guarantee minimal border rank in higher dimensions. Furthermore, the assumption of genericity (invertibility of $Z_1$) and 1-regularity are restrictive, and relaxing them to solve the general debordering question remains open.

In summary, the paper provides a rigorous algebraic framework for bounding the complexity of tensor degeneration, achieving polynomial bounds where exponential ones previously existed, and establishing a direct path to non-trivial rank bounds for a significant subclass of 3-tensors.