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

• Published in: Algorithmica 2024-06, Vol.86 (6), p.1979-2025
• Main Authors: Das, Bireswar, Kumar, Anant, Sharma, Shivdutt, Thakkar, Dhara
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data structures; Data Structures and Information Theory; Group theory; Information theory; Lower bounds; Mathematics of Computing; Query processing; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-024-01212-9

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. Das et al. (J Comput Syst Sci 114:137–146, 2020) showed that for any finite group G of order n and for any δ ∈ [ 1 / log n , 1 ] , a data structure can be constructed for G that uses O ( n 1 + δ / δ ) space and answers a multiplication query in time O ( 1 / δ ) . Farzan and Munro (ISSAC, 2006) gave an information theoretic lower bound of Ω ( n ) on the number of words to store a group of order n . 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. Since our data structure achieves the information theoretic 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 nonabelian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups.