Slow splitting fields

[rbommel]

When trying to run the test set for p = 2 and n = 4, the code is really slow and seems to be hanging on computing the splitting fields. It might be worth to reconsider the way these are generated now. Maybe it would be faster if they are all in standard form.

[rlercier]

I agree. The behavior of the SplittingField function in characteristic 2 is a bit of a mystery to me. In my few experiments, setting its option Std:=true doesn't seem to improve the timings (and it is worse in odd characteristic).

Otherwise, the few tests I did were for n=1, at the magma prompt: I stopped and restarted until I got a result in a reasonable time.

So, certainly, avoiding this splitting field calculation would be very useful, but how?

[rbommel]

Yes, maybe the ramification is just way worse (to be more precise: very wild) in that case. I agree that we can probably not solve this splitting field issue as part of this project. It would probably require rewriting Magma's p-adics, which I would rather not go into right now.

One thing I did notice is that the precision was increased to very high numbers. I did not look into this in detail yet, but I was wondering if it is maybe the case that the two points of tangency of one bitangent collide, i.e. that we actually have a quadtangent. Is this a case you already thought about?

[rlercier]

I also find this huge precision very intriguing, several thousand bits are not unusual.

But I don't see why the bitangents would be special in characteristic 2, it's not necessarily related, but for example quartic invariants in carac. 2 are quite nice (but it's hell in characteristic 3..). It's worth taking a look at it, I think

[rbommel]

One reason why they are different in characteristic 2 is that #Sp(6,2) has 9 factors 2. In general, the points of pairs of points of bitangency should give full level 2 structure, which means that the field extension needed, say over a number field, is expected to have a degree of #Sp(6,2). That means that there is a lot of possibility for ramification for the prime 2, much more than for any other prime. I am not convinced, though, that this would completely explain the huge precision that seems to be used, already in the case of good reduction.

[rlercier]

To try to understand what is going on, I propose that we do some experiments with a Rieman model (to have rational bitangents), simplified a bit with a call to MinimizeReducePlaneQuartic(), e.g.

  _<X,Y,Z> := PolynomialRing(Rationals(), 3);

  f := -30672435*X^4 - 29276301*X^3*Y + 3160135*X^3*Z + 38187637*X^2*Y^2 +
    12352731*X^2*Y*Z + 70442836*X^2*Z^2 - 834380*X*Y^3 + 46885124*X*Y^2*Z +
    46968525*X*Y*Z^2 - 26656943*X*Z^3 + 1331044*Y^4 + 5331504*Y^3*Z +
    5771148*Y^2*Z^2 - 10042517*Y*Z^3 + 2541016*Z^4;

So, the bitangent polynomial has a nice factorization over the rationals(), i.e

polinb :=
    (x - 104/11) *
    (x - 15/4) *
    (x - 11191899/8738020) *
    (x - 99/140) *
    (x - 782495495/1223143916) *
    (x - 26216/42249) *
    (x - 685/1984) *
    (x - 1/3) *
    (x - 409/1352) *
    (x - 1069/3759) *
    (x - 987875/4112608) *
    (x - 9/80) *
    (x - 517/5144) *
    (x + 8981/164520) *
    (x + 1/16) *
    (x + 561/2029) *
    (x + 3891/11168) *
    (x + 7/12) *
    (x + 1505321309/2333903473) *
    (x + 540/569) *
    (x + 13/9) *
    (x + 52/35) *
    (x + 4309/2248) *
    (x + 449/140) *
    (x + 7643804984113/2218052234104) *
    (x + 6691/911) *
    (x + 365/44) *
    (x + 4405677/79892);

This example seems to me quite instructive, it shows how badly conditioned this polynomial is. If we want to factor this polynomial in the following field, we have to go to the precision 500!

Q2 := pAdicField(2, 500);
_<x> := PolynomialRing(Q2);

Factorization(polinb);

Strangely, we find solutions when we work with a fixed precision (e.g 30 by default),

Q2 := pAdicField(2 : Exact := true);
_<x> := PolynomialRing(Q2);

Factorization(polinb);

[rbommel]

It seems that you lose a lot of precision while factoring a polynomial. I guess one can measure this somehow with Hensel's lemma. Given that two random integers have 50% chance to collide modulo 2, I guess it is to be expected that a reasonably high precision loss will occur. I can't remember if we tried this before, but do you think working with this exact p-adic field might improve things?

[rlercier]

do you think working with this exact p-adic field might improve things

I have doubts that it can work for the full algorithm (can we compute splitting fields in fixed precision ?), but why not for the factorization step as a starting point, and then further lift the result with hensel ?

Otherwise, one of the issue is probably the valuation at 2 of the discriminant of this polynomial (several hundreds...). So, an idea might be to minimize this discriminant up to some PGL2-transformation, and work with this improved polynomial instead. The magma function MinimizeAtP(f, 2) could be useful for this, I think.

[rlercier]

Something weird happens with the Klein curve f := x^3*y+x*z^3+y^3*z; modulo 2.

The curve has good reduction, but the octad thats pAdicCayleyOctad() compute have some subsets of 4 points that are coplanar modulo 2. Hence, the reduction type that QuarticTypeFromOctad() returns is (0eee) , instead of (3)?!

Note that I make the change of variable y->x+y in order to make pAdicCayleyOctad() work. So, I work with the curve F := x^4+x^3*y+x^3*z+3*x^2*y*z+3*x*y^2*z+x*z^3+y^3*z;

[rlercier]

This quartic is somehow instructive!

Even if a quartic defined modulo 2 has at most 7 bitangents (instead of 28 in odd characteristic), we can consider it 2-adically, and reduce the result modulo 2. Here, we can really find over GF(2) a determinantial form Determinant(x*A + y*B + z*C) isomorphic to x^3*y+x*z^3+y^3*z (see below for a definition of A, B, C).

But unlike what we have in odd characteristic, (0:1:1:0) is the only projective point (a:b:c:d)defined on the algebraic closure of GF(2) that is in the locus defined by the 3 quadratic forms given by A, B, C, i.e a^2 + b^2 + c^2=0, b^2 + c^2 + d^2=0 and a^2=0.

In other words , any 2-adic octad should have in such a situation its 8 points that are all equal modulo 2. Obviously our reduction criterions can not work "as is" in charracteristic 2!

I didn't look further, but I guess that it is possible to define octads in characteristic 2 as well (to avoid the problem of diagonalizing quadratic forms in characteristic 2).

`A := [ 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0 ] ;

B := [ 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1 ] ;

C := [ 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 ]; `

[rbommel]

In principle, it is no problem that all the points collide modulo 2, this could be undone with a PGL transformation. I do agree that some things might be different in characteristic 2, and that this maybe should be postponed for now.

[rlercier]

Yes, that's right. With this example, I understand better your point about octads in standard position (regardless of the characteristic).