algebraeon_groups/composition_table/
subgroup.rs

1use std::collections::BTreeSet;
2use std::collections::HashSet;
3
4use algebraeon_sets::combinatorics::Partition;
5
6use super::group::*;
7use super::normal_subgroup::*;
8use super::partition::*;
9use super::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.len() > 0 {
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.len() > 0 {
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        match self.is_normal_subgroup() {
142            true => Some(NormalSubgroup::new_unchecked(self.clone())),
143            false => None,
144        }
145    }
146}
147
148#[cfg(test)]
149mod subgroup_tests {
150    use super::*;
151
152    #[test]
153    fn subgroup_counts() {
154        for (grp, num_sgs) in vec![
155            (examples::cyclic_group_structure(12), 6),
156            (examples::cyclic_group_structure(13), 2),
157            (examples::dihedral_group_structure(1), 2),
158            (examples::dihedral_group_structure(12), 34),
159            (examples::dihedral_group_structure(13), 16),
160            (examples::symmetric_group_structure(1), 1),
161            (examples::symmetric_group_structure(2), 2),
162            (examples::symmetric_group_structure(3), 6),
163            (examples::symmetric_group_structure(4), 30),
164            (examples::symmetric_group_structure(5), 156),
165        ] {
166            assert_eq!(grp.subgroups().len(), num_sgs);
167        }
168    }
169
170    #[test]
171    fn subgroup_state() {
172        //are the states of subgroups, normal subgroups, and generating sets correct when produced by grp.subgroups() and grp.normal_subgroups()?
173        for grp in vec![
174            examples::symmetric_group_structure(4),
175            examples::dihedral_group_structure(12),
176            examples::cyclic_group_structure(8),
177        ] {
178            let sgs = grp.subgroups();
179            for (sg, gens) in sgs {
180                // sg.is_normal_subgroup(); //cache is to check if the coset partition has the right is_congruence value
181                sg.check_state().unwrap();
182                gens.check_state().unwrap();
183                // sg.left_cosets().unwrap().check_state().unwrap();
184                // sg.right_cosets().unwrap().check_state().unwrap();
185            }
186        }
187    }
188
189    #[test]
190    fn subgroup_left_cosets() {
191        use crate::examples::symmetric::Permutation;
192
193        let (grp, _perms, elems) = Permutation::<3>::symmetric_composition_table();
194        let sg = Subgroup {
195            subset: Subset::new_unchecked(
196                &grp,
197                vec![
198                    elems[&Permutation::new([0, 1, 2]).unwrap()],
199                    elems[&Permutation::new([1, 0, 2]).unwrap()],
200                ]
201                .into_iter()
202                .collect(),
203            ),
204        };
205        sg.check_state().unwrap();
206        let cosets = sg.left_cosets();
207        cosets.check_state().unwrap();
208        assert_eq!(cosets.size(), 3);
209        assert!(
210            cosets
211                == GroupPartition::from_subsets(
212                    &grp,
213                    vec![
214                        vec![
215                            elems[&Permutation::new([0, 1, 2]).unwrap()],
216                            elems[&Permutation::new([1, 0, 2]).unwrap()],
217                        ]
218                        .into_iter()
219                        .collect(),
220                        vec![
221                            elems[&Permutation::new([1, 2, 0]).unwrap()],
222                            elems[&Permutation::new([2, 1, 0]).unwrap()],
223                        ]
224                        .into_iter()
225                        .collect(),
226                        vec![
227                            elems[&Permutation::new([2, 0, 1]).unwrap()],
228                            elems[&Permutation::new([0, 2, 1]).unwrap()],
229                        ]
230                        .into_iter()
231                        .collect()
232                    ]
233                )
234                .unwrap()
235        );
236    }
237
238    #[test]
239    fn subgroup_right_cosets() {
240        use crate::examples::symmetric::Permutation;
241
242        let (grp, _perms, elems) = Permutation::<3>::symmetric_composition_table();
243        let sg = Subgroup {
244            subset: Subset::new_unchecked(
245                &grp,
246                vec![
247                    elems[&Permutation::new([0, 1, 2]).unwrap()],
248                    elems[&Permutation::new([1, 0, 2]).unwrap()],
249                ]
250                .into_iter()
251                .collect(),
252            ),
253        };
254        sg.check_state().unwrap();
255        let cosets = sg.right_cosets();
256        println!("{:#?}", cosets);
257        cosets.check_state().unwrap();
258        assert_eq!(cosets.size(), 3);
259        assert!(
260            cosets
261                == GroupPartition::from_subsets(
262                    &grp,
263                    vec![
264                        vec![
265                            elems[&Permutation::new([0, 1, 2]).unwrap()],
266                            elems[&Permutation::new([1, 0, 2]).unwrap()],
267                        ]
268                        .into_iter()
269                        .collect(),
270                        vec![
271                            elems[&Permutation::new([1, 2, 0]).unwrap()],
272                            elems[&Permutation::new([0, 2, 1]).unwrap()],
273                        ]
274                        .into_iter()
275                        .collect(),
276                        vec![
277                            elems[&Permutation::new([2, 0, 1]).unwrap()],
278                            elems[&Permutation::new([2, 1, 0]).unwrap()],
279                        ]
280                        .into_iter()
281                        .collect()
282                    ]
283                )
284                .unwrap()
285        );
286    }
287}
algebraeon_groups/composition_table/subgroup.rs

algebraeon_groups/composition_table/
subgroup.rs
