Linear time algorithms for Abelian group isomorphism and related problems (Q2643019): Difference between revisions

The author shows that for a group \(G\), given by a multiplication table, the orders of all elements can be determined in time \(O(n)\), where \(n\) is the group order. The algorithm simply powers up elements until powers are known, the linear runtime is obtained by amortization analysis. This result implies that (nonconstructive) isomorphism of groups can be tested in time \(O(|G|)\). Usually algorithms for groups (see for example [\textit{D. F. Holt, B. Eick, E. A. O'Brien}, Handbook of computational group theory. Discrete Mathematics and its Applications. Boca Raton, FL: Chapman \& Hall/CRC Press (2005; Zbl 1091.20001)]) aim to work with a generating set such that the size of the input is much smaller than \(|G|\). One therefore would expect a sublinear runtime in \(O(\log(|G|)^k)\) for small \(k\). (If \(G\) is abelian and given by a presentation nonconstructive isomorphism simply requires a Smith normal form computation, which is known to be polynomial in the size of the generating set [\textit{R. Kannan} and \textit{A. Bachem}, SIAM J. Comput. 8, 499--507 (1979; Zbl 0446.65015)].)