Peter-Lawrence . Montgomery on Mon, 9 Nov 1998 09:36:33 +0100 (MET)

 idealred returns ideal with different norm

/*
idealred is returning an ideal with different norm than its input.
Is this the way it is supposed to behave?

I am using PARI/GP version 2.0.11.beta on a SGI Onyx under IRIX 6.5
(both with BITS_IN_LONG = 32 and BITS_IN_LONG = 64),
I have experienced many MIPS compiler bugs as I upgrade from
PARI/GP 1.39, but suspect this problem is in the PARI library itself.

If you have GP/PARI 2.0.11.beta on a non-MIPS system,
let's hear how this behaves on your system.

Peter L. Montgomery
pmontgom@cwi.nl
November 9, 1998
*/
default(echo, 1)

c5 = 200
fX = c5*X^5 + 102*X^4 + 315*X^3 - 11*X^2 - 262*X + 5
fXM = subst(fX*c5^4, X, XM/c5)     /* fXM is monic in XM */
nf = nfinit(fXM);

ideal2fac = idealfactor(nf, idealprincipal(nf, 2)) /* Factor ideal (2) */
fac2a = ideal2fac[1,1]
fac2b = ideal2fac[2,1]
fac8  = ideal2fac[3,1]
/* fac2a and fac2b have norm 2.  fac8 has norm 8.  All have exponent 1. */
idealnorm(nf, fac2a)
idealnorm(nf, fac2b)
idealnorm(nf, fac8)

for(k=1,20,print(k, " ", factor(idealnorm(nf, idealpow(nf,fac2a,k,1))/2^k)))
for(k=1,20,print(k, " ", factor(idealnorm(nf, idealpow(nf,fac2b,k,1))/2^k)))
for(k=1,20,print(k, " ", factor(idealnorm(nf, idealpow(nf,fac8, k,1))/8^k)))
/*
For 1 <= k <= 6, the fac2a and fac2b quotients give 1, as expected.
The empty factorization primts a cryptic   matrix(0,2,j,k,0).

For larger k, the idealnorm factorizations are divisible by
other primes, usually to the fourth power.

For fac8, the mis-behavior occurs for k >= 14.
*/

a7unr = idealpow(nf, fac2a, 7, 0)      /* Exponentiation without reduction */
factor(idealnorm(nf, a7unr))           /* Norm 2^7, as expected */
a7red = idealpow(nf, fac2a, 7, 1)      /* Exponentiation with reduction */
factor(idealnorm(nf, a7red))           /* Wrong norm */

idealred(nf, a7unr)                    /* Same as a7red output */
default(debug,6)
idealred(nf, a7unr)                    /* Get debug printout from idealred */
quit;

