Comparing the computational complexity of monomials and elements of finite Abelian groups

V. V. Kochergin

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2022), pp. 6-11

Résumé

The complexity of the element $a_1^{k_1} a_2^{k_2} \ldots a_q^{k_q}$ of the Abelian group $\langle a_1 \rangle_{u_1} \times \langle a_2 \rangle_{u_2} \times \ldots$\break $\ldots \times \langle a_q \rangle_{u_q}$ (it is supposed that $k_i$ for all $i$) computation and the complexity of the term $x_1^{k_1} x_2^{k_2} \ldots x_q^{k_q}$ computation are compared in the paper. The complexity of computation means the minimal possible number of multiplication operations, and all the results of intermediate multiplications can be used multiple times. It it established that if $u_1 u_2 \ldots u_q \le n$, then the maximal possible difference and ratio of the above values asymptotically grow for $n\to \infty$ as $\log_2 /( \log_2 \log_2 n)$ and $\sqrt{\log_2} / (2 \log_2 \log_2 n)$, respectively.