Arithmetic complexity of certain linear transformations

We obtain order-sharp quadratic and slightly higher estimates of the computa- tional complexity of certain linear transformations (binomial, Stirling, Lah, Gauss, Serpi ´ nski, Sylvester) in the basis {x + y }∪{ ax : |a |≤ C} consisting of the operations of addition and in- ner multiplication by a bounded constant as well as upper bounds O(n log n) for the compu- tational complexity in the basis {ax + by : a, b ∈ R} consisting of all linear functions. Lower bounds of the form Ω(n log n) are obtained for the basis consisting of all monotone linear functions {ax + by : a, b > 0} .F or thefinite arithmetic basis B+,∗,/ = {x ± y, xy,1/x, 1} and for the bases {x ± y }∪{ nx : n ∈ N }∪{ x/n : n ∈ N} and B+,∗ = {x + y, xy,−1} ,e stimates O(n log n log log n) are obtained in certain cases. In the case of a field of characteristic p ,c om- putations in the basis {x + y mod p} are also considered.