ogdoad 1.0.0

//! The ADE root lattices: `A_n`, `D_n`, and `E_{6,7,8}`.
//!
//! A **root lattice** is generated by its norm-2 vectors (its *roots*). The
//! irreducible ones are classified by the simply-laced Dynkin diagrams `A`–`D`–`E`,
//! and each is recorded here by its Gram matrix in a basis of simple roots — which
//! for a simply-laced diagram *is* the Cartan matrix (`2` on the diagonal, `-1` for
//! each Dynkin edge, `0` otherwise). `D_n` is built instead from the explicit
//! geometric basis `{eᵢ − e_{i+1}} ∪ {e_{n-2}+e_{n-1}}` via `B·Bᵀ`, which sidesteps
//! the fork-indexing ambiguity; the determinant and kissing-number oracles pin
//! every construction.
//!
//! Numerology these satisfy (all checked in tests): `det A_n = n+1`, `det D_n = 4`,
//! `det E_{6,7,8} = 3, 2, 1`; kissing numbers (= number of roots) `n(n+1)`,
//! `2n(n−1)`, `72, 126, 240`; and the Coxeter number `h = #roots / rank` (an
//! irreducible root system has `n·h` roots), so [`coxeter_number`] is *computed*,
//! not tabulated.
//!
//! `E_8` is the unique rank-8 even unimodular lattice — the first place the char-0
//! mod-8 story (`witt::bw_class_real`, `BW(ℝ) = ℤ/8`) and the lattice world
//! visibly coincide; see root AGENTS.md. Its automorphism group is the Weyl group
//! `W(E_8)` of order 696729600, far past brute force but returned by
//! [`IntegralForm::automorphism_group_order`] from the standard Cartan basis or
//! from the basis-independent norm-2 root-system recognizer.

use crate::forms::IntegralForm;
use crate::linalg::integer::normalize_relation_rows;

/// `|W(E8)|`, the automorphism group order of the `E8` root lattice.
pub const E8_WEYL_GROUP_ORDER: u128 = 696_729_600;

/// Build the simply-laced Cartan/Gram matrix on `n` nodes from a Dynkin edge list.
fn cartan(n: usize, edges: &[(usize, usize)]) -> IntegralForm {
    let mut g = vec![vec![0i128; n]; n];
    for (i, row) in g.iter_mut().enumerate() {
        row[i] = 2;
    }
    for &(a, b) in edges {
        g[a][b] = -1;
        g[b][a] = -1;
    }
    IntegralForm::new(g).expect("Cartan matrix is symmetric")
}

/// `G = B·Bᵀ` for an integer basis matrix `B` (rows are the basis vectors in an
/// ambient orthonormal frame).
fn gram_from_basis(b: &[Vec<i128>]) -> IntegralForm {
    let n = b.len();
    let mut g = vec![vec![0i128; n]; n];
    for i in 0..n {
        for j in 0..n {
            g[i][j] = b[i].iter().zip(&b[j]).map(|(&x, &y)| x * y).sum();
        }
    }
    IntegralForm::new(g).expect("Gram matrix B·Bᵀ is symmetric")
}

/// The root lattice `A_n` (`n ≥ 1`): the Cartan matrix `2I − (adjacency of a path)`.
/// `det = n+1`, kissing number `n(n+1)`, Coxeter number `n+1`,
/// `|Aut| = 2` for `n = 1` and `2·(n+1)!` for `n ≥ 2`. Returns `None` for `n = 0`
/// (out of domain) — matching `niemeier.rs`'s `Option` contract for the same shape
/// of input, rather than panicking.
pub fn a_n(n: usize) -> Option<IntegralForm> {
    if n < 1 {
        return None;
    }
    let edges: Vec<(usize, usize)> = (0..n.saturating_sub(1)).map(|i| (i, i + 1)).collect();
    Some(cartan(n, &edges))
}

