The complexity of bivariate power series arithmetic

AbstractInspired by Schönhage'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 (Xd+1,XdY,Xd−1Y2,…,Yd+1) and (Xd+1,Yd+1), respectively. For multiplication, we obtain the lower bounds 54d2−O(d) and 213d2−O(d) for the triangular and quadratic case, respectively, opposed to the upper bounds 32d2+O(d) and 3d2+O(d). For squaring, we prove the lower bounds 78d2−O(d) and 135d2−O(d). As upper bounds, we have d2+O(d) and 212d2+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 356d2+O(d) and 813d2+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 fields (in the case of multiplication and division) and over fields of characteristic distinct from two (in the case of squaring and inversion), respectively. All upper bounds are valid for fields that “support FFTs”, that is, fields that have characteristic zero and contain all roots of unity