File size: 7,241 Bytes
5316c4e | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 | -- SPDX-License-Identifier: AGPL-3.0-or-later
-- | Finite crystallographic root systems, from vectors to Weyl group orders.
--
-- Nothing about a root system is typed in by hand beyond its vectors. Simple
-- roots are extracted from a generic linear functional, the Cartan matrix is
-- computed from them, and the Weyl group order is computed from the Cartan
-- matrix by orbit–stabilizer. The tests then compare against the
-- classification tables, which are the authority, not an input.
--
-- Vectors are integral. Where the usual coordinates have halves (E8, F4) the
-- whole system is scaled by 2; every quantity used here is a ratio of inner
-- products, so the scale cancels.
module MP.RootSystem
( Vec
, dot
, reflect
, axiomViolations
-- * The classical and exceptional systems
, typeA
, typeB
, typeD
, typeG2
, typeF4
, typeE8
, orthogonalSubsystem
-- * Structure
, positiveRoots
, simpleRoots
, cartanMatrix
, weylOrder
, weightOrbit
) where
import Data.List (nub, sortOn)
import qualified Data.Set as Set
type Vec = [Integer]
dot :: Vec -> Vec -> Integer
dot x y = sum (zipWith (*) x y)
-- | @2(b, a) / (a, a)@ when it is an integer, which is the crystallographic
-- condition.
cartanInteger :: Vec -> Vec -> Maybe Integer
cartanInteger b a =
let num = 2 * dot b a
den = dot a a
in if den /= 0 && num `rem` den == 0 then Just (num `quot` den) else Nothing
-- | The reflection of @b@ in the hyperplane orthogonal to @a@.
reflect :: Vec -> Vec -> Maybe Vec
reflect a b = (\c -> zipWith (\bi ai -> bi - c * ai) b a) <$> cartanInteger b a
-- | Every way the input fails to be a reduced crystallographic root system.
-- Empty means it is one.
axiomViolations :: [Vec] -> [String]
axiomViolations rs =
concat
[ ["empty" | null rs]
, ["contains the zero vector" | any (all (== 0)) rs]
, ["contains a repeated vector" | length (nub rs) /= length rs]
, [ "not crystallographic at " <> show (a, b)
| a <- rs, b <- rs, cartanInteger b a == Nothing
]
, [ "not closed: s_" <> show a <> " " <> show b
| a <- rs, b <- rs, Just r <- [reflect a b], not (Set.member r set)
]
, [ "not reduced: " <> show (a, b)
| a <- rs, b <- rs, a /= b, a /= map negate b, parallel a b
]
]
where
set = Set.fromList rs
parallel a b = dot a b * dot a b == dot a a * dot b b
------------------------------------------------------------------------------
-- Constructions
unit :: Int -> Int -> Integer -> Vec
unit n i c = [if k == i then c else 0 | k <- [0 .. n - 1]]
plus :: Vec -> Vec -> Vec
plus = zipWith (+)
-- | @e_i - e_j@ in @R^(n+1)@.
typeA :: Int -> [Vec]
typeA n = [plus (unit (n + 1) i 1) (unit (n + 1) j (-1)) | i <- [0 .. n], j <- [0 .. n], i /= j]
-- | @±e_i@ and @±e_i ± e_j@ in @R^n@.
typeB :: Int -> [Vec]
typeB n = [unit n i s | i <- [0 .. n - 1], s <- [1, -1]] ++ typeD n
-- | @±e_i ± e_j@, @i < j@, in @R^n@.
typeD :: Int -> [Vec]
typeD n =
[ plus (unit n i s) (unit n j t)
| i <- [0 .. n - 1], j <- [i + 1 .. n - 1], s <- [1, -1], t <- [1, -1]
]
-- | In the plane @x + y + z = 0@: short roots @e_i - e_j@ and long roots
-- @±(2e_i - e_j - e_k)@.
typeG2 :: [Vec]
typeG2 =
typeA 2
++ [ map (* s) (plus (unit 3 i 2) (plus (unit 3 j (-1)) (unit 3 k (-1))))
| (i, j, k) <- [(0, 1, 2), (1, 0, 2), (2, 0, 1)], s <- [1, -1]
]
-- | Scaled by 2: @±2e_i@, @±2e_i ± 2e_j@, and @(±1, ±1, ±1, ±1)@.
typeF4 :: [Vec]
typeF4 = map (map (* 2)) (typeB 4) ++ signs 4
-- | Scaled by 2: @±2e_i ± 2e_j@ (112) and @(±1, ..., ±1)@ with an even number
-- of minus signs (128).
typeE8 :: [Vec]
typeE8 = map (map (* 2)) (typeD 8) ++ filter (even . length . filter (< 0)) (signs 8)
signs :: Int -> [Vec]
signs n = mapM (const [1, -1]) [1 .. n]
-- | The roots orthogonal to every given vector. A subsystem cut out this way
-- is again a root system; E7 and E6 are obtained from E8 like this.
orthogonalSubsystem :: [Vec] -> [Vec] -> [Vec]
orthogonalSubsystem vs = filter (\r -> all ((== 0) . dot r) vs)
------------------------------------------------------------------------------
-- Positive and simple roots
-- | A functional @x -> sum x_i k^i@ that vanishes on no root, for the least
-- @k >= 2@ that works. 'Nothing' only if none up to 64 does, which would mean
-- the input was not a root system.
genericFunctional :: [Vec] -> Maybe (Vec -> Integer)
genericFunctional rs =
case [f | k <- [2 .. 64], let f = functional k, all ((/= 0) . f) rs] of
(f : _) -> Just f
[] -> Nothing
where
functional k v = sum (zipWith (*) v (iterate (* k) 1))
positiveRoots :: [Vec] -> [Vec]
positiveRoots rs = maybe [] (\f -> filter ((> 0) . f) rs) (genericFunctional rs)
-- | Positive roots that are not the sum of two positive roots. Ordered by the
-- functional, so the result is deterministic.
simpleRoots :: [Vec] -> [Vec]
simpleRoots rs = case genericFunctional rs of
Nothing -> []
Just f ->
let pos = filter ((> 0) . f) rs
posSet = Set.fromList pos
decomposable a = any (\b -> Set.member (zipWith (-) a b) posSet) pos
in sortOn f (filter (not . decomposable) pos)
-- | @C_ij = 2(a_i, a_j) / (a_j, a_j)@. Integral for a crystallographic system.
cartanMatrix :: [Vec] -> [[Integer]]
cartanMatrix simple = [[maybe 0 id (cartanInteger ai aj) | aj <- simple] | ai <- simple]
------------------------------------------------------------------------------
-- Weyl group order
-- | The orbit of a weight, given in the basis of fundamental weights, under
-- the Weyl group of the Cartan matrix. In that basis the simple root @a_i@ is
-- row @i@ of the Cartan matrix, and @s_i(l) = l - l_i a_i@.
weightOrbit :: [[Integer]] -> [Integer] -> Set.Set [Integer]
weightOrbit c start = go (Set.singleton start) [start]
where
reflections l = [zipWith (\lj aij -> lj - li * aij) l row | (li, row) <- zip l c, li /= 0]
go seen [] = seen
go seen (l : rest) =
let new = filter (`Set.notMember` seen) (nub (reflections l))
in go (foldl' (flip Set.insert) seen new) (new ++ rest)
-- | @|W| = |W . w_k| * |W_k|@, where @w_k@ is a fundamental weight and @W_k@,
-- its stabilizer, is the parabolic subgroup generated by the other simple
-- reflections, i.e. the Weyl group of the Cartan matrix with node @k@ deleted.
--
-- Any @k@ is correct. A leaf of the Dynkin diagram with the smallest orbit is
-- chosen because it is cheap: for E8 the orbits are 240, 56, 27, 10, 8, 4, 3, 2.
weylOrder :: [[Integer]] -> Integer
weylOrder [] = 1
weylOrder c =
let n = length c
degree k = length [() | (j, v) <- zip [0 ..] (row k), j /= k, v /= 0]
row k = concat (take 1 (drop k c))
leaves = [k | k <- [0 .. n - 1], degree k <= 1]
candidates = if null leaves then [0 .. n - 1] else leaves
sized = [(Set.size (weightOrbit c (fundamental n k)), k) | k <- candidates]
(orbitSize, k0) = foldl' min (maxBound, 0) sized
in toInteger orbitSize * weylOrder (deleteNode k0 c)
fundamental :: Int -> Int -> [Integer]
fundamental n k = [if i == k then 1 else 0 | i <- [0 .. n - 1]]
deleteNode :: Int -> [[a]] -> [[a]]
deleteNode k = map dropK . dropK
where
dropK xs = [x | (i, x) <- zip [0 :: Int ..] xs, i /= k]
|