Inspired by Sch onhage's discussion in the Proc. 11th Applied Algebra and Error Correcting Codes Conference (AAECC), Lecture Notes in Comput. Sci., Springer, Berlin, Vol. 948, 1995 pp. 70, we study the multiplicative complexity of the multiplication, squaring, inversion, and division of bivariate power series modulo the "triangular" and "quadratic" ideals (X d+1 ; X d Y; X d-1 Y 2 ; : : : ; Y d+1 ) and (X d+1 ; Y d+1 ), respectively. For multiplication, we obtain the lower bounds 5 4 d 2 -O(d) and 2 1 3 d 2 -O(d) for the triangular and quadratic case, respectively, opposed to the upper bounds 3 2 d 2 + O(d) and 3d 2 + O(d). For squaring, we prove the lower bounds 7 8 d 2 -O(d) and 1 3 5 d 2 -O(d).
As upper bounds, we have d 2 +O(d) and 2 1 2 d 2 +O(d) for the triangular and quadratic case, respectively. Concerning inversion, the obtained lower bounds coincide with those of squaring. As upper bounds, we show 3 5 6 d 2 + O(d) and 8 1 3 d 2 + O(d), respectively. The lower bounds for division are those of multiplication. The upper bounds follow from combining the bounds for inversion and multiplication. All of the above lower bounds hold over arbitrary ÿelds (in the case of multiplication and division) and over ÿelds of characteristic distinct from two (in the case of squaring and inversion), respectively. All upper bounds are valid for ÿelds that "support FFTs", that is, ÿelds that have characteristic zero and contain all roots of unity.