montrepol / packages /mp-lie /src /MP /RootSystem.hs
SNAPKITTYWEST's picture
montrepol: exact mathematics in Haskell, with proofs and a certifying solver
5316c4e verified
Raw History Blame Contribute Delete
7.24 kB
-- 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]