/// The root lattice `D_n` (`n ≥ 2`): `{x ∈ ℤⁿ : Σxᵢ even}`, built from the basis
/// `eᵢ − e_{i+1}` (`i = 0..n−1`) together with `e_{n-2} + e_{n-1}`. `det = 4`,
/// kissing number `2n(n−1)`, Coxeter number `2n−2`. Returns `None` for `n < 2`
/// (out of domain) — matching `niemeier.rs`'s `Option` contract for the same shape
/// of input, rather than panicking.
pub fn d_n(n: usize) -> Option<IntegralForm> {
    if n < 2 {
        return None;
    }
    let mut b = vec![vec![0i128; n]; n];
    for i in 0..n - 1 {
        b[i][i] = 1;
        b[i][i + 1] = -1;
    }
    b[n - 1][n - 2] = 1;
    b[n - 1][n - 1] = 1;
    Some(gram_from_basis(&b))
}

/// The root lattice `E_6`: `det = 3`, kissing number 72, Coxeter number 12.
pub fn e_6() -> IntegralForm {
    // Trivalent node 2; arms of length 2, 2, 1.
    cartan(6, &[(0, 1), (1, 2), (2, 3), (3, 4), (2, 5)])
}

/// The root lattice `E_7`: `det = 2`, kissing number 126, Coxeter number 18.
pub fn e_7() -> IntegralForm {
    // Trivalent node 2; arms of length 2, 3, 1.
    cartan(7, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (2, 6)])
}

/// The root lattice `E_8`: the unique rank-8 even unimodular lattice. `det = 1`,
/// kissing number 240, Coxeter number 30, `|Aut| = |W(E_8)| = 696729600`.
pub fn e_8() -> IntegralForm {
    // Trivalent node 4; arms of length 4, 2, 1.
    cartan(8, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (4, 7)])
}

/// The Coxeter number `h = #roots / rank` of an irreducible root lattice (an
/// irreducible root system has exactly `n·h` roots, all of norm 2). Returns
/// `None` if the lattice has no roots, is not positive definite, or the root
/// count is not divisible by the rank (i.e. the lattice is not an irreducible
/// root lattice with minimum 2).
pub fn coxeter_number(l: &IntegralForm) -> Option<i128> {
    if l.minimum()? != 2 {
        return None;
    }
    let roots = l.kissing_number()? as i128;
    let n = l.dim() as i128;
    if n == 0 || roots % n != 0 {
        return None;
    }
    Some(roots / n)
}

