Full-text PDF (591 kB) Citations (4)

DOI: https://doi.org/10.4213/dm1333

Abstract: 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.

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

Funding agency	Grant number
Russian Foundation for Basic Research	14--01--00598
This work was financially supported by the Russian Foundation for Basic Research, grant № 14–01–00598.

Received: 25.05.2015

English version:
Discrete Mathematics and Applications, 2017, Volume 27, Issue 2, Pages 81–95
DOI: https://doi.org/10.1515/dma-2017-0010

Bibliographic databases:

Citation: V. V. Kochergin, “On some measures of complexity of finite Abelian groups”, Diskr. Mat., 27:3 (2015), 25–43; Discrete Math. Appl., 27:2 (2017), 81–95

Citation in format AMSBIB

Linking options:

https://www.mathnet.ru/eng/dm1333

https://doi.org/10.4213/dm1333

https://www.mathnet.ru/eng/dm/v27/i3/p25

This publication is cited in the following 4 articles:

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles