Re: nfinit() is eager for memory

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Sat, Aug 07, 2010 at 05:53:53PM -0400, Max Alekseyev wrote:
> >> Is that expected? Does nfinit() indeed needs that much memory?
> >
> > Independently of the algorithm used, nfinit output (amon other things) the
> > multiplication table which is a NxNxN tensor where N is the degree of the polynomial.
> > Here N = 45360, so it has 93*10^12 entries. This will not fit in memory.
> 
> Is there a way to overcome this?
> My goal is to compute
> nffactor(x^3+x^2-16440*x+80375,nfinit(polcyclo(49321,y)))
> that is, to express roots of x^3+x^2-16440*x+80375 in terms of
> trigonometric functions (by later substituting y=exp(2*Pi*I/49321)).

This is a known computation so there is a better way to do it:
? B=bnfinit(y);
? R=rnfconductor(B,x^3+x^2-16440*x+80375)
%2 = [[Mat(49321), [0]], [22680, [1260, 6, 3], [34059, 26752, [-10111]~]], [1, 0, 0; 0, 3, 1; 0, 0, 1]]

This tells you that x^3+x^2-16440*x+80375 defines an abelian extension of Q of conductor
49321 and congruence subgroup [1, 0, 0; 0, 3, 1; 0, 0, 1] over [22680, [1260,
6, 3], [34059, 26752, -10111]].

Now compute the associated Gauss sums:
(This is a bit cumbersome since they have 7560 cosine terms each).

a=Mod(34059,49321);b=Mod(26752,49321);c=Mod(-10111,49321);
S1=sum(i=1,1260,sum(j=1,2,sum(k=1,3,2*cos(2*lift(a^i*b^(3*j+k)*c^k)*Pi/49321))))
S2=sum(i=1,1260,sum(j=1,2,sum(k=1,3,2*cos(2*lift(a^i*b^(3*j+k+1)*c^k)*Pi/49321))))
S3=sum(i=1,1260,sum(j=1,2,sum(k=1,3,2*cos(2*lift(a^i*b^(3*j+k+2)*c^k)*Pi/49321))))

PARI will compute the minimal polynomial of theses Gauss sums (using
essentially the above formulae) with:

? galoissubcyclo([22680, [1260, 6, 3], [a, b, c]], R[3])
%7 = x^3 + x^2 - 16440*x + 80375

Since %65 is the polynomial you are looking for, you are done. Else you would need 
to factor your polynomial over the field given by this one (of degree 3 instead of
45360).

So S1,S2,S3 are the three roots of x^3+x^2-16440*x+80375 expressed as sums of cosine,
as you can check numerically.

Cheers,
Bill.