Functional Decomposition of Sparse Polynomials

Mark Giesbrecht, Computer Science, University of Wateroo

Thursday July 25th, 10:30am-11:20am in AQ 5004

We consider the algorithmic problem of the functional decomposition of sparse polynomials. For example, given a very high degree (5*2^100) and very sparse (7 terms) polynomial like

   f(x) = x^(5*2^100) + 15*x^(2^102+2^47) + 90*x^(2^101+2^100 + 2^48)

       + 270*x^(2^101 + 3*2^47) + 405*x^(2^100 + 2^49) + 243*x^(5* 2^47) + 1

we ask how to quickly determine whether it can be be quickly written as a composition of lower degree polynomials such as

    f(x) = g(h(x)) = g o h = (x^5+1) o (x^(2^100)+3x^(2^47)).

Mathematically, Erdos (1949), Schinzel(1987), and Zannier(2008) have made major progress in showing that polynomial roots and functional decompositions of sparse polynomials, remain (fairly) sparse, unlike factorizations into irreducibels for example.

Computationally, we have had algorithms for functional decomposition of dense polynomials since Barton & Zippel (1976), though the first polynomial-time algorithms did not arrive until Kozen & Landau (1986}) and a linear-time algorithm by Gathen et al. (1987), at least in the ``tame'' case, where the characteristic of the underlying field does not divide the degree.

Algorithms for polynomial decomposition that exploit sparsity have remained elusive until now. We demonstrate new algorithms which provide very fast sparsity-sensitive solutions to some of these problems. But important open algorithmic problems remain, including proving indecomposibility, and more general sparse functional decomposition. And there is still considerable room to tighten sparsity bounds in the underlying mathematics and/or the implied complexities.

This is ongoing work with Saiyue Liu (UBC) and Daniel S. Roche (USNA).