Karim Belabas on Wed, 17 Aug 2022 01:47:02 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: S-units algorithm in Pari. |
Hi, * Melanka Saroad Wedige [2022-08-17 00:55]: > I am doing some experiments on S-units for a given set S of primes in an > imaginary quadratic extension. I am using the bnfsunit function in Pari/Gp > to find a basis for the S-units. For my experiments, it is important to > understand the recipe for generating that certain basis (output by > bnfsunit), and under what criteria the basis elements are ordered. So I am > interested in finding out the S-unit algorithm implemented in Pari. May I > know what algorithm is implemented in it? Any reference to it? The algorithm is folklore, following from the exact sequence defining the S-unit and standard algorithms to handle short exact sequences of abelian groups (HNF, etc.). It was originally implemented in PARI by Denis Simon around 1997. A general overview is given in Denis's paper on relative norm equations: https://www.ams.org/journals/mcom/2002-71-239/S0025-5718-02-01309-1/S0025-5718-02-01309-1.pdf Proofs are not given for this part but can be found in his PhD thesis http://simond.users.lmno.cnrs.fr/maths/these.pdf I rewrote the details around 2004 to allow privately so called "compact representations" (which was used to compute tame kernels in algebraic K-theory; these functions were never included in Pari). Compact representations were systematized much later and in particular exposed in the new public function bnfunits() for Pari-2.13. You should first check this latter function and its documentation. Details of the basis are meant to be opaque: you shouldn't need any particular property that's not part of the documentation. It's basically meant as an input to bnfisunit() [precomputations allow to decompose any S-unit into a unit and product of generators given its valuations at S]; the S-units basis is meant to be given in compact form (which allows to also handle cases where fundamental units are huge). What do you need exactly ? N.B. Unless you 'bnfcertify' the bnf structure, everything is conditional to GRH. > Also, is there any other algorithm that specifically addresses this problem > for (imaginary) quadratic extensions? If yes, is it implemented in Pari? The S-units algorithm itself is quite elementary but it relies on the complicated 'bnfinit' machinery (index calculus, etc.) and general element / ideal arithmetic. This part can be simplified for imaginary quadratic fields since Gauss (composition and) reduction of definite binary quadratic forms allows to compute in the class group and find generators of principal ideals without the general theory (in particular to prove that an ideal is not principal with decent complexity without requiring the GRH). Concerns about the size of fundamental units disapear completely as well. But I very much doubt that it would change the overall complexity of the algorithm since we must be able to compute the class group to do anything and that part requires GRH to replace sqrt(D) complexity by subexponential L_{1/2}(log D). So there's no motivation to re-implement everything for that special case: little of this is implemented in PARI. In particular, even though the quadclassunit function *does* use binary quadratic forms to compute class groups of quadratic fields, it's not an 'init' function and there's no way to use its output for anything else than checking what the class group is (as well as fundamental unit / regulator, for real fields). Cheers, K.B. -- Karim Belabas, IMB (UMR 5251), Université de Bordeaux Vice-président en charge du Numérique T: (+33) 05 40 00 29 77; http://www.math.u-bordeaux.fr/~kbelabas/ `