Аннотация:Мультипликативная сложность двоичного слова $\alpha$~--- это длина
$m$ самой короткой цепочки двоичных слов
$$ \tau_{-1} = 0, \quad \tau_0 = 1, \quad \tau_1, \dots, \tau_m = \alpha, $$
где каждое $\tau_i$ может быть представлено в виде конкатенации двух предшествующих слов:
$\tau_i = \tau_j\tau_k$,~ $-1 \le j,k < i$. Через $l(k,n)$ обозначается
максимальная мультипликативная сложность слов длины $n$ с $k$ единицами.
Установлены интересные связи между величиной $l(k,n)$ и
наименьшим числом операций умножения, достаточным
для вычисления набора степеней $x^{n_1}, \dots, x^{n_k}$.
Основным результатом работы является асимптотическое соотношение
$$ l(k,n) = (1+o(1)) \left( \log
n + {\log C_{n}^{k} \over \log \log C_{n}^{k}} \right) $$
при $ n \to \infty$.
