Linear algebra

[JRSijsling]

Polredbestabs has been integrated throughout, meaning that the determination of the endomorphism field is very fast and that the results at the end are even readable. This is awesome. The current package works very well now, over any field. Still, there are some things that give it pause, even in genus 2, and that have to do with linear algebra. This is not my specialty and it would be great to get some expert advice.

Check out the current SingleHyp.m. I entered a curve with Sato-Tate group J (O). This one requires a degree 48 extension to see all endomorphisms. The determination of that extension, call it K, goes very fast. However, after that I have to recognize elements gamma of CC as elements of K. Right now I take the following approach. I write down the powers of the embeddings of a generator of K and try to find a ZZ-linear dependence with gamma as the integral kernel of a certain matrix.

This works, but only if I set the precision very high. I think that this is disappointing. Sure, precision 100 should be needed here, or perhaps 200. But 1000 seems extreme. Probably part the reason is that alpha gets powered so much. There is also a parameter epsLLL to choose (defined in Precision.m) and there I have just done something that worked in most cases.

Can you see a better approach to solving this question?

Let gamma be an element of CC, and let K be a Galois number field with a fixed embedding iota into CC. Find an element beta of K of small height such that iota (beta) is very close to gamma.

[JRSijsling]

Actually there is one answer that usually works: find the minimal polynomial, determine the roots algebraically, and see which one works. But I find that vile (and it takes quite long in the J (O) case).

[jvoight]

Are you using LinearRelation in Magma with respect to an LLL-reduced basis of the ring of integers of K?

[JRSijsling]

In fact LinearRelation is deprecated and really slow, we have to use IntegerRelation. There you can also specify the maximum height that you accept. Sounds great, but

(1) When both versions work, then mine is quite a bit faster; (2) Precision 500 fails in both cases; (3) Precision 1000 works for my version, but fails when using IntegerRelation if I give it a height bound that I know to work (which is extremely sucky). (4) If I do not add a height bound, then IntegerRelation does work at precision 1000. But I know, from considering minimal polynomials, that this is a bad thing to do. In that case IntegerRelation will often find linear combinations that are too big, especially when the precision is small. Ironically, if I take a height bound that is largeish, then also things go wrong. Anyway, this suggests that IntegerRelation will be problematic on low precision, so does not resolve anything.

This must mean that we are doing difficult things. I feel better now and will keep things the way they were, then I at least know where things go wrong. In the meantime I will ask every numerics expert that I encounter what I should do.

[jvoight]

Wow, why is this problem so hard?

You're given complex numbers alpha, beta_1, ..., beta_n and you know there exist unique rational numbers r_i such that alpha = sum_i r_i*beta_i and you want to find the r_i given approximations to alpha the beta_i, right? Why can't you solve for the r_i's numerically, then use continued fractions to recognize the rational numbers r_i?

[JRSijsling]

Because there is no unique solution. The beta_i are all in CC, as is alpha. So the numerical kernel is big, size of the order of the degree of the number field. And then you have to find an integral element close to that.

[jvoight]

I mean embed using the Minkowski embedding, so there is a unique element in the numerical kernel with the coefficient of alpha equal to 1, up to rescaling. Finding the kernel of a 49 x 48 matrix over the complex numbers to 1000 digits of precision should be very doable.

[JRSijsling]

I had this thought once, but does not this require me to know what the conjugates of alpha are? And I do not, that is the crux.

[jvoight]

But at some point you recognized at least one minimal polynomial. Is it too expensive to do the rest? I thought this worked pretty well, using LLL. If so, then you have the conjugates.

[JRSijsling]

I still do not know which conjugate is which. But you make a good point.

[jvoight]

Hmm, that's true, but you only need to list the conjugates in the same way as G-sets.

But if you can compute all the minimal polynomials, then iterated polredbest should quickly almost always return the same polynomial, and it gives you the isomorphism, so then you just need to identify the right embedding. So maybe a modification like this of your "answer that usually works" is just fine.

[JRSijsling]

Identifying the right embedding gets us back to calculating the roots algebraically, which is what I wanted to avoid. Still, this may simply be needed, otherwise I really do not see how to magically detect the root order.

So I think that a compromise might be in order. I can try the current method and see if the element obtained is indeed a root. If that fails, we can revert to calculaing the roots of the polynomial algebraically. That is more expensive, but at least it is guaranteed to work.

(I agree that I should exploit known root embeddings, but in general I cannot; the field gets larger all the time, so these embeddings lose their relevance for the larger field obtained in the end.)

[JRSijsling]

Solved now; improvements by Nicolas enable us to calculate roots much faster, so that route is taken. Precision 100 now suffices.