algebraeon_groups/composition_table/
subgroup.rs

1use std::collections::BTreeSet;
2use std::collections::HashSet;
3
4use algebraeon_sets::combinatorics::Partition;
5
6use super::group::FiniteGroupMultiplicationTable;
7use super::normal_subgroup::NormalSubgroup;
8use super::partition::GroupPartition;
9use super::subset::Subset;
10use std::hash::Hash;
11
12#[derive(Clone)]
13pub struct Subgroup<'a> {
14    pub subset: Subset<'a>,
15}
16
17impl<'a> PartialEq for Subgroup<'a> {
18    fn eq(&self, other: &Self) -> bool {
19        self.subset == other.subset
20    }
21}
22
23impl<'a> Eq for Subgroup<'a> {}
24
25impl<'a> Hash for Subgroup<'a> {
26    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
27        self.subset
28            .elems()
29            .iter()
30            .collect::<BTreeSet<_>>()
31            .hash(state);
32    }
33}
34
35impl<'a> Subgroup<'a> {
36    pub fn check_state(&self) -> Result<(), &'static str> {
37        match self.subset.check_state() {
38            Ok(()) => {}
39            Err(msg) => {
40                return Err(msg);
41            }
42        }
43
44        if !self.subset.is_subgroup() {
45            return Err("subgroup is not closed under composition");
46        }
47
48        Ok(())
49    }
50
51    pub fn size(&self) -> usize {
52        self.subset.size()
53    }
54
55    pub fn to_group(&self) -> FiniteGroupMultiplicationTable {
56        let sg_elems: Vec<usize> = self.subset.elems().clone().into_iter().collect();
57        let k = sg_elems.len();
58        let mut group_to_subgroup: Vec<Option<usize>> = vec![None; self.subset.group().size()];
59        for (i, x) in sg_elems.iter().enumerate() {
60            group_to_subgroup[*x] = Some(i);
61        }
62        //TODO: add a test that this group has valid structure
63        FiniteGroupMultiplicationTable::new_unchecked(
64            self.size(),
65            group_to_subgroup[self.subset.group().ident()].unwrap(),
66            (0..k)
67                .map(|x| group_to_subgroup[self.subset.group().inv(sg_elems[x])].unwrap())
68                .collect(),
69            (0..k)
70                .map(|x| {
71                    (0..k)
72                        .map(|y| {
73                            group_to_subgroup[self.subset.group().mul(sg_elems[x], sg_elems[y])]
74                                .unwrap()
75                        })
76                        .collect()
77                })
78                .collect(),
79            None,
80            None,
81        )
82    }
83
84    pub fn left_cosets(&'_ self) -> GroupPartition<'_> {
85        let mut cosets: Vec<HashSet<usize>> = vec![];
86        let mut coset_lookup = vec![0; self.subset.group().size()];
87        let mut missing: HashSet<usize> = self.subset.group().elems().collect();
88        while !missing.is_empty() {
89            let g = missing.iter().next().unwrap();
90            let coset = self.subset.left_mul(*g).unwrap().elems().clone();
91            for h in &coset {
92                missing.remove(h);
93                coset_lookup[*h] = cosets.len();
94            }
95            cosets.push(coset);
96        }
97        GroupPartition {
98            group: self.subset.group(),
99            partition: Partition::new_unchecked(cosets, coset_lookup),
100        }
101    }
102
103    pub fn right_cosets(&'_ self) -> GroupPartition<'_> {
104        let mut cosets: Vec<HashSet<usize>> = vec![];
105        let mut coset_lookup = vec![0; self.subset.group().size()];
106        let mut missing: HashSet<usize> = self.subset.group().elems().collect();
107        while !missing.is_empty() {
108            let g = missing.iter().next().unwrap();
109            let coset = self.subset.right_mul(*g).unwrap().elems().clone();
110            for h in &coset {
111                missing.remove(h);
112                coset_lookup[*h] = cosets.len();
113            }
114            cosets.push(coset);
115        }
116        GroupPartition {
117            group: self.subset.group(),
118            partition: Partition::new_unchecked(cosets, coset_lookup),
119        }
120    }
121
122    pub fn is_normal_subgroup(&self) -> bool {
123        for x in self.subset.elems() {
124            for g in self.subset.group().elems() {
125                if !self.subset.elems().contains(
126                    &self
127                        .subset
128                        .group()
129                        .mul(self.subset.group().mul(g, *x), self.subset.group().inv(g)),
130                )
131                //gxg^{-1}
132                {
133                    return false;
134                }
135            }
136        }
137        true
138    }
139
140    pub fn to_normal_subgroup(&'_ self) -> Option<NormalSubgroup<'_>> {
141        if self.is_normal_subgroup() {
142            Some(NormalSubgroup::new_unchecked(self.clone()))
143        } else {
144            None
145        }
146    }
147}
148
149#[cfg(test)]
150mod subgroup_tests {
151    use super::*;
152    use crate::composition_table::group::examples;
153
154    #[test]
155    fn subgroup_counts() {
156        for (grp, num_sgs) in vec![
157            (examples::cyclic_group_structure(12), 6),
158            (examples::cyclic_group_structure(13), 2),
159            (examples::dihedral_group_structure(1), 2),
160            (examples::dihedral_group_structure(12), 34),
161            (examples::dihedral_group_structure(13), 16),
162            (examples::symmetric_group_structure(1), 1),
163            (examples::symmetric_group_structure(2), 2),
164            (examples::symmetric_group_structure(3), 6),
165            (examples::symmetric_group_structure(4), 30),
166            (examples::symmetric_group_structure(5), 156),
167        ] {
168            assert_eq!(grp.subgroups().len(), num_sgs);
169        }
170    }
171
172    #[test]
173    fn subgroup_state() {
174        //are the states of subgroups, normal subgroups, and generating sets correct when produced by grp.subgroups() and grp.normal_subgroups()?
175        for grp in [
176            examples::symmetric_group_structure(4),
177            examples::dihedral_group_structure(12),
178            examples::cyclic_group_structure(8),
179        ] {
180            let sgs = grp.subgroups();
181            for (sg, gens) in sgs {
182                // sg.is_normal_subgroup(); //cache is to check if the coset partition has the right is_congruence value
183                sg.check_state().unwrap();
184                gens.check_state().unwrap();
185                // sg.left_cosets().unwrap().check_state().unwrap();
186                // sg.right_cosets().unwrap().check_state().unwrap();
187            }
188        }
189    }
190
191    #[test]
192    fn subgroup_left_cosets() {
193        use crate::examples::symmetric::Permutation;
194
195        let (grp, _perms, elems) = Permutation::<3>::symmetric_composition_table();
196        let sg = Subgroup {
197            subset: Subset::new_unchecked(
198                &grp,
199                vec![
200                    elems[&Permutation::new([0, 1, 2]).unwrap()],
201                    elems[&Permutation::new([1, 0, 2]).unwrap()],
202                ]
203                .into_iter()
204                .collect(),
205            ),
206        };
207        sg.check_state().unwrap();
208        let cosets = sg.left_cosets();
209        cosets.check_state().unwrap();
210        assert_eq!(cosets.size(), 3);
211        assert!(
212            cosets
213                == GroupPartition::from_subsets(
214                    &grp,
215                    vec![
216                        vec![
217                            elems[&Permutation::new([0, 1, 2]).unwrap()],
218                            elems[&Permutation::new([1, 0, 2]).unwrap()],
219                        ]
220                        .into_iter()
221                        .collect(),
222                        vec![
223                            elems[&Permutation::new([1, 2, 0]).unwrap()],
224                            elems[&Permutation::new([2, 1, 0]).unwrap()],
225                        ]
226                        .into_iter()
227                        .collect(),
228                        vec![
229                            elems[&Permutation::new([2, 0, 1]).unwrap()],
230                            elems[&Permutation::new([0, 2, 1]).unwrap()],
231                        ]
232                        .into_iter()
233                        .collect()
234                    ]
235                )
236                .unwrap()
237        );
238    }
239
240    #[test]
241    fn subgroup_right_cosets() {
242        use crate::examples::symmetric::Permutation;
243
244        let (grp, _perms, elems) = Permutation::<3>::symmetric_composition_table();
245        let sg = Subgroup {
246            subset: Subset::new_unchecked(
247                &grp,
248                vec![
249                    elems[&Permutation::new([0, 1, 2]).unwrap()],
250                    elems[&Permutation::new([1, 0, 2]).unwrap()],
251                ]
252                .into_iter()
253                .collect(),
254            ),
255        };
256        sg.check_state().unwrap();
257        let cosets = sg.right_cosets();
258        println!("{:#?}", cosets);
259        cosets.check_state().unwrap();
260        assert_eq!(cosets.size(), 3);
261        assert!(
262            cosets
263                == GroupPartition::from_subsets(
264                    &grp,
265                    vec![
266                        vec![
267                            elems[&Permutation::new([0, 1, 2]).unwrap()],
268                            elems[&Permutation::new([1, 0, 2]).unwrap()],
269                        ]
270                        .into_iter()
271                        .collect(),
272                        vec![
273                            elems[&Permutation::new([1, 2, 0]).unwrap()],
274                            elems[&Permutation::new([0, 2, 1]).unwrap()],
275                        ]
276                        .into_iter()
277                        .collect(),
278                        vec![
279                            elems[&Permutation::new([2, 0, 1]).unwrap()],
280                            elems[&Permutation::new([2, 1, 0]).unwrap()],
281                        ]
282                        .into_iter()
283                        .collect()
284                    ]
285                )
286                .unwrap()
287        );
288    }
289}
algebraeon_groups/composition_table/subgroup.rs

algebraeon_groups/composition_table/
subgroup.rs
