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: |

### 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:2 Changed 5 years ago by

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

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

I see the following two problems:

- finding roots of a polynomial over the UCF does not seem to be implemented.
- 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. - the minpoly is not implemented for matrices over the UCF.

### comment:5 Changed 5 years ago by

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

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).

### comment:7 Changed 5 years ago by

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.

The last problem is with the

`cartan_type`

of`ReflectionGroup`

:whereas it should use more of the information in

`self._type`

(at least for I_{2}(m)).