The multiplicative complexity of a binary word α is the length m of the shortest chain of binary words τ₋₁ = 0, τ₀ = 1, τ₁, . . . , τ_m = α, where each τ_i can be written as a concatenation of two previous words: τ_i = τ_j τ_k, −1 ≤ j, k < i. Let l(k, n) denote the largest multiplicative complexity taken over all binary words of length n with k ones. Some interesting links between l(k, n) and the smallest possible number of multiplications to compute k-tuples of powers x^n₁,..., x^n_k are established. The main result of the paper is the asymptotic formula l(k,n) = (1 + o(1))(log n + log C_n^k / loglog C_n^k) as n→∞.

word chain, concatenation circuit, circuit complexity, Shannon function

Mathematical problems and theory of numerical methods