gcd and lcm for field elements

[luisfe]

I have added a new ticket for adding a default gcd and lcm for field
elements.

http://trac.sagemath.org/sage_trac/ticket/9819

For the case of field elements gcd and lcm methods are not of great
interest. However, they can be addecuated for some reasons.

- Some algorithms may accept as input either polynomials or rational
functions. In these algorithms we may reduce a list of polynomials and
rational functions to a common denominator. If all the inputs are
polynomials, the denominators are the one element of the base field.
In this case, lcm would fail.

See the problem raised in #9063 for a case of this problem.

I propose to add a lcm and gcd funtion for field elements.

By default, if both elements are zero, their gcd is 0. Otherwise 1

if one of the elements is zero, their lcm is zero. 1 Otherwise.

However, I can imaging that this approach may lead to further
problems. Does anyone have a case where this approcah can lead to
problems?


Luis

[Sebastian Pancratz]

On Aug 27, 1:00 pm, luisfe <lftab...@yahoo.es> wrote:
> I have added a new ticket for adding a default gcd and lcm for field
> elements.
>
> http://trac.sagemath.org/sage_trac/ticket/9819
>
> For the case of field elements gcd and lcm methods are not of great
> interest. However, they can be addecuated for some reasons.
>
> - Some algorithms may accept as input either polynomials or rational
> functions. In these algorithms we may reduce a list of polynomials and
> rational functions to a common denominator. If all the inputs are
> polynomials, the denominators are the one element of the base field.
> In this case, lcm would fail.

I just briefly want to point out that this is not true (e.g.
polynomial over the rationals, instead of finite fields). For
example,

sage: R.<t> = QQ[]
sage: f = 1/3 + x/5
sage: f.denominator()
15

Here f is a polynomial and f.denominator() gives the least common
multiple of the denominators of the coefficients. On the technical
side, here f simply isn't an element of a fraction field and hence the
denominator() method is not meant to return the denominator of a
fraction field element. Note that, I hope quite obviously, the notion
of the "denominator" of a polynomial over a fraction field makes
sense, although it is implemented here for polynomial rings over Q
rather than any such polynomial ring.

For comparison,

sage: S = Frac(R)
sage: S(f).denominator()
1

Here, denominator() is the method for rational functions over Q.
Fortunately, 1 and 15 are the same up to multiplication by units in
the rationals and everything is fine.

--- Actually, let me give a short aside. The construction mentioned
above, that is, polynomial rings R over fraction fields F of a ring K,
isn't yet handled separately in Sage. After having worked on
polynomial rings over Q and rational functions over Q, I think this
would help a lot. For example, it would allow for an implementation
of the field of rational functions (elements in the fraction field of
R) not as a fraction field of R but as the fraction field of the ring
of polynomials over K (instead of F). Incidentally, in the example
above, if Frac(QQ[]) was implemented as Frac(ZZ[]), the second example
might reasonably result in the answer 15, too. ---

> See the problem raised in #9063 for a case of this problem.
>
> I propose to add a lcm and gcd funtion for field elements.
>
> By default, if both elements are zero, their gcd is 0. Otherwise 1
>
> if one of the elements is zero, their lcm is zero. 1 Otherwise.
>
> However, I can imaging that this approach may lead to further
> problems. Does anyone have a case where this approcah can lead to
> problems?
>
> Luis

The main problem with GCDs and LCMs, as far as their implementation is
concerned, is that they are only defined up to units. Thus, as choice
*must* be made in the underlying implementation. However, this does
*not* mean that calling methods always have to rely on a specific
choice. In fact, in particular for a system as large and quickly
changing as Sage, the code will be a lot more robust if calling
methods choose to not depend on such choices.

--- This might all sound as if I've copied this out of some design
pattern book and as if it's completely irrelevant in practice.
Actually, it's not :(. When working on univariate polynomials over
the rationals in #4000, I ran into a more than a handful of such
problems. For example, the normalisation of the greatest common
divisor wasn't the same in gcd and xgcd. Moreover, the normalisation
of the greatest common divisor wasn't obvious. There are two obvious
choices, namely either monic or primitive over Z with positive leading
coefficient, where the first choice is often mathematically convenient
and the second one is closer to the implementation at hand now. The
choice in the old implementation was something like the first, except
that something like gcd(self, 0) would return self to shave of some
speed in that special case, neglecting that self might not be monic.
Of course, all of these issues carry over to the implementation of
lcm. And finally, to make matters worse, some other code
(mathematically relevant, as opposed to, say, pretty printing of
rational functions) in the Sage library depended on this specific
choice for correctness. ----

