-
Notifications
You must be signed in to change notification settings - Fork 113
/
WeylGroup.jl
695 lines (565 loc) · 16.6 KB
/
WeylGroup.jl
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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
# This file is based on an implementation from CoxeterGroups.jl by Ulrich Thiel (@ulthiel), Cameron Braunstein (@CameronBraunstein),
# Joel Gibson (University of Sydney, @joelgibson), and Tom Schmit (@schto223)
###############################################################################
#
# Weyl Groups
#
###############################################################################
@attributes mutable struct WeylGroup <: AbstractAlgebra.Group
finite::Bool # finite indicates whether the Weyl group is finite
refl::Matrix{UInt} # see positive_roots_and_reflections
root_system::RootSystem # root_system is the RootSystem from which the Weyl group was constructed
function WeylGroup(finite::Bool, refl::Matrix{UInt}, root_system::RootSystem)
return new(finite, refl, root_system)
end
end
struct WeylGroupElem <: AbstractAlgebra.GroupElem
parent::WeylGroup # parent group
word::Vector{UInt8} # short revlex normal form of the word
function WeylGroupElem(W::WeylGroup, word::Vector{<:Integer}; normalize::Bool=true)
if !normalize
if word isa Vector{UInt8}
return new(W, word)
else
return new(W, UInt8.(word))
end
end
@req all(1 <= i <= ngens(W) for i in word) "word contains invalid generators"
x = new(W, sizehint!(UInt8[], length(word)))
for s in Iterators.reverse(word)
lmul!(x, s)
end
return x
end
end
const WeylIteratorNoCopyState = Tuple{WeightLatticeElem,WeylGroupElem}
@doc raw"""
weyl_group(cartan_matrix::ZZMatrix) -> WeylGroup
Returns the Weyl group defined by a generalized Cartan matrix `cartan_matrix`.
"""
function weyl_group(cartan_matrix::ZZMatrix)
return weyl_group(root_system(cartan_matrix))
end
@doc raw"""
weyl_group(fam::Symbol, rk::Int) -> WeylGroup
Returns the Weyl group of the given type. See `cartan_matrix(fam::Symbol, rk::Int)` for allowed combinations.
# Examples
```jldoctest
julia> weyl_group(:A, 2)
Weyl group for root system defined by Cartan matrix [2 -1; -1 2]
```
"""
function weyl_group(fam::Symbol, rk::Int)
return weyl_group(root_system(fam, rk))
end
@doc raw"""
weyl_group(type::Vector{Tuple{Symbol,Int}}) -> WeylGroup
Returns the Weyl group of the given type. See `cartan_matrix(fam::Symbol, rk::Int)` for allowed combinations.
"""
function weyl_group(type::Vector{Tuple{Symbol,Int}})
return weyl_group(root_system(type))
end
@doc raw"""
weyl_group(type::Tuple{Symbol,Int}...) -> WeylGroup
Returns the Weyl group of the given type. See `cartan_matrix(fam::Symbol, rk::Int)` for allowed combinations.
"""
function weyl_group(type::Tuple{Symbol,Int}...)
return weyl_group(root_system(collect(type)))
end
@doc raw"""
(W::WeylGroup)(word::Vector{Int}) -> WeylGroupElem
"""
function (W::WeylGroup)(word::Vector{<:Integer}; normalize::Bool=true)
return WeylGroupElem(W, word; normalize=normalize)
end
function Base.IteratorSize(::Type{WeylGroup})
return Base.SizeUnknown()
end
function Base.eltype(::Type{WeylGroup})
return WeylGroupElem
end
function Base.iterate(W::WeylGroup)
state = (weyl_vector(root_system(W)), one(W))
return one(W), state
end
function Base.iterate(W::WeylGroup, state::WeylIteratorNoCopyState)
state = _iterate_nocopy(state)
if isnothing(state)
return nothing
end
return deepcopy(state[2]), state
end
@doc raw"""
isfinite(W::WeylGroup) -> Bool
"""
function is_finite(W::WeylGroup)
return W.finite
end
@doc raw"""
one(W::WeylGroup) -> WeylGroupElem
"""
function Base.one(W::WeylGroup)
return W(UInt8[]; normalize=false)
end
function Base.show(io::IO, W::WeylGroup)
@show_name(io, W)
@show_special(io, W)
print(pretty(io), LowercaseOff(), "Weyl group for ", Lowercase(), W.root_system)
end
function coxeter_matrix(W::WeylGroup)
return cartan_to_coxeter_matrix(cartan_matrix(root_system(W)))
end
function elem_type(::Type{WeylGroup})
return WeylGroupElem
end
@doc raw"""
gen(W::WeylGroup, i::Int) -> WeylGroupElem
Returns the `i`th simple reflection (with respect to the underlying root system) of `W`.
"""
function gen(W::WeylGroup, i::Integer)
@req 1 <= i <= ngens(W) "invalid index"
return W(UInt8[i]; normalize=false)
end
@doc raw"""
gens(W::WeylGroup) -> WeylGroupElem
Returns the simple reflections (with respect to the underlying root system) of `W`.
"""
function gens(W::WeylGroup)
return [gen(W, i) for i in 1:ngens(W)]
end
@doc raw"""
longest_element(W::WeylGroup) -> WeylGroupElem
Returns the unique longest element of `W`.
"""
function longest_element(W::WeylGroup)
@req is_finite(W) "$W is not finite"
_, w0 = conjugate_dominant_weight_with_elem(-weyl_vector(root_system(W)))
return w0
end
@doc raw"""
number_of_generators(W::WeylGroup) -> Int
Returns the number of generators of the `W`, i.e. the rank of the underyling root system.
"""
function number_of_generators(W::WeylGroup)
return rank(root_system(W))
end
@doc raw"""
order(::Type{T}, W::WeylGroup) where {T} -> T
Returns the order of `W`.
"""
function order(::Type{T}, W::WeylGroup) where {T}
if !is_finite(W)
throw(InfiniteOrderError(W))
end
ord = T(1)
for (fam, rk) in root_system_type(root_system(W))
if fam == :A
ord *= T(factorial(rk + 1))
elseif fam == :B || fam == :C
ord *= T(2^rk * factorial(rk))
elseif fam == :D
ord *= T(2^(rk - 1) * factorial(rk))
elseif fam == :E
if rk == 6
ord *= T(51840)
elseif rk == 7
ord *= T(2903040)
elseif rk == 8
ord *= T(696729600)
end
elseif fam == :F
ord *= T(1152)
else
ord *= T(12)
end
end
return ord
end
@doc raw"""
root_system(W::WeylGroup) -> RootSystem
Returns the underlying root system of `W`.
"""
function root_system(W::WeylGroup)
return W.root_system
end
###############################################################################
# Weyl group elements
function Base.:(*)(x::WeylGroupElem, y::WeylGroupElem)
@req x.parent === y.parent "$x, $y must belong to the same Weyl group"
p = deepcopy(y)
for s in Iterators.reverse(word(x))
lmul!(p, s)
end
return p
end
function Base.:(*)(x::WeylGroupElem, w::WeightLatticeElem)
@req root_system(parent(x)) === root_system(w) "Incompatible root systems"
w2 = deepcopy(w)
for s in Iterators.reverse(x.word)
reflect!(w2, Int(s))
end
return w2
end
# to be removed once GroupCore is supported
function Base.:(^)(x::WeylGroupElem, n::Int)
if n == 0
return one(parent(x))
elseif n < 0
return inv(x)^(-n)
end
px = deepcopy(x)
for _ in 2:n
for s in Iterators.reverse(x.word)
lmul!(px, s)
end
end
return px
end
@doc raw"""
<(x::WeylGroupElem, y::WeylGroupElem) -> Bool
Returns whether `x` is smaller than `y` with respect to the Bruhat order,
i.e., whether some (not necessarily connected) subexpression of a reduced
decomposition of `y`, is a reduced decomposition of `x`.
"""
function Base.:(<)(x::WeylGroupElem, y::WeylGroupElem)
@req parent(x) === parent(y) "$x, $y must belong to the same Weyl group"
if length(x) >= length(y)
return false
elseif isone(x)
return true
end
tx = deepcopy(x)
for i in 1:length(y)
b, j, _ = explain_lmul(tx, y[i])
if !b
deleteat!(word(tx), j)
if isone(tx)
return true
end
end
if length(tx) > length(y) - i
return false
end
end
return false
end
function Base.:(==)(x::WeylGroupElem, y::WeylGroupElem)
return x.parent === y.parent && x.word == y.word
end
function Base.deepcopy_internal(x::WeylGroupElem, dict::IdDict)
if haskey(dict, x)
return dict[x]
end
y = parent(x)(deepcopy_internal(word(x), dict); normalize=false)
dict[x] = y
return y
end
@doc raw"""
getindex(x::WeylGroupElem, i::Int) -> UInt8
Returns the index of simple reflection at the `i`th position in the normal form of `x`.
"""
function Base.getindex(x::WeylGroupElem, i::Int)
return word(x)[i]
end
function Base.hash(x::WeylGroupElem, h::UInt)
b = 0x80f0abce1c544784 % UInt
h = hash(x.parent, h)
h = hash(x.word, h)
return xor(h, b)
end
@doc raw"""
inv(x::WeylGroupElem) -> WeylGroupElem
Returns the inverse of `x`.
"""
function Base.inv(x::WeylGroupElem)
y = parent(x)(sizehint!(UInt8[], length(x)); normalize=false)
for s in word(x)
lmul!(y, s)
end
return y
end
@doc raw"""
isone(x::WeylGroupElem) -> Bool
Returns whether `x` is the identity.
"""
function Base.isone(x::WeylGroupElem)
return isempty(word(x))
end
@doc raw"""
length(x::WeylGroupElem) -> Int
Returns the length of `x`.
"""
function Base.length(x::WeylGroupElem)
return length(word(x))
end
@doc raw"""
parent(x::WeylGroupElem) -> WeylGroup
Returns the Weyl group that `x` is an element of.
"""
function Base.parent(x::WeylGroupElem)
return x.parent
end
@doc raw"""
rand(rng::Random.AbstractRNG, rs::Random.SamplerTrivial{WeylGroup})
Returns a random element of the Weyl group. The elements are not uniformally distributed.
"""
function Base.rand(rng::Random.AbstractRNG, rs::Random.SamplerTrivial{WeylGroup})
W = rs[]
return W(Int.(Random.randsubseq(rng, word(longest_element(W)), 2 / 3)))
end
function Base.show(io::IO, x::WeylGroupElem)
@show_name(io, x)
@show_special_elem(io, x)
if length(x.word) == 0
print(io, "id")
else
print(io, join(Iterators.map(i -> "s$i", x.word), " * "))
end
end
@doc raw"""
lmul(x::WeylGroupElem, i::Integer) -> WeylGroupElem
Returns the result of multiplying `x` from the left by the `i`th simple reflection.
"""
function lmul(x::WeylGroupElem, i::Integer)
return lmul!(deepcopy(x), i)
end
@doc raw"""
lmul!(x::WeylGroupElem, i::Integer) -> WeylGroupElem
Returns the result of multiplying `x` in place from the left by the `i`th simple reflection.
"""
function lmul!(x::WeylGroupElem, i::Integer)
b, j, r = explain_lmul(x, i)
if b
insert!(word(x), j, r)
else
deleteat!(word(x), j)
end
return x
end
# explains what multiplication of s_i from the left will do.
# Returns a tuple where the first entry is true/false, depending on whether an insertion or deletion will happen,
# the second entry is the position, and the third is the simple root.
function explain_lmul(x::WeylGroupElem, i::Integer)
@req 1 <= i <= rank(root_system(parent(x))) "Invalid generator"
insert_index = 1
insert_letter = UInt8(i)
root = insert_letter
for s in 1:length(x)
if x[s] == root
return false, s, x[s]
end
root = parent(x).refl[Int(x[s]), Int(root)]
if iszero(root)
# r is no longer a minimal root, meaning we found the best insertion point
return true, insert_index, insert_letter
end
# check if we have a better insertion point now. Since word[i] is a simple
# root, if root < word[i] it must be simple.
if root < x[s]
insert_index = s + 1
insert_letter = UInt8(root)
end
end
return true, insert_index, insert_letter
end
function parent_type(::Type{WeylGroupElem})
return WeylGroup
end
# rename to reduced decompositions ?
function reduced_expressions(x::WeylGroupElem; up_to_commutation::Bool=false)
return ReducedExpressionIterator(x, up_to_commutation)
end
@doc raw"""
word(x::WeylGroupElem) -> Vector{UInt8}
"""
function word(x::WeylGroupElem)
return x.word
end
###############################################################################
# ReducedExpressionIterator
struct ReducedExpressionIterator
el::WeylGroupElem # the Weyl group element for which we a searching reduced expressions
#letters::Vector{UInt8} # letters are the simple reflections occuring in one (hence any) reduced expression of el
up_to_commutation::Bool # if true and say s1 and s3 commute, we only list s3*s1 and not s1*s3
end
function Base.IteratorSize(::Type{ReducedExpressionIterator})
return Base.SizeUnknown()
end
function Base.eltype(::Type{ReducedExpressionIterator})
return Vector{UInt8}
end
function Base.iterate(iter::ReducedExpressionIterator)
w = deepcopy(word(iter.el))
return w, w
end
function Base.iterate(iter::ReducedExpressionIterator, word::Vector{UInt8})
rk = rank(root_system(parent(iter.el)))
# we need to copy word; iterate behaves differently when length is (not) known
next = deepcopy(word)
weight = reflect!(weyl_vector(root_system(parent(iter.el))), Int(next[1]))
i = 1
s = rk + 1
while true
# search for new simple reflection to add to the word
while s <= rk && weight.vec[s] > 0
s += 1
end
if s == rk + 1
i += 1
if i == length(next) + 1
return nothing
elseif i == 1
return next, next
end
# revert last reflection and continue with next one
s = Int(next[i])
reflect!(weight, s)
s += 1
else
if iter.up_to_commutation &&
i < length(word) &&
s < next[i + 1] &&
is_zero_entry(cartan_matrix(root_system(parent(iter.el))), s, Int(next[i + 1]))
s += 1
continue
end
next[i] = UInt8(s)
reflect!(weight, s)
i -= 1
s = 1
end
end
end
###############################################################################
# WeylIteratorNoCopy
# Iterates over all weights in the Weyl group orbit of the dominant weight `weight`,
# or analogously over all elements in the quotient W/W_P
# The iterator returns a tuple (wt, x), such that x*wt == iter.weight;
# this choice is made to align with conjugate_dominant_weight_with_elem
struct WeylIteratorNoCopy
weight::WeightLatticeElem # dominant weight
weyl_group::WeylGroup
function WeylIteratorNoCopy(wt::WeightLatticeElem)
return new(conjugate_dominant_weight(wt), weyl_group(root_system(wt)))
end
end
function Base.IteratorSize(::Type{WeylIteratorNoCopy})
return Base.SizeUnknown()
end
function Base.eltype(::Type{WeylIteratorNoCopy})
return WeylIteratorNoCopyState
end
function Base.iterate(iter::WeylIteratorNoCopy)
state = deepcopy(iter.weight), one(iter.weyl_group)
return state, state
end
# based on [Ste01], 4.C and 4.D
function Base.iterate(iter::WeylIteratorNoCopy, state::WeylIteratorNoCopyState)
state = _iterate_nocopy(state)
if isnothing(state)
return nothing
end
return state, state
end
function _iterate_nocopy(state::WeylIteratorNoCopyState)
wt, path = state[1], word(state[2])
R = root_system(wt)
ai = isempty(path) ? UInt8(0) : path[end]
# compute next descendant index
di = UInt8(0)
while true
di = next_descendant_index(Int(ai), Int(di), wt)
if !iszero(di)
break
elseif isempty(path)
return nothing
elseif iszero(di)
reflect!(wt, Int(ai))
di = pop!(path)
ai = isempty(path) ? UInt8(0) : path[end]
end
end
push!(path, di)
reflect!(wt, Int(di))
return state
end
# based on [Ste01], 4.D
function next_descendant_index(ai::Int, di::Int, wt::WeightLatticeElem)
if iszero(ai)
for j in (di + 1):rank(root_system(wt))
if !iszero(wt[j])
return j
end
end
return 0
end
for j in (di + 1):(ai - 1)
if !iszero(wt[j])
return j
end
end
for j in (max(ai, di) + 1):rank(root_system(wt))
if is_zero_entry(cartan_matrix(root_system(wt)), ai, j)
continue
end
ok = true
for k in ai:(j - 1)
if reflect(wt, j)[k] < 0
ok = false
break
end
end
if ok
return j
end
end
return 0
end
###############################################################################
# WeylOrbitIterator
struct WeylOrbitIterator
nocopy::WeylIteratorNoCopy
function WeylOrbitIterator(wt::WeightLatticeElem)
return new(WeylIteratorNoCopy(wt))
end
end
@doc raw"""
weyl_orbit(wt::WeightLatticeElem)
Returns an iterator over the Weyl group orbit at the weight `wt`.
"""
function weyl_orbit(wt::WeightLatticeElem)
return WeylOrbitIterator(wt)
end
@doc raw"""
weyl_orbit(R::RootSystem, vec::Vector{<:Integer})
Shorthand for `weyl_orbit(WeightLatticeElem(R, vec))`.
"""
function weyl_orbit(R::RootSystem, vec::Vector{<:Integer})
return weyl_orbit(WeightLatticeElem(R, vec))
end
@doc raw"""
weyl_orbit(W::WeylGroup, vec::Vector{<:Integer})
Shorthand for `weyl_orbit(root_system(R), vec)`.
"""
function weyl_orbit(W::WeylGroup, vec::Vector{<:Integer})
return weyl_orbit(root_system(W), vec)
end
function Base.IteratorSize(::Type{WeylOrbitIterator})
return Base.IteratorSize(WeylIteratorNoCopy)
end
function Base.eltype(::Type{WeylOrbitIterator})
return WeightLatticeElem
end
function Base.iterate(iter::WeylOrbitIterator)
(wt, _), data = iterate(iter.nocopy)
# wt is already a copy, so here we don't need to make one
return wt, data
end
function Base.iterate(iter::WeylOrbitIterator, state::WeylIteratorNoCopyState)
it = iterate(iter.nocopy, state)
if isnothing(it)
return nothing
end
(wt, _), state = it
return deepcopy(wt), state
end