Opened 5 years ago

Last modified 5 years ago

#24333 new defect

Wrong computations for reflection groups

Reported by: Christian Stump Owned by:
Priority: major Milestone: sage-8.2
Component: combinatorics Keywords: gap3, reflection group
Cc: Nicolas M. Thiéry, Travis Scrimshaw, Frédéric Chapoton Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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]
    

Change History (7)

comment:1 Changed 5 years ago by Travis Scrimshaw

The last problem is with the cartan_type of ReflectionGroup:

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

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

Last edited 5 years ago by Travis Scrimshaw (previous) (diff)

comment:2 Changed 5 years ago by Christian Stump

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 5 years ago by Travis Scrimshaw

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 5 years ago by Christian Stump

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 5 years ago by Travis Scrimshaw

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 5 years ago by Travis Scrimshaw

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 5 years ago by Travis Scrimshaw (previous) (diff)

comment:7 Changed 5 years ago by Christian Stump

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.