Compact Data Structures for Dedekind Groups and Finite Rings

A group with n elements can be stored using O(n²) space via its Cayley table which can answer a group multiplication query in O(1 ) time. Information theoretically it needs Ω(nlog n) bits or Ω(n) words in word-RAM model just to store a group (Farzan and Munro, ISSAC 2006). For functions s, t: N⟶ R<inf>≥ 0</inf>, we say that a data structure is an (O(s), O(t) ) -data structure if it uses O(s) space and answers a query in O(t) time. Except for cyclic groups it was not known if we can design (O(n), O(1 ) ) -data structure for interesting classes of groups. In this paper, we show that there exist (O(n), O(1 ) ) -data structures for several classes of groups and for any ring and thus achieve information theoretic lower bound asymptotically. More precisely, we show that there exist (O(n), O(1 ) ) -data structures for the following algebraic structures with n elements: Dedekind groups: This class contains abelian groups, Hamiltonian groups.Groups whose indecomposable factors admit (O(n), O(1 ) ) -data structures.Groups whose indecomposable factors are strongly indecomposable.Groups defined as a semidirect product of groups that admit (O(n), O(1 ) ) -data structures.Finite rings.