Re: S-units algorithm in Pari.

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

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/
`