Help needed with getting PARI/GP residue fields in Sage finite field form

[Misja]

For a number field N I am trying to factor an integral prime p in a p-maximal order Op. In the end I would like a map from the quotient of the p-maximal order Op/P (for P|p) to some finite field in Sage's standard finite field form, but I can't quite figure out how to do it.

Firstly, Sage doesn't have ideals or residue fields of non-maximal orders implemented, so I am trying to compute the factorisation of p in Op via the PARI/GP interface with sage. I think this can be done, for example, in the following way, in which we compute a 7-maximal order of the number field defined by x^8+x^3-13*x+26 and compute all primes above 7 in this order.

x=polygen(QQ);

nf=gp.nfinit([x^8 + x^3 - 13*x + 26,[7]]); #Note the [7] at the end, indicating a 7-maximal order only.
nf; 

fact=gp.idealprimedec(nf,7);
fact;

res_field_sizes=[];

for i in fact:

    res_field_sizes.append(i[1]**i[4]);

res_field_sizes;

Now, for each element fact[i] of fact, I would like to compute a homomorphism Op->Op/fact[i]->GF(res_field_sizes[i-1],'gen') - note that we're using a vector in pari/gp and a list in sage hence fact[i] corresponds to res_field_sizes[i-1]. I can't quite get this to work.

I feel like there are two options:

1. Translate the p-maximal order and prime factorisation back to sage. Take a poly quotient or something. Map this to a finite field.
2. Keep on working in pari/gp and use, for example, nfeltreducemodpr to reduce elts of Op to the residue field (does this really calculate Op/P if the nf.zk is a non-maximal Z-basis?). Map this to a finite field somehow. Translate back to Sage.

I can't really get either approach to work at the moment. But I wouldn't call myself a big Sage or PARI/GP expert, so it is very possible that I am missing something.

Any suggestions would be much appreciated!

[David Loeffler]

There are two reasons why people work with non-maximal orders: because they're actually interested in their arithmetic; or (more often) because they're working with examples where the discriminant is too large to efficiently factor. Which is the case in your problem? In the example you give, you're letting PARI choose the order for you, but the discriminant is small enough that one can find a maximal order in a few milliseconds anyway (and Sage is perfectly happy to work with residue fields of maximal orders).

If you genuinely don't want to factor the discriminant, but the orders you're interested in are "monogenic" (generated by a single element over Z), then you can just factor the characteristic polynomial of the generator over Fp and that gives you the factorisation, and the reduction maps, immediately.

Can you give an example of a case you'd be interested in where the maximal order is really too big to easily find?

Regards, David

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[Misja]

Hi David,

Thank you very much for this helpful reply! You're right, of course: my example was silly. Here's an example with a 104 digit discriminant that my code just got stuck on (for a bit).

x=polygen(QQ);

K=NumberField(x^5 + 16255223088*(x^4) - 330681713908949415936*(x^3) - 5058938091171222191449571328000*(x^2) - 2907488578277274989701398473183198183424*x + 76587534178613500902724649685949865805676749520896,'a');

fact=K.factor(5);

print K.residue_field(fact[0][0]);

What I am trying to do is to calculate reductions of modular forms modulo some prime ideal P. However, the coefficients of such a modular form may lie in a number field with a 1000 digit discriminant and I want to avoid trying to factor this if I can, hence my trying to use p-maximal orders.

Could you explain a bit more what you mean in the monogenic case? Could you do something like EquationOrder(K.defining_polynomial(),'alpha'), take a p-maximal order there and then do what you are suggesting? Although, actually, I don't know if sage can calculate a p-maximal order of a given order.

Misja

[David Loeffler]

Dear Misja,

What I had in mind was something like this. Given some monstrous number field K with enormous discriminant, and some small prime p, you can ask Sage for a p-maximal order and it'll find one reasonably quickly, as you know.

All I was saying is that if the resulting order O is of the form Z[X] / (f), for some polynomial f in Z[X] -- i.e. if "O.ring_generators()" is a list of length 1 -- then you can quickly compute all possible maps O --> Fp-bar by just factoring f modulo p. (Sage really ought to have this coded up already; sadly it doesn't, but it's trivial to implement.) Maybe this isn't a terribly helpful remark; I don't know how likely it is that the orders you work with have this form.

David

[David Loeffler]

PS: In your example, the order generated by the element

b = 3033120361/143075599831793664*a^4 + 1953773/876688724459520*a^3 + 53/38811740405760*a^2 + 1/3158507520*a

is actually locally maximal at 7, so you can compute all the primes above 7 and the residue maps for this order just by computing the min poly of b and factorising it mod 7. Amusingly, the factorisation of the minimal polynomial turns out to be

sage: b.minpoly().change_ring(GF(7)).factor()

(x + 2) * (x + 3) * (x + 4) * (x + 5) * (x + 6)

David

[Misja]

On the contrary: it is a helpful remark! I hadn't realised this before. At least I can check whether I am lucky and the order is of the form Z[X]/(f) and proceed very quickly if so :-)