Counting decomposable multivariate polynomials

DOI10.1007/S00200-011-0141-9MaRDI QIDQ429753zbMATHOpenAlexFDO

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 algebrapolynomial decompositionmultivariate polynomialsfinite fields.

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.

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

• scientific article; zbMATH DE number 1273634 (Why is no real title available?)
• 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
• Indecomposable polynomials and their spectrum
• Multivariate polynomial decomposition
• The Distribution of Irreducible Polynomials in Several Indeterminates II
• The distribution of irreducible polynomials in several indeterminates
• The distribution of irreducible polynomials in several indeterminates over a finite field
• Unirational fields of transcendence degree one and functional decomposition

Cited in

(13)

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

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)