We observe that if we allow for the use of
division and the floor function
besides multiplication, addition and
subtraction then we can
compute the arithmetic convolution
of two n-dimensional integer vectors in O(n) steps and
perform the arithmetic matrix multiplication
of two integer n times n matrices in O(n^2) steps.
Hence, any method for proving superlinear
(in the input size) lower bounds
for the aforementioned problems has to assume a more restricted
set of arithmetic operations and/or an upper bound on the size
of allowed integers.
Keywords and the second author were missing in the previous version.
We observe that if we allow for the use of
division and the floor function
besides multiplication, addition and
subtraction then we can
compute the arithmetic convolution
of two n-dimensional integer vectors in O(n) steps and
perform the arithmetic matrix multiplication
of two integer n times n matrices in O(n^2) steps.
Hence, any method for proving superlinear
(in the input size) lower bounds
for the aforementioned problems has to assume a more restricted
set of arithmetic operations and/or an upper bound on the size
of allowed integers.