Group Decision Diagrams (GDDs): A Data Structure for Mathematical Groups

Groups are an element of abstract algebra that are used in a number of different domains such as physics, chemistry, statistics and cryptography. Set operations like union, intersection and cartesian product on groups are fundamental to more complex algorithms and methods of analysis in the aforementioned fields. A concise representation of groups can help improve the speed and ease at which binary operations like taking union and intersection can be carried out on them. In abstract algebra, a group is an infinite or finite set of elements that satisfies the axioms of closure, associativity, inverse and identity. For the purpose of this project we will only consider finite abelian group. If the group operation is commutative over a group it is called an abelian group. According to the fundamental theorem of finitely-generated abelian groups, a finite abelian group has a unique decomposition that allows it to be expressed as the direct product of cyclic groups. Further, cyclic groups can be described using a single element that generates the group. The existence of a unique decomposition for finite abelian groups makes it ideal to use a decision tree for its representation. A decision tree is a data structure where each parent node represents a decision and each child node is one of the outcomes. Our decision tree for groups can have each node be the generator representing a cyclic group from its decomposition. This data structure is based on the prior work of Shin-ichi Minato on permutation decision diagrams, that is, binary decision tree for storing sets of permutations, and subsequent work we did last summer. The decision diagram for a set of permutations is a decision tree with each node representing elemental transpositions obtained using a decomposition algorithm where if a permutation has an accepting path through the diagram, it is a member of the set. This project models a similar data structure for storing groups which will allow set operations to be carried out with relative efficiency on them just like it did for large sets of permutations using Python. We also conducted time analysis on the operations and found that multiplying two groups together takes the most amount of time using our data structure, followed by the transpose function which swaps all two indexes of every permutation in the data structure. Overall we found that our data structure is considerably effective in taking intersections and unions of group. However, some work needs to be done for a more effective implementation of multip[ly and transpose operations.