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

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...

Full description

Saved in:
Bibliographic Details
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
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:2331-8422