On some measures of complexity of finite Abelian groupsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 12 июля 2017 г.
Аннотация:Let a finite Abelian multiplicative group G be specified by the basis B = {a1, a2, …, aq}, that is, the group G is decomposed into a direct product of cyclic subgroups generated by the elements of the set B: G = 〈a1〉 × 〈a2〉 × … × 〈aq〉. 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) = maxg∈G L(g; B), LM(G) = maxB L(G, B), Lm(G)= minB L(G, B), M(n) = maxG:|G|≤n LM(G), m(n) = maxG:|G|≤n Lm(G), Mav(n) = (∑G:|G|=nLM(G))/A(n),mav(n)=(∑G:|G|=nLm(G))/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), Mav(n), and mav(n) are established.