/// Whether `l` is a root lattice: positive definite with minimum 2, whose roots
/// (norm-2 minimal vectors) generate the whole lattice (index 1). The index is
/// read off the Hermite normal form of the root vectors — `[L : ⟨roots⟩]` is the
/// product of the HNF pivots, and the lattice is a root lattice exactly when that
/// product is 1.
pub fn is_root_lattice(l: &IntegralForm) -> bool {
    if !l.is_positive_definite() {
        return false;
    }
    let Some(min) = l.minimum() else {
        return false;
    };
    if min != 2 {
        return false;
    }
    let Some(roots) = l.minimal_vectors() else {
        return false;
    };
    let n = l.dim();
    let hnf = normalize_relation_rows(roots);
    if hnf.len() != n {
        return false; // roots span a proper-rank sublattice
    }
    // index [L : ⟨roots⟩] = ∏ (pivot of each HNF row); root lattice ⟺ index 1.
    let mut index = 1i128;
    for (i, row) in hnf.iter().enumerate() {
        index *= row[i]; // HNF is upper-triangular with the pivot on the diagonal
    }
    index == 1
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn a_n_invariants() {
        for n in 1..=5 {
            let l = a_n(n).unwrap();
            assert_eq!(l.determinant(), n as i128 + 1, "det A_{n}");
            assert_eq!(l.minimum(), Some(2));
            assert_eq!(l.kissing_number(), Some(n * (n + 1)), "kissing A_{n}");
            assert_eq!(coxeter_number(&l), Some(n as i128 + 1));
            assert!(is_root_lattice(&l));
        }
        // |Aut(A_1)| = 2; |Aut(A_n)| = 2·(n+1)! for n ≥ 2.
        assert_eq!(a_n(1).unwrap().automorphism_group_order(), Some(2));
        assert_eq!(a_n(2).unwrap().automorphism_group_order(), Some(12)); // 2·3!
        assert_eq!(a_n(3).unwrap().automorphism_group_order(), Some(48)); // 2·4!
        assert_eq!(a_n(4).unwrap().automorphism_group_order(), Some(240)); // 2·5!
                                                                           // n = 0 is out of domain.
        assert_eq!(a_n(0), None);
    }

    #[test]
    fn d_n_invariants() {
        for n in 2..=6 {
            let l = d_n(n).unwrap();
            assert_eq!(l.determinant(), 4, "det D_{n}");
            if n >= 3 {
                assert_eq!(l.minimum(), Some(2));
                assert_eq!(l.kissing_number(), Some(2 * n * (n - 1)), "kissing D_{n}");
                assert_eq!(coxeter_number(&l), Some(2 * n as i128 - 2));
                assert!(is_root_lattice(&l));
            }
        }
        // D_2 = A_1 ⊕ A_1 = ⟨2⟩ ⊕ ⟨2⟩.
        assert_eq!(
            d_n(2).unwrap().gram(),
            IntegralForm::diagonal(&[2, 2]).gram()
        );
        // |Aut(D_4)| = 1152 (triality), |Aut(D_5)| = 2^5·5! = 3840.
        assert_eq!(d_n(4).unwrap().automorphism_group_order(), Some(1152));
        assert_eq!(d_n(5).unwrap().automorphism_group_order(), Some(3840));
        // n < 2 is out of domain.
        assert_eq!(d_n(0), None);
        assert_eq!(d_n(1), None);
    }

    #[test]
    fn e_series_invariants() {
        let e6 = e_6();
        assert_eq!(e6.dim(), 6);
        assert_eq!(e6.determinant(), 3);
        assert!(e6.is_even());
        assert_eq!(e6.automorphism_group_order_bounded(1), Some(103_680));

        let e7 = e_7();
        assert_eq!(e7.dim(), 7);
        assert_eq!(e7.determinant(), 2);
        assert!(e7.is_even());
        assert_eq!(e7.automorphism_group_order_bounded(1), Some(2_903_040));

        let e8 = e_8();
        assert_eq!(e8.dim(), 8);
        assert_eq!(e8.determinant(), 1);
        assert!(e8.is_unimodular());
        assert!(e8.is_even());
        assert_eq!(e8.level(), Some(1));
        // |W(E_8)| = 696729600 is far past brute force but recognized by the
        // root-lattice fast path, even under a tiny fallback budget.
        assert_eq!(
            e8.automorphism_group_order_bounded(1),
            Some(E8_WEYL_GROUP_ORDER)
        );
    }

    #[test]
    fn root_lattice_predicate() {
        // ℤⁿ has minimum 1, not 2 ⇒ not a root lattice.
        assert!(!is_root_lattice(&IntegralForm::diagonal(&[1, 1, 1])));
        // ⟨4, 4⟩ has no roots at all (minimum 4).
        assert!(!is_root_lattice(&IntegralForm::diagonal(&[4, 4])));
        // Roots exist but do not span the lattice.
        assert!(!is_root_lattice(&IntegralForm::diagonal(&[2, 8])));
        // A_1³ = ⟨2,2,2⟩: the roots ±eᵢ are a basis ⇒ a (reducible) root lattice.
        assert!(is_root_lattice(&IntegralForm::diagonal(&[2, 2, 2])));
    }

    #[test]
    fn e8_is_the_unique_even_unimodular_rank8() {
        // Independent of the basis: even + unimodular + rank 8 ⇒ E_8.
        let e8 = e_8();
        assert!(e8.is_even() && e8.is_unimodular() && e8.dim() == 8);
        assert_eq!(e8.level(), Some(1));
    }
}