Bill Allombert on Sun, 21 Dec 2003 00:29:39 +0100


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

Re: Fundamental Units Again


On Sat, Dec 20, 2003 at 04:25:48PM -0500, McLaughlin, James wrote:
> "When flag = 1, GP insists on finding the fundamental units exactly, the
> internal precision being doubled and the computation redone, until the exact
> results are obtained".
> 
> I had understood this to me that the output was guaranteed to be a system of
> fundamental units ( I think it was the words "exactly" and "exact" that threw
> me off course :-)  ).

[I will let Karim will correct any mistake I could say]

Exact is used as meaning 'not a floating point approximation'.

For the purpose of computing the class group and the regulator, complex
approximations of the logarithmic embedding of the (tentative)
fundamental units are quite sufficient, but if you insist to get the
exact values, a larger precision can be needed.

Of course computing accurately a false result is usually not what we
want...

> I have been informed that this is not the case and that the output is
> actually conditional on an assumption that is stronger than GRH.
> bnfcertify will guarantee the output unconditionally for number fields
> of low degree over Q fairly easily (up to, say, 11), but using
> bnfcertify becomes practically impossible as the degree of f goes much
> beyond this. 

The algorithm need a bound B so that the ideal above all primes smaller
than B generate the class group. Given a know-correct bound C larger
than B it is easy (but in O(C) operations) to check if the bound B is
correct.

Known unconditional bound are exponential in the log of the
discriminant.

Under the GRH we can use Bach estimate which is 12*log^2(D).

PARI use by default a smaller bound, like 0.3*log^2(D). This is known
among us as 'Bach constant cheating'. You can pass `technical' parameter
to bnfinit() to change the number 0.3 to 12.

 From the manual:

     The  numbers  c and c2 are positive real numbers which control the
     execution time and the stack size.   To get maximum speed, set c2 =
     c.  To get a rigorous result (under GRH)  you must take c2 = 12 (or
     c2 = 6 in the quadratic case, but then you should use the much
     faster function quadclassunit).  Reasonable values for c are
     between 0.1 and 2. (The defaults are c = c2 = 0.3.) 

However, 12 is a worst case estimate, if you compute carefully the
Bach constant for your field, you will get a smaller value so you should
be able to remove that assumption and get the result under the GRH
without increasing the running time too much.

> However, I have also been told that the output of bnfinit(f,1).fu is
> guaranteed unconditionally to be at least a system of > independent
> units. If this were true, I could work around the difficulty by using
> known general lower bounds on the regulator of a number field of
> degree n over Q.  

It is true. Since we know the rank of the units group, it is a trivial
linear algebra problem to check whether the units are independant.

You can check this for yourself, so you don't need to trust PARI for
that matter.

However, the algorithm is not warranted to give a result at all if the
assumption is false.

Cheers,
Bill.