James Wanless on Mon, 22 Jul 2013 20:18:28 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Bug in bnfcertify?


I don't know if this is relevant - possibly not and it's just a regular bug. But it's interesting you mention Minkowski... When I was reading Weber's "Lehrbuch der Algebra" a year or two ago, I discovered a distinctly non-trivial flaw in specifically some of Minkowski's reasoning quoted by Weber.
J

On 22 Jul 2013, at 18:38, Stephan Ehlen wrote:

Hello,

I tried to compute class numbers of Hilbert class fields of several
imaginary quadratic fields, originally using sage but sage basically
interfaces pari/gp for this purpose. In one particular example, the
computation took very long, so I tried to find out what was going on.
If I perform bnfinit() in pari/gp with the polynomial that defines the
Hilbert class field in this case, the process terminates after less
than a minute or so on my laptop. It is the bnfcertify that takes so
long. Well, in order to see if we end up in an infinite loop or so, I
turned on debugging and was a bit surprised to see that pari continued
with the function testprimes beyond the Minkowski bound in this case.
Looking at the source code only briefly, it seems that the second for
loop in 'testprimes' in the file buch2.c does never terminate.

Here are the details of the computation:

I take the following number field, which is supposed to have class number one.

L=bnfinit(x^26 - 2*x^25 + 2484*x^24 - 4586*x^23 + 2847822*x^22 -
4818170*x^21 + 1995228021*x^20 - 3066971426*x^19 + 953096577112*x^18 -
1317359310304*x^17 + 327800081539043*x^16 - 402251522690840*x^15 +
83510912485885347*x^14 - 89531620356216582*x^13 +
15956451256652162441*x^12 - 14635777566553330924*x^11 +
2286606726322811557998*x^10 - 1743936046731088471916*x^9 +
242727050765913635497471*x^8 - 147714971678918552212564*x^7 +
18551902020333005985565004*x^6 - 8442206085607103221290354*x^5 +
966819395778520305239696441*x^4 - 292299434248523177559301894*x^3 +
30792768551084507948533502345*x^2 - 4636558762445458519624201052*x +
452684584165052348313734803063)

Then I run bnfcertify(L) with default settings...
The Minkowski bound is about 1.01592210234705e6. Pari continues to
check for primes beyond that bound in 'testprimes'
(called from bnfcertify0 in buch3.c) in the second for loop.

Now, if I start gp instead with

gp -p 1060000

then bnfcertify terminates and returns 1 (in this case, it simply does
not run into the second loop)...
So this seems to be a bug to me. However, I don't know exactly why the
second for - loop is built the way it is, so maybe someone who knows
more about that can help me here.

Best,
Stephan