Confusing behaviour with Dirichlet characters

[loefflerd]

Funny things happen if you have two Dirichlet groups with the same modulus and the same base ring, but different roots of unity. This can happen if you use base_extend:

sage: G = DirichletGroup(10, QQ).base_extend(CyclotomicField(4))
sage: H = DirichletGroup(10, CyclotomicField(4))

Now G and H look pretty similar:

sage: G
Group of Dirichlet characters of modulus 10 over Cyclotomic Field of order 4 and degree 2
sage: H
Group of Dirichlet characters of modulus 10 over Cyclotomic Field of order 4 and degree 2

But they don't compare as equal and the generators of H don't live in G:

sage: G == H
False
sage: H.0 in G
False

Here G only actually contains those characters which factor through its original base ring, namely QQ. This is probably going to be a bit mystifying for the end-user.

Similar phenomena can make it next to impossible to do arithmetic with characters obtained by base extension, which somehow are second-class citizens:

sage: K5 = CyclotomicField(5); K3 = CyclotomicField(3); K30 = CyclotomicField(30)
sage: (DirichletGroup(31, K5).0).base_extend(K30) * (DirichletGroup(31, K3).0).base_extend(K30)
TypeError: unsupported operand parent(s) for '*': 
'Group of Dirichlet characters of modulus 31 over Cyclotomic Field of order 30 and degree 8' and 
'Group of Dirichlet characters of modulus 31 over Cyclotomic Field of order 30 and degree 8'

This is a particularly mystifying error for the uninitiated, since it's asserting that it can't find a common parent, but the string representations of the parents it already has are identical.

There are a couple of solutions:

