algebraeon_groups/
structure.rs1use algebraeon_nzq::traits::Abs;
2use algebraeon_nzq::{Integer, 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 #[allow(clippy::comparison_chain)]
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::FiniteGroupMultiplicationTable,
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 #[allow(clippy::manual_while_let_some)]
128 while !to_mul.is_empty() {
129 let (i, j) = to_mul.pop().unwrap();
130 let k = add_elem!(Self::compose_refs(&idx_to_elem[i], &idx_to_elem[j]));
131 debug_assert!(mul[i][j].is_none());
132 mul[i][j] = Some(k);
133 }
134 drop(to_mul);
135 let mul = mul
136 .into_iter()
137 .map(|m| m.into_iter().map(|x| x.unwrap()).collect_vec())
138 .collect_vec();
139 let inv = idx_to_elem
140 .iter()
141 .map(|elem| *elem_to_idx.get(&Self::inverse_ref(elem)).unwrap())
142 .collect_vec();
143
144 let grp = crate::composition_table::group::FiniteGroupMultiplicationTable::new_unchecked(
145 n, 0, inv, mul, None, None,
146 );
147
148 #[cfg(debug_assertions)]
149 grp.check_state().unwrap();
150
151 (grp, idx_to_elem, elem_to_idx)
152 }
153
154 #[allow(clippy::assigning_clones)]
155 fn generated_finite_subgroup(gens: Vec<Self>) -> FiniteSubgroup<Self>
156 where
157 Self: Hash,
158 {
159 let mut sg = HashSet::new();
161 sg.insert(Self::identity());
162
163 let mut boundary = vec![Self::identity()];
164 let mut next_boundary = vec![];
165 let mut y;
166 while !boundary.is_empty() {
167 println!("{}", sg.len());
168 for x in &boundary {
169 for g in &gens {
170 y = Self::compose_refs(x, g);
171 if !sg.contains(&y) {
172 sg.insert(y.clone());
173 next_boundary.push(y);
174 }
175 }
176 }
177 boundary = next_boundary.clone();
178 next_boundary = vec![];
179 }
180
181 FiniteSubgroup {
182 elems: sg.into_iter().collect(),
183 }
184 }
185}
186
187pub trait Pow<ExpT> {
188 fn pow(&self, exp: ExpT) -> Self;
189}
190impl<G: Group> Pow<Natural> for G {
191 fn pow(&self, exp: Natural) -> Self {
192 self.nat_pow(&exp)
193 }
194}
195impl<G: Group> Pow<u8> for G {
196 fn pow(&self, exp: u8) -> Self {
197 self.nat_pow(&Natural::from(exp))
198 }
199}
200impl<G: Group> Pow<u16> for G {
201 fn pow(&self, exp: u16) -> Self {
202 self.nat_pow(&Natural::from(exp))
203 }
204}
205impl<G: Group> Pow<u32> for G {
206 fn pow(&self, exp: u32) -> Self {
207 self.nat_pow(&Natural::from(exp))
208 }
209}
210impl<G: Group> Pow<u64> for G {
211 fn pow(&self, exp: u64) -> Self {
212 self.nat_pow(&Natural::from(exp))
213 }
214}
215impl<G: Group> Pow<Integer> for G {
216 fn pow(&self, exp: Integer) -> Self {
217 self.int_pow(&exp)
218 }
219}
220impl<G: Group> Pow<i8> for G {
221 fn pow(&self, exp: i8) -> Self {
222 self.int_pow(&Integer::from(exp))
223 }
224}
225impl<G: Group> Pow<i16> for G {
226 fn pow(&self, exp: i16) -> Self {
227 self.int_pow(&Integer::from(exp))
228 }
229}
230impl<G: Group> Pow<i32> for G {
231 fn pow(&self, exp: i32) -> Self {
232 self.int_pow(&Integer::from(exp))
233 }
234}
235impl<G: Group> Pow<i64> for G {
236 fn pow(&self, exp: i64) -> Self {
237 self.int_pow(&Integer::from(exp))
238 }
239}
240
241#[derive(Debug, Clone)]
242pub struct FiniteSubgroup<G: Group> {
243 elems: Vec<G>,
244}
245
246impl<G: Group> FiniteSubgroup<G> {
247 pub fn size(&self) -> usize {
248 self.elems.len()
249 }
250
251 pub fn elements(&self) -> impl Iterator<Item = &G> {
252 self.elems.iter()
253 }
254}