Quotient ring of integer ring?
Simon King
Currently, we have
sage: QuotientRing(ZZ, 8)
Quotient of Integer Ring by the ideal (8)
sage: ZZ.quotient_ring(8)
Ring of integers modulo 8
sage: _ == __
False
Question: Should QuotientRing(R,I) for an ideal I in a ring R always
return the same object as R.quotient_ring(I)? I.e., should
QuotientRing(ZZ,8) be the ring of integers modulo 8?
Best regards,
Simon
Simon King
The following is a clear bug IMHO.
sage: Q = QuotientRing(ZZ,8)
sage: F,R = Q.construction()
sage: F(R)==Q
False
I think it would be better if the QuotientRing(R,I) constructor would
always return an instance of the class that suites best for quotients
of R.
Note that it already does return an instance of a specialised class
in other cases: For quotients of univariate polynomial rings, it is
sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.
So, why should a generic implementation be used for quotients of ZZ,
even more when the construction of the quotient does not reproduce the
quotient?
Best regards,
Simon
William Stein
I remember writing the QuotientRing_generic class back in 2005 when
there were no quotient rings in Sage yet (after a conversation with
Joe Wetherell and David Kohel...). The file
sage/rings/quotient_ring.py has a function "QuotientRing", and its
initial behavior was to create an object of type QuotientRing_generic.
It still does that in some cases:
sage: Q = QuotientRing(ZZ,8)
sage: type(Q)
<class 'sage.rings.quotient_ring.QuotientRing_generic'>
Simon, I agree with you. The function "QuotientRing" should be
improved so that it works like the functor, e.g,. calls the
".quo(...)" method if it exists. In fact, the code in _apply_functor
in sage/categories/pushout.py (which I had nothing to do with) and the
code in the QuotientRing function should be refactored so the actual
construction only involves calling one function that does the work.
-- William
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
Simon King
On 7 Sep., 17:36, William Stein <wst...@gmail.com> wrote:
> Simon, I agree with you. The function "QuotientRing" should be
> improved so that it works like the functor, e.g,. calls the
> ".quo(...)" method if it exists.
So, the existence of a ".quo()" method is granted for usual rings. And
with #11068, the quo[tient[_ring]] methods will also be available
from the category of rings, so that it is also available for matrix
algebras.
The default for .quotient() is to call QuotientRing. But I guess,
instead of that, the QuotientRing should call the .quotient() method,
because any ring should know what class its quotients belong to.
A related question: Should quotient rings be unique parents? If "yes":
How should equality of quotient rings be defined?
Currently, the quotient rings are equal if the defining ideals have
the same list of generators. The variable names are *not* considered
in the comparison:
sage: P.<x,y> = QQ[]
sage: I = P*[x,y]
sage: Q1 = P.quo(I,names=['a','b'])
sage: Q2 = P.quo(I,names=['c','d'])
sage: Q1==Q2
True
If quotient rings should become unique parents (this is what I hope),
the generator names must be considered, IMHO.
Should we preserve the "quick and dirty" approach to test equality of
the generator list of the ideals? Or can we afford to properly test
equality of ideals (via Gröbner bases, if available)?
My opinion is: R1.quo(I1,names1)==R2.quo(I2,names2) if and only if
R1==R2, I1.gens()==I2.gens() and names2==names2. Testing I1==I2 via
Gröbner bases is too expensive.
> In fact, the code in _apply_functor
> in sage/categories/pushout.py (which I had nothing to do with) and the
> code in the QuotientRing function should be refactored so the actual
> construction only involves calling one function that does the work.
rebasing both #10667 and #11068 relative to the new ticket.
Cheers,
Simon
William Stein
+1 Yes, definitely the generator names should be considered.
> Should we preserve the "quick and dirty" approach to test equality of
> the generator list of the ideals? Or can we afford to properly test
> equality of ideals (via Gröbner bases, if available)?
Good question. It seems like we should defer the question to
whatever ideal equality testing already does, which is surely equality
of ideals.
It definitely seems like the "right thing" is to test equality of
ideals, but it is potentially very expensive indeed.
> My opinion is: R1.quo(I1,names1)==R2.quo(I2,names2) if and only if
> R1==R2, I1.gens()==I2.gens() and names2==names2. Testing I1==I2 via
> Gröbner bases is too expensive.
I'll let you decide, unless anybody else has a strong opinion.
>
>> In fact, the code in _apply_functor
>> in sage/categories/pushout.py (which I had nothing to do with) and the
>> code in the QuotientRing function should be refactored so the actual
>> construction only involves calling one function that does the work.
>
> Sounds reasonable. Probably I can fit a new ticket on top of #9138,
> rebasing both #10667 and #11068 relative to the new ticket.
>
> Cheers,
> Simon
>
> --
> 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
Volker Braun
Simon King
On 7 Sep., 19:42, Volker Braun <vbraun.n...@gmail.com> wrote:
> For ideals in Sage, comparison (==) means mathematical equality.
(1)==1==GF(3)(1), but GF(2)(1)!=GF(3)(1).
> I think it would be more consistent to demand mathematical equality for
> equality of the quotient rings. It is very likely that this is what the user
> actually wants if he/she compares two quotient rings.
There is a cache indexed by parents. Thus, if you have a quotient ring
Q=R/I and want to add an element of Q with an element of R, then
equality is tested for Q, in order to see whether there is an
appropriate coercion in the test.
Hence, equality test ought to be as fast as possible. Ideally, parents
are equal if and only if they are identical.
Moreover, ideals must not be used as a key of a dictionary:
sage: I = P*[x,y]
6308421454588240813
sage: J = P*[x+y,-y]
sage: hash(J)
5043924375983940909
sage: I==J
True
In other words, I and J are equal, but have different hash. Actually,
I think it is a bug that hash(I) does not result in a TypeError.
That's why I think one should simplify the equality test to rely on
the generator list of the ideals, not on equality of the ideals as
sets.
Best regards,
Simon
William Stein
> Hi Volker, hi William,
>
> On 7 Sep., 19:42, Volker Braun <vbraun.n...@gmail.com> wrote:
>> For ideals in Sage, comparison (==) means mathematical equality.
>
> Only in an ideal world. In fact, == is not transitive in Sage: GF(2)
> (1)==1==GF(3)(1), but GF(2)(1)!=GF(3)(1).
I know you were making a pun, but just for clarification, what Volker
said is exactly right. E.g.,
sage: R.<x,y> = QQ[]
sage: I = R.ideal([x^2, 3*y^2, x^2 - y^2])
sage: J = R.ideal([x^2, y^2, y^2 - x^2])
sage: I
Ideal (x^2, 3*y^2, x^2 - y^2) of Multivariate Polynomial Ring in x, y
over Rational Field
sage: J
Ideal (x^2, y^2, -x^2 + y^2) of Multivariate Polynomial Ring in x, y
over Rational Field
sage: I == J
True
sage: I.__cmp__??
...
l = self.groebner_basis()
r = other.groebner_basis()
...
return cmp(l,r)
>
>> I think it would be more consistent to demand mathematical equality for
>> equality of the quotient rings. It is very likely that this is what the user
>> actually wants if he/she compares two quotient rings.
>
> Unfortunately, equality tests happen implicitly when using coercion:
> There is a cache indexed by parents. Thus, if you have a quotient ring
> Q=R/I and want to add an element of Q with an element of R, then
> equality is tested for Q, in order to see whether there is an
> appropriate coercion in the test.
>
> Hence, equality test ought to be as fast as possible. Ideally, parents
> are equal if and only if they are identical.
>
> Moreover, ideals must not be used as a key of a dictionary:
> sage: P.<x,y> = QQ[]
> sage: I = P*[x,y]
> sage: hash(I)
> 6308421454588240813
> sage: J = P*[x+y,-y]
> sage: hash(J)
> 5043924375983940909
> sage: I==J
> True
>
> In other words, I and J are equal, but have different hash. Actually,
> I think it is a bug that hash(I) does not result in a TypeError.
It's a bug that hash isn't canonical. One should compute a standard
form for I before hashing it. At least this is what happens with
ideals of rings of integers of number fields. (I'm not claiming that
hash is good -- it's something dumb like hashing the Pari HNF string,
but still it is well defined.)
> That's why I think one should simplify the equality test to rely on
> the generator list of the ideals, not on equality of the ideals as
> sets.
I've changed my perspective to disagree with this.
I good compromise may be the following. When creating a quotient
ring, compute a standard form for the ideal. Then when testing
equality of two quotient rings, the whole issue we're talking about
vanishes. If you're going to do any nontrivial arithmetic in the
quotient ring, you'll *need* this standard form anyways. So just
compute it up front. In a multivariate poly ring it would be computed
via something like his:
self.change_ring(R.change_ring(order="degrevlex")).groebner_basis()
(code copied from the __cmp__ method.) The point is that degrevlex
GB's are faster to compute than wrt other term orders... and for our
purposes a GB wrt any term order suffices.
William
>
> Best regards,
> Simon
>
> --
> 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
>
--
Simon King
On 7 Sep., 22:27, William Stein <wst...@gmail.com> wrote:
> > In other words, I and J are equal, but have different hash. Actually,
> > I think it is a bug that hash(I) does not result in a TypeError.
>
> It's a bug that hash isn't canonical. One should compute a standard
> form for I before hashing it. At least this is what happens with
> ideals of rings of integers of number fields. (I'm not claiming that
> hash is good -- it's something dumb like hashing the Pari HNF string,
> but still it is well defined.)
> ring, compute a standard form for the ideal. Then when testing
> equality of two quotient rings, the whole issue we're talking about
> vanishes. If you're going to do any nontrivial arithmetic in the
> quotient ring, you'll *need* this standard form anyways.
> So just
> compute it up front. In a multivariate poly ring it would be computed
> via something like his:
>
> self.change_ring(R.change_ring(order="degrevlex")).groebner_basis()
>
> (code copied from the __cmp__ method.) The point is that degrevlex
> GB's are faster to compute than wrt other term orders... and for our
> purposes a GB wrt any term order suffices.
you are likely to want to work with a Gröbner basis *for the given
term order of the polynomial ring*. And even degrevlex Gröbner bases
are often enough difficult to compute.
Moreover, one must not forget that we want to create quotient rings
not only for ideals in polynomial rings. See #11068: Technically, we
can do computations in the quotient ring as soon as the ideal has a
method I.reduce(x) that returns a normal form of x with respect to I.
But in addition to I.reduce(x), we may consider to request another
method:
* We could introduce a new method of ideals called, say,
I.normal_form(), returning some hashable object.
* Comparison of ideals I,J should be reduced to I.ring()==J.ring()
and I.normal_form()==J.normal_form().
* hash(I) should return hash(I.normal_form()).
* By default, I.normal_form() just returns the given generators of I
as a tuple (or polynomial sequence?). Hence, for general ideals
(without the possibility to compute Gröbner bases), equality of ideals
becomes equality of generator lists
* For some types of ideals, I.normal_form() returns a "proper" normal
form. So, for polynomial ideals, it returns an ordered reduced Gröbner
basis. In rings of integers of number fields, it returns the pari HNF
string.
It seems better to me to have a general __cmp__ method for *all*
ideals and implement a normal_form method, than to have different
__cmp__ for all types of ideals.
And then, uniqueness of quotient rings could easily be implemented,
based on R.quo(I,names1)==S.quo(J,names2) <=> R==S and I==J and
names1==names2.
Best regards,
Simon
William Stein
If "arithmetic" is addition, subtraction, multiplication, and equality
checking, then it does not matter which term order you use. The
specific term order doesn't matter in the least for basic arithmetic.
> And even degrevlex Gröbner bases
> are often enough difficult to compute.
If you don't do that, then how will you ever check equality. There is
little arithmetic one would do that never involves actually doing
something (like testing an equality) with the answer.
> Moreover, one must not forget that we want to create quotient rings
> not only for ideals in polynomial rings.
True, but it is an important case, since the ideas covers all finitely
generated quotient rings, and there are a lot of finitely generated
rings in Sage.
I'm personally more interested in rings of integers of number fields,
where one uses Hermite form and linear algebra instead of Groebner
basis.
> See #11068: Technically, we
> can do computations in the quotient ring as soon as the ideal has a
> method I.reduce(x) that returns a normal form of x with respect to I.
>
> But in addition to I.reduce(x), we may consider to request another
> method:
> * We could introduce a new method of ideals called, say,
> I.normal_form(), returning some hashable object.
> * Comparison of ideals I,J should be reduced to I.ring()==J.ring()
> and I.normal_form()==J.normal_form().
> * hash(I) should return hash(I.normal_form()).
> * By default, I.normal_form() just returns the given generators of I
> as a tuple (or polynomial sequence?). Hence, for general ideals
> (without the possibility to compute Gröbner bases), equality of ideals
> becomes equality of generator lists
> * For some types of ideals, I.normal_form() returns a "proper" normal
> form. So, for polynomial ideals, it returns an ordered reduced Gröbner
> basis. In rings of integers of number fields, it returns the pari HNF
> string.
>
> It seems better to me to have a general __cmp__ method for *all*
> ideals and implement a normal_form method, than to have different
> __cmp__ for all types of ideals.
>
> And then, uniqueness of quotient rings could easily be implemented,
> based on R.quo(I,names1)==S.quo(J,names2) <=> R==S and I==J and
> names1==names2.
This would be an acceptable solution to me.
Nicolas M. Thiery
> > Moreover, one must not forget that we want to create quotient rings
> > not only for ideals in polynomial rings.
>
> True, but it is an important case, since the ideas covers all finitely
> generated quotient rings, and there are a lot of finitely generated
> rings in Sage.
To be precise, finitely generated *commutative* quotient rings :-)
My point is just that the ideals/quotients framework will be used in a
fairly large context. So it would be good if it did not impose too
many constraints, like forcing '==' to *always* mean mathematical
equality (though it could in the simple/not too expensive cases).
Otherwise, this will prevent modeling complex objects where some
lazyness is vital.
For a concrete example, take a quotient of a free non commutative
algebra by a graded ideal. Its Gr�bner basis will typically be
infinite, so one can't compute it in full. Yet, arithmetic can be
achieved by lazily computing it up to the appropriate degree.
In general, after three years, I still remain a big fan of MuPAD's
approach where ``=='' meant syntactical equality, and mathematical
equality was achieved with a different syntax. Especially since ``==''
is used implicitly in many situations (coercion, arithmetic,
dictionary) that ought to be super fast.
Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Simon King
On 13 Sep., 10:00, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
> > > Moreover, one must not forget that we want to create quotient rings
> > > not only for ideals in polynomial rings.
>
> > True, but it is an important case, since the ideas covers all finitely
> > generated quotient rings, and there are a lot of finitely generated
> > rings in Sage.
>
> To be precise, finitely generated *commutative* quotient rings :-)
#11115) has a positive review :)
> My point is just that the ideals/quotients framework will be used in a
> fairly large context. So it would be good if it did not impose too
> many constraints, like forcing '==' to *always* mean mathematical
> equality (though it could in the simple/not too expensive cases).
> Otherwise, this will prevent modeling complex objects where some
> lazyness is vital.
"_determining_data") that is used by "==" behind the scenes. If one
wants to be lazy then "_determining_data" returns the frozen set of
generators. If one rather wants mathematical equality, then one should
better return the reduced Gröbner basis.
> For a concrete example, take a quotient of a free non commutative
> algebra by a graded ideal. Its Gr bner basis will typically be
> infinite, so one can't compute it in full.
ideals is at most d, then the ideals are equal if the Gröbner bases
out to degree d are equal, isn't it? And that's a finite computation.
> Especially since ``==''
> is used implicitly in many situations (coercion, arithmetic,
> dictionary) that ought to be super fast.
unique parents. The question is whether we want them unique.
Cheers,
Simon