Opened 23 months ago

Wrong computations for reflection groups

Reported by: Owned by: stumpc5 major sage-8.2 combinatorics gap3, reflection group nthiery, tscrim, chapoton N/A

Description

We currently use intensively the reflection group code in Sage. Here we report bugs that are there because the connections to other pars of Sage are broken. We will update when we find further issues.

• absolute_length and canonical_matrix was broken but recently fixed, thanks (we realized only after not using my collaborators old Sage version).
• the reflection group element cycle type gives you the cycle type in the permutation representation on the roots. This is *not* the cycle type of the reflection group element
• the Cartan type for dihedral types is broken:
sage: W = ReflectionGroup(['I',5])
sage: W.cartan_type()
['I', 2]

comment:1 Changed 23 months ago by tscrim

The last problem is with the cartan_type of ReflectionGroup:

ct = self._type
return CartanType([ct['series'], ct['rank']])

whereas it should use more of the information in self._type (at least for I2(m)).

Last edited 23 months ago by tscrim (previous) (diff)

comment:2 Changed 23 months ago by stumpc5

Not quite a bug, but an issue to check: computing the eigenvalues of the reflection group elements currently calls gap3 and needs (for no good reason, I believe) all conjugacy classes representatives to be known already. Instead calling to_matrix().minpoly() seems to be much faster, we would then only need to check how to parse it to some cyclotomic field.

comment:3 Changed 23 months ago by tscrim

What about doing the computation over the UCF and then possibly converting to the appropriate cyclotomic field? Or is there a theorem about what roots of unity we can expect?

comment:4 Changed 23 months ago by stumpc5

I see the following two problems:

1. finding roots of a polynomial over the UCF does not seem to be implemented.
2. concerning the output, we currently have a list of rationals k/h representing E(h)^k. This would also be the optimal way of representing the eigenvalues.
3. the minpoly is not implemented for matrices over the UCF.

comment:5 Changed 23 months ago by tscrim

At least on some simple testing I have been able to get the minpoly:

sage: W = ReflectionGroup(29)
sage: x = prod(W.gens()).matrix()
sage: x

[      1/2 -1/2*E(4)       1/2 -1/2*E(4)]
[      1/2  1/2*E(4)       1/2  1/2*E(4)]
[-1/2*E(4)       1/2  1/2*E(4)      -1/2]
[ 1/2*E(4)       1/2 -1/2*E(4)      -1/2]
sage: x.minpoly()
x^4 - E(4)*x^3 - x^2 + E(4)*x + 1

Although it is quite possible this will fail for only certain elements because of the call to factor in minpoly if it gets past the is_squarefree. Although to get the eigenvalues with multiplicities, we would need to factor the charpoly, and at least in that case, we could brute force search the coefficients and find the "minimal" cyclotomic field we would need, convert to that, and then call the factorization. Then we could either: convert back to UCF and then extract the data or manually extract the data (if we still wanted the list of rationals format).

comment:6 Changed 23 months ago by tscrim

Ah, I see the problem. We may not have a large enough cyclotomic field just by considering the one for the coefficient ring. With the example above:

sage: p = x.minpoly()
sage: p
x^4 - E(4)*x^3 - x^2 + E(4)*x + 1
sage: p.change_ring(CyclotomicField(4)).factor()
x^4 - zeta4*x^3 - x^2 + zeta4*x + 1
sage: p.change_ring(CyclotomicField(4)).roots()
[]

sage: p.change_ring(CyclotomicField(20)).factor()
(x + zeta20) * (x - zeta20^3) * (x - zeta20^7) * (x + zeta20^7 - zeta20^5 + zeta20^3 - zeta20)
sage: p.change_ring(CyclotomicField(20)).roots()
[(-zeta20, 1),
(zeta20^3, 1),
(zeta20^7, 1),
(-zeta20^7 + zeta20^5 - zeta20^3 + zeta20, 1)]
sage: for rt, m in p.change_ring(CyclotomicField(20)).roots():
....:     UCF(rt)
-E(20)
-E(20)^13
-E(20)^17
-E(20)^9

There probably is a smarter way than just increasing k in the cyclotomic field C(km) until the number of roots equals the degree. Although this would work and I believe avoid calls to gap (well, up to whatever the cyclotomic fields do).

Last edited 23 months ago by tscrim (previous) (diff)

comment:7 Changed 23 months ago by stumpc5

All roots will be in the cyclotomic field of the order of the element, so

sage: W = ReflectionGroup(29)
sage: w = W.coxeter_element()
sage: x = w.to_matrix()
sage: p = x.charpoly()
sage: p.change_ring(CyclotomicField(w.order())).roots()
[(-zeta20, 1),
(zeta20^3, 1),
(zeta20^7, 1),
(-zeta20^7 + zeta20^5 - zeta20^3 + zeta20, 1)]

works in this case. So we have to check that this really always works and is implemented, check its speed, and parse it back to a better format, preferably a/b) for E(a)^b. Observe for example that

sage: zeta20 = CyclotomicField(20).gen()
sage: a = -zeta20^7 + zeta20^5 - zeta20^3 + zeta20
sage: UCF = UniversalCyclotomicField()
sage: UCF(a)
-E(20)^9
Note: See TracTickets for help on using tickets.