Having said that, as far as correctness and robustness are concerned,
it's clear that the calling method simply should only expect some
greatest common divisor, rather than a specific one. Thus, the focus
now shifts to speed.

In light of #9063, yes, it would be very convenient if gcd(x,y) for a
pair of field elements (x, y) not equal to (0, 0) returns 1. But it's
completely feasible that other, perhaps even more low-level
implementations, might benefit (in terms of speed) from another
arbitrary choice.

Is it worth that once and for all we try to force a specific choice
across all field implementations? I don't think so.

You could try to argue that there's nothing wrong with implementing a
generic choice (the one you outlined!) for all fields now, and then
specific fields might be allowed to overwrite this method later.
However, so long as calling methods (taking any field elements as
input) actually depend on the specific choice you fix generically,
this doesn't help and brings us right back to this discussion.

Best wishes,

Sebastian

[luisfe]

you are right, it will work as long as the base ring have a lcm
function.

> --- Actually, let me give a short aside. The construction mentioned
> above, that is, polynomial rings R over fraction fields F of a ring K,
> isn't yet handled separately in Sage. After having worked on
> polynomial rings over Q and rational functions over Q, I think this
> would help a lot. For example, it would allow for an implementation
> of the field of rational functions (elements in the fraction field of
> R) not as a fraction field of R but as the fraction field of the ring
> of polynomials over K (instead of F). Incidentally, in the example
> above, if Frac(QQ[]) was implemented as Frac(ZZ[]), the second example
> might reasonably result in the answer 15, too. ---

The difference in this case is that the denominator would be a
polynomial instead of an element of the base ring. With the actual
implementation, for a polynomial f, it should be that f.numerator()/
f.denominator() is a polynomial equal to f. With the alternative,
f.numerator()/f.denominator() would be a rational function equal to f.
I can imaging users expecting one result or the other depending on the
situation.

> > See the problem raised in #9063 for a case of this problem.
>
> > I propose to add a lcm and gcd funtion for field elements.
>
> > By default, if both elements are zero, their gcd is 0. Otherwise 1
>
> > if one of the elements is zero, their lcm is zero. 1 Otherwise.
>
> > However, I can imaging that this approach may lead to further
> > problems. Does anyone have a case where this approcah can lead to
> > problems?
>
> > Luis
>
> The main problem with GCDs and LCMs, as far as their implementation is
> concerned, is that they are only defined up to units. Thus, as choice
> *must* be made in the underlying implementation. However, this does
> *not* mean that calling methods always have to rely on a specific
> choice. In fact, in particular for a system as large and quickly
> changing as Sage, the code will be a lot more robust if calling
> methods choose to not depend on such choices.

I agree with that, the algorithms using gcd and lcm output should not
be expected to be on a specific choice of the unit if possible.

> --- This might all sound as if I've copied this out of some design
> pattern book and as if it's completely irrelevant in practice.
> Actually, it's not :(. When working on univariate polynomials over
> the rationals in #4000, I ran into a more than a handful of such
> problems. For example, the normalisation of the greatest common
> divisor wasn't the same in gcd and xgcd. Moreover, the normalisation
> of the greatest common divisor wasn't obvious. There are two obvious
> choices, namely either monic or primitive over Z with positive leading
> coefficient, where the first choice is often mathematically convenient
> and the second one is closer to the implementation at hand now. The
> choice in the old implementation was something like the first, except
> that something like gcd(self, 0) would return self to shave of some
> speed in that special case, neglecting that self might not be monic.
> Of course, all of these issues carry over to the implementation of
> lcm. And finally, to make matters worse, some other code
> (mathematically relevant, as opposed to, say, pretty printing of
> rational functions) in the Sage library depended on this specific
> choice for correctness. ----

Yes, this is a problem.

> Is it worth that once and for all we try to force a specific choice
> across all field implementations? I don't think so.

I would not like that neither.

> You could try to argue that there's nothing wrong with implementing a
> generic choice (the one you outlined!) for all fields now, and then
> specific fields might be allowed to overwrite this method later.
> However, so long as calling methods (taking any field elements as
> input) actually depend on the specific choice you fix generically,
> this doesn't help and brings us right back to this discussion.

