groups.rs

1use crate::rules::RULES;2use mrlymath::bang::symmetries;3use mrlymath::bang::universe::{apply, corner_index, corners, permutations};4use std::collections::BTreeSet;56pub type Elem = (Vec<usize>, Vec<u8>, bool);78pub fn act(code: usize, element: &Elem) -> usize {9    let cells = corners(3);10    let mut image = 0usize;11    for (i, cell) in cells.iter().enumerate() {12        if (code >> i) & 1 == 1 {13            image |= 1 << corner_index(&apply(&(element.0.clone(), element.1.clone()), cell));14        }15    }16    if element.2 {17        image ^= 0xff;18    }19    image20}2122fn flip(bits: usize) -> Vec<u8> {23    (0..3).map(|j| ((bits >> (2 - j)) & 1) as u8).collect()24}2526pub fn group(name: &str) -> Vec<Elem> {27    match name {28        "R" => vec![29            (vec![0, 1, 2], vec![0, 0, 0], false),30            (vec![2, 1, 0], vec![0, 0, 0], false),31        ],32        "H" => vec![33            (vec![0, 1, 2], vec![0, 0, 0], false),34            (vec![2, 1, 0], vec![0, 0, 0], false),35            (vec![0, 1, 2], vec![1, 1, 1], true),36            (vec![2, 1, 0], vec![1, 1, 1], true),37        ],38        "flips" => (0..8).map(|f| (vec![0, 1, 2], flip(f), false)).collect(),39        "perms" => permutations(3)40            .into_iter()41            .map(|p| (p, vec![0, 0, 0], false))42            .collect(),43        "B3" => symmetries(3)44            .into_iter()45            .map(|(p, f)| (p, f, false))46            .collect(),47        "B3xZ2" => symmetries(3)48            .into_iter()49            .flat_map(|(p, f)| [(p.clone(), f.clone(), false), (p.clone(), f.clone(), true)])50            .collect(),51        _ => unreachable!(),52    }53}5455pub fn orbit(code: usize, elements: &[Elem]) -> BTreeSet<usize> {56    elements.iter().map(|e| act(code, e)).collect()57}5859pub fn representatives(elements: &[Elem]) -> Vec<usize> {60    (0..RULES)61        .map(|code| {62            *orbit(code, elements)63                .iter()64                .next()65                .expect("an orbit is nonempty")66        })67        .collect()68}6970fn walk_count(elements: &[Elem]) -> usize {71    representatives(elements)72        .into_iter()73        .collect::<BTreeSet<_>>()74        .len()75}7677fn burnside(elements: &[Elem]) -> usize {78    let fixed: usize = elements79        .iter()80        .map(|e| (0..RULES).filter(|&c| act(c, e) == c).count())81        .sum();82    assert_eq!(fixed % elements.len(), 0, "Burnside sum is not divisible");83    fixed / elements.len()84}8586fn action(elements: &[Elem]) -> BTreeSet<Vec<usize>> {87    elements88        .iter()89        .map(|e| (0..RULES).map(|c| act(c, e)).collect())90        .collect()91}9293pub const NAMES: [&str; 6] = ["R", "H", "flips", "perms", "B3", "B3xZ2"];9495pub fn report() {96    println!("GROUP LATTICE");97    println!("group order classes burnside");98    let mut counts = Vec::new();99    for name in NAMES {100        let elements = group(name);101        let walk = walk_count(&elements);102        let burn = burnside(&elements);103        assert_eq!(walk, burn, "{name} disagrees with its Burnside average");104        println!("{name} {} {walk} {burn}", elements.len());105        counts.push((name, walk));106    }107    for (name, want) in [("H", 88), ("B3", 22), ("B3xZ2", 14)] {108        let got = counts109            .iter()110            .find(|(n, _)| *n == name)111            .expect("the group is listed")112            .1;113        assert_eq!(got, want, "{name} class count is not {want}");114    }115    let actions: Vec<(&str, BTreeSet<Vec<usize>>)> =116        NAMES.iter().map(|n| (*n, action(&group(n)))).collect();117    println!("containments");118    for (a, sa) in &actions {119        let inside: Vec<&str> = actions120            .iter()121            .filter(|(b, sb)| b != a && sa.is_subset(sb))122            .map(|(b, _)| *b)123            .collect();124        let inside = if inside.is_empty() {125            "nothing".to_string()126        } else {127            inside.join(" ")128        };129        println!("{a} sits inside {inside}");130    }131    let h = &actions.iter().find(|(n, _)| *n == "H").expect("H").1;132    let b3 = &actions.iter().find(|(n, _)| *n == "B3").expect("B3").1;133    let r = &actions.iter().find(|(n, _)| *n == "R").expect("R").1;134    let meet: BTreeSet<Vec<usize>> = h.intersection(b3).cloned().collect();135    assert_eq!(&meet, r, "H meets B3 outside the reflection group");136    assert!(!h.is_subset(b3), "H is a subgroup of B3");137    assert!(!b3.is_subset(h), "B3 is a subgroup of H");138    println!("H and B3 are incomparable and meet in R of order 2");139    println!("the walk is 256 -> 88 under H and 256 -> 22 under B3, two branches, joined at 14 under B3xZ2");140}