algebraeon_groups/
group.rs1use algebraeon_nzq::integer::*;
2use algebraeon_nzq::natural::*;
3use itertools::Itertools;
4use std::{
5 borrow::Borrow,
6 collections::{HashMap, HashSet},
7 fmt::Debug,
8 hash::Hash,
9};
10
11pub trait Group: Debug + Clone + PartialEq + Eq {
12 fn identity() -> Self;
13
14 fn inverse(self) -> Self;
15 fn inverse_ref(&self) -> Self {
16 self.clone().inverse()
17 }
18
19 fn compose_mut(&mut self, other: &Self);
20 fn compose(mut a: Self, b: Self) -> Self {
21 Self::compose_mut(&mut a, &b);
22 a
23 }
24 fn compose_lref(a: &Self, b: Self) -> Self {
25 Self::compose(a.clone(), b)
26 }
27 fn compose_rref(a: Self, b: &Self) -> Self {
28 Self::compose(a, b.clone())
29 }
30 fn compose_refs(a: &Self, b: &Self) -> Self {
31 Self::compose(a.clone(), b.clone())
32 }
33
34 fn compose_list(elems: Vec<impl Borrow<Self>>) -> Self {
35 let mut ans = Self::identity();
36 for elem in elems {
37 ans.compose_mut(elem.borrow());
38 }
39 ans
40 }
41
42 fn nat_pow(&self, n: &Natural) -> Self {
43 if *n == Natural::ZERO {
44 Self::identity()
45 } else if *n == Natural::ONE {
46 self.clone()
47 } else {
48 debug_assert!(*n >= Natural::TWO);
49 let bits: Vec<_> = n.bits().collect();
50 let mut pows = vec![self.clone()];
51 while pows.len() < bits.len() {
52 pows.push(Self::compose_refs(
53 &pows.last().unwrap(),
54 &pows.last().unwrap(),
55 ));
56 }
57 let count = bits.len();
58 debug_assert_eq!(count, pows.len());
59 let mut ans = Self::identity();
60 for i in 0..count {
61 if bits[i] {
62 ans.compose_mut(&pows[i]);
63 }
64 }
65 ans
66 }
67 }
68
69 fn int_pow(&self, n: &Integer) -> Self {
70 if *n == Integer::ZERO {
71 Self::identity()
72 } else if *n > Integer::ZERO {
73 self.nat_pow(&n.unsigned_abs_ref())
74 } else {
75 self.nat_pow(&(-n).unsigned_abs()).inverse()
76 }
77 }
78
79 fn generated_finite_subgroup_table(
80 generators: Vec<Self>,
81 ) -> (
82 crate::composition_table::group::Group,
83 Vec<Self>,
84 HashMap<Self, usize>,
85 )
86 where
87 Self: std::hash::Hash,
88 {
89 let mut n = 0;
90 let mut idx_to_elem: Vec<Self> = vec![];
91 let mut elem_to_idx: HashMap<Self, usize> = HashMap::new();
92 let mut mul: Vec<Vec<Option<usize>>> = vec![];
93 let mut to_mul: Vec<(usize, usize)> = vec![];
94
95 macro_rules! add_elem {
96 ($elem : expr) => {{
97 debug_assert_eq!(idx_to_elem.len(), n);
98 debug_assert_eq!(elem_to_idx.len(), n);
99 debug_assert_eq!(mul.len(), n);
100 for m in &mul {
101 debug_assert_eq!(m.len(), n);
102 }
103 if !elem_to_idx.contains_key(&$elem) {
104 n += 1;
105 let k = elem_to_idx.len();
106 idx_to_elem.push($elem.clone());
107 elem_to_idx.insert($elem, k);
108 for i in (0..k) {
109 mul[i].push(None);
110 to_mul.push((i, k));
111 to_mul.push((k, i));
112 }
113 mul.push(vec![None; k + 1]);
114 to_mul.push((k, k));
115 k
116 } else {
117 *elem_to_idx.get(&$elem).unwrap()
118 }
119 }};
120 }
121
122 add_elem!(Self::identity());
123 for g in generators {
124 add_elem!(g);
125 }
126 while !to_mul.is_empty() {
127 let (i, j) = to_mul.pop().unwrap().clone();
128 let k = add_elem!(Self::compose_refs(&idx_to_elem[i], &idx_to_elem[j]));
129 debug_assert!(mul[i][j].is_none());
130 mul[i][j] = Some(k);
131 }
132 drop(to_mul);
133 let mul = mul
134 .into_iter()
135 .map(|m| m.into_iter().map(|x| x.unwrap()).collect_vec())
136 .collect_vec();
137 let inv = idx_to_elem
138 .iter()
139 .map(|elem| *elem_to_idx.get(&Self::inverse_ref(elem)).unwrap())
140 .collect_vec();
141
142 let grp = crate::composition_table::group::Group::new_unchecked(n, 0, inv, mul, None, None);
143
144 #[cfg(debug_assertions)]
145 grp.check_state().unwrap();
146
147 (grp, idx_to_elem, elem_to_idx)
148 }
149
150 fn generated_finite_subgroup(gens: Vec<Self>) -> FiniteSubgroup<Self>
151 where
152 Self: Hash,
153 {
154 let mut sg = HashSet::new();
156 sg.insert(Self::identity());
157
158 let mut boundary = vec![Self::identity()];
159 let mut next_boundary = vec![];
160 let mut y;
161 while boundary.len() > 0 {
162 println!("{}", sg.len());
163 for x in &boundary {
164 for g in &gens {
165 y = Self::compose_refs(x, g);
166 if !sg.contains(&y) {
167 sg.insert(y.clone());
168 next_boundary.push(y);
169 }
170 }
171 }
172 boundary = next_boundary.clone();
173 next_boundary = vec![];
174 }
175
176 FiniteSubgroup {
177 elems: sg.into_iter().collect(),
178 }
179 }
180}
181
182pub trait Pow<ExpT> {
183 fn pow(&self, exp: ExpT) -> Self;
184}
185impl<G: Group> Pow<Natural> for G {
186 fn pow(&self, exp: Natural) -> Self {
187 self.nat_pow(&exp)
188 }
189}
190impl<G: Group> Pow<u8> for G {
191 fn pow(&self, exp: u8) -> Self {
192 self.nat_pow(&Natural::from(exp))
193 }
194}
195impl<G: Group> Pow<u16> for G {
196 fn pow(&self, exp: u16) -> Self {
197 self.nat_pow(&Natural::from(exp))
198 }
199}
200impl<G: Group> Pow<u32> for G {
201 fn pow(&self, exp: u32) -> Self {
202 self.nat_pow(&Natural::from(exp))
203 }
204}
205impl<G: Group> Pow<u64> for G {
206 fn pow(&self, exp: u64) -> Self {
207 self.nat_pow(&Natural::from(exp))
208 }
209}
210impl<G: Group> Pow<Integer> for G {
211 fn pow(&self, exp: Integer) -> Self {
212 self.int_pow(&exp)
213 }
214}
215impl<G: Group> Pow<i8> for G {
216 fn pow(&self, exp: i8) -> Self {
217 self.int_pow(&Integer::from(exp))
218 }
219}
220impl<G: Group> Pow<i16> for G {
221 fn pow(&self, exp: i16) -> Self {
222 self.int_pow(&Integer::from(exp))
223 }
224}
225impl<G: Group> Pow<i32> for G {
226 fn pow(&self, exp: i32) -> Self {
227 self.int_pow(&Integer::from(exp))
228 }
229}
230impl<G: Group> Pow<i64> for G {
231 fn pow(&self, exp: i64) -> Self {
232 self.int_pow(&Integer::from(exp))
233 }
234}
235
236#[derive(Debug, Clone)]
237pub struct FiniteSubgroup<G: Group> {
238 elems: Vec<G>,
239}
240
241impl<G: Group> FiniteSubgroup<G> {
242 pub fn size(&self) -> usize {
243 self.elems.len()
244 }
245
246 pub fn elements(&self) -> impl Iterator<Item = &G> {
247 self.elems.iter()
248 }
249}