A Log-Log Saving for Matrix-Algebra Length and Terseness

Technical Summary: A Log-Log Saving for Matrix-Algebra Length and Terseness

Problem Statement
The paper addresses the "length problem" for full matrix algebras $Mat_n(F)$ over a field $F$. Specifically, it seeks a uniform upper bound on the length $\ell(S)$ required for a set of matrices $S \subseteq Mat_n(F)$ to generate the entire algebra as a vector space. The length $\ell(S)$ is defined as the smallest integer $k$ such that the linear span of all words in $S$ of length at most $k$ equals the unital algebra generated by $S$. The quantity of interest is $\ell(Mat_n(F))$, the maximum of $\ell(S)$ over all generating sets $S$.

Historically, Paz established a quadratic bound ($O(n^2)$), which was later improved by Pappacena to a subquadratic estimate of $O(n^{3/2})$. Šitov subsequently refined this to a bound of $2n \log_2 n + 4n - 4$ (later improved to $2n \log_2 n + 2n - 4$ in the paper's analysis). The paper aims to improve upon Šitov's bound by obtaining a "log-log saving," specifically reducing the linear coefficient of the logarithmic term by a factor involving $\log_2 \log_2 n$.

A secondary application of this result concerns the "terseness" $\tau(n)$ in Specht's theorem. Specht's theorem states that two complex $n \times n$ matrices are unitarily similar if and only if their traces are equal for all words $w$ in the matrices and their adjoints. While Pearcy showed that words of length up to $2n^2$ suffice, the paper seeks the minimal length $\tau(n)$ required to guarantee this condition.

Methodology
The proof strategy builds upon the "square-zero descent" technique introduced by Šitov. The core methodology involves the following steps:

1. Reduction to Irreducible Case: Using Burnside's theorem and block reduction (Theorem 2.2), the problem is reduced to the case where the generating set $S$ is irreducible (i.e., generates the full matrix algebra).
2. Square-Zero Descent: The authors utilize Šitov's descent mechanism, which iteratively finds square-zero matrices of decreasing rank within word spans. Starting from a square-zero matrix of rank $\rho_0$, the process generates a sequence of square-zero matrices with ranks $\rho_i$ such that $\rho_{i+1} \leq \rho_i / 2$.
3. Rank-Length Analysis: The authors track the "rank-length" product $\mu_i = \lambda_i \rho_i$, where $\lambda_i$ is the word length required to find a square-zero matrix of rank $\rho_i$. Šitov's original approach continued this descent all the way to rank 1.
4. Strategic Stopping Point: The paper's primary innovation is the decision to halt the descent earlier. Instead of descending to rank 1, the descent stops as soon as the rank $\rho$ falls below a threshold of $\sqrt{2 \log_2 n}$.
   • If the rank falls into the range $[2, \sqrt{2 \log_2 n}]$, Pappacena's finishing lemma is applied directly.
   • If the descent "overshoots" directly to rank 1 (meaning the previous rank was $> \sqrt{2 \log_2 n}$), the authors apply a telescoping argument. This argument relies on the inequality $1-x \leq -\frac{1}{2}\log_2 x$ for $x \in (0, 1/2]$ to bound the accumulated cost of the descent steps.
5. Convexity Arguments: For the reducible case (block triangular matrices), the authors prove an auxiliary lemma (Lemma 3.1) showing that the proposed bound function $B(n) = 2n \log_2 n - 2n \log_2 \log_2 n + 5n$ satisfies the necessary sub-additivity properties ($B(p) + B(q) + 1 \leq B(p+q)$) for $p+q \geq 16$.

Key Contributions and Results

• Theorem A (Main Result): For every field $F$ and integer $n > 1$, the length of the full matrix algebra is bounded by:
  $$\ell(Mat_n(F)) \leq 2n \log_2 n - 2n \log_2 \log_2 n + 5n$$
  This improves upon Šitov's bound of $2n \log_2 n + 2n - 4$ by introducing a negative $2n \log_2 \log_2 n$ term.

• Theorem B (Application to Terseness): By applying the Freedman–Gupta–Guralnick trace argument, the paper derives a corresponding bound for the terseness $\tau(n)$ in Specht's theorem for $n > 1$:
  $$\tau(n) \leq 4n \log_2 n - 4n \log_2 \log_2 n + 10n + 1$$
  This implies that the number of words required to distinguish unitary similarity classes is bounded by approximately $(n / \log_2 n)^{4n} 2^{O(n)}$.

• Numerical Comparison: The paper provides tables comparing the new bound $B(n)$ against Pappacena's bound ($BPap(n)$) and Šitov's bound ($BSh(n)$). The new bound becomes strictly smaller than Šitov's bound starting at $n=64$, and smaller than Pappacena's bound starting at $n=63$.

Significance and Claims
The paper claims a "log-log saving" in the upper bound for matrix algebra length. The authors note that the improvement stems from a more judicious stopping point in the rank descent process. By stopping the descent when the rank is approximately $\sqrt{2 \log_2 n}$ rather than continuing to rank 1, the authors leverage the large "previous rank" to reduce the final cost estimate.

The authors are modest regarding the optimality of the constant term. They observe that the coefficient $5n$ in the linear term appears optimal if the stopping threshold is a constant multiple of $\log_2 n$. They suggest that allowing a non-constant multiple might improve the linear term to $4n + o(n)$, but they do not pursue this refinement in the current work. The paper does not claim to resolve Paz's conjecture of a linear bound ($2n-2$), but rather provides a tighter sub-quadratic bound that refines the current state-of-the-art.