Simple multivariate polynomial multiplication (Q1346473)

Let \(u= u(x_1, \dots, x_m)\) and \(v= v(x_1, \dots, x_m)\) be \(m\)-variate polynomials over a field \(F\) and let \(N= c^m\), where \(c\) is chosen so that \(c\geq 2\deg_{x_i} (u)+ 1,2 \deg_{x_i} (v)+ 1\) \((1\leq i\leq m)\). It is known that the product \(uv\) can be computed in time \(O(N \log N\log \log N)\). In this note it is shown that it can be computed in time \(O(N \log N)\), the bound already known to hold when \(F\) supports FFT at \(2^{\lceil \log_2 N\rceil}\).