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]