On the Computation Complexity of the Systems of Finite Abelian Group Elements
V. V. Kochergin · Moscow University Mathematics Bulletin · 2023
The computation complexity 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$$ , then the asymptotic equality $$L(n,m)\sim\log_{2}n$$ is valid. In addition, the asymptotics of the maximal possible difference of computation complexity of the systems of 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.