On some measures of complexity of finite Abelian groups

V. V. Kochergin

Diskretnaya Matematika, Tome 27 (2015) no. 3, pp. 25-43

Résumé

Let a finite Abelian multiplicative group $G$ be specified by the basis $B = \{ a_1, a_2, \ldots , a_q\}$, that is, the group $G$ is decomposed into a direct product of cyclic subgroups generated by the elements of the set $B$: $G= \langle a_1 \rangle \times \langle a_2 \rangle \times \ldots \times \langle a_q \rangle$. The complexity $L(g;B)$ of an element $g$ of the group $G$ in the basis $B$ is defined as the minimum number of multiplication operations required to compute the element $g$ given the basis $B$ (it is allowed to use the results of intermediate computations many times). Let $L(G, B)= \max\limits_{g \in G} L(g; B),$ $ LM(G)= \max\limits_{B} L(G, B),$ $Lm(G)= \min\limits_{B} L(G, B),$ $M(n) = \max\limits_{G \colon |G| \le n} LM(G),$ $m(n) = \max\limits_{G \colon |G| \le n} Lm(G),$ $M_{\hbox{\small av}}(n) = \left( \sum\limits_{G \colon |G|= n}{ LM(G)}\right)/{A(n)},$ $m_{\hbox{\small av}}(n) = \left( \sum\limits_{G \colon |G|= n}{ Lm(G)}\right)/{A(n)},$ where $A(n)$ is the number of Abelian groups of order $n$. In this work the asymptotic estimates for the quantities $L(G, B)$, $M(n)$, $m(n)$, $M_{\hbox{\small av}}(n)$, and ${m_{\hbox{\small av}}}(n)$ are established.

Détail

Keywords: finite Abelian group, computational complexity, addition chains, vectorial addition chains, Bellman's problem, Knuth's problem.