algebraeon_groups/composition_table/
partition.rs

1use algebraeon_sets::combinatorics::Partition;
2
3use super::group::*;
4use super::subset::*;
5use std::collections::HashSet;
6
7#[derive(Debug)]
8pub struct GroupPartition<'a> {
9    pub group: &'a FiniteGroupMultiplicationTable,
10    pub partition: Partition,
11    // is_left_cosets: Option<bool>,
12    // is_right_cosets: Option<bool>,
13}
14
15impl<'a> PartialEq for GroupPartition<'a> {
16    fn eq(&self, other: &Self) -> bool {
17        let grp = self.group;
18        if !std::ptr::eq(grp, other.group) {
19            return false;
20        }
21        let n = self.size();
22        if n != other.size() {
23            return false;
24        }
25        //check equality by comparing lookup lists
26        //equal iff lookups are equal up to permutation
27        //build up a permutation f from indicies of self.lookup to indicies of other.lookup
28        let mut f: Vec<Option<usize>> = vec![None; n];
29        for i in 0..grp.size() {
30            match f[self.partition.project(i)] {
31                Some(expected_other_lookup_i) => {
32                    if expected_other_lookup_i != other.partition.project(i) {
33                        return false;
34                    }
35                }
36                None => {
37                    f[self.partition.project(i)] = Some(other.partition.project(i));
38                }
39            }
40        }
41        true
42    }
43}
44
45impl<'a> Eq for GroupPartition<'a> {}
46
47impl<'a> GroupPartition<'a> {
48    pub fn check_state(&self) -> Result<(), &'static str> {
49        if self.partition.num_elements() != self.group.size() {
50            return Err("Partition is of set of the wrong size");
51        }
52        Ok(())
53    }
54
55    pub fn size(&self) -> usize {
56        self.partition.size()
57    }
58
59    pub fn is_left_cosets(&self) -> bool {
60        let ident_class = Subset::new_unchecked(
61            self.group,
62            self.partition.class_containing(self.group.ident()).clone(),
63        );
64        match ident_class.to_subgroup() {
65            Some(ident_subgroup) => &ident_subgroup.left_cosets() == self,
66            None => false,
67        }
68    }
69
70    pub fn is_right_cosets(&self) -> bool {
71        let ident_class = Subset::new_unchecked(
72            self.group,
73            self.partition.class_containing(self.group.ident()).clone(),
74        );
75        match ident_class.to_subgroup() {
76            Some(ident_subgroup) => &ident_subgroup.right_cosets() == self,
77            None => false,
78        }
79    }
80
81    pub fn is_congruence(&self) -> bool {
82        self.is_left_cosets() && self.is_right_cosets()
83    }
84
85    pub fn from_subsets(
86        group: &'a FiniteGroupMultiplicationTable,
87        subsets: Vec<HashSet<usize>>,
88    ) -> Result<Self, ()> {
89        let classes = subsets;
90        let mut lookup = vec![0; group.size()];
91        for (class_idx, class) in classes.iter().enumerate() {
92            for x in class {
93                if !(*x < group.size()) {
94                    return Err(());
95                }
96                lookup[*x] = class_idx;
97            }
98        }
99        let partition = Self {
100            group,
101            partition: Partition::new_unchecked(classes, lookup),
102        };
103        match partition.check_state() {
104            Ok(_) => {}
105            Err(_) => {
106                return Err(());
107            }
108        }
109        Ok(partition)
110    }
111}
112
113pub struct Congruence<'a> {
114    pub partition: GroupPartition<'a>,
115}
116
117impl<'a> Congruence<'a> {
118    pub fn check_state(&self) -> Result<(), &'static str> {
119        match self.partition.check_state() {
120            Ok(()) => {}
121            Err(msg) => {
122                return Err(msg);
123            }
124        }
125
126        match self.partition.is_congruence() {
127            false => return Err("congruence is not a congruence"),
128            true => {}
129        }
130
131        Ok(())
132    }
133
134    pub fn size(&self) -> usize {
135        self.partition.size()
136    }
137
138    pub fn quotient_group(&self) -> FiniteGroupMultiplicationTable {
139        let n = self.size();
140        self.partition.group.check_state().unwrap();
141        FiniteGroupMultiplicationTable::new_unchecked(
142            n,
143            self.partition
144                .partition
145                .project(self.partition.group.ident()),
146            {
147                let mut inv = vec![0; n];
148                for i in 0..n {
149                    inv[i] = self.partition.partition.project(
150                        self.partition
151                            .group
152                            .inv(*self.partition.partition.get_class(i).iter().next().unwrap()),
153                    );
154                }
155                inv
156            },
157            {
158                let mut mul = vec![vec![0; n]; n];
159                for i in 0..n {
160                    for j in 0..n {
161                        mul[i][j] = self.partition.partition.project(self.partition.group.mul(
162                            *self.partition.partition.get_class(i).iter().next().unwrap(),
163                            *self.partition.partition.get_class(j).iter().next().unwrap(),
164                        ));
165                    }
166                }
167                mul
168            },
169            None,
170            None,
171        )
172    }
173}
174
175#[cfg(test)]
176mod partition_tests {
177    use super::*;
178
179    #[test]
180    fn congruence_check_state() {
181        let grp = examples::symmetric_group_structure(4);
182        for (sg, _gens) in grp.subgroups() {
183            match sg.to_normal_subgroup() {
184                None => {
185                    let cong: Congruence<'_> = Congruence {
186                        partition: sg.left_cosets(),
187                    };
188                    match cong.check_state() {
189                        Ok(_) => panic!(),
190                        Err(_) => {}
191                    }
192                    let cong: Congruence<'_> = Congruence {
193                        partition: sg.right_cosets(),
194                    };
195                    match cong.check_state() {
196                        Ok(_) => panic!(),
197                        Err(_) => {}
198                    }
199                }
200                Some(nsg) => {
201                    let cong = nsg.cosets();
202                    match cong.check_state() {
203                        Ok(_) => {}
204                        Err(_) => panic!(),
205                    }
206                }
207            }
208        }
209    }
210}
algebraeon_groups/composition_table/partition.rs

algebraeon_groups/composition_table/
partition.rs
