dynamics.rs

1use crate::groups::{group, orbit};2use crate::rules::{output, RULES};3use std::collections::BTreeSet;45fn arrows(rule: usize) -> Vec<(usize, usize, u8)> {6    let mut out = Vec::new();7    for a in 0..2u8 {8        for b in 0..2u8 {9            for c in 0..2u8 {10                out.push((11                    2 * a as usize + b as usize,12                    2 * b as usize + c as usize,13                    output(rule, a, b, c),14                ));15            }16        }17    }18    out19}2021pub fn surjective(rule: usize) -> bool {22    let edges = arrows(rule);23    let start = 0b1111usize;24    let mut seen = BTreeSet::from([start]);25    let mut stack = vec![start];26    while let Some(set) = stack.pop() {27        for label in 0..2u8 {28            let mut next = 0usize;29            for &(u, v, l) in &edges {30                if l == label && (set >> u) & 1 == 1 {31                    next |= 1 << v;32                }33            }34            if next == 0 {35                return false;36            }37            if seen.insert(next) {38                stack.push(next);39            }40        }41    }42    true43}4445pub fn balanced_to(rule: usize, length: usize) -> bool {46    let mut counts = vec![0u32; 1 << length];47    for source in 0..1usize << (length + 2) {48        let mut word = 0usize;49        for i in 0..length {50            let a = ((source >> i) & 1) as u8;51            let b = ((source >> (i + 1)) & 1) as u8;52            let c = ((source >> (i + 2)) & 1) as u8;53            word |= (output(rule, a, b, c) as usize) << i;54        }55        counts[word] += 1;56    }57    counts.iter().all(|&c| c == 4)58}5960pub fn injective(rule: usize) -> bool {61    let edges = arrows(rule);62    let mut adjacency = vec![BTreeSet::new(); 16];63    for &(u1, v1, l1) in &edges {64        for &(u2, v2, l2) in &edges {65            if l1 == l2 {66                adjacency[4 * u1 + u2].insert(4 * v1 + v2);67            }68        }69    }70    let mut core: BTreeSet<usize> = (0..16).collect();71    loop {72        let outs: BTreeSet<usize> = core73            .iter()74            .filter(|p| adjacency[**p].iter().any(|q| core.contains(q)))75            .copied()76            .collect();77        let ins: BTreeSet<usize> = outs78            .iter()79            .flat_map(|p| adjacency[*p].iter().filter(|q| outs.contains(q)).copied())80            .collect();81        let next: BTreeSet<usize> = outs.intersection(&ins).copied().collect();82        if next == core {83            break;84        }85        core = next;86    }87    !core.iter().any(|p| p / 4 != p % 4)88}8990pub fn surjective_set() -> Vec<usize> {91    (0..RULES).filter(|&r| surjective(r)).collect()92}9394pub fn injective_set() -> Vec<usize> {95    (0..RULES).filter(|&r| injective(r)).collect()96}9798pub fn report() {99    println!("GEOMETRY IS NOT DYNAMICS");100    let surj = surjective_set();101    let inj = injective_set();102    println!(103        "de Bruijn subset walk: {} surjective rules {surj:?}",104        surj.len()105    );106    let mut previous: Vec<usize> = (0..RULES).collect();107    let mut settles = None;108    for length in 1..=12 {109        let balanced: Vec<usize> = (0..RULES).filter(|&r| balanced_to(r, length)).collect();110        assert!(111            balanced.iter().all(|r| previous.contains(r)),112            "the balanced set grows from length {} to {length}",113            length - 1114        );115        assert!(116            surj.iter().all(|r| balanced.contains(r)),117            "a surjective rule is not balanced at length {length}"118        );119        println!(120            "balanced on words of length {length}: {} rules",121            balanced.len()122        );123        if balanced == surj && settles.is_none() {124            settles = Some(length);125        }126        previous = balanced;127    }128    let settles = settles.expect("the balance test never reaches the de Bruijn set");129    println!("the exact balance test on all words of length n shrinks monotonically and equals the de Bruijn set from n = {settles} to n = 12");130    if surj.len() == 30 {131        println!("the count is 30, the published figure");132    } else {133        println!(134            "UNCLEAR the count is {} against the published 30",135            surj.len()136        );137    }138    println!("pair-graph core: {} injective rules {inj:?}", inj.len());139    assert_eq!(140        inj,141        vec![15, 51, 85, 170, 204, 240],142        "the reversible rules are not the expected six"143    );144    assert!(145        inj.iter().all(|r| surj.contains(r)),146        "an injective rule is not surjective"147    );148    let b3 = group("B3");149    let identity_class: Vec<usize> = orbit(204, &b3).into_iter().collect();150    assert_eq!(151        inj, identity_class,152        "the reversible rules are not the B3 orbit of 204"153    );154    println!(155        "the reversible six are exactly the B3 orbit of 204, the single-axis degree-1 designs"156    );157    let surjective_flags: Vec<bool> = (0..RULES).map(|r| surj.contains(&r)).collect();158    let mut mixed = Vec::new();159    let mut constant_yes = 0usize;160    let mut constant_no = 0usize;161    let mut reps: Vec<usize> = (0..RULES)162        .map(|c| *orbit(c, &b3).iter().next().expect("nonempty"))163        .collect();164    reps.sort();165    reps.dedup();166    for rep in &reps {167        let cls: Vec<usize> = orbit(*rep, &b3).into_iter().collect();168        let yes: Vec<usize> = cls169            .iter()170            .copied()171            .filter(|c| surjective_flags[*c])172            .collect();173        let no: Vec<usize> = cls174            .iter()175            .copied()176            .filter(|c| !surjective_flags[*c])177            .collect();178        if yes.is_empty() {179            constant_no += 1;180        } else if no.is_empty() {181            constant_yes += 1;182        } else {183            mixed.push((*rep, cls.len(), yes, no));184        }185    }186    println!(187        "B3 classes: {constant_yes} all surjective, {constant_no} none surjective, {} mixed",188        mixed.len()189    );190    for (rep, size, yes, no) in &mixed {191        println!("mixed class rep {rep} size {size} surjective {yes:?} not {no:?}");192    }193    assert!(194        !mixed.is_empty(),195        "surjectivity is constant on every B3 class"196    );197    let thirty = orbit(30, &b3);198    assert!(thirty.contains(&54), "30 and 54 do not share a B3 orbit");199    assert!(200        surjective_flags[30] && !surjective_flags[54],201        "30 and 54 do not split on surjectivity"202    );203    println!("witness: 30 and 54 share the B3 orbit of rep 30, 30 is surjective and 54 is not");204    println!("surjectivity is not a B3 invariant, witnessed by 30 and 54 in one orbit");205    let mut reps: Vec<usize> = (0..RULES)206        .map(|c| *orbit(c, &b3).iter().next().expect("nonempty"))207        .collect();208    reps.sort();209    reps.dedup();210    let mut mixed_rev = 0usize;211    for rep in &reps {212        let cls: Vec<usize> = orbit(*rep, &b3).into_iter().collect();213        if cls.iter().any(|c| injective(*c)) && cls.iter().any(|c| !injective(*c)) {214            mixed_rev += 1;215        }216    }217    assert_eq!(218        mixed_rev, 0,219        "reversibility is not constant on every B3 orbit"220    );221    println!("reversibility IS constant on every B3 orbit, 0 mixed of {}, the reversible six being exactly the orbit of 204", reps.len());222    let mut mixed_h = 0usize;223    let h = group("H");224    let mut hreps: Vec<usize> = (0..RULES)225        .map(|c| *orbit(c, &h).iter().next().expect("nonempty"))226        .collect();227    hreps.sort();228    hreps.dedup();229    for rep in &hreps {230        let cls: Vec<usize> = orbit(*rep, &h).into_iter().collect();231        if cls.iter().any(|c| surjective_flags[*c]) && cls.iter().any(|c| !surjective_flags[*c]) {232            mixed_h += 1;233        }234    }235    println!(236        "H classes with mixed surjectivity: {mixed_h} of {}",237        hreps.len()238    );239}