Re: Bug in Mod (2.0.15)

[Ilya Zakharevich <ilya@math.ohio-state.edu>]

On Fri, May 05, 2000 at 12:53:40AM +0200, Bill Allombert wrote:
> >But is a "much more correct" answer.  What I see is the following:
> >simplify() assumes that any ring in which POLMODs live is a ring of
> >principal ideals.  (This assumption is hidden in the algorithm of
> >converting to the lowest common denominator when combining POLMODs
> >with different moduli).
> 
> Not really. PARI assume that all polynomial have coefficient in a _field_.

This is not hardwired into the internal representation.  Thus the only
problem is with the assumption used in algorithms, which should not be
many, right?

> This is reasonnable, since there is currently no ways to specify rings.
> (this is a major problem in the cursed gdivexact function).

Did not find any mention of the problem in my archive.  And it looks
like a very recent function...  And it is not documented what it does
(in 2.0.15 I have here).

> PARI works in the ring K(y,z,t)[X] in which the result is true.

I see.  But I do not see any reason why it would/should ;-) do it...

> > a) a way to represent an element in a quotient by a non-principal
> >    ideal in terms of the PARI type system;
> 
> Yes, but we have to add support for rings first, and then add ideals.

Do not see what you mean.  Which other places (in addition to
simplify()) depend-on/use the K(y,z,t)[X] hack?

> > I can be wrong, but do not Groebner bases give a canonical system of
> > generators of any ideal? 
> 
> Not truly. You get a reduced basis which nice reduction property but
> it still depend of lot of choice.

Given marked generators (x,y,z etc) of the ring, could not we get
something canonical?

> simplify() only handle "stupid" conversion (5+0*I -->5 ; 5*X^0 -->5).
> It is  probably gmod that would need to be modified.

Well, if it is two places to modify, it is still not that bad as
adding a new type to PARI...

> Saying that there exists canonical generators for ideals is not the
> same thing that saying there are canonical generators for cosets, but
> it is probably not a big problem here.

All one needs is the ability to check that an element is in the ideal...

> Currently the way PARI implement multivariate polynomial is not
> efficient and need to be changed before considering to implement
> Groebner basis. 

Why this obsession with efficiency?  It is good when possible, but
having *some* pilot implementation will clear the way for future
improvements...

> Moreover writing efficient Groebner basis programs is not easy.

Do not people have them written?  Cannot we use IPC with some other
program which can do them?

Ilya