Linear Space Data Structures for Finite Groups with Constant Query-time

• Published in: arXiv.org 2023-03
• Main Authors: Das, Bireswar, Kumar, Anant, Sharma, Shivdutt, Thakkar, Dhara
• Format: Article
• Language: English
• Subjects: Data structures; Group theory; Information theory; Lower bounds; Queries
• ISSN: 2331-8422

A finite group of order \(n\) can be represented by its Cayley table. In the word-RAM model the Cayley table of a group of order \(n\) can be stored using \(O(n^2)\) words and can be used to answer a multiplication query in constant time. It is interesting to ask if we can design a data structure to store a group of order \(n\) that uses \(o(n^2)\) space but can still answer a multiplication query in constant time. We design a constant query-time data structure that can store any finite group using \(O(n)\) words where \(n\) is the order of the group. Farzan and Munro (ISSAC 2006) gave an information theoretic lower bound of \(\Omega(n)\) on the number of words to store a group of order \(n\). Since our data structure achieves this lower bound and answers queries in constant time, it is optimal in both space usage and query-time. A crucial step in the process is essentially to design linear space and constant query-time data structures for nonabelian simple groups. The data structures for nonableian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups (CFSG).