On the Additive Complexity of Some Numerical Sequences

The paper presents several results concerning the complexity of calculations in the model of vector additive chains. A refinement of N. Pippenger's upper bound is obtained for the complexity of the class of integer $m \times n$ matrices with the constraint $q$ on the size of the coefficients as $H=mn\log_2 q \to \infty$ up to $\min\{m,n\}\log_2 q+(1+o(1))H/\log_2 H+n$. The established complexity of calculating the number $2^n-1$ in the basis of powers of two is asymptotically sharp: it is equal to $(2+o(1))\sqrt n$. Based on generalized Sidon sequences, constructive examples of numerical sets of cardinality $n$ are constructed: sets, with polynomial size of elements, having the complexity $n+\Omega(n^{1-\varepsilon})$ for any $\varepsilon>0$ and sets, with the size $n^{O(\log n)}$ of the elements, having the complexity $n+\Omega(n)$.