Bivariate Polynomial Multiplication

Inspired by the discussion in [5], we study the multiplicative complexity and the rank of the multiplication in the local algebras Rm;n = k[x; y]=(x y; : : : ; y ) of bivariate polynomials. We obtain the lower bounds (2 3 \Gamma o(1))\Delta dim R m;n 2 \Gamma o(1))\Delta dim Tn for the multiplicative complexity of the multiplication in Rm;n and Tn , respectively. On the other hand, we derive the upper bounds 3\Delta dim Tn \Gamma 2n \Gamma 2 and 3\Delta dim Rm;n \Gamma m \Gamma n \Gamma 3 for the rank of the multiplication in Tn and Rm;n , respectively, provided that the ground field k admits "fast" univariate polynomial multiplication mod x \Gamma 1. Our results are also applicable to arbitrary finite dimensional algebras of truncated bivariate polynomials k[x; y]=I , where the ideal I = pattern d 0 d 1 \Delta \Delta \Delta dn 0