atlas_embeddings/cartan/
mod.rs

1//! Cartan Matrices and Dynkin Diagrams
2//!
3//! This module provides Cartan matrix representations for Lie algebras,
4//! with compile-time rank verification and exact integer arithmetic.
5//!
6//! # Cartan Matrix
7//!
8//! A Cartan matrix C is an n×n integer matrix satisfying:
9//! 1. Diagonal entries C\[i\]\[i\] = 2
10//! 2. Off-diagonal entries C\[i\]\[j\] ≤ 0 for i ≠ j
11//! 3. C\[i\]\[j\] = 0 ⟺ C\[j\]\[i\] = 0
12//!
13//! # Simply-Laced
14//!
15//! A Cartan matrix is **simply-laced** if all off-diagonal entries are in {0, -1}.
16//! The exceptional simply-laced groups are E₆, E₇, E₈.
17//! Non-simply-laced exceptional groups are G₂ (triple bond), F₄ (double bond).
18//!
19//! # Examples
20//!
21//! ```
22//! use atlas_embeddings::cartan::CartanMatrix;
23//!
24//! // G₂ Cartan matrix (rank 2, triple bond)
25//! let g2 = CartanMatrix::new([
26//!     [ 2, -3],
27//!     [-1,  2],
28//! ]);
29//! assert_eq!(g2.rank(), 2);
30//! assert!(!g2.is_simply_laced());
31//! assert!(g2.is_valid());
32//!
33//! // F₄ Cartan matrix (rank 4, double bond)
34//! let f4 = CartanMatrix::new([
35//!     [ 2, -1,  0,  0],
36//!     [-1,  2, -2,  0],
37//!     [ 0, -1,  2, -1],
38//!     [ 0,  0, -1,  2],
39//! ]);
40//! assert_eq!(f4.rank(), 4);
41//! assert!(!f4.is_simply_laced());
42//! ```
43
44/// Cartan matrix for a Lie algebra
45///
46/// The type parameter `N` encodes the rank at compile time.
47/// All entries are exact integers (no floating point).
48#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
49pub struct CartanMatrix<const N: usize> {
50    entries: [[i8; N]; N],
51}
52
53impl<const N: usize> CartanMatrix<N> {
54    /// Create a new Cartan matrix
55    ///
56    /// # Examples
57    ///
58    /// ```
59    /// use atlas_embeddings::cartan::CartanMatrix;
60    ///
61    /// let g2 = CartanMatrix::new([
62    ///     [ 2, -3],
63    ///     [-1,  2],
64    /// ]);
65    /// ```
66    #[must_use]
67    pub const fn new(entries: [[i8; N]; N]) -> Self {
68        Self { entries }
69    }
70
71    /// Get the rank (dimension) of the Cartan matrix
72    #[must_use]
73    pub const fn rank(&self) -> usize {
74        N
75    }
76
77    /// Get entry at position (i, j)
78    ///
79    /// # Panics
80    ///
81    /// Panics if indices are out of bounds
82    #[must_use]
83    pub const fn get(&self, i: usize, j: usize) -> i8 {
84        self.entries[i][j]
85    }
86
87    /// Get all entries as a 2D array
88    #[must_use]
89    pub const fn entries(&self) -> &[[i8; N]; N] {
90        &self.entries
91    }
92
93    /// Check if this is a valid Cartan matrix
94    ///
95    /// Verifies:
96    /// 1. Diagonal entries = 2
97    /// 2. Off-diagonal entries ≤ 0
98    /// 3. Symmetry condition: C\[i\]\[j\] = 0 ⟺ C\[j\]\[i\] = 0
99    #[must_use]
100    pub fn is_valid(&self) -> bool {
101        // Check diagonal = 2
102        for i in 0..N {
103            if self.entries[i][i] != 2 {
104                return false;
105            }
106        }
107
108        // Check off-diagonal ≤ 0 and symmetry condition
109        for i in 0..N {
110            for j in 0..N {
111                if i != j {
112                    // Off-diagonal must be non-positive
113                    if self.entries[i][j] > 0 {
114                        return false;
115                    }
116
117                    // Symmetry condition: zero iff other is zero
118                    let is_zero_ij = self.entries[i][j] == 0;
119                    let is_zero_ji = self.entries[j][i] == 0;
120                    if is_zero_ij != is_zero_ji {
121                        return false;
122                    }
123                }
124            }
125        }
126
127        true
128    }
129
130    /// Check if the Cartan matrix is simply-laced
131    ///
132    /// A Cartan matrix is simply-laced if all off-diagonal entries are in {0, -1}.
133    /// The simply-laced exceptional groups are E₆, E₇, E₈.
134    #[must_use]
135    pub fn is_simply_laced(&self) -> bool {
136        for i in 0..N {
137            for j in 0..N {
138                if i != j {
139                    let entry = self.entries[i][j];
140                    if entry != 0 && entry != -1 {
141                        return false;
142                    }
143                }
144            }
145        }
146        true
147    }
148
149    /// Check if the matrix is symmetric
150    ///
151    /// A symmetric Cartan matrix corresponds to a simply-laced group.
152    #[must_use]
153    pub fn is_symmetric(&self) -> bool {
154        for i in 0..N {
155            for j in 0..N {
156                if self.entries[i][j] != self.entries[j][i] {
157                    return false;
158                }
159            }
160        }
161        true
162    }
163
164    /// Compute determinant of the Cartan matrix
165    ///
166    /// Uses exact integer arithmetic (no floating point).
167    /// For small ranks (≤ 8), uses direct computation.
168    #[must_use]
169    pub fn determinant(&self) -> i64 {
170        match N {
171            1 => i64::from(self.entries[0][0]),
172            2 => {
173                let a = i64::from(self.entries[0][0]);
174                let b = i64::from(self.entries[0][1]);
175                let c = i64::from(self.entries[1][0]);
176                let d = i64::from(self.entries[1][1]);
177                a * d - b * c
178            },
179            3 => self.determinant_3x3(),
180            4 => self.determinant_4x4(),
181            _ => self.determinant_general(),
182        }
183    }
184
185    /// Determinant for 3×3 matrix
186    fn determinant_3x3(&self) -> i64 {
187        let m = &self.entries;
188        let a = i64::from(m[0][0]);
189        let b = i64::from(m[0][1]);
190        let c = i64::from(m[0][2]);
191        let d = i64::from(m[1][0]);
192        let e = i64::from(m[1][1]);
193        let f = i64::from(m[1][2]);
194        let g = i64::from(m[2][0]);
195        let h = i64::from(m[2][1]);
196        let i = i64::from(m[2][2]);
197
198        a * (e * i - f * h) - b * (d * i - f * g) + c * (d * h - e * g)
199    }
200
201    /// Determinant for 4×4 matrix
202    fn determinant_4x4(&self) -> i64 {
203        let m = &self.entries;
204        let mut det = 0_i64;
205
206        // Expansion by first row
207        for j in 0..4 {
208            let sign = if j % 2 == 0 { 1 } else { -1 };
209            let cofactor = self.minor_3x3(0, j);
210            det += sign * i64::from(m[0][j]) * cofactor;
211        }
212
213        det
214    }
215
216    /// Compute 3×3 minor (for 4×4 determinant)
217    fn minor_3x3(&self, skip_row: usize, skip_col: usize) -> i64 {
218        let mut minor = [[0_i8; 3]; 3];
219        let mut mi = 0;
220
221        for i in 0..4 {
222            if i == skip_row {
223                continue;
224            }
225            let mut mj = 0;
226            for j in 0..4 {
227                if j == skip_col {
228                    continue;
229                }
230                minor[mi][mj] = self.entries[i][j];
231                mj += 1;
232            }
233            mi += 1;
234        }
235
236        let a = i64::from(minor[0][0]);
237        let b = i64::from(minor[0][1]);
238        let c = i64::from(minor[0][2]);
239        let d = i64::from(minor[1][0]);
240        let e = i64::from(minor[1][1]);
241        let f = i64::from(minor[1][2]);
242        let g = i64::from(minor[2][0]);
243        let h = i64::from(minor[2][1]);
244        let i = i64::from(minor[2][2]);
245
246        a * (e * i - f * h) - b * (d * i - f * g) + c * (d * h - e * g)
247    }
248
249    /// General determinant computation (for larger matrices)
250    ///
251    /// Uses Laplace expansion (slow but exact)
252    fn determinant_general(&self) -> i64 {
253        if N == 0 {
254            return 1;
255        }
256        if N == 1 {
257            return i64::from(self.entries[0][0]);
258        }
259
260        let mut det = 0_i64;
261
262        // Expansion by first row
263        for j in 0..N {
264            let sign = if j % 2 == 0 { 1 } else { -1 };
265            let cofactor = self.minor_general(0, j);
266            det += sign * i64::from(self.entries[0][j]) * cofactor;
267        }
268
269        det
270    }
271
272    /// Compute general minor (recursive)
273    fn minor_general(&self, skip_row: usize, skip_col: usize) -> i64 {
274        if N <= 1 {
275            return 1;
276        }
277
278        // Build (N-1)×(N-1) minor matrix
279        let mut minor_entries = vec![vec![0_i8; N - 1]; N - 1];
280        let mut mi = 0;
281
282        for i in 0..N {
283            if i == skip_row {
284                continue;
285            }
286            let mut mj = 0;
287            for j in 0..N {
288                if j == skip_col {
289                    continue;
290                }
291                minor_entries[mi][mj] = self.entries[i][j];
292                mj += 1;
293            }
294            mi += 1;
295        }
296
297        // Recursive determinant computation
298        Self::determinant_recursive(&minor_entries, N - 1)
299    }
300
301    /// Recursive determinant helper
302    fn determinant_recursive(matrix: &[Vec<i8>], size: usize) -> i64 {
303        if size == 1 {
304            return i64::from(matrix[0][0]);
305        }
306        if size == 2 {
307            let a = i64::from(matrix[0][0]);
308            let b = i64::from(matrix[0][1]);
309            let c = i64::from(matrix[1][0]);
310            let d = i64::from(matrix[1][1]);
311            return a * d - b * c;
312        }
313
314        let mut det = 0_i64;
315
316        for j in 0..size {
317            let sign = if j % 2 == 0 { 1 } else { -1 };
318
319            // Build minor
320            let mut minor = vec![vec![0_i8; size - 1]; size - 1];
321            for i in 1..size {
322                let mut mj = 0;
323                for k in 0..size {
324                    if k == j {
325                        continue;
326                    }
327                    minor[i - 1][mj] = matrix[i][k];
328                    mj += 1;
329                }
330            }
331
332            det += sign * i64::from(matrix[0][j]) * Self::determinant_recursive(&minor, size - 1);
333        }
334
335        det
336    }
337
338    /// Find connected components in Dynkin diagram
339    ///
340    /// Returns the number of connected components.
341    /// A connected Cartan matrix has exactly 1 component.
342    #[must_use]
343    pub fn num_connected_components(&self) -> usize {
344        let mut visited = vec![false; N];
345        let mut num_components = 0;
346
347        for start in 0..N {
348            if !visited[start] {
349                // BFS from this node
350                let mut queue = vec![start];
351                visited[start] = true;
352
353                while let Some(i) = queue.pop() {
354                    #[allow(clippy::needless_range_loop)]
355                    for j in 0..N {
356                        if i != j && !visited[j] && self.entries[i][j] != 0 {
357                            visited[j] = true;
358                            queue.push(j);
359                        }
360                    }
361                }
362
363                num_components += 1;
364            }
365        }
366
367        num_components
368    }
369
370    /// Check if Cartan matrix is connected (indecomposable)
371    #[must_use]
372    pub fn is_connected(&self) -> bool {
373        self.num_connected_components() == 1
374    }
375
376    /// Extract Dynkin diagram from Cartan matrix
377    ///
378    /// Computes bonds between simple roots based on Cartan matrix entries.
379    /// Bond multiplicity is determined by |Cᵢⱼ × Cⱼᵢ|:
380    /// - 1 = single bond (—)
381    /// - 2 = double bond (⇒) for F₄
382    /// - 3 = triple bond (≡) for G₂
383    ///
384    /// # Examples
385    ///
386    /// ```
387    /// use atlas_embeddings::cartan::CartanMatrix;
388    ///
389    /// let g2 = CartanMatrix::g2();
390    /// let dynkin = g2.to_dynkin_diagram("G₂");
391    ///
392    /// assert_eq!(dynkin.rank(), 2);
393    /// assert_eq!(dynkin.bonds().len(), 1);
394    /// assert_eq!(dynkin.bonds()[0].2, 3); // Triple bond
395    /// ```
396    #[must_use]
397    pub fn to_dynkin_diagram(&self, group_name: &str) -> DynkinDiagram<N> {
398        DynkinDiagram::from_cartan(self, group_name)
399    }
400}
401
402/// Standard Cartan matrices for exceptional groups
403impl CartanMatrix<2> {
404    /// G₂ Cartan matrix
405    ///
406    /// ```text
407    /// [ 2  -3]
408    /// [-1   2]
409    /// ```
410    #[must_use]
411    pub const fn g2() -> Self {
412        Self::new([[2, -3], [-1, 2]])
413    }
414}
415
416impl CartanMatrix<4> {
417    /// F₄ Cartan matrix
418    ///
419    /// ```text
420    /// [ 2  -1   0   0]
421    /// [-1   2  -2   0]
422    /// [ 0  -1   2  -1]
423    /// [ 0   0  -1   2]
424    /// ```
425    #[must_use]
426    pub const fn f4() -> Self {
427        Self::new([[2, -1, 0, 0], [-1, 2, -2, 0], [0, -1, 2, -1], [0, 0, -1, 2]])
428    }
429}
430
431impl CartanMatrix<6> {
432    /// E₆ Cartan matrix
433    ///
434    /// ```text
435    /// [ 2  -1   0   0   0   0]
436    /// [-1   2  -1   0   0   0]
437    /// [ 0  -1   2  -1   0  -1]
438    /// [ 0   0  -1   2  -1   0]
439    /// [ 0   0   0  -1   2   0]
440    /// [ 0   0  -1   0   0   2]
441    /// ```
442    #[must_use]
443    pub const fn e6() -> Self {
444        Self::new([
445            [2, -1, 0, 0, 0, 0],
446            [-1, 2, -1, 0, 0, 0],
447            [0, -1, 2, -1, 0, -1],
448            [0, 0, -1, 2, -1, 0],
449            [0, 0, 0, -1, 2, 0],
450            [0, 0, -1, 0, 0, 2],
451        ])
452    }
453}
454
455impl CartanMatrix<7> {
456    /// E₇ Cartan matrix
457    ///
458    /// ```text
459    /// [ 2  -1   0   0   0   0   0]
460    /// [-1   2  -1   0   0   0   0]
461    /// [ 0  -1   2  -1   0   0   0]
462    /// [ 0   0  -1   2  -1   0  -1]
463    /// [ 0   0   0  -1   2  -1   0]
464    /// [ 0   0   0   0  -1   2   0]
465    /// [ 0   0   0  -1   0   0   2]
466    /// ```
467    #[must_use]
468    pub const fn e7() -> Self {
469        Self::new([
470            [2, -1, 0, 0, 0, 0, 0],
471            [-1, 2, -1, 0, 0, 0, 0],
472            [0, -1, 2, -1, 0, 0, 0],
473            [0, 0, -1, 2, -1, 0, -1],
474            [0, 0, 0, -1, 2, -1, 0],
475            [0, 0, 0, 0, -1, 2, 0],
476            [0, 0, 0, -1, 0, 0, 2],
477        ])
478    }
479}
480
481impl CartanMatrix<8> {
482    /// E₈ Cartan matrix
483    ///
484    /// ```text
485    /// [ 2  -1   0   0   0   0   0   0]
486    /// [-1   2  -1   0   0   0   0   0]
487    /// [ 0  -1   2  -1   0   0   0   0]
488    /// [ 0   0  -1   2  -1   0   0   0]
489    /// [ 0   0   0  -1   2  -1   0  -1]
490    /// [ 0   0   0   0  -1   2  -1   0]
491    /// [ 0   0   0   0   0  -1   2   0]
492    /// [ 0   0   0   0  -1   0   0   2]
493    /// ```
494    #[must_use]
495    pub const fn e8() -> Self {
496        Self::new([
497            [2, -1, 0, 0, 0, 0, 0, 0],
498            [-1, 2, -1, 0, 0, 0, 0, 0],
499            [0, -1, 2, -1, 0, 0, 0, 0],
500            [0, 0, -1, 2, -1, 0, 0, 0],
501            [0, 0, 0, -1, 2, -1, 0, -1],
502            [0, 0, 0, 0, -1, 2, -1, 0],
503            [0, 0, 0, 0, 0, -1, 2, 0],
504            [0, 0, 0, 0, -1, 0, 0, 2],
505        ])
506    }
507}
508
509// ============================================================================
510// Dynkin Diagrams
511// ============================================================================
512
513/// Dynkin diagram representation
514///
515/// A Dynkin diagram is a graph encoding the structure of a Lie algebra.
516/// Nodes represent simple roots, edges represent root relationships.
517///
518/// From certified Python implementation: exact bonds from Cartan matrix.
519#[derive(Debug, Clone, PartialEq, Eq)]
520pub struct DynkinDiagram<const N: usize> {
521    /// Group name (e.g., "G₂", "F₄", "E₆")
522    group_name: String,
523    /// Rank (number of simple roots)
524    rank: usize,
525    /// Cartan matrix (exact integers)
526    cartan: CartanMatrix<N>,
527    /// Bonds: (`from_node`, `to_node`, multiplicity)
528    /// Multiplicity: 1=single, 2=double, 3=triple
529    bonds: Vec<(usize, usize, u8)>,
530    /// Node degrees (connectivity in Dynkin diagram)
531    degrees: Vec<usize>,
532}
533
534impl<const N: usize> DynkinDiagram<N> {
535    /// Create Dynkin diagram from Cartan matrix
536    ///
537    /// Extracts bond structure using exact formula: multiplicity = |Cᵢⱼ × Cⱼᵢ|
538    ///
539    /// # Panics
540    ///
541    /// Panics if the computed multiplicity doesn't fit in `u8` (should never happen for valid Cartan matrices).
542    #[must_use]
543    pub fn from_cartan(cartan: &CartanMatrix<N>, group_name: &str) -> Self {
544        let mut bonds = Vec::new();
545        let mut degrees = vec![0; N];
546
547        // Extract bonds from Cartan matrix
548        // Only check upper triangle to avoid duplicates
549        for i in 0..N {
550            for j in (i + 1)..N {
551                let c_ij = cartan.get(i, j);
552                let c_ji = cartan.get(j, i);
553
554                // Bond exists if both entries are non-zero
555                if c_ij != 0 && c_ji != 0 {
556                    // Multiplicity = |Cᵢⱼ × Cⱼᵢ| (exact integer arithmetic)
557                    let product = i32::from(c_ij) * i32::from(c_ji);
558                    let multiplicity = u8::try_from(product.unsigned_abs())
559                        .expect("multiplicity should fit in u8");
560
561                    bonds.push((i, j, multiplicity));
562
563                    // Update degrees
564                    degrees[i] += 1;
565                    degrees[j] += 1;
566                }
567            }
568        }
569
570        Self { group_name: group_name.to_string(), rank: N, cartan: *cartan, bonds, degrees }
571    }
572
573    /// Get rank (number of simple roots)
574    #[must_use]
575    pub const fn rank(&self) -> usize {
576        self.rank
577    }
578
579    /// Get group name
580    #[must_use]
581    pub fn group_name(&self) -> &str {
582        &self.group_name
583    }
584
585    /// Get bonds: (`from_node`, `to_node`, multiplicity)
586    #[must_use]
587    pub fn bonds(&self) -> &[(usize, usize, u8)] {
588        &self.bonds
589    }
590
591    /// Get node degree (number of bonds to this node)
592    #[must_use]
593    pub fn degree(&self, node: usize) -> usize {
594        self.degrees[node]
595    }
596
597    /// Get all node degrees
598    #[must_use]
599    pub fn degrees(&self) -> &[usize] {
600        &self.degrees
601    }
602
603    /// Get Cartan matrix
604    #[must_use]
605    pub const fn cartan_matrix(&self) -> &CartanMatrix<N> {
606        &self.cartan
607    }
608
609    /// Check if diagram is connected
610    #[must_use]
611    pub fn is_connected(&self) -> bool {
612        if N == 0 {
613            return true;
614        }
615
616        // BFS to check connectivity
617        let mut visited = vec![false; N];
618        let mut queue = vec![0];
619        visited[0] = true;
620        let mut count = 1;
621
622        while let Some(node) = queue.pop() {
623            // Check all bonds involving this node
624            for &(i, j, _) in &self.bonds {
625                let neighbor = if i == node {
626                    Some(j)
627                } else if j == node {
628                    Some(i)
629                } else {
630                    None
631                };
632
633                if let Some(n) = neighbor {
634                    if !visited[n] {
635                        visited[n] = true;
636                        queue.push(n);
637                        count += 1;
638                    }
639                }
640            }
641        }
642
643        count == N
644    }
645
646    /// Get indices of branch nodes (nodes with degree ≥ 3)
647    ///
648    /// Branch nodes are the vertices where the Dynkin diagram branches.
649    /// For E₆, E₇, E₈, there is exactly one branch node.
650    ///
651    /// # Examples
652    ///
653    /// ```
654    /// use atlas_embeddings::cartan::CartanMatrix;
655    ///
656    /// let e6 = CartanMatrix::e6();
657    /// let dynkin = e6.to_dynkin_diagram("E₆");
658    /// let branches = dynkin.branch_nodes();
659    ///
660    /// assert_eq!(branches.len(), 1, "E₆ has exactly 1 branch node");
661    /// ```
662    #[must_use]
663    pub fn branch_nodes(&self) -> Vec<usize> {
664        self.degrees
665            .iter()
666            .enumerate()
667            .filter(|(_, &deg)| deg >= 3)
668            .map(|(i, _)| i)
669            .collect()
670    }
671
672    /// Get indices of endpoint nodes (nodes with degree 1)
673    ///
674    /// Endpoints are the terminal vertices of the Dynkin diagram.
675    /// For E₆, there are 3 endpoints (the three arms of the diagram).
676    ///
677    /// # Examples
678    ///
679    /// ```
680    /// use atlas_embeddings::cartan::CartanMatrix;
681    ///
682    /// let e6 = CartanMatrix::e6();
683    /// let dynkin = e6.to_dynkin_diagram("E₆");
684    /// let endpoints = dynkin.endpoints();
685    ///
686    /// assert_eq!(endpoints.len(), 3, "E₆ has 3 endpoints");
687    /// ```
688    #[must_use]
689    pub fn endpoints(&self) -> Vec<usize> {
690        self.degrees
691            .iter()
692            .enumerate()
693            .filter(|(_, &deg)| deg == 1)
694            .map(|(i, _)| i)
695            .collect()
696    }
697
698    /// Get indices of middle nodes (nodes with degree 2)
699    ///
700    /// Middle nodes are non-branching, non-terminal vertices.
701    ///
702    /// # Examples
703    ///
704    /// ```
705    /// use atlas_embeddings::cartan::CartanMatrix;
706    ///
707    /// let e6 = CartanMatrix::e6();
708    /// let dynkin = e6.to_dynkin_diagram("E₆");
709    /// let middle = dynkin.middle_nodes();
710    ///
711    /// assert_eq!(middle.len(), 2, "E₆ has 2 middle nodes");
712    /// ```
713    #[must_use]
714    pub fn middle_nodes(&self) -> Vec<usize> {
715        self.degrees
716            .iter()
717            .enumerate()
718            .filter(|(_, &deg)| deg == 2)
719            .map(|(i, _)| i)
720            .collect()
721    }
722
723    /// Generate ASCII diagram representation
724    ///
725    /// Creates a text visualization of the Dynkin diagram with proper bond notation:
726    /// - Single bond: —
727    /// - Double bond: ⇒
728    /// - Triple bond: ≡
729    #[must_use]
730    pub fn to_ascii(&self) -> String {
731        // Generate ASCII based on group structure
732        // This matches the certified Python implementation's diagram format
733        match self.group_name.as_str() {
734            "G₂" => Self::ascii_g2(),
735            "F₄" => Self::ascii_f4(),
736            "E₆" => Self::ascii_e6(),
737            "E₇" => Self::ascii_e7(),
738            "E₈" => Self::ascii_e8(),
739            _ => self.ascii_generic(),
740        }
741    }
742
743    /// Generate G₂ ASCII diagram
744    fn ascii_g2() -> String {
745        "\nG₂ Dynkin Diagram (rank 2):\n\n  α₁ o≡≡≡o α₂\n\nTriple bond: |C₁₂ × C₂₁| = 3\n\
746             Short root (α₁) connected to long root (α₂)\n"
747            .to_string()
748    }
749
750    /// Generate F₄ ASCII diagram
751    fn ascii_f4() -> String {
752        "\nF₄ Dynkin Diagram (rank 4):\n\n  α₁ o---o α₂ ⇒ α₃ o---o α₄\n\n\
753             Double bond (⇒): |C₂₃ × C₃₂| = 2\n\
754             Arrow points from short to long roots\n"
755            .to_string()
756    }
757
758    /// Generate E₆ ASCII diagram
759    fn ascii_e6() -> String {
760        "\nE₆ Dynkin Diagram (rank 6):\n\n          α₂\n          o\n          |\n  \
761             α₁ o---o α₀ ---o α₃ ---o α₄ ---o α₅\n\n\
762             Branching structure: central node (α₀) has degree 3\n\
763             Simply-laced: all single bonds\n"
764            .to_string()
765    }
766
767    /// Generate E₇ ASCII diagram
768    fn ascii_e7() -> String {
769        "\nE₇ Dynkin Diagram (rank 7):\n\n              α₆\n              o\n              |\n  \
770             α₀ o---o α₁ ---o α₂ ---o α₃ ---o α₄ ---o α₅\n\n\
771             Extended E₆ structure\n\
772             Simply-laced: all single bonds\n"
773            .to_string()
774    }
775
776    /// Generate E₈ ASCII diagram
777    fn ascii_e8() -> String {
778        "\nE₈ Dynkin Diagram (rank 8):\n\n                  α₇\n                  o\n                  |\n  \
779             α₀ o---o α₁ ---o α₂ ---o α₃ ---o α₄ ---o α₅ ---o α₆\n\n\
780             Largest exceptional group\n\
781             Simply-laced: all single bonds\n".to_string()
782    }
783
784    /// Generate generic ASCII diagram (for unknown groups)
785    fn ascii_generic(&self) -> String {
786        use std::fmt::Write as _;
787        let mut diagram = format!("\n{} Dynkin Diagram (rank {}):\n\n", self.group_name, N);
788
789        // Simple linear representation
790        diagram.push_str("  ");
791        for i in 0..N {
792            write!(diagram, "α{i}").unwrap();
793            if i < N - 1 {
794                diagram.push_str(" o");
795                // Find bond to next node
796                let bond = self
797                    .bonds
798                    .iter()
799                    .find(|(a, b, _)| (*a == i && *b == i + 1) || (*a == i + 1 && *b == i));
800                match bond {
801                    Some((_, _, 1)) => diagram.push_str("---"),
802                    Some((_, _, 2)) => diagram.push_str("==>"),
803                    Some((_, _, 3)) => diagram.push_str("≡≡≡"),
804                    _ => diagram.push_str("   "),
805                }
806                diagram.push_str("o ");
807            }
808        }
809        diagram.push('\n');
810
811        // List bonds
812        if !self.bonds.is_empty() {
813            diagram.push_str("\nBonds:\n");
814            for (i, j, mult) in &self.bonds {
815                writeln!(diagram, "  α{i} ↔ α{j} (multiplicity {mult})").unwrap();
816            }
817        }
818
819        diagram
820    }
821}
822
823#[cfg(test)]
824mod tests {
825    use super::*;
826
827    #[test]
828    fn test_g2_cartan() {
829        let g2 = CartanMatrix::g2();
830        assert_eq!(g2.rank(), 2);
831        assert!(g2.is_valid());
832        assert!(!g2.is_simply_laced());
833        assert!(!g2.is_symmetric());
834        assert_eq!(g2.determinant(), 1);
835        assert!(g2.is_connected());
836    }
837
838    #[test]
839    fn test_f4_cartan() {
840        let f4 = CartanMatrix::f4();
841        assert_eq!(f4.rank(), 4);
842        assert!(f4.is_valid());
843        assert!(!f4.is_simply_laced());
844        assert!(!f4.is_symmetric());
845        assert_eq!(f4.determinant(), 1);
846        assert!(f4.is_connected());
847    }
848
849    #[test]
850    fn test_e6_cartan() {
851        let e6 = CartanMatrix::e6();
852        assert_eq!(e6.rank(), 6);
853        assert!(e6.is_valid());
854        assert!(e6.is_simply_laced());
855        assert!(e6.is_symmetric());
856        assert_eq!(e6.determinant(), 3);
857        assert!(e6.is_connected());
858    }
859
860    #[test]
861    fn test_e7_cartan() {
862        let e7 = CartanMatrix::e7();
863        assert_eq!(e7.rank(), 7);
864        assert!(e7.is_valid());
865        assert!(e7.is_simply_laced());
866        assert!(e7.is_symmetric());
867        assert_eq!(e7.determinant(), 2);
868        assert!(e7.is_connected());
869    }
870
871    #[test]
872    fn test_e8_cartan() {
873        let e8 = CartanMatrix::e8();
874        assert_eq!(e8.rank(), 8);
875        assert!(e8.is_valid());
876        assert!(e8.is_simply_laced());
877        assert!(e8.is_symmetric());
878        assert_eq!(e8.determinant(), 1);
879        assert!(e8.is_connected());
880    }
881
882    #[test]
883    fn test_cartan_validity() {
884        // Invalid: diagonal not 2
885        let invalid = CartanMatrix::new([[1, 0], [0, 2]]);
886        assert!(!invalid.is_valid());
887
888        // Invalid: positive off-diagonal
889        let invalid2 = CartanMatrix::new([[2, 1], [1, 2]]);
890        assert!(!invalid2.is_valid());
891
892        // Invalid: asymmetric zeros
893        let invalid3 = CartanMatrix::new([[2, 0], [-1, 2]]);
894        assert!(!invalid3.is_valid());
895    }
896
897    #[test]
898    fn test_simply_laced() {
899        // Simply-laced: all off-diagonal in {0, -1}
900        let sl = CartanMatrix::new([[2, -1], [-1, 2]]);
901        assert!(sl.is_simply_laced());
902
903        // Not simply-laced: has -2
904        let nsl = CartanMatrix::new([[2, -2], [-1, 2]]);
905        assert!(!nsl.is_simply_laced());
906
907        // Not simply-laced: has -3
908        let nsl2 = CartanMatrix::new([[2, -3], [-1, 2]]);
909        assert!(!nsl2.is_simply_laced());
910    }
911
912    #[test]
913    fn test_determinant_2x2() {
914        let m = CartanMatrix::new([[2, -1], [-1, 2]]);
915        assert_eq!(m.determinant(), 3);
916    }
917
918    #[test]
919    fn test_connected_components() {
920        // Disconnected: two A₁ components
921        let disconnected = CartanMatrix::new([[2, 0], [0, 2]]);
922        assert_eq!(disconnected.num_connected_components(), 2);
923        assert!(!disconnected.is_connected());
924
925        // Connected
926        let connected = CartanMatrix::new([[2, -1], [-1, 2]]);
927        assert_eq!(connected.num_connected_components(), 1);
928        assert!(connected.is_connected());
929    }
930
931    // ========================================================================
932    // Dynkin Diagram Tests
933    // ========================================================================
934
935    #[test]
936    fn test_dynkin_g2_triple_bond() {
937        let g2 = CartanMatrix::g2();
938        let dynkin = g2.to_dynkin_diagram("G₂");
939
940        assert_eq!(dynkin.rank(), 2);
941        assert_eq!(dynkin.group_name(), "G₂");
942        assert!(dynkin.is_connected());
943
944        // G₂ has exactly 1 bond with multiplicity 3
945        let bonds = dynkin.bonds();
946        assert_eq!(bonds.len(), 1, "G₂ has 1 bond");
947        assert_eq!(bonds[0].2, 3, "G₂ triple bond: |C₁₂ × C₂₁| = |-3 × -1| = 3");
948
949        // Both nodes have degree 1 (single connection)
950        assert_eq!(dynkin.degree(0), 1);
951        assert_eq!(dynkin.degree(1), 1);
952
953        // Verify ASCII output contains key elements
954        let ascii = dynkin.to_ascii();
955        assert!(ascii.contains("G₂"));
956        assert!(ascii.contains("Triple bond"));
957    }
958
959    #[test]
960    fn test_dynkin_f4_double_bond() {
961        let f4 = CartanMatrix::f4();
962        let dynkin = f4.to_dynkin_diagram("F₄");
963
964        assert_eq!(dynkin.rank(), 4);
965        assert_eq!(dynkin.group_name(), "F₄");
966        assert!(dynkin.is_connected());
967
968        // F₄ has 3 bonds: one double, two single
969        let bonds = dynkin.bonds();
970        assert_eq!(bonds.len(), 3, "F₄ has 3 bonds");
971
972        // Find the double bond (multiplicity 2)
973        let double_bond = bonds.iter().find(|(_, _, m)| *m == 2);
974        assert!(double_bond.is_some(), "F₄ has a double bond");
975
976        let double = double_bond.unwrap();
977        assert_eq!(double.2, 2, "F₄ double bond: |C₂₃ × C₃₂| = |-2 × -1| = 2");
978
979        // Verify node degrees: linear chain means middle nodes have degree 2
980        assert_eq!(dynkin.degree(0), 1, "Endpoint");
981        assert_eq!(dynkin.degree(1), 2, "Middle");
982        assert_eq!(dynkin.degree(2), 2, "Middle");
983        assert_eq!(dynkin.degree(3), 1, "Endpoint");
984
985        // Verify ASCII output
986        let ascii = dynkin.to_ascii();
987        assert!(ascii.contains("F₄"));
988        assert!(ascii.contains("Double bond"));
989    }
990
991    #[test]
992    fn test_dynkin_e6_simply_laced() {
993        let e6 = CartanMatrix::e6();
994        let dynkin = e6.to_dynkin_diagram("E₆");
995
996        assert_eq!(dynkin.rank(), 6);
997        assert_eq!(dynkin.group_name(), "E₆");
998        assert!(dynkin.is_connected());
999
1000        // E₆ tree structure: 6 nodes → 5 bonds (rank - 1)
1001        let bonds = dynkin.bonds();
1002        assert_eq!(bonds.len(), 5, "E₆ has 5 bonds (tree with 6 nodes)");
1003
1004        // All bonds must be single (multiplicity 1)
1005        for &(_, _, mult) in bonds {
1006            assert_eq!(mult, 1, "E₆ is simply-laced: all bonds are single");
1007        }
1008
1009        // E₆ Dynkin structure: 1 central node (degree 3), 3 endpoints (degree 1), 2 middle (degree 2)
1010        let degrees = dynkin.degrees();
1011        let deg_1_count = degrees.iter().filter(|&&d| d == 1).count();
1012        let deg_2_count = degrees.iter().filter(|&&d| d == 2).count();
1013        let deg_3_count = degrees.iter().filter(|&&d| d == 3).count();
1014
1015        assert_eq!(deg_1_count, 3, "E₆ has 3 endpoints");
1016        assert_eq!(deg_2_count, 2, "E₆ has 2 middle nodes");
1017        assert_eq!(deg_3_count, 1, "E₆ has 1 branch node");
1018
1019        // Verify ASCII output
1020        let ascii = dynkin.to_ascii();
1021        assert!(ascii.contains("E₆"));
1022        assert!(ascii.contains("Branching structure"));
1023    }
1024
1025    #[test]
1026    fn test_dynkin_e7_simply_laced() {
1027        let e7 = CartanMatrix::e7();
1028        let dynkin = e7.to_dynkin_diagram("E₇");
1029
1030        assert_eq!(dynkin.rank(), 7);
1031        assert!(dynkin.is_connected());
1032
1033        // E₇ tree structure: 7 nodes → 6 bonds (rank - 1)
1034        let bonds = dynkin.bonds();
1035        assert_eq!(bonds.len(), 6, "E₇ has 6 bonds (tree with 7 nodes)");
1036
1037        for &(_, _, mult) in bonds {
1038            assert_eq!(mult, 1, "E₇ is simply-laced");
1039        }
1040
1041        // Verify ASCII output
1042        let ascii = dynkin.to_ascii();
1043        assert!(ascii.contains("E₇"));
1044    }
1045
1046    #[test]
1047    fn test_dynkin_e8_simply_laced() {
1048        let e8 = CartanMatrix::e8();
1049        let dynkin = e8.to_dynkin_diagram("E₈");
1050
1051        assert_eq!(dynkin.rank(), 8);
1052        assert!(dynkin.is_connected());
1053
1054        // E₈ tree structure: 8 nodes → 7 bonds (rank - 1)
1055        let bonds = dynkin.bonds();
1056        assert_eq!(bonds.len(), 7, "E₈ has 7 bonds (tree with 8 nodes)");
1057
1058        for &(_, _, mult) in bonds {
1059            assert_eq!(mult, 1, "E₈ is simply-laced");
1060        }
1061
1062        // E₈ Dynkin structure: 3 endpoints, 4 middle, 1 branch
1063        let degrees = dynkin.degrees();
1064        let deg_1_count = degrees.iter().filter(|&&d| d == 1).count();
1065        let deg_2_count = degrees.iter().filter(|&&d| d == 2).count();
1066        let deg_3_count = degrees.iter().filter(|&&d| d == 3).count();
1067
1068        assert_eq!(deg_1_count, 3, "E₈ has 3 endpoints");
1069        assert_eq!(deg_2_count, 4, "E₈ has 4 middle nodes");
1070        assert_eq!(deg_3_count, 1, "E₈ has 1 branch node");
1071
1072        // Verify ASCII output
1073        let ascii = dynkin.to_ascii();
1074        assert!(ascii.contains("E₈"));
1075    }
1076
1077    #[test]
1078    fn test_dynkin_bond_extraction_exact() {
1079        // Test exact formula: multiplicity = |C_ij × C_ji|
1080
1081        // G₂: C[0,1] = -3, C[1,0] = -1 → |-3 × -1| = 3
1082        let g2 = CartanMatrix::g2();
1083        let g2_diagram = g2.to_dynkin_diagram("G₂");
1084        assert_eq!(g2_diagram.bonds()[0].2, 3);
1085
1086        // F₄: C[1,2] = -2, C[2,1] = -1 → |-2 × -1| = 2
1087        let f4 = CartanMatrix::f4();
1088        let f4_diagram = f4.to_dynkin_diagram("F₄");
1089        let double = f4_diagram.bonds().iter().find(|(_, _, m)| *m == 2).unwrap();
1090        assert_eq!(double.2, 2);
1091
1092        // E₆: all C[i,j] × C[j,i] = -1 × -1 = 1 (simply-laced)
1093        let e6 = CartanMatrix::e6();
1094        let e6_diagram = e6.to_dynkin_diagram("E₆");
1095        for &(i, j, mult) in e6_diagram.bonds() {
1096            let c_ij = e6.get(i, j);
1097            let c_ji = e6.get(j, i);
1098            let expected = u8::try_from((i32::from(c_ij) * i32::from(c_ji)).unsigned_abs())
1099                .expect("multiplicity should fit in u8");
1100            assert_eq!(mult, expected, "Bond ({i},{j}) multiplicity");
1101        }
1102    }
1103
1104    #[test]
1105    fn test_dynkin_degrees_from_bonds() {
1106        // Verify that degrees are computed correctly from bonds
1107
1108        // A₂: two nodes, one bond → both degree 1
1109        let a2 = CartanMatrix::new([[2, -1], [-1, 2]]);
1110        let dynkin = a2.to_dynkin_diagram("A₂");
1111        assert_eq!(dynkin.degree(0), 1);
1112        assert_eq!(dynkin.degree(1), 1);
1113
1114        // A₃: three nodes in a line → endpoints degree 1, middle degree 2
1115        let a3 = CartanMatrix::new([[2, -1, 0], [-1, 2, -1], [0, -1, 2]]);
1116        let dynkin = a3.to_dynkin_diagram("A₃");
1117        assert_eq!(dynkin.degree(0), 1);
1118        assert_eq!(dynkin.degree(1), 2);
1119        assert_eq!(dynkin.degree(2), 1);
1120    }
1121
1122    #[test]
1123    fn test_dynkin_connectivity() {
1124        // All exceptional group Dynkin diagrams are connected
1125        assert!(CartanMatrix::g2().to_dynkin_diagram("G₂").is_connected());
1126        assert!(CartanMatrix::f4().to_dynkin_diagram("F₄").is_connected());
1127        assert!(CartanMatrix::e6().to_dynkin_diagram("E₆").is_connected());
1128        assert!(CartanMatrix::e7().to_dynkin_diagram("E₇").is_connected());
1129        assert!(CartanMatrix::e8().to_dynkin_diagram("E₈").is_connected());
1130
1131        // Disconnected example: A₁ × A₁
1132        let disconnected = CartanMatrix::new([[2, 0], [0, 2]]);
1133        let dynkin = disconnected.to_dynkin_diagram("A₁×A₁");
1134        assert!(!dynkin.is_connected(), "Disconnected Dynkin diagram");
1135    }
1136
1137    #[test]
1138    fn test_dynkin_helper_methods() {
1139        // E₆: 1 branch, 3 endpoints, 2 middle
1140        let e6 = CartanMatrix::e6().to_dynkin_diagram("E₆");
1141        assert_eq!(e6.branch_nodes().len(), 1, "E₆ has 1 branch node");
1142        assert_eq!(e6.endpoints().len(), 3, "E₆ has 3 endpoints");
1143        assert_eq!(e6.middle_nodes().len(), 2, "E₆ has 2 middle nodes");
1144
1145        // E₇: 1 branch, 3 endpoints, 3 middle
1146        let e7 = CartanMatrix::e7().to_dynkin_diagram("E₇");
1147        assert_eq!(e7.branch_nodes().len(), 1, "E₇ has 1 branch node");
1148        assert_eq!(e7.endpoints().len(), 3, "E₇ has 3 endpoints");
1149        assert_eq!(e7.middle_nodes().len(), 3, "E₇ has 3 middle nodes");
1150
1151        // E₈: 1 branch, 3 endpoints, 4 middle
1152        let e8 = CartanMatrix::e8().to_dynkin_diagram("E₈");
1153        assert_eq!(e8.branch_nodes().len(), 1, "E₈ has 1 branch node");
1154        assert_eq!(e8.endpoints().len(), 3, "E₈ has 3 endpoints");
1155        assert_eq!(e8.middle_nodes().len(), 4, "E₈ has 4 middle nodes");
1156
1157        // G₂: no branching (linear)
1158        let g2 = CartanMatrix::g2().to_dynkin_diagram("G₂");
1159        assert_eq!(g2.branch_nodes().len(), 0, "G₂ has no branch nodes");
1160        assert_eq!(g2.endpoints().len(), 2, "G₂ has 2 endpoints");
1161
1162        // F₄: no branching (linear)
1163        let f4 = CartanMatrix::f4().to_dynkin_diagram("F₄");
1164        assert_eq!(f4.branch_nodes().len(), 0, "F₄ has no branch nodes");
1165        assert_eq!(f4.endpoints().len(), 2, "F₄ has 2 endpoints");
1166        assert_eq!(f4.middle_nodes().len(), 2, "F₄ has 2 middle nodes");
1167    }
1168}
atlas_embeddings/cartan/mod.rs

atlas_embeddings/cartan/
mod.rs
