【报告摘要】We consider the algorithmic problem of the functional decomposition of sparse polynomials and rational functions.  For example, (very) given a sparse polynomial like

f(x) = x^(5⋅2^100) + 15⋅x^(2^102+2^47) + 90⋅x^(3⋅2^100+2^48) + 270⋅x^(2^101+3⋅2^47)+ 405⋅x^(2^100+2^49)

       + 243⋅x^(5⋅2^47) -4⋅x^(2^101) - 24⋅x^(2^100+2^47)- 36⋅x^(2^48)) + 1

with 10 terms and degree 5⋅2^100, 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)) = (x^5-4x^2+1) o (x^(2^100)+3x^(2^(47)))

Mathematically, Erdos(1949), Schinzel(1987), and Zannier(2009) have made major progress in showing that polynomial roots and functional decompositions of sparse polynomials, and even sparse rational functions, remain sparse (unlike factorizations 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 (1989) and a nearly linear time algorithm by von zur Gathen (1989), 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 and simple solutions to many of these problems. Open algorithmic problems remain, including proving indecomposibility, and general rational function decomposition. And there is still considerable room to tighten sparsity bounds in the underlying mathematics.

We will explore connections to proving sparse divisibility, polynomial irreducibility, and other  well-known open problems in the algebraic complexity of sparse polynomials.

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