Symmetric Tensor Decompositions over Finite Fields

技术摘要：有限域上的对称张量分解

问题陈述
本文探讨了确定有限域扩张上乘法映射 $M_{q^m}: \mathbb{F}_{q^m} \times \mathbb{F}_{q^m} \to \mathbb{F}_{q^m}$ 的对称张量秩的问题。虽然标准双线性复杂度 $\mu_q(m)$（所需的最小非标量乘法次数）是代数复杂度理论的核心议题，但对称张量秩 $\mu_q^{\text{sym}}(m)$ 施加了额外的约束：分解中每个秩一和项的两个线性形式必须重合。尽管 $\mu_q^{\text{sym}}(m) \ge \mu_q(m) \ge 2m-1$，但在特定范围之外（例如当 $q \ge 2m-2$ 时），确定 $\mu_q^{\text{sym}}(m)$ 的精确值仍然困难。现有方法通常依赖于代数几何或特定构造，导致在一般参数下缺乏构造性方法。

方法论
作者开发了一个基于线性化多项式（也称为 $q$-多项式）的构造性框架。核心方法论在于建立三个数学对象之间的保秩对应关系：

1. 代数 $L_{m,q}$ 中的对称线性化多项式。
2. 通过域迹 $\text{Tr}_{q^m/q}(xy)$ 定义的 $\mathbb{F}_{q^m}$ 上关于 $\mathbb{F}_q$ 的对称双线性型。
3. $\mathbb{F}_q^{m \times m}$ 中的对称矩阵。

作者指出，长度为 $R$ 的对称张量分解对应于存在 $R$ 个秩一对称线性化多项式，这些多项式张成表示乘法映射的线性化多项式空间。具体而言，他们利用了一个结论：秩一对称线性化多项式具有 $\alpha \text{Tr}_{q^m/q}(\beta x)$ 的形式，其中 $\alpha/\beta \in \mathbb{F}_q$。

为了将这一张成条件转化为计算上可处理的问题，作者：

• 固定 $\mathbb{F}_{q^m}$ 关于 $\mathbb{F}_q$ 的一个生成元 $\xi$。
• 将张成条件转化为 $\mathbb{F}_q$ 上的一组显式线性方程。
• 利用弗罗贝尼乌斯自同构（Frobenius automorphism）扩充这些方程组。通过添加方程的弗罗贝尼乌斯共轭，他们推导出了一个判据：若 $\mathbb{F}_q^R$ 中存在解，则保证存在有效的对称张量分解。这种扩充确保了所找到的解在弗罗贝尼乌斯映射下保持不变，从而位于基域中。

主要贡献与结果

1. 构造性判据：本文提供了 $\mu_q^{\text{sym}}(m) \le R$ 的充要条件，该条件涉及 $\mathbb{F}_{q^m}$ 中元素及其弗罗贝尼乌斯共轭的幂所构成的特定线性方程组的可解性（定理 3.2）。
2. 小 $m$ 值的显式分解：作者应用其判据获得了扩展次数 $m \in \{2, 3, 4\}$ 的显式对称张量分解：
   • 情形 $m=2$：他们恢复了已知值 $\mu_q^{\text{sym}}(2) = 3$，并提供了一个涉及三个迹函数的显式分解，该分解对任意 $q$ 均有效。
   • 情形 $m=3$：他们证明对于所有 $q$，$\mu_q^{\text{sym}}(3) \le 6$，且当 $q \in \{2, 3\}$ 时取等号。对于 $q \ge 4$，该值为 5。他们提供了一种利用特定行列式多项式的非零性来寻找所需元素的方法。
   • 情形 $m=4$：利用计算验证（通过 MAGMA 软件），他们为 $q \in \{2, 3, 4, 5\}$ 提供了显式分解。他们恢复了 $q=2$（$\mu=9$）、$q=4$（$\mu=8$）和 $q=5$（$\mu=8$）的最优值，并为 $q=3$ 提供了一个长度为 9 的分解。
3. 编码理论解释：作者引入了对称秩距码的对称张量秩，定义为包含该码的 $\mathbb{F}_q$-张成空间所需的最小秩一对称矩阵数量。他们证明了乘法张量的第一切片空间等价于一维 Gabidulin 码 $G_1(m, q) = \langle x \rangle_{\mathbb{F}_{q^m}}$。因此，$\mu_q^{\text{sym}}(m)$ 正是该特定 Gabidulin 码的对称张量秩。

意义
本文声称其重要性在于提供了一种针对对称张量分解的构造性和算法化方法，超越了基于代数几何的存在性证明或界限。通过将问题重构为涉及弗罗贝尼乌斯稳定系统的有限域上的线性代数问题，作者提供了一种实用方法，用于：

• 验证候选分解。
• 为之前精确值未知或仅有界限的参数生成显式示例。
• 弥合张量秩理论与秩距编码理论之间的差距，具体通过将乘法对称张量秩解释为对称秩距码的不变量。

作者指出，虽然他们的方法成功处理了较小的扩展次数，但确定较大 $m$ 的精确值以及寻找满足线性条件的统一元素族仍然是未解决的挑战。该框架被呈现为进一步研究有限域乘法对称双线性复杂度的工具。