algebraeon_groups/composition_table/
partition.rs

1use algebraeon_sets::combinatorics::Partition;
2
3use super::group::FiniteGroupMultiplicationTable;
4use super::subset::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 indices of self.lookup to indices of other.lookup
28        let mut f: Vec<Option<usize>> = vec![None; n];
29        #[allow(clippy::indexing_slicing)]
30        for i in 0..grp.size() {
31            match f[self.partition.project(i)] {
32                Some(expected_other_lookup_i) => {
33                    if expected_other_lookup_i != other.partition.project(i) {
34                        return false;
35                    }
36                }
37                None => {
38                    f[self.partition.project(i)] = Some(other.partition.project(i));
39                }
40            }
41        }
42        true
43    }
44}
45
46impl<'a> Eq for GroupPartition<'a> {}
47
48impl<'a> GroupPartition<'a> {
49    pub fn check_state(&self) -> Result<(), &'static str> {
50        if self.partition.num_elements() != self.group.size() {
51            return Err("Partition is of set of the wrong size");
52        }
53        Ok(())
54    }
55
56    pub fn size(&self) -> usize {
57        self.partition.size()
58    }
59
60    pub fn is_left_cosets(&self) -> bool {
61        let ident_class = Subset::new_unchecked(
62            self.group,
63            self.partition.class_containing(self.group.ident()).clone(),
64        );
65        match ident_class.to_subgroup() {
66            Some(ident_subgroup) => &ident_subgroup.left_cosets() == self,
67            None => false,
68        }
69    }
70
71    pub fn is_right_cosets(&self) -> bool {
72        let ident_class = Subset::new_unchecked(
73            self.group,
74            self.partition.class_containing(self.group.ident()).clone(),
75        );
76        match ident_class.to_subgroup() {
77            Some(ident_subgroup) => &ident_subgroup.right_cosets() == self,
78            None => false,
79        }
80    }
81
82    pub fn is_congruence(&self) -> bool {
83        self.is_left_cosets() && self.is_right_cosets()
84    }
85
86    pub fn from_subsets(
87        group: &'a FiniteGroupMultiplicationTable,
88        subsets: Vec<HashSet<usize>>,
89    ) -> Result<Self, ()> {
90        let classes = subsets;
91        let mut lookup = vec![0; group.size()];
92        for (class_idx, class) in classes.iter().enumerate() {
93            for x in class {
94                if *x >= group.size() {
95                    return Err(());
96                }
97                lookup[*x] = class_idx;
98            }
99        }
100        let partition = Self {
101            group,
102            partition: Partition::new_unchecked(classes, lookup),
103        };
104        match partition.check_state() {
105            Ok(()) => {}
106            Err(_) => {
107                return Err(());
108            }
109        }
110        Ok(partition)
111    }
112}
113
114pub struct Congruence<'a> {
115    pub partition: GroupPartition<'a>,
116}
117
118impl<'a> Congruence<'a> {
119    pub fn check_state(&self) -> Result<(), &'static str> {
120        match self.partition.check_state() {
121            Ok(()) => {}
122            Err(msg) => {
123                return Err(msg);
124            }
125        }
126
127        if !self.partition.is_congruence() {
128            return Err("congruence is not a congruence");
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    use crate::composition_table::group::examples;
179
180    #[test]
181    fn congruence_check_state() {
182        let grp = examples::symmetric_group_structure(4);
183        for (sg, _gens) in grp.subgroups() {
184            match sg.to_normal_subgroup() {
185                None => {
186                    let cong: Congruence<'_> = Congruence {
187                        partition: sg.left_cosets(),
188                    };
189                    if let Ok(()) = cong.check_state() {
190                        panic!();
191                    }
192                    let cong: Congruence<'_> = Congruence {
193                        partition: sg.right_cosets(),
194                    };
195                    if let Ok(()) = cong.check_state() {
196                        panic!();
197                    }
198                }
199                Some(nsg) => {
200                    let cong = nsg.cosets();
201                    if cong.check_state().is_err() {
202                        panic!();
203                    }
204                }
205            }
206        }
207    }
208}
algebraeon_groups/composition_table/partition.rs

algebraeon_groups/composition_table/
partition.rs
