×

On the complexity of the simultaneous calculation of three elements of a free abelian group with two generators. (Russian) Zbl 1249.94069

Summary: We study the complexity of the simultaneous calculation of three elements of a free Abelian group with two generators. By definition, the complexity \(l_F(A)\) of the set \(\Sigma=\{x_1^{a_{11}}x_2^{a_{12}}, x_1^{a_{21}}x_2^{a_{22}}, x_1^{a_{31}}x_2^{a_{32}}\}\) of elements of the free Abelian group with generators \(x_1\) and \(x_2\), generated by an integer matrix \(A = (a_{ij})\) of size \(3\times 2\), is equal to the minimum number of multiplications that is sufficient for the calculation of \(\Sigma\) using the generators \(x_1, x_2\) and inverse elements \(x_1^{-1}, x_2^{-1}\) (multiple use of the results of intermediate calculations is allowed).
We find an asymptotic behavior of \(l_F (A(n))\) for an arbitrary sequence of integer matrices \(A(n)=(a_{ij}(n))\) of size \(3\times 2\) such that \(\max_{i,j} a_{ij}(n)\to\infty\) as \(n\to\infty\).

MSC:

94B40 Arithmetic codes