Abstract: We wish to compute with polynomials where the exponents are not known in advance. Expressions of this sort arise frequently in practice, for example in the analysis of algorithms, and it is difficult to work with them effectively in current computer algebra systems. There are various simple operations we must be able to perform, such as squaring $x^{2n}-1$ to get $x^{4n}-2x^{2n}+1$, or differentiating to get $2nx^{2n-1}$. Other operations are less obvious.

We consider the case where multivariate polynomials can have exponents that are themselves integer-valued multivariate polynomials. We call these objects "symbolic polynomials" and show they form a unique factorization domain, naturally related to the polynomial ring. We present algorithms to compute their GCD, factorization and functional decomposition.