• Change base_extend for Dirichlet groups to pick a maximal order root of unity in the new base ring, rather than just base-extending the root of unity it already has. This is nice and transparent, but it could be slow in some cases, and it prevents us constructing Dirichlet characters with values in rings where the unit group isn't cyclic or we can't compute a generator (e.g. we'd lose the ability to base extend elements of DirichletGroup(N, ZZ) to DirichletGroup(N, Integers(15))).

• Change the _repr_ method for Dirichlet groups so it explicitly prints the root of unity involved. I don't like this idea much.

• Some combination of the above two, with a special class for Dirichlet groups over domains where a unique root of unity of maximal order dividing euler_phi(N) doesn't exist or can't be calculated. This might be fiddly to write and maintain.

• Make zeta optional (implemented in the current branch); see comment:18 for details

Depends on #18540

Component: modular forms

Keywords: Dirichlet characters, days71

Author: David Loeffler, Peter Bruin

Branch/Commit: 3b51d5d

Reviewer: Aly Deines

Issue created by migration from https://trac.sagemath.org/ticket/6018

[williamstein]

comment:1

David, I like your analysis of the situation a lot. I'm going to do what you suggest first. Regarding performance issues, I think if the user really is worried about that in some case, they can be explicit about the relevant spaces and zeta's.

[williamstein]

Attachment: trac_6018.patch.gz

[craigcitro]

comment:3

This looks like a nice clean fix -- my only worry would be that a few subtle choices cause mayhem with some random modular symbols code. William, did you run doctests on the modular/ directory?

Also, one potentially silly comment: your fix assumes that the constructor for DirichletGroup always chooses a maximal order and an appropriate zeta if one isn't given. While I can't imagine us ever changing that constructor to do anything different, should we either (1) explicitly choose the maximal order or (2) check and/or document this in some way? I think it's unlikely, but should it ever come up, a comment near that line of code pointing someone in the right direction could be a huge help ...

[loefflerd]

comment:4

I am running sage -testall on this patch at the moment.

The key question, I think, is what we want to happen in the following situation:

sage: f = DirichletGroup(17, ZZ).0
sage: f.base_extend(Integers(15))

This worked under the old approach, because the parent of the base-extended thing was the Dirichlet group of modulus 17 and zeta = ZZ(15)(-1), of order 2. But I suspect that with this patch it will fail now, with an error message about not being able to compute roots of unity mod 15.

I suggest a further modification which makes the constructor raise a more intelligent error message if the root of unity isn't specified and the base ring is one where we can't do factorisation. If the tests pass I will write such a patch, and give William's patch a positive review conditional on that.

[loefflerd]

Attachment: trac_6018-2.patch.gz

apply over previous patch

[loefflerd]

comment:5

As promised, here is a second patch. This takes a compromise approach where base_extend tries to calculate a maximal order root of unity in the new base ring if it's an integral domain, but otherwise uses the base-extension. I've added a couple of doctests, including one to illustrate the perils of the zeta_order argument.

If someone else can approve the new patch I think we're sorted.

[craigcitro]

comment:6

This looks good -- I just have two questions:

• In the last example, you show that weirdness ensues when the provided zeta doesn't have order zeta_order. Couldn't we (optionally, with a check=... parameter) check this? Having it on by default definitely seems like it'd stop users from shooting themselves in the foot.

• Is it possible for the call to base_ring(zeta) to raise an exception? If so, do we want to catch that and provide a more direct error message, or just let it go?

[loefflerd]

comment:7

The docs state several times that you don't actually need to supply zeta_order, so nobody's going to use the option in the first place unless they've got a pretty good reason to do so. I'd rather not make the code still more complicated! (Would it actually cause that much harm to get rid of the zeta_order argument entirely?)

If base_ring(zeta) raises an exception, the error message will say something like "Unable to coerce foo into bar", and it should be reasonably clear what the problem is. With these patches, the constructor will almost always be getting called without specifying zeta and zeta_order anyway.

David

[craigcitro]

comment:8

I'm a big fan of just removing the zeta_order argument -- looking at the code, there's no real reason to specify it, and it'll clean up a few statements in the constructor.

[loefflerd]

Attachment: trac_6018-3.patch.gz

[loefflerd]

comment:9

Here's a third patch that kills zeta_order. All doctests in modular/ pass, I'm running a full test cycle now.

[craigcitro]

comment:10

Two thumbs up! Apply all three.

[loefflerd]

apply only this patch

[williamstein]

comment:11

Attachment: trac_6018_folded.patch.gz

Hey, why, wait, what happens if you create a zeta such that zeta.multiplicative_order() doesn't work?!

sage: a = CDF(CyclotomicField(5).0)
sage: G = DirichletGroup(11, base_ring=a.parent(), zeta=a, zeta_order=5)
sage: G
Group of Dirichlet characters of modulus 11 over Complex Double Field
sage: G.0
[0.309016994375 + 0.951056516295*I]
sage: G.0(2)
0.309016994375 + 0.951056516295*I

Please revert getting rid of zeta_order and make that part of another ticket, keeping in mind that you can't exactly do that, since it is important. The above doctest should be put in that ticket since this problem wouldn't have happened if I had included the above test.

[loefflerd]

comment:12

OK, so would you be happy with applying just the first two patches?

David

[loefflerd]

comment:13

On reflection, the issue is surprisingly subtle.

Consider taking a Dirichlet group with values in the integers of a cyclotomic field K, and base_extending to: (1) the complex double field; (2) the residue field of a prime of K.

In case (1), your example shows that we can't expect the constructor of the new group to calculate the order of a given zeta. But case (2) shows that the order of the base-extended zeta might not be the same as the order of the original zeta, and one can easily get nonsense if one assumes this.

Case (1) is actually OK if we don't pass zeta as an argument at all, because we can factor polynomials in CDF. This is more or less what applying Craig's patch and mine will give: zeta_order is still available as an argument, but it's not used by the base extension code, which relies on the base ring supporting either polynomial factoring or multiplicative_order.

[sagetrac-git]

Changed commit from 0fa9dd5 to d0bb0e4

[jdemeyer]

comment:23

This is just a detail, but instead of

Group of Dirichlet characters of modulus 5 over Number Field in a with defining polynomial x^4 + 1 with values in the group of order 8 generated by a

I would prefer

Group of Dirichlet characters of modulus 5 with values in the group of order 8 generated by a over Number Field in a with defining polynomial x^4 + 1

[jdemeyer]

comment:24

Replying to @pjbruin:

Besides solving the problems in the ticket description, this ticket greatly speeds up constructing Dirichlet groups over number fields.

I assume that this is the main motivation for making zeta optional, right? I am not really convinced though that this extra complexity is needed...

It is true that zeta() for number fields is slow, but that can easily be improved (#18917).

[pjbruin]

comment:25

Replying to @jdemeyer:

Replying to @pjbruin:

Besides solving the problems in the ticket description, this ticket greatly speeds up constructing Dirichlet groups over number fields.

I assume that this is the main motivation for making zeta optional, right? I am not really convinced though that this extra complexity is needed...

This is not really true; it also makes more sense conceptually if one does not have to make a choice of root of unity. I think the problems related to base extension do deserve to be solved and are at least as important as the speed-up.

It is true that zeta() for number fields is slow, but that can easily be improved (#18917).

It would be great if it could, but when making a speed improvement to zeta() in #15486, I found out that it was necessary to avoid calling PARI's nfinit(), because it was too slow for the number fields involved. This unfortunately precludes using PARI's nfrootsof1()...

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

1431319

Trac 6018: improve repr() of Dirichlet groups

[sagetrac-git]

Changed commit from d0bb0e4 to 1431319

[pjbruin]

comment:27

Replying to @jdemeyer:

This is just a detail, but instead of

Group of Dirichlet characters of modulus 5 over Number Field in a with defining polynomial x^4 + 1 with values in the group of order 8 generated by a

I would prefer

Group of Dirichlet characters of modulus 5 with values in the group of order 8 generated by a over Number Field in a with defining polynomial x^4 + 1

I took the opportunity to make a more general improvement to the wording; the format is now

Group of Dirichlet characters modulo N with values in [the group of order M generated by Z in ]R

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

36dcdc3

Merge branch 'develop' into ticket/6018-DirichletGroup_zeta

[sagetrac-git]

Changed commit from 1431319 to 36dcdc3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

08052f9

Trac 6018: replace arith.gcd() and arith.lcm() by gcd() and lcm()

[sagetrac-git]

Changed commit from 36dcdc3 to 08052f9

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

cbc5d7f

Trac 6018: fix doctest failures

[sagetrac-git]

Changed commit from 08052f9 to cbc5d7f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3b51d5d

Merge branch 'develop' into ticket/6018-DirichletGroup_zeta

[sagetrac-git]

Changed commit from cbc5d7f to 3b51d5d

[adeines]

Reviewer: Aly Deines

[adeines]

comment:32

Looks good to me.

[adeines]

Changed keywords from Dirichlet characters to Dirichlet characters, days71

[vbraun]

comment:33

Doctests fail

[vbraun]

comment:34

http://build.sagedev.org/release/builders/%20%20slow%20AIMS%20%20%28Debian%207%2032%20bit%29%20incremental/builds/439/steps/shell_4/logs/stdio

[pjbruin]

comment:35

Replying to @vbraun:

http://build.sagedev.org/release/builders/%20%20slow%20AIMS%20%20%28Debian%207%2032%20bit%29%20incremental/builds/439/steps/shell_4/logs/stdio

From the failing doctest in cachefunc.pyx, it seems that #15692 is also merged in that branch; I suspect the failure is actually due to that ticket (cf. #15692 comment:48).

[vbraun]

Changed branch from u/pbruin/6018-DirichletGroup_zeta to 3b51d5d