algebraeon_groups/
structure.rs

1use algebraeon_macros::signature_meta_trait;
2use algebraeon_nzq::traits::Abs;
3use algebraeon_nzq::{Integer, Natural};
4use algebraeon_sets::structure::{MetaType, SetSignature};
5use std::borrow::Borrow;
6use std::collections::{HashMap, HashSet};
7
8/// A set with a binary operation of composition.
9#[signature_meta_trait]
10pub trait CompositionSignature: SetSignature {
11    fn compose(&self, a: &Self::Set, b: &Self::Set) -> Self::Set;
12    fn compose_mut(&self, a: &mut Self::Set, b: &Self::Set) {
13        *a = self.compose(a, b);
14    }
15}
16
17/// When composition is associative.
18#[signature_meta_trait]
19pub trait AssociativeCompositionSignature: CompositionSignature {
20    /// Returns `None` if the list is empty.
21    fn compose_nonempty_list(&self, mut elems: Vec<impl Borrow<Self::Set>>) -> Option<Self::Set> {
22        let mut total = elems.pop()?.borrow().clone();
23        for elem in elems {
24            total = self.compose(&total, elem.borrow());
25        }
26        Some(total)
27    }
28}
29
30/// When composition is commutative.
31#[signature_meta_trait]
32pub trait CommutativeCompositionSignature: CompositionSignature {}
33
34/// When `compose(a, x)` = `compose(a, y)` implies `x` = `y` for all `a`, `x`, `y`.
35#[signature_meta_trait]
36pub trait LeftCancellativeCompositionSignature: CompositionSignature {
37    /// Try to find `x` such that `a` = `compose(b, x)`.
38    fn try_left_difference(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set>;
39}
40
41/// When `compose(x, a)` = `compose(y, a)` implies `x` = `y` for all `a`, `x`, `y`.
42#[signature_meta_trait]
43pub trait RightCancellativeCompositionSignature: CompositionSignature {
44    /// Try to find `x` such that `a` = `compose(x, b)`.
45    fn try_right_difference(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set>;
46}
47
48#[signature_meta_trait]
49pub trait CancellativeCompositionSignature:
50    CommutativeCompositionSignature
51    + LeftCancellativeCompositionSignature
52    + RightCancellativeCompositionSignature
53{
54    fn try_difference(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set>;
55}
56impl<S: CancellativeCompositionSignature> LeftCancellativeCompositionSignature for S {
57    fn try_left_difference(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
58        self.try_difference(a, b)
59    }
60}
61impl<S: CancellativeCompositionSignature> RightCancellativeCompositionSignature for S {
62    fn try_right_difference(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
63        self.try_difference(a, b)
64    }
65}
66
67/// A set with a special element `e` called the identity element.
68#[signature_meta_trait]
69pub trait IdentitySignature: SetSignature {
70    /// Returns the identity element `e`.
71    fn identity(&self) -> Self::Set;
72}
73
74/// When the solution to `compose(x, a)` = `e` for `x` given `a` is unique whenever it exists.
75#[signature_meta_trait]
76pub trait TryLeftInverseSignature: IdentitySignature + CompositionSignature {
77    /// Return `x` such that `compose(x, a)` = `e` or `None` if no such `x` exists.
78    fn try_left_inverse(&self, a: &Self::Set) -> Option<Self::Set>;
79}
80
81/// When the solution to `compose(a, x)` = `e` for `x` given `a` is unique whenever it exists.
82#[signature_meta_trait]
83pub trait TryRightInverseSignature: IdentitySignature + CompositionSignature {
84    /// Return `x` such that `compose(a, x)` = `e` or `None` if no such `x` exists.
85    fn try_right_inverse(&self, a: &Self::Set) -> Option<Self::Set>;
86}
87
88/// When the solution to `compose(x, a)` = `compose(a, x)` = `e` for `x` given `a` is unique whenever it exists.
89#[signature_meta_trait]
90pub trait TryInverseSignature: IdentitySignature + CompositionSignature {
91    /// Return `x` such that `compose(x, a)` = `compose(a, x)` = `e` or `None` if no such `x` exists.
92    ///
93    /// Note, whenever `try_inverse` returns `Some`, `try_left_inverse` and `try_right_inverse` must also return the same value.
94    /// Also, whenever `try_left_inverse` and `try_right_inverse` both return a value, it must be the same value an `try_inverse` must also return that same value.
95    fn try_inverse(&self, a: &Self::Set) -> Option<Self::Set>;
96}
97
98impl<S: TryInverseSignature + CommutativeCompositionSignature> TryLeftInverseSignature for S {
99    fn try_left_inverse(&self, a: &Self::Set) -> Option<Self::Set> {
100        self.try_inverse(a)
101    }
102}
103
104impl<S: TryInverseSignature + CommutativeCompositionSignature> TryRightInverseSignature for S {
105    fn try_right_inverse(&self, a: &Self::Set) -> Option<Self::Set> {
106        self.try_inverse(a)
107    }
108}
109
110/// When `compose(x, e)` = `compose(e, x)` = `x` for all `x`.
111#[signature_meta_trait]
112pub trait MonoidSignature: IdentitySignature + AssociativeCompositionSignature {
113    fn compose_list(&self, elems: Vec<impl Borrow<Self::Set>>) -> Self::Set {
114        if elems.is_empty() {
115            self.identity()
116        } else {
117            self.compose_nonempty_list(elems).unwrap()
118        }
119    }
120
121    fn nat_pow(&self, a: &Self::Set, n: &Natural) -> Self::Set {
122        if *n == Natural::ZERO {
123            self.identity()
124        } else if *n == Natural::ONE {
125            a.clone()
126        } else {
127            debug_assert!(*n >= Natural::TWO);
128            let bits: Vec<_> = n.bits().collect();
129            let mut pows = vec![a.clone()];
130            while pows.len() < bits.len() {
131                pows.push(self.compose(pows.last().unwrap(), pows.last().unwrap()));
132            }
133            let count = bits.len();
134            debug_assert_eq!(count, pows.len());
135            let mut ans = self.identity();
136            for i in 0..count {
137                if bits[i] {
138                    ans = self.compose(&ans, &pows[i]);
139                }
140            }
141            ans
142        }
143    }
144}
145
146/// When inverses always exist.
147#[signature_meta_trait]
148pub trait GroupSignature:
149    MonoidSignature
150    + TryInverseSignature
151    + TryLeftInverseSignature
152    + TryRightInverseSignature
153    + LeftCancellativeCompositionSignature
154    + RightCancellativeCompositionSignature
155{
156    fn inverse(&self, a: &Self::Set) -> Self::Set;
157
158    fn int_pow(&self, a: &Self::Set, n: &Integer) -> Self::Set {
159        #[allow(clippy::comparison_chain)]
160        if *n == Integer::ZERO {
161            self.identity()
162        } else if *n > Integer::ZERO {
163            self.nat_pow(a, &n.abs())
164        } else {
165            self.nat_pow(&self.inverse(a), &n.abs())
166        }
167    }
168
169    fn generated_finite_subgroup_table(
170        &self,
171        generators: Vec<Self::Set>,
172    ) -> (
173        crate::composition_table::group::FiniteGroupMultiplicationTable,
174        Vec<Self::Set>,
175        HashMap<Self::Set, usize>,
176    )
177    where
178        Self::Set: std::hash::Hash + Eq,
179    {
180        let mut n = 0;
181        let mut idx_to_elem: Vec<Self::Set> = vec![];
182        let mut elem_to_idx: HashMap<Self::Set, usize> = HashMap::new();
183        let mut mul: Vec<Vec<Option<usize>>> = vec![];
184        let mut to_mul: Vec<(usize, usize)> = vec![];
185
186        macro_rules! add_elem {
187            ($elem : expr) => {{
188                debug_assert_eq!(idx_to_elem.len(), n);
189                debug_assert_eq!(elem_to_idx.len(), n);
190                debug_assert_eq!(mul.len(), n);
191                for m in &mul {
192                    debug_assert_eq!(m.len(), n);
193                }
194                if !elem_to_idx.contains_key(&$elem) {
195                    n += 1;
196                    let k = elem_to_idx.len();
197                    idx_to_elem.push($elem.clone());
198                    elem_to_idx.insert($elem, k);
199                    for i in (0..k) {
200                        mul[i].push(None);
201                        to_mul.push((i, k));
202                        to_mul.push((k, i));
203                    }
204                    mul.push(vec![None; k + 1]);
205                    to_mul.push((k, k));
206                    k
207                } else {
208                    *elem_to_idx.get(&$elem).unwrap()
209                }
210            }};
211        }
212
213        add_elem!(self.identity());
214        for g in generators {
215            add_elem!(g);
216        }
217        #[allow(clippy::manual_while_let_some)]
218        while !to_mul.is_empty() {
219            let (i, j) = to_mul.pop().unwrap();
220            let k = add_elem!(self.compose(&idx_to_elem[i], &idx_to_elem[j]));
221            debug_assert!(mul[i][j].is_none());
222            mul[i][j] = Some(k);
223        }
224        drop(to_mul);
225        let mul = mul
226            .into_iter()
227            .map(|m| m.into_iter().map(|x| x.unwrap()).collect::<Vec<_>>())
228            .collect::<Vec<_>>();
229        let inv = idx_to_elem
230            .iter()
231            .map(|elem| *elem_to_idx.get(&self.inverse(elem)).unwrap())
232            .collect::<Vec<_>>();
233
234        let grp = crate::composition_table::group::FiniteGroupMultiplicationTable::new_unchecked(
235            n, 0, inv, mul, None, None,
236        );
237
238        #[cfg(debug_assertions)]
239        grp.check_state().unwrap();
240
241        (grp, idx_to_elem, elem_to_idx)
242    }
243
244    fn generated_finite_subgroup(&self, gens: Vec<Self::Set>) -> FiniteSubgroup<Self::Set>
245    where
246        Self::Set: std::hash::Hash + Eq,
247    {
248        //generate subgroup by adding all generated elements
249        let mut sg = HashSet::new();
250        sg.insert(self.identity());
251
252        let mut boundary = vec![self.identity()];
253        let mut next_boundary = vec![];
254        let mut y;
255        while !boundary.is_empty() {
256            println!("{}", sg.len());
257            for x in &boundary {
258                for g in &gens {
259                    y = self.compose(x, g);
260                    if !sg.contains(&y) {
261                        sg.insert(y.clone());
262                        next_boundary.push(y);
263                    }
264                }
265            }
266            boundary = next_boundary.clone();
267            next_boundary = vec![];
268        }
269
270        FiniteSubgroup {
271            elems: sg.into_iter().collect(),
272        }
273    }
274}
275
276#[signature_meta_trait]
277pub trait AbelianGroupSignature:
278    GroupSignature + CommutativeCompositionSignature + CancellativeCompositionSignature
279{
280}
281impl<S: GroupSignature + CommutativeCompositionSignature + CancellativeCompositionSignature>
282    AbelianGroupSignature for S
283{
284}
285
286#[derive(Debug, Clone)]
287pub struct FiniteSubgroup<Set> {
288    elems: Vec<Set>,
289}
290
291impl<Set> FiniteSubgroup<Set> {
292    pub fn size(&self) -> usize {
293        self.elems.len()
294    }
295
296    pub fn elements(&self) -> impl Iterator<Item = &Set> {
297        self.elems.iter()
298    }
299}
algebraeon_groups/structure.rs

algebraeon_groups/
structure.rs
