algebraeon_groups/composition_table/
subgroup.rs

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

algebraeon_groups/composition_table/
subgroup.rs
