On the Additive Complexity of Some Integer Sequences
Igor' Sergeevich Sergeev · Mathematical Notes · 2024
The paper presents several results concerning the complexity of calculations in the model of vector addition 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$$ . Next, we establish an asymptotically tight bound $$(2+o(1))\sqrt n$$ on the complexity of сomputation of the number $$2^n-1$$ in the base of powers of $$2$$ . Based on generalized Sidon sequences, constructive examples of integer 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)$$ .