algebraeon_groups/composition_table/

generating_set.rs

use std::collections::{BTreeSet, HashSet};

use super::group::FiniteGroupMultiplicationTable;
use super::homomorphism::Homomorphism;

pub struct GeneratingSet<'a> {
    group: &'a FiniteGroupMultiplicationTable,
    gens: Vec<usize>,       //subset of group which generates it
    elems: Vec<Vec<usize>>, //each element of group written as a product of gens
}

impl<'a> GeneratingSet<'a> {
    pub fn check_state(&self) -> Result<(), &'static str> {
        for g in &self.gens {
            if *g >= self.group.size() {
                return Err("bad generator");
            }
        }

        if self.elems.len() != self.group.size() {
            return Err("bad elems len");
        }

        for x in self.group.elems() {
            if x != self.group.mul_many(
                &self.elems[x]
                    .iter()
                    .map(|gen_idx| self.gens[*gen_idx])
                    .collect(),
            ) {
                return Err("incorrect word of gens for elem");
            }
        }

        Ok(())
    }

    pub fn size(&self) -> usize {
        self.gens.len()
    }

    pub fn gens(&self) -> &Vec<usize> {
        &self.gens
    }

    pub fn generated_homomorphism<'b>(
        &self,
        partial_func: &Vec<usize>,
        range_group: &'b FiniteGroupMultiplicationTable,
    ) -> Result<
        Option<
            Homomorphism<&'a FiniteGroupMultiplicationTable, &'b FiniteGroupMultiplicationTable>,
        >,
        &'static str,
    > {
        if partial_func.len() != self.gens.len() {
            return Err("partial func entries should correspond to images for each generator");
        }
        for x in partial_func {
            if *x >= range_group.size() {
                return Err("partial func has invalid element from range group");
            }
        }

        //try to make a function from self.group -> range sending self.gens -> the images as in partial_func
        let func: Vec<usize> = self
            .group
            .elems()
            .map(|x| {
                range_group.mul_many(&self.elems[x].iter().map(|g| partial_func[*g]).collect())
            })
            .collect();

        //check if func is a homomorphism i.e. f(xy) = f(x)f(y) for all x, y in range group
        //only need to check for all x and for all generators y
        for x in self.group.elems() {
            for g in &self.gens {
                if func[self.group.mul(x, *g)] != range_group.mul(func[x], func[*g]) {
                    return Ok(None);
                }
            }
        }

        Ok(Some(Homomorphism::new_unchecked(
            self.group,
            range_group,
            func,
        )))
    }
}

impl FiniteGroupMultiplicationTable {
    fn try_find_generating_set(&'_ self, max_size: Option<usize>) -> Result<GeneratingSet<'_>, ()> {
        let mut missing = HashSet::new();
        for x in self.elems() {
            missing.insert(x);
        }
        missing.remove(&self.ident());

        let mut sg = BTreeSet::new();
        sg.insert(self.ident());
        let mut gen_words = vec![vec![]; self.size()];
        gen_words[self.ident()] = vec![];
        let mut gens = vec![];
        #[allow(clippy::assigning_clones)]
        while sg.len() < self.size() {
            //if we are going to need more gens than max_size allows, then give up
            if let Some(max_size_val) = max_size
                && gens.len() == max_size_val
            {
                return Err(());
            }

            //add a new generator
            let new_g = *missing.iter().next().unwrap(); //random choice of new generator to try
            gens.push(new_g);

            //compute the subgroup generated by gens
            let mut y;
            let mut boundary: Vec<usize> = vec![];
            for s in sg.clone() {
                y = self.mul(s, new_g);
                if !sg.contains(&y) {
                    sg.insert(y);
                    missing.remove(&y);
                    gen_words[y] = gen_words[s].clone();
                    gen_words[y].push(gens.len() - 1);
                    boundary.push(y);
                }
            }
            let mut next_boundary: Vec<usize> = vec![];
            while !boundary.is_empty() {
                for x in &boundary {
                    for (g_idx, g) in gens.iter().enumerate() {
                        y = self.mul(*x, *g);
                        if !sg.contains(&y) {
                            sg.insert(y);
                            missing.remove(&y);
                            gen_words[y] = gen_words[*x].clone();
                            gen_words[y].push(g_idx);
                            next_boundary.push(y);
                        }
                    }
                }
                boundary = next_boundary.clone();
                next_boundary = vec![];
            }
        }

        Ok(GeneratingSet {
            group: self,
            gens,
            elems: gen_words,
        })
    }

    pub fn generating_set(&'_ self) -> GeneratingSet<'_> {
        self.try_find_generating_set(None).unwrap()
    }

    pub fn small_generating_set(&'_ self, attempts: Option<usize>) -> GeneratingSet<'_> {
        let a = attempts.unwrap_or(12);
        assert!(a > 0);

        let mut smallest_gens = self.generating_set();
        for _i in 0..a - 1 {
            if let Ok(gens) = self.try_find_generating_set(Some(smallest_gens.size() - 1)) {
                smallest_gens = gens;
            }
        }

        smallest_gens
    }
}

#[cfg(test)]
mod generating_set_tests {
    use crate::composition_table::group::examples;

    #[test]
    fn test_generating_set() {
        let grp = examples::cyclic_group_structure(10);
        let g_set = grp.generating_set();
        g_set.check_state().unwrap();

        let grp = examples::dihedral_group_structure(12);
        let g_set = grp.generating_set();
        g_set.check_state().unwrap();

        let grp = examples::symmetric_group_structure(4);
        let g_set = grp.generating_set();
        g_set.check_state().unwrap();

        let grp = examples::symmetric_group_structure(5);
        let g_set = grp.generating_set();
        g_set.check_state().unwrap();
    }
}