RE: Fundamental Units Again

["McLaughlin, James" <James.McLaughlin@trincoll.edu>]

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.