Document Open Access Logo

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

Authors Bireswar Das, Anant Kumar, Shivdutt Sharma, Dhara Thakkar

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.25.pdf
  • Filesize: 0.7 MB
  • 17 pages

Document Identifiers

Author Details

Bireswar Das
  • Indian Institute of Technology Gandhinagar, India
Anant Kumar
  • Indian Institute of Technology Gandhinagar, India
Shivdutt Sharma
  • Indian Institute of Information Technology, Una, India
Dhara Thakkar
  • Indian Institute of Technology Gandhinagar, India

Funding

  • Das, Bireswar: Funded by Ministry of Education, Govt. of India.
  • Thakkar, Dhara: Funded by CSIR-UGC NET JRF Fellowship.

Cite As Get BibTex

Bireswar Das, Anant Kumar, Shivdutt Sharma, and Dhara Thakkar. Linear Space Data Structures for Finite Groups with Constant Query-Time. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.25

Abstract

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²) 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²) 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 Ω(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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
  • Theory of computation → Data compression
Keywords
  • Compact Data Structures
  • Space Efficient Representations
  • Finite Groups
  • Simple Groups
  • Classification Theorem for Finite Simple Groups

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Vikraman Arvind and Jacobo Torán. The complexity of quasigroup isomorphism and the minimum generating set problem. In International Symposium on Algorithms and Computation, pages 233-242. Springer, 2006. Google Scholar
  2. Vikraman Arvind and Jacobo Torán. Solvable group isomorphism is (almost) in NP ∩ conp. ACM Trans. Comput. Theory, 2(2):4:1-4:22, 2011. URL: https://doi.org/10.1145/1944857.1944859.
  3. M. Aschbacher. Finite Group Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2000. URL: https://doi.org/10.1017/CBO9781139175319.
  4. László Babai, Paolo Codenotti, and Youming Qiao. Polynomial-time isomorphism test for groups with no abelian normal subgroups. In International Colloquium on Automata, Languages, and Programming, pages 51-62. Springer, 2012. Google Scholar
  5. László Babai and Youming Qiao. Polynomial-time isomorphism test for groups with abelian sylow towers. In STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), volume 14, pages 453-464. LIPIcs, 2012. Google Scholar
  6. Roger W. Carter. Finite groups of Lie type. Wiley Classics Library. John Wiley & Sons, Ltd., Chichester, 1993. Conjugacy classes and complex characters, Reprint of the 1985 original, A Wiley-Interscience Publication. Google Scholar
  7. J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson. ATLAS of Finite Groups. Oxford University Press, Eynsham, 1985. Maximal subgroups and ordinary characters for simple groups, With computational assistance from J. G. Thackray. Google Scholar
  8. Bireswar Das and Shivdutt Sharma. Compact data structures for dedekind groups and finite rings. In WALCOM, pages 90-102, 2021. Google Scholar
  9. Bireswar Das, Shivdutt Sharma, and P. R. Vaidyanathan. Space efficient representations of finite groups. J. Comput. Syst. Sci., 114:137-146, 2020. URL: https://doi.org/10.1016/j.jcss.2020.06.007.
  10. David S. Dummit and Richard M. Foote. Abstract algebra. John Wiley & Sons, Inc., Hoboken, NJ, third edition, 2004. Google Scholar
  11. Arash Farzan and J. Ian Munro. Succinct representation of finite abelian groups. In ISSAC 2006, pages 87-92. ACM, New York, 2006. Google Scholar
  12. Merrick Furst, John Hopcroft, and Eugene Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 36-41. IEEE, 1980. Google Scholar
  13. François Le Gall. Efficient isomorphism testing for a class of group extensions. CoRR, abs/0812.2298, 2008. URL: http://arxiv.org/abs/0812.2298.
  14. T. Kavitha. Linear time algorithms for abelian group isomorphism and related problems. J. Comput. System Sci., 73(6):986-996, 2007. Google Scholar
  15. Neeraj Kayal and Timur Nezhmetdinov. Factoring groups efficiently. In International colloquium on automata, languages, and programming, pages 585-596. Springer, 2009. Google Scholar
  16. Peter B. Kleidman and Martin W. Liebeck. The Subgroup Structure of the Finite Classical Groups. London Mathematical Society Lecture Note Series. Cambridge University Press, 1990. URL: https://doi.org/10.1017/CBO9780511629235.
  17. Daniel J. Kleitman, Bruce R. Rothschild, and Joel H. Spencer. The number of semigroups of order n. Proc. Amer. Math. Soc., 55(1):227-232, 1976. Google Scholar
  18. S Ravi Kumar and Ronitt Rubinfeld. Property testing of abelian group operations, 1998. Google Scholar
  19. Gary L. Miller. On the n^log n isomorphism technique: A preliminary report. In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 51-58. ACM, 1978. Google Scholar
  20. Youming Qiao, Jayalal Sarma, and Bangsheng Tang. On isomorphism testing of groups with normal hall subgroups. J. Comput. Sci. Technol., 27(4):687-701, 2012. URL: https://doi.org/10.1007/s11390-012-1255-7.
  21. Joseph J. Rotman. An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics. Springer-Verlag, New York, fourth edition, 1995. Google Scholar
  22. Ákos Seress. Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2003. Google Scholar
  23. Charles C. Sims. Computational methods in the study of permutation groups. In John Leech, editor, Computational Problems in Abstract Algebra, pages 169-183. Pergamon, 1970. URL: https://doi.org/10.1016/B978-0-08-012975-4.50020-5.
  24. Charles C Sims. Computation with permutation groups. In Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, pages 23-28, 1971. Google Scholar
  25. Charles C. Sims. Computation with finitely presented groups, volume 48 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1994. Google Scholar
  26. J. H. van Lint and R. M. Wilson. A course in combinatorics. Cambridge University Press, Cambridge, 1992. Google Scholar
  27. Robert A. Wilson. The finite simple groups, volume 251 of Graduate Texts in Mathematics. Springer-Verlag London, Ltd., London, 2009. URL: https://doi.org/10.1007/978-1-84800-988-2.
  28. Robert A. Wilson. Maximal subgroups of sporadic groups. In Finite simple groups: thirty years of the atlas and beyond, volume 694 of Contemp. Math., pages 57-72. Amer. Math. Soc., Providence, RI, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact