Effective Noether irreducibility forms and applications
type: Item
instance of: scholarly article
title: Effective Noether irreducibility forms and applications
zbMATH Open document ID: 0844.12006
published in: Journal of Computer and System Sciences
publication date: 1995-07-13T00:00:00Z
review text: 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…
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 12E25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 762172
zbMATH Keywords: growth of degrees
zbMATH Keywords: effective Noether irreducibility forms
zbMATH Keywords: growth of norms
zbMATH Keywords: multivariate polynomial
zbMATH Keywords: irreducibility forms
zbMATH Keywords: algorithm
zbMATH Keywords: absolute irreducibility of bivariate forms
zbMATH Keywords: polynomial with symbolic coefficients
zbMATH Keywords: effective Hilbert irreducibility theorem
zbMATH Keywords: effective bound for the Ostrowski theorem
zbMATH Keywords: complexity
author: Erich L. Kaltofen
reviewed by: Francis Wright
MaRDI profile type: Publication
OpenAlex ID: W4210639400
DOI: 10.1006/JCSS.1995.1023
description: scientific article; zbMATH DE number 762172