实τ猜想相关研究

### 实 τ 猜想相关研究 #### 1. 研究背景与相关成果 在多项式研究领域，有许多关于多项式根的数量以及复杂度的研究。一些近期的研究成果与我们的研究相关。比如有研究探讨了多项式 \(f_j\) 的某些性质，其结果在某些方面比我们的更具一般性，但他们的算法复杂度是关于 \(f_j\) 次数的多项式，而我们能够在多项式时间内处理次数为指数级的多项式，且他们的研究未给出下界。还有 Manindra Agrawal 等人的研究，通过对所考虑多项式的雅可比矩阵的研究，探索了多项式恒等测试与行列式复杂度下界之间的联系，并将我们的结果扩展到更广泛的多项式类。另外，Pascal Koiran 等人的最新研究继续对实 τ 猜想进行了研究，利用一种名为朗斯基行列式的代数工具，得到了一个仅关于 \(k\) 为指数级的新界限。 #### 2. 我们的研究方法 我们对实根数量界限的证明可以看作是笛卡尔符号法则证明的一种推广。笛卡尔法则实际上比这里陈述的结果更精确，它考虑了多项式系数的符号，但这里我们采用不考虑系数符号的简化版本，将其称为笛卡尔法则。 - **命题 6.3**：一个具有 \(t \geq 1\) 个单项式的多项式 \(f \in R[X]\) 最多有 \((t - 1)\) 个严格正实根。通过考虑 \(f(-X)\) 可以同样限制负根的数量，再加上 \(f\) 可能存在的根 \(0\)，可以得出 \(f\) 最多有 \((2t - 1)\) 个不同的实根。证明采用对 \(t\) 进行归纳的方法。当 \(t = 1\) 时，多项式没有非零根。当 \(t > 1\) 时，设 \(c_{\alpha}X^{\alpha}\) 是 \(f\) 中次数最低的单项式，将 \(f\) 除以 \(X^{\alpha}\) 不改变其严格正根，可假设 \(\alpha = 0\)。此时 \(f\) 的导数 \(f'\) 有 \((t - 1)\) 个单项式，根据归纳假设，\(f'\) 最多有 \((t - 2)\) 个严格正根，再根据罗尔定理，\(f\) 最多有 \((t - 2) + 1 = t - 1\) 个严格正根。 对于形如 \(f = \sum_{i=1}^{k} \prod_{j=1}^{m} f_{j}^{\alpha_{ij}}\) 的多项式，我们用 \(k\) 个稀疏多项式幂的乘积之和代替 \(t\) 个单项式之和。证明时采用类似的策略，即除以其中一项然后对多项式求导，但与笛卡尔法则不同的是，这会导致剩余 \((k - 1)\) 项的复杂度增加，从而得到更宽松的界限。下面以 \(k = 2\) 的特殊情况为例： - **定理 6.4**：设 \(f = \prod_{j=1}^{m} f_{j}^{\alpha_{1j}} + \prod_{j=1}^{m} f_{j}^{\alpha_{2j}}\)，其中 \(f_j\) 最多有 \(t\) 个单项式，则 \(f\) 最多有 \(2mt^m + 4m(t - 1)\) 个不同的实根。证明过程如下：设 \(\varphi = \frac{f}{\prod_{j} f_{j}^{\alpha_{1j}}} = 1 + \prod_{j} f_{j}^{\alpha_{2j}-\alpha_{1j}}\)，则 \(\varphi'\) 的表达式为 \(\varphi' = \prod_{j=1}^{m} f_{j}^{\alpha_{2j}-\alpha_{1j}-1} \times \sum_{j=1}^{m} (\alpha_{2j} - \alpha_{1j}) f_{j}' \prod_{\ell \neq j} f_{\ell}\)。由于每个 \(f_j\) 最多有 \(t\) 个单项式，所以 \(\sum_{j=1}^{m} (\alpha_{2j} - \alpha_{1j}) f_{j}' \prod_{\ell \neq j} f_{\ell}\) 最多有 \(mt^m\) 个单项式，根据笛卡尔法则，它最多有 \(2mt^m - 1\) 个不同的实根。另外，分式 \(\prod_{j} f_{j}^{\alpha_{2j}-\alpha_{1j}-1}\) 的根或极点是某个 \(f_j\) 的根，最多有 \(1 + 2m(t - 1)\) 个。因此，\(\varphi'\) 最多有 \(2mt^m + 2m(t - 1) - 1\) 个根，再根据罗尔定理，\(\varphi\) 最多有 \(2mt^m + 2m(t - 1)\) 个不同的实根。最后，\(f\) 的根是 \(\varphi\) 或 \(\prod_{j} f_{j}^{\alpha_{1j}}\) 的根，所以 \(f\) 最多有 \(2mt^m + 2m(t - 1) + 2m(t - 1)\) 个不同的实根。 从定理 6.2 的界限可以通过 Koiran 描述的方法推导出行列式复杂度的下界。具体来说，在假设行列式可以简洁地表示为 (6.2) 的形式下，利用 Bürgisser 的结果可以证明多项式 \(\prod_{i=1}^{2n} (X - i)\) 也可以这样表示，这与我们对实根数量的界限产生矛盾。 我们的第三个结果是针对形如 (6.2) 的多项式的恒等测试算法。经典的方法是使用相交集，即对于一个多项式类 \(F\)，相交集 \(H\) 是一个点集，使得对于 \(F\) 中任何非零多项式 \(f\)，都存在 \(x \in H\) 使得 \(f(x) \neq 0\)。给定一个相交集，很容易推导出一个用于测试 \(F\) 中多项式是否为零的黑盒算法。另一方面，一个关于 \(F\) 中任何非零多项式实根数量的界限 \(z(F)\) 表明，任何大小为 \((z(F) + 1)\) 的集合都是 \(F\) 的相交集。当 \(k\) 和 \(m\) 固定时，我们的界限提供了一个大小为多项式级的相交集，但由此产生的黑盒算法复杂度不是多项式级的，因为计算形如 (6.2) 的多项式在给定参数上的值由于高次幂的存在而成本过高。因此，我们采用另一种策略，将上界的证明转化为一个算法，这要求在算法的每一步都知道多项式的结构，所以这是一个白盒算法。 #### 3. 稀疏多项式乘积之和的实根 ##### 3.1 相关定义 我们首先精确地定义我们所研究的稀疏多项式乘积之和的类。 - **定义 6.5**：记 \(SPS(k, m, t, h)\) 为满足 \(f = \sum_{i=1}^{k} g_{i} \prod_{j=1}^{m} f_{j}^{\alpha_{ij}}\) 的多项式 \(f \in R[X]\) 的类，其中 \(g_1, \cdots, g_k\) 是最多有 \(h\) 个单项式的多项式，\(f_1, \cdots, f_m\) 是非零多项式且最多有 \(t\) 个单项式，\(\alpha_{11}, \cdots, \alpha_{km}\) 是自然数。定义 \(P_i = \prod_{j=1}^{m} f_{j}^{\alpha_{ij}}\) 和 \(T_i = g_iP_i\)。记 \(SPS(k, m, t)\) 为 \(SPS(k, m, t, h)\) 的子类，其中所有 \(g_i\) 都等于常数 \(1\)。 我们的目标是构造一个从 \(SPS(k, m, t, h)\) 到 \(SPS(k - 1, m, t, \tilde{h})\) 的多项式 \(\Delta f\)，使得 \(f\) 的实根数量最多等于 \(\Delta f\) 的实根数量。 - **定义 6.6**：设 \(f = \sum_{i} g_{i} \prod_{j} f_{j}^{\alpha_{ij}} \in SPS(k, m, t, h)\)，则 \(\Delta f\) 的定义如下： \[ \Delta f = \begin{cases} g_{k}^{2}P_{k} \left(\prod_{j=1}^{m} f_{j}\right) \left(\frac{f}{g_{k}P_{k}}\right)' & \text{如果 } g_{k} \neq 0 \\ f & \text{否则} \end{cases} \] - **引理 6.7**：对于 \(f \in SPS(k, m, t, h)\)，存在一个整数 \(\tilde{h}\) 使得 \(\Delta f \in SPS(k - 1, m, t, \tilde{h})\)。具体来说，存在多项式 \(\delta g_i\) 最多有 \(\tilde{h}\) 个单项式，使得 \(\Delta f = \sum_{i=1}^{k - 1} \delta g_i \prod_{j=1