michaelmusty/belyi

belyi's Issues

PassportRepresentatives -> Mass

In line 76 of BelyiMap (main function), we compute the number of passport representatives, which indicates how much precision we'll need since that grows with the degree. But this can eat up all memory.

We only need an estimate here, so I propose we place this with a mass computation instead, which should be much faster.

PassportRepresentatives

lambda := [
        [ <2, 8>, <1, 7> ],
        [ <8, 2>, <4, 1>, <2, 1>, <1, 1> ],
        [ <8, 2>, <4, 1>, <2, 1>, <1, 1> ]
    ];
G := TransitiveGroup(23,5);
pass := PassportRepresentatives(G : partitions := lambda);
pass[1]; 

gives as output:

[*
    [
        [ <2, 8>, <1, 7> ],
        [ <7, 3>, <1, 2> ],
        [ <8, 2>, <4, 1>, <2, 1>, <1, 1> ]

So it's returning output that doesn't satisfy the vararg conditions.

Need examples

Including a Euclidean map of large degree

Genus one and hyperelliptic: nevermind about series

Did some experiments including a large degree example and it is really tricky to get the matrix which computes the coefficients of the Belyi map using power series expansions to have good stability properties. You can fiddle with a lot of things (replace w <- c*w in the series, rescale x and y, etc.), and this can significantly change things like the condition number.

But I'm not sure we need any of this! The series are designed to behave when they are evaluated, and indeed when we work in precision 10^(-100) we'll get values of x and y that are pretty close to that amount of precision. (Even though the precision in the coefficients decays polynomially.)

In genus zero, no series are solved for: the Newton equations are set up using the ramification values in the usual way: we write A(x) + B(x) = C(x) with A,B,C factored, and we plug in the approximate roots.

I think we can do the same in the elliptic and hyperelliptic case. Because of the issue of the common zero, we may need just a tiny bit from the series, imposing a few additional linear equations, but that should be it. That should mean that we can get away with much less power series precision, which means the whole thing will run a lot lot faster.

BelyiDB in galoisorbits.m

We didn't get a clean breakup: there are functions in galoisorbits.m that call BelyiDB functions. They should be moved there.

Euclidean descent

Matt Radosevich's code is super fast to compute Euclidean Belyi maps. But unfortunately the method does not guarantee descent to a minimal field of definition, and actually I'm not sure it will always be possible!

But there are many cases where it should be possible, and for that we'd need an algorithm.

Examples where I did descent by hand:

• 6T10-[4,4,2]-42-42-2211-g0
• 6T6-[6,3,2]-6-33-21111-g0

Currently the code in this case gives a map defined over a quadratic extension of the minimal field.

Here are ones where I haven't yet descended:

• 8T20-[4,4,2]-44-44-221111-g0
• 8T21-[4,4,2]-422-422-2222-g0
• 9T13-[6,3,2]-63-333-222111-g0
• 9T7-[3,3,3]-333-333-333-g1

Improvements for large passports

Our code runs reasonably well when the base field doesn't have too large of a degree. We should think about a better approach when the degree is large. Here are some thoughts:

• We should be able to quickly identify and assign Galois conjugate Belyi maps, once we have computed one such. So maybe a vararg to BelyiMap which takes possible Galois conjugates Gamma', and then it does just enough power series computations to get complex approximations to coefficients, which can then be matched against the known values. If that fails, it computes the maps.
• Maybe in some cases we'll only ever want to know a Polredabs for the pointed field of definition (usually the pointed field of moduli). We could add a flag for this, which would save time in computing all the coefficients of the map.

We now depend on MagmaPolred

How do we handle this dependency in a reasonable way, without assuming that all of our users have CHIMPed up?

Rewrite history to make BelyDB deletion permanent

https://stackoverflow.com/questions/43762338/how-to-remove-file-from-git-history

Genus zero equations

Right now, in genus zero we only use the equations implied by
A(x) - B(x) = C(x)
where phi(x) = A(x)/B(x) and phi(x)-1 = C(x)/B(x).

The resulting ideal is far from reduced (see SV, https://math.dartmouth.edu/~jvoight/articles/compute-belyi-090519.pdf, Example 2.11), and a way to improve things is to apply the Atkin-Swinnerton-Dyer trick.

We should be able to get away with a lot less precision as input into Newton this way.

Precision

AttachSpec("spec");
sigma := [Sym(4) | (1,2,3,4), (1,3,4,2), (1,3,4)];
Gamma := TriangleSubgroup(sigma);
SetVerbose("Shimura", true);
FundamentalDomain(Gamma : Precision := 70);
X, phi := BelyiMap(Gamma);

The above code fails, but works if you delete the FundamentalDomain line. Something is wrong when it computes the elliptic curve periods, and it's a precision issue (the imaginary parts are 10^-30, and should be zero). [And if you replace the last line with BelyiMap(Gamma : Precision := 30), it works again.]