On the computation complexity of the systems of finite Abelian group elements

V. V. Kochergin

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 4 (2023), pp. 22-29

Résumé

The computation compelxity of the systems of the finite Abelian group elements is studied in the paper. The complexity of computation means the minimal number of group operations required to calculate elements of the system over the basis elements, all results of intermediate calculations may be used multiple times. We define the Shannon function $L(n, m)$ as the maximal complexity of $m$-elements system group, the maximum is taken over all Abelian groups of order less than $n,$ over all their bases, over all computed systems. It is stated that if $m = o(\log \log n)$ for $n \to \infty$, than the asymptotic equality $L(n,m) \sim \log_2 n$ is valid. In addition, the asymptotic of the maximal possible difference of computation complexity of the systems of a finite Abelian group elements and the computation complexity of a monomial system corresponding to the representation of these elements over basis elements is obtained under the same conditions.