Re: muldep

[Denis Simon <denis.simon@unicaen.fr>]

Thank you John for your suggestion.

As a first step, you probably mean something like
Factoring into coprimes in essentially linear time, by Bernstein ?

Denis SIMON.

----- Mail original -----
> De: "John Cremona" <john.cremona@gmail.com>
> À: "Denis Simon" <denis.simon@unicaen.fr>
> Cc: "pari-users" <pari-users@pari.math.u-bordeaux.fr>
> Envoyé: Mercredi 9 Décembre 2020 15:13:11
> Objet: Re: muldep

> Hello Denis,
> 
> As a first step, using only gcds you can extract from your x_i a list
> of integers p_i which are mutually coprime -- but not necessarily
> prime -- so that each x_i is a product of powers of the p_i.  There is
> a name for that process, which I forget.  Then your problem  becomes
> one of finding the kernel of an integer matrix, which you know how to
> do.  I was thinking of the x_i as being integers, but just apply this
> to the list of all numerators and denominators.
> 
> Sorry, I do not have code for this.
> 
> I do something similar in Lemma 2.5 of my paper on solving rational
> conics (see https://johncremona.github.io/papers/conics.pdf for a
> preprint, or
> https://www.ams.org/journals/mcom/2003-72-243/S0025-5718-02-01480-1/home.html).
> 
> John
> 
> On Wed, 9 Dec 2020 at 13:30, Denis Simon <denis.simon@unicaen.fr> wrote:
>>
>> Dear pari users,
>>
>> I would like to write a GP code for the following question, but if someone
>> already has a code, it would be very helpful:
>>
>> given a vector X = [x1,...,xn] of nonzero rational numbers ("t_FRAC")
>> compute a Z-basis of the set of vectorvs e = [e1,...,en]~ of integers ("t_INT")
>> such that x1^e1 * ... * xn^en = 1.
>> Following the general taxonomy in GP, this function could be named "muldep()".
>>
>> For efficiency reasons, I would be happy with a function that performs no
>> factorization.
>>
>> More generally, I need a function "nfmuldep()" that does the same work when X =
>> [x1,...,xn]
>> contains nonzero elements of a given number field nf.
>>
>> Thanks in advance,
>> Denis SIMON.
>>
>>