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