Joachim von zur Gathen
ABSTRACT
A univariate polynomial f over a field is decomposable if it is the composition f = g ⊕ h of two polynomials g and h whose degree is at least 2. We determine an approximation to the number of decomposable polynomials over a finite field. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood, and we obtain exponentially decreasing error bounds.
The wild case, where p divides n, is more challenging and our error bounds are weaker. A centerpiece of our approach is a decomposition algorithm in the wild case, which shows that sufficiently many polynomials are decomposable.
- Antonia W. Bluher (2004). On xq+1 + ax + b. Finite Fields and Their Applications 10(3), 285--305. URL http://dx.doi.org/10.1016/j.ffa.2003.08.004. Google Scholar
Digital Library
- Arnaud Bodin, Pierre Dèbes & Salah Najib (2009). Indecomposable polynomials and their spectrum. Acta Arithmetica (2009), to appear.Google Scholar
- Martin Fürer (2007). Fast Integer Multiplication. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 57--66. ACM. URL http://dx.doi.org/10.1145/1250790.1250800. Preprint available at: URL http://www.cse.psu.edu/~furer/Papers/mult.pdf. Google ScholarDigital Library
- Joachim von zur Gathen (1990a). Functional Decomposition of Polynomials: the Tame Case. Journal of Symbolic Computation 9, 281--299. Google ScholarDigital Library
- Joachim von zur Gathen (1990b). Functional Decomposition of Polynomials: the Wild Case. Journal of Symbolic Computation 10, 437--452. Google ScholarDigital Library
- Joachim von zur Gathen (2002). Factorization and Decomposition of Polynomials. In The Concise Handbook of Algebra, Alexander V. Mikhalev & Güünter F. Pilz, editors, 159--161. Kluwer Academic Publishers. ISBN 0-7923-7072-4.Google Scholar
- Joachim von zur Gathen (2008a). Counting reducible and singular bivariate polynomials. Finite Fields and Their Applications 18(4), 944--978. Extended abstract in Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation ISSAC2007, Waterloo, Ontario, Canada (2007), 369--376. Google ScholarDigital Library
- Joachim von zur Gathen (2008b). Counting decomposable multivariate polynomials. Preprint, 21 pages. URL http://arxiv.org/abs/0811.4726.Google Scholar
- Joachim von zur Gathen (2008c). Counting decomposable univariate polynomials. Preprint, 84 pages. URL http://arxiv.org/abs/0901.0054.Google Scholar
- Joachim von zur Gathen & Jüürgen Gerhard (2003). Modern Computer Algebra. Cambridge University Press, Cambridge, UK, 2nd edition. ISBN 0-521-82646-2, 800 pages. URL http://cosec.bit.uni-bonn.de/science/mca.html. First edition 1999. Google ScholarDigital Library
- Joachim von zur Gathen, Mark Giesbrecht & Konstantin Ziegler (2009a). Collisions of polynomial compositions. In preparation.Google Scholar
- Joachim von zur Gathen, Dexter Kozen & Susan Landau (1987). Functional Decomposition of Polynomials. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles CA, 127--131. IEEE Computer Society Press, Washington DC. Google ScholarDigital Library
- Joachim von zur Gathen, Alfredo Viola & Konstantin Ziegler (2009). Exact counting of reducible multivariate polynomials. In preparation.Google Scholar
- Mark William Giesbrecht (1988). Complexity Results on the Functional Decomposition of Polynomials. Technical Report 209/88, University of Toronto, Department of Computer Science, Toronto, Ontario, Canada.Google Scholar
- Johannes Grabmeier, Erich Kaltofen & Volker Weispfenning (editors) (2003). Computer Algebra Handbook. Springer-Verlag, Berlin. ISBN 3-540-65466-6. Google ScholarDigital Library
- Jaime Gutierrez & Dexter Kozen (2003). Polynomial Decomposition, section 2.2.4 (pages 26--28) in Grabmeier et al. (2003). Springer.Google Scholar
- Jaime Gutierrez & David Sevilla (2006). On Ritt's decomposition theorem in the case of finite fields. Finite Fields and Their Applications 12(3), 403--412. URL http://dx.doi.org/10.1016/j.ffa.2005.08.004. Google ScholarDigital Library
- D. Kozen & S. Landau (1986). Polynomial Decomposition Algorithms. Technical Report 86-773, Department of Computer Science, Cornell University, Ithaca NY. Google ScholarDigital Library
- Dexter Kozen & Susan Landau (1989). Polynomial Decomposition Algorithms. Journal of Symbolic Computation 7, 445--456. Google ScholarDigital Library
- Dexter Kozen, Susan Landau & Richard Zippel (1996). Decomposition of Algebraic Functions. Journal of Symbolic Computation 22, 235--246. Google ScholarDigital Library
- Beniamino Segre (1964). Arithmetische Eigenschaften von Galois-Räumen, I. Mathematische Annalen 154, 195--256. URL http://dx.doi.org/10.1007/BF01362097.Google ScholarCross Ref
- Daqing Wan (1990). Permutation Polynomials and Resolution of Singularities over Finite Fields. Proceedings of the American Mathematical Society 110(2), 303--309. ISSN 0002-9939. URL http://www.jstor.org/journals/00029939.html.Google ScholarCross Ref
- U. Zannier (1993). Ritt's Second Theorem in arbitrary characteristic. Journal für die reine und angewandte Mathematik 445, 175--203.Google Scholar
Index Terms
- The number of decomposable univariate polynomials. extended abstract
Recommendations
Lower bounds for decomposable univariate wild polynomials
A univariate polynomial f over a field is decomposable if it is the composition f=g@?h of two polynomials g and h whose degree is at least 2. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well ...
Counting reducible and singular bivariate polynomials
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computationAmong the bivariate polynomials over a finite field, most are irreducible. We count some classes of special polynomials, namely the reducible ones, those with a square factor, the "relatively irreducible" ones which are irreducible but factor over an ...
Tame decompositions and collisions
A univariate polynomial f over a field is decomposable if f = g h = g ( h ) with nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials over a finite field F q . The tame case,...
Comments