Counting decomposable multivariate polynomials

DOI10.1007/S00200-011-0141-9MaRDI QIDQ429753zbMATH OpenOpenAlexFDO

Authors Joachim von zur Gathen

Publication date 20 June 2012

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.4726

zbMATH Keywords

computer algebrafinite fields.multivariate polynomialspolynomial decomposition

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Abstract: A polynomial f (multivariate over a field) is decomposable if f = g(h) with g univariate of degree at least 2. We determine the dimension (over an algebraically closed field) of the set of decomposables, and an approximation to their number over a finite field. The relative error in our approximations is exponentially decaying in the input size.

Review text

A polynomial \(f\) in \(r\) variables over a field \(F\) is decomposable if \(f=g\circ h\) with \(g\) univariate of degree at least 2. The author determines the dimension of the set of decomposables of degree \(\leq n\) when \(F\) is an algebraically closed field. He also finds an approximation to their number when \(F\) is the finite field of order a prime power. Further, he proves that the bound is exponentially decreasing in the input size. The methods used are derived by those developed by the author while studying reducible bivariate polynomials [Finite Fields Appl. 14, No. 4, 944--978 (2008; Zbl 1192.12003)]. From this it is shown that there are many more reducible or relatively irreducible bivariate polynomials than decomposable polynomials. The paper cites 21 references.

Recommendations

• Counting decomposable univariate polynomials
• The number of decomposable univariate polynomials
• Survey on counting special types of polynomials
• Counting decomposable polynomials with integer coefficients
• Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields (extended abstract)

Cites work

• A rational function decomposition algorithm by near-separated polynomials
• Algebraic closure of a rational function
• Composition collisions and projective polynomials: statement of results
• Counting reducible and singular bivariate polynomials
• Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields (extended abstract)
• Functional decomposition of polynomials: the tame case
• scientific article; zbMATH DE number 1273634 (Why is no real title available?)
• Indecomposable polynomials and their spectrum
• Multivariate polynomial decomposition
• The distribution of irreducible polynomials in several indeterminates
• The Distribution of Irreducible Polynomials in Several Indeterminates II
• The distribution of irreducible polynomials in several indeterminates over a finite field
• Unirational fields of transcendence degree one and functional decomposition

Cited in

(14)

• Normal form for Ritt's second theorem
• Counting decomposable polynomials with integer coefficients
• Survey on counting special types of polynomials
• A recombination algorithm for the decomposition of multivariate rational functions
• The number of decomposable univariate polynomials
• Indecomposable polynomials and their spectrum
• Root-Based Compositions of Multivariate Polynomials: Structure, Geometric Interpretations, and Decomposition Results
• On decomposition of sub-linearised-polynomials
• Counting reducible and singular bivariate polynomials
• Counting decomposable univariate polynomials
• On a decomposition of polynomials in several variables
• Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields (extended abstract)
• Homogeneous bivariate decompositions
• An approximate decomposition of a multivariate polynomial and its application

This page was built for publication: Counting decomposable multivariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q429753)