Effective Noether irreducibility forms and applications
Effective Noether irreducibility forms and applications
复制标题
有效的诺特不可约形式和应用
DOI：
10.1145/103418.103431
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
E. Kaltofen
中科院分区：
文献类型：
--
作者：
E. Kaltofen
使用最新的绝对不可约性测试算法，我们推导出新的不可约性形式。这些是变量中的整数多项式，它们是给定次数的多元多项式的通用系数。如果特定域上的（多元）多项式在其系数域的代数闭包上不可约，则称该多项式是绝对不可约的。当且仅当以特定多项式的系数求值时所有相应的不可约形式都消失时，特定次数的特定多项式是绝对不可约的。我们的形式比 Emmy Noether 最初导出的形式具有小得多的阶数和系数。我们还可以应用我们的估计来推导奥斯特洛夫斯基和杜林的不可约定理以及希尔伯特不可约定理的更有效版本。我们还对绝对不可约多项式的邻域直径相对于保留绝对不可约性的系数空间给出了有效估计。此外，我们可以应用有效估计来导出并行计算复杂性理论中的多个因式分解结果：我们展示了如何计算多元积分多项式的复因子的任意高精度近似，以及如何计算具有有理函数域中的系数的多元多项式的绝对不可约因子的数量，两者都在复杂性类 NC 中。因式分解结果也扩展到系数域是函数域的情况。
Using recent absolute irreducibility testing algorithms, we derive new irreducibility forms. These are integer polynomials in variables which are the generic coefficients of a multivariate polynomial of a given degree. A (multivariate) polynomial over a specific field is said to be absolutely irreducible if it is irreducible over the algebraic closure of its coefficient field. A specific polynomial of a certain degree is absolutely irreducible, if and only if all the corresponding irreducibility forms vanish when evaluated at the coefficients of the specific polynomial. Our forms have much smaller degrees and coefficients than the forms derived originally by Emmy Noether. We can also apply our estimates to derive more effective versions of irreducibility theorems by Ostrowski and Deuring and of the Hilbert irreducibility theorem. We also give an effective estimate on the diameter of the neighborhood of an absolutely irreducible polynomial with respect to the coefficient space in which absolute irreducibility is preserved. Furthermore, we can apply the effective estimates to derive several factorization results in parallel computational complexity theory: we show how to compute arbitrary high precision approximations of the complex factors of a multivariate integral polynomial and how to count the number of absolutely irreducible factors of a multivariate polynomial with coefficients in a rational function field, both in the complexity class NC. The factorization results also extend to the case where the coefficient field is a function field.