Compact data structures for Dedekind groups and finite rings (Q2232236)

Let \(G\) be a finite group with \(n\) elements. Without loss of generality, it is assumed that \(G = \{1, \ldots , n\}\). The Cayley table for \(G\) is a two-dimensional table indexed by a pair of group elements \((i, j)\) such that the \((i, j)\)-th entry of the table is the product of \(i\) and \(j\). This product can be found in constant time. It needs \(O(n^2 \log n)\) bits or \(O(n^2)\) words in the word-RAM model to store the Cayley table. Furthermore, the number of words required to store a group in the word-RAM model is \(\Omega(n)\). A data structure that achieves the optimum information-theoretic lower bound asymptotically is known as a \textit{compact data structure}. The class of cyclic groups is the only class of groups that is known to have compact data structures while still retaining the capability to answer queries in constant time. In this paper, it is proved that the following classes of groups with \(n\) elements have compact data structures using \(O(n)\)-space and answers a multiplication query in constant time: Dedekind groups, groups whose indecomposable factors have this property, groups whose indecomposable factors are strongly indecomposable, groups defined as a semidirect product of groups with this property, and finite rings. For the entire collection see [Zbl 1470.68028].