/*   *************   Output follows ************

GP/PARI CALCULATOR Version 2.0.11 (beta)
unknown 32-bit version
(readline disabled, extended help not available)

C. Batut, K. Belabas, D. Bernardi, H. Cohen and M. Olivier.

Send bug reports, suggestions and patches to pari@math.u-bordeaux.fr
Type ? for help.

realprecision = 38 significant digits
seriesprecision = 16 significant terms
format = g0.38

parisize = 10000000, primelimit = 500000, buffersize = 30000
echo = 1 (on)
? ? c5=200
%1 = 200
? fX=c5*X^5+102*X^4+315*X^3-11*X^2-262*X+5
%2 = 200*X^5 + 102*X^4 + 315*X^3 - 11*X^2 - 262*X + 5
? fXM=subst(fX*c5^4,X,XM/c5)
%3 = XM^5 + 102*XM^4 + 63000*XM^3 - 440000*XM^2 - 2096000000*XM + 8000000000
? ? nf=nfinit(fXM);
? ? ideal2fac=idealfactor(nf,idealprincipal(nf,2))
%5 =
[[2, [1, 0, 1, 0, 0]~, 1, 1, [2, 2, 1, 0, 0]~] 1]

[[2, [3, 1, 0, 0, 0]~, 1, 1, [2, 1, 0, 0, 0]~] 1]

[[2, [0, 1, 1, 0, 0]~, 1, 3, [1, 1, 1, 0, 0]~] 1]

? ? fac2a=ideal2fac[1,1]
%6 = [2, [1, 0, 1, 0, 0]~, 1, 1, [2, 2, 1, 0, 0]~]
? fac2b=ideal2fac[2,1]
%7 = [2, [3, 1, 0, 0, 0]~, 1, 1, [2, 1, 0, 0, 0]~]
? fac8=ideal2fac[3,1]
%8 = [2, [0, 1, 1, 0, 0]~, 1, 3, [1, 1, 1, 0, 0]~]
? ? idealnorm(nf,fac2a)
%9 = 2
? idealnorm(nf,fac2b)
%10 = 2
? idealnorm(nf,fac8)
%11 = 8
? ? for(k=1,20,print(k," ",factor(idealnorm(nf,idealpow(nf,fac2a,k,1))/2^k)))
1 matrix(0,2,j,k,0)
2 matrix(0,2,j,k,0)
3 matrix(0,2,j,k,0)
4 matrix(0,2,j,k,0)
5 matrix(0,2,j,k,0)
6 matrix(0,2,j,k,0)
7 [2, -4; 5, 4; 20543, 4]
8 [2, -4; 5, 4; 20543, 4]
9 [2, -8; 7, 4; 68447, 4]
10 [2, -8; 7, 4; 68447, 4]
11 [2, -7; 5, 4; 4224317, 4]
12 [2, -12; 5, 4; 4224317, 4]
13 [2, 11; 149, 4; 2707, 4]
14 [2, -10; 5, 4; 37, 4; 98689, 4]
15 [2, -15; 5, 4; 37, 4; 98689, 4]
16 [2, -12; 22373671, 4]
17 [2, -17; 5, 4; 2309, 4; 6037, 4]
18 [2, -18; 5, 4; 9151, 4; 9923, 4]
19 [2, -19; 59, 4; 1733, 4; 2011, 4]
20 [2, 2; 239, 4; 1901, 4]
? for(k=1,20,print(k," ",factor(idealnorm(nf,idealpow(nf,fac2b,k,1))/2^k)))
1 matrix(0,2,j,k,0)
2 matrix(0,2,j,k,0)
3 matrix(0,2,j,k,0)
4 matrix(0,2,j,k,0)
5 matrix(0,2,j,k,0)
6 matrix(0,2,j,k,0)
7 [2, -7; 1759, 4; 16141, 4]
8 [2, -5; 31843967, 4]
9 [2, -5; 31843967, 4]
10 [2, -10; 7, 4; 14772917, 4]
11 [2, -11; 227, 4; 24551, 4]
12 [2, -11; 47, 4; 377287, 4]
13 [2, -11; 47, 4; 377287, 4]
14 [2, -10; 5, 4; 47, 4; 103, 4; 673, 4]
15 [2, -7; 73, 4; 139, 4; 317, 4]
16 [2, -12; 5, 4; 23, 4; 191929, 4]
17 [2, -17; 5, 4; 23, 4; 191929, 4]
18 [2, -10; 51814799, 4]
19 [2, -15; 51814799, 4]
20 [2, -20; 51814799, 4]
? for(k=1,20,print(k," ",factor(idealnorm(nf,idealpow(nf,fac8,k,1))/8^k)))
1 matrix(0,2,j,k,0)
2 matrix(0,2,j,k,0)
3 matrix(0,2,j,k,0)
4 matrix(0,2,j,k,0)
5 matrix(0,2,j,k,0)
6 matrix(0,2,j,k,0)
7 matrix(0,2,j,k,0)
8 matrix(0,2,j,k,0)
9 matrix(0,2,j,k,0)
10 matrix(0,2,j,k,0)
11 matrix(0,2,j,k,0)
12 matrix(0,2,j,k,0)
13 matrix(0,2,j,k,0)
14 [2, -34; 13375249, 4]
15 [2, -45; 5187449, 4]
16 [2, -45; 5187449, 4]
17 [2, -51; 1949, 4; 19259, 4]
18 [2, -50; 199, 4; 14327, 4]
19 [2, -37; 1560523, 4]
20 [2, -56; 41075149, 4]
? ? ? ? ? ? ? ? ? ? ? a7unr=idealpow(nf,fac2a,7,0)
%12 =
[128 82 95 0 82]

[0 1 0 0 0]

[0 0 1 0 0]

[0 0 0 1 0]

[0 0 0 0 1]

? factor(idealnorm(nf,a7unr))
%13 =
[2 7]

? a7red=idealpow(nf,fac2a,7,1)
%14 =
[205430 0 0 0 205386]

[0 102715 0 0 102485]

[0 0 102715 0 429]

[0 0 0 205430 84042]

[0 0 0 0 2]

? factor(idealnorm(nf,a7red))
%15 =
[2 3]

[5 4]

[20543 4]

? ? idealred(nf,a7unr)
%16 =
[205430 0 0 0 205386]

[0 102715 0 0 102485]

[0 0 102715 0 429]

[0 0 0 205430 84042]

[0 0 0 0 2]

? default(debug,6)
debug = 6
? idealred(nf,a7unr)
Time entering idealllred: 850
Time initialisations: 0
k = 2 K2 (0) 2 3 K3 4 K4 (0) 3 4 5 K5 (3) 4 3 2 2 3 4 5 6Time lllgram: 10
Time alpha/beta: 0
Time new ideal: 0
Time final hnf: 0
prec = [4, 16]
%17 =
[205430 0 0 0 205386]

[0 102715 0 0 102485]

[0 0 102715 0 429]

[0 0 0 205430 84042]

[0 0 0 0 2]

? quit;
Good bye!

*/