That would be my answer indeed. I still think that there should be a
fallback implementation of lcm but I see the problem, calling methods
that depend on a specific shape of a gcd/lcm (ex. monic polynomials)
are not bug free because they will fail if the gcd/lcm is not in that
shape (because the function has been overwritten somewhere, this is
specially the case if QQ is involved). On the other hand, if on every
calling method rewrite the gcd/lcm on a specific shape, this would
yield to an undesirable overhead.

For instance in structure/element_base.pyx a _lcm for FieldElement is
already there with the same defaults as above, but nobody has written
a lcm function that is coercion-aware for FieldElement.

Furthermore, appart from the field case, lcm is broken from the point
of view of the coercion model, the gcd seems more robust to me. The
lcm has to be changed in any case.

{{{
sage: gcd(ZZ(4),QQ(4))
1
sage: type(_)
<type 'sage.rings.rational.Rational'> #ok
sage: lcm(ZZ(4),QQ(4))
4
sage: type(_)
<type 'sage.rings.rational.Rational'> #ok
sage: lcm(QQ(4),ZZ(4))
...
TypeError: Argument 'other' has incorrect type (expected
sage.rings.rational.Rational, got sage.rings.integer.Integer) # not ok
sage: lcm([QQ(4),ZZ(4)])
4
sage: type(_)
<type 'sage.rings.rational.Rational'> #ok
sage: x=QQ[x](x)
sage: lcm(x, ZZ(4))
x
sage: lcm(x, QQ(4))
...
RuntimeError: Singular error: #not ok
}}}


Best,

Luis

[luisfe]

Another issue,

Assuming that we allow a fallback implementation of gcd/lcm for field
elements.

Do we want such gcd/lcm if the field is non-exact?

FractionField(RR[x]) and so on.

[John Cremona]

Any field with an is_zero() function on its elements is presumably OK?

John

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

[Sebastian Pancratz]

Dear Luis,

I think the points you raise are valid ones. Perhaps the following
would be a sensible solution?

Implement gcd and lcm for general field elements just as you suggest.
(So gcd(x,y) is 1 unless (x,y) is (0,0), in which case it is 0.) It
should be just fine for inexact fields, too, so long as 0 and 1 are
exactly representable. (See John Cremona's message.) However, it's
important to emphasize (in the documentation of that new code) that
the methods gcd and lcm might be overwritten to implement any
mathematical correct answer.

I don't think this change in code should be used as a band-aid to make
things work in one of the trac tickets you mentioned earlier.

On to the next points... your examples do show that lcm isn't as well
set up as gcd with respect to the coercion system. If you're
implementing gcd/ lcm for field elements already, could you change
this, too? (I unfortunately can't claim to understand the coercion
system well enough to "just do this quickly".)

There seems to be another problem suggested by your examples. Of
course, if a user does

sage: x.gcd(y)

then I would think the user wants y to be interpreted as an element of
the parent of x, if possible. That is, the operation x.gcd(y) is
*not* necessarily symmetric. On the other hand, if a user types

sage: gcd(x, y)

one might (mistakenly) expect it to be symmetric. Of course, in
principle this problems might have come up with many other operations
which a mathematician would expect to be commutative. Perhaps a
solution to this way has been discussed somewhere else already?
Otherwise, looking at the implementation of addition should give some
guidelines.

Best wishes,

Sebastian

[luisfe]

On Sep 1, 5:27 pm, Sebastian Pancratz <s...@pancratz.org> wrote:

> I don't think this change in code should be used as a band-aid to make
> things work in one of the trac tickets you mentioned earlier.

For the problem that raised all the stuff up I have an alternative
solution (with pros and cons of course)

> On to the next points... your examples do show that lcm isn't as well
> set up as gcd with respect to the coercion system. If you're
> implementing gcd/ lcm for field elements already, could you change
> this, too? (I unfortunately can't claim to understand the coercion
> system well enough to "just do this quickly".)

Yes, that should be corrected, I am looking at this.

> There seems to be another problem suggested by your examples. Of
> course, if a user does
>
> sage: x.gcd(y)
>
> then I would think the user wants y to be interpreted as an element of
> the parent of x, if possible. That is, the operation x.gcd(y) is
> *not* necessarily symmetric. On the other hand, if a user types
>
> sage: gcd(x, y)
>
> one might (mistakenly) expect it to be symmetric. Of course, in
> principle this problems might have come up with many other operations
> which a mathematician would expect to be commutative. Perhaps a
> solution to this way has been discussed somewhere else already?
> Otherwise, looking at the implementation of addition should give some
> guidelines.

This is considered in the sage.structure.element.pyx through
coerce_bin_op I will carefully read the module.