# Algorithm for multiplying multivariate polynomials in a commutative ring

Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multivariate polynomials with the same $x_i$-terms with maximal total degree $\delta$, but with different coefficients in $R$. How fast can we compute the product of $f$ and $g$, i.e. the resulting coefficients of each term?

For univariate multiplication in a general setting like this, one can use variants of schonhage-strassen to achieve $O(\delta \log \delta \log\log \delta)$ (e.g. Theorem 8.23 in von zur Gathen & Gerhard, Modern Computer Algebra).

I have only been able to find a non-trivial algorithm for when $R$ is a field of characteristic 0, but not for $R$ being a general commutative ring.

• The number of degree $d$ multivariate monomials is exponential in $d$, so how exactly do you represent the input and output polynomials? In the most obvious representation by a list of nonzero monomials, you cannot beat the trivial quadratic algorithm, as the number of monomials in the output can be that high (consider e.g. $(x^d+x^{d-1}+\dots+1)(y^d+y^{d-1}+\dots+1)$). – Emil Jeřábek Jun 15 '15 at 9:22
• Thanks for pointing out this flaw in the question. In my case the x-terms of $f$ and $g$ are actually the same, but the coefficients are not. Will update the question to cover that. – Chiel ten Brinke Jun 15 '15 at 11:34
• The edit did nothing to clarify the question, so let me ask again: what is the representation of input and output? – Emil Jeřábek Jun 15 '15 at 20:58
• A list of monomials indeed. – Chiel ten Brinke Jun 15 '15 at 21:35
• As I already explained in the first comment, with a list of monomials you cannot do better than the trivial quadratic algorithm. The additional restriction is of no consequence, you can take e.g. $(x^d+\dots+x+y^d+\dots+y+1)^2$. – Emil Jeřábek Jun 16 '15 at 8:27