McLaughlin, James on Sun, 21 Dec 2003 21:40:54 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
RE: Fundamental Units Again |
Thanks for the very informative reply. There was one thing I was a little unsure about: "However, the algorithm is not warranted to give a result at all if the assumption is false." Which assumption is meant here? Thanks. Jimmy Mc Laughlin. -----Original Message----- From: Bill Allombert [mailto:allomber@math.u-bordeaux.fr] Sent: Sat 12/20/2003 6:22 PM To: pari-users@list.cr.yp.to Cc: Subject: 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.