On the Additive Complexity of Some Integer Sequences

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 × n matrices with the constraint q on the size of the coefficients as H=mnlog₂ q → ∞ up to min,nlog₂ q+(1+o(1))H/log₂ H+n . Next, we establish an asymptotically tight bound (2+o(1))√ n on the complexity of сomputation of the number 2ⁿ-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+Ω(n1-ε) for any ε>0 and sets, with the size nO(log n) of the elements, having the complexity n+Ω(n) .