Question: I would like to ask the community where my following suggestion for an asymptotic bound for the running time of multiplying two multivariate polynomials using theorem $8.23 $ recursively fails.
In Modern Computer Algebra from Joachim von zur Gathen and Jürgen Gerhard theorem $8.23 $ states that the running time for multiplying two polynomials $ f, g \in R [t] $ both having degrees bounded by $ n $ over any commutative Ring $ R $ with $1 $ amounts to
$$ O^{\sim}(n) $$
arithmetic operations in the ring $ R $. Here $O^{\sim}(n)$ ignores logarithmic terms, the original result gives
$$ (18 + 72 \log_3 2) n \log n \log \log n + O (n \log n) $$
arithmetic operations in $ R $.
My idea:
Let $ f(x_1,..., x_m), g(x_1,..., x_m) \in K [x_1, ... , x_m] $ be two multivariate polynomials in which the power of $ x_i$ is at most $ n_i $. We can regard those polynomials as polynomials in $ x_m $ over the ring $ R_{m-1} = K [x_1, ... , x_{m-1}]$, then thoerem $8.23$ gives us a complexity of $O^{\sim}(n_m)$ arithmetic operations in $R_{m-1}$. Those operations are at worst again multplications of multivariate polynomials in $x_{m-1}$ (having degrees at most $n_{m-1}$ in $x_{m-1}$) over $ R_{m-2} = K [x_1, ... , x_{m-2}]$ and now we could use this procedure recursively to obtain an estimated running time of
$$O^{\sim}\left(\prod_{i=1}^m n_i\right)$$
operations in $K$.
Where does this arumentation not hold?
I'd be grateful for any kind of help or comments.
Your specific argument has the following gap, assuming you've quoted all relevant details.
While theorem 8.23 does say that you can multiply with $\tilde{O}(n_m)$ operations in $R_{m-1}$, it does not say anything about the degrees of the elements of $R_{m-1}$ you need to multiply.
I'm not sure why you're skeptical of the result. The runtime you derive is achievable; a simple method is Kronecker substitution. E.g. you can multiply two bivariate polynomials $f,g \in R[x,y]$ of degree less than $m$ in $x$ and degree less than $n$ in $y$ by computing the product of the two univariate polynomials $f(x, x^{2m})$ and $g(x, x^{2m})$ of degree less than $2mn$.