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