Effective Noether irreducibility forms and applications (Q1892221)

A (multivariate) polynomial is absolutely irreducible if it is irreducible over the algebraic closure of its coefficient field. Irreducibility forms are integer polynomials in the generic coefficients of a multivariate polynomial of given degree. A specific polynomial of that degree is absolutely irreducible if and only if its coefficients make all the irreducibility forms vanish. This paper derives simpler irreducibility forms and more effective irreducibility theorems than the ``classical'' versions, and some related results. The new approach is based on recent polynomial-time multivariate polynomial factorization algorithms, in particular the author's [SIAM J. Comput. 14, 469-489 (1985; Zbl 0605.12001)]. If \(d\) is the total degree of an \(n\)-variate polynomial then approximately there are \(2^{(d + n)^{O(1)}}\) new irreducibility forms having degree \(O(d^6)\) and integer coefficients with \(O((d^7 + d^6n) \log d)\) digits. Substituting affine linear forms in two variables for the variables in a multivariate irreducible polynomial over a perfect field fails to preserve irreducibility with probability \(2d^4/\text{card}(S)\), where \(\text{card}(S)\) is the cardinality of the set \(S\) from which the coefficients in the bivariate linear forms are uniformly selected. The first step is to derive, from an algorithm [loc. cit.; the author's [J. Symbolic Comput. 1, 57-67 (1985; Zbl 0599.68038); and ibid. 9, 301-320 (1989; Zbl 0712.12001)] to factorize bivariate polynomials over the algebraic closure of their coefficient field, an algorithm to test absolute irreducibility of bivariate forms. The next step is to analyse the growth of the norms and degrees of the coefficients in terms of a generic input, i.e. a polynomial with symbolic coefficients. The growth is shown to be polynomial, regardless of the representation used for algebraic numbers and of the coefficient field. The above algorithms require the polynomial to be squarefree. This can be achieved by a generic (symbolic) translation that, when applied to a general \(f \in \mathbb{K}[X_1, \dots, X_n]\), gives the form \[ \varphi(x,y_2,\dots, y_n):= f(x + v_1, v_2 + w_2 x + v_2,\dots, y_n + w_nx + v_n), \] where \(v_i\), \(w_j\) are symbolic constants. This translation preserves irreducibility. If the monic form of \(\varphi(x, 0, \dots, 0)\) is not squarefree then \(f\) is reducible over \(\overline {\mathbb{K}}\). Now consider \[ \chi (x, y, z_2, \dots, z_n) := f(x + \nu_1, \omega_2 x + z_2 y + \nu_2,\dots, \omega_n x + z_ny + \nu_n) \in \overline{\mathbb{K}} [x, y, z_2, \dots, z_n], \] where \(\nu_i, \omega_j \in \overline{\mathbb{K}}\). It is proved that, provided \(\nu_i\), \(\omega_j\) satisfy a polynomial condition to ensure that \(\chi\) is squarefree, there exists a non-zero polynomial \[ \Psi \in \overline{\mathbb{K}} [z_2,\dots, z_n],\quad \text{deg} (\Psi) \leq {3\over 2} d^4 - 2d^3 + {1\over 2} d^2, \] where \(d\) is the total degree of \(f\), such that for all \(\eta_2,\dots, \eta_n \in \overline {\mathbb{K}}\), \(\psi(\eta_2,\dots, \eta_n) \neq 0\) implies that \(\chi(x,y,\eta_2, \dots, \eta_n)\) is absolutely irreducible in \(\mathbb{K} [x,y]\). This can be modified to deal with irreducibility over \(\mathbb{K}\) rather than \(\overline{\mathbb{K}}\), leading to an effective Hilbert irreducibility theorem. Effective Noether irreducibility forms are deduced, and from them an effective bound for the Ostrowski theorem. The size of the neighbourhood in the coefficient space in which a polynomial remains irreducible is deduced. The complexity of computing, in parallel, high precision complex approximations to the absolutely irreducible factors of multivariate polynomials with rational or algebraic coefficients is investigated. The paper concludes with an investigation of factorization over a coefficient field that is a field of functions.