#7580: bugs in infinite polynomial ring
-----------------------+----------------------------------------------------
Reporter: was | Owner: SimonKing
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.3
Component: algebra | Keywords: infinite polynomial ring coercion
Work_issues: | Author: Simon King
Upstream: N/A | Reviewer:
Merged: |
-----------------------+----------------------------------------------------
Changes (by newvalueoldvalue):
* cc: nthiery (added)
* keywords: => infinite polynomial ring coercion
* status: needs_work => needs_review
* author: => Simon King
Comment:
Hi!
Cc to Nicolas, since it partially concerns categories/functors.
We proudly present a major revision of Infinite Polynomial Rings; the
patch bomb is relative to sage-4.3.alpha1.
First of all, it fixes the bugs that William stated in the ticket
description.
Second, it is now possible to use ''any'' commutative base ring; the
restriction of using fields is now moved to the {{{groebner_basis()}}}
method.
Third, and that's the biggest change: It now uses the strength of Sage's
coercion machinery in pushout.py. I hope I did not overdo my use of it...
'''__Bug fixes__'''
Answer to William's failing examples:
1.
{{{
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: x[2^31]
---------------------------------------------------------------------------
IndexError Traceback (most recent call
last)
...
IndexError: Variable index is too big - consider using the sparse
implementation
}}}
I think that error message is clearer, and it gives a good advice...
{{{
sage: x[100]
x_100
}}}
So, that bug is gone.
2.
{{{
sage: X.<a,b> = InfinitePolynomialRing(QQ)
sage: a[100]
a_100
sage: a[2/3]
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
...
ValueError: The index (= 2/3) must be an integer
sage: a[Mod(2,3)]
a_2
sage: X.<a,b> = InfinitePolynomialRing(QQ)
sage: a[0]
a_0
sage: a['0+5']
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
...
ValueError: invalid literal for int() with base 10: '0+5'
}}}
'''__Extensions__'''
1.
The variable names can be any alphanumeric string. The base ring can be
any commutative ring. Note the rhyme...
{{{
sage: A.<t> = ZZ[]
sage: X.<alpha,beta>= InfinitePolynomialRing(A)
sage: X
Infinite polynomial ring in alpha, beta over Univariate Polynomial Ring in
t over Integer Ring
sage: 1/2*alpha[2]*t^3+alpha[1]*beta[4]^2
1/2*t^3*alpha_2 + alpha_1*beta_4^2
sage: latex(_)
(\frac{1}{2} t^{3}) \alpha_{2} + \alpha_{1}\beta_{4}^{2}
}}}
1.1.
Some words on the implementation for arbitrary base rings: Working on it,
I discovered some bugs in {{{MPolynomialRing_polydict}}}, as I reported on
[http://groups.google.com/group/sage-
devel/browse_thread/thread/b69ba8e631bd3bf7/bc6ee7bdccf26ee1?lnk=gst&q=FakeRing#bc6ee7bdccf26ee1
sage-devel]. However, there was no answer (so, apparently no interest).
Therefore I decided to just work around these bugs. One issue is to
evaluate a string 'x_2*t', if 'x_2' is a variable in an infinite
polynomial ring and 't' is a variable in the base ring. gens_dict() would
at most know about 'x_2' --- but with the additional complication that
there is no fixed finite list of variables for the infinite polynomial
ring.
__Solution__
I introduced a dictionary-like class {{{InfiniteGenDict}}}, that returns a
variable of an infinite polynomial ring, given its name.
And I introduced a class {{{GenDictWithBasering}}} that returns a variable
of the ring or its base-ring or the base-ring of its base-ring or... The
first answer wins.
I think that this class might be of general use, e.g., for fixing issues
in {{{MPolynomialRing_polydict}}}.
Examples:
{{{
sage: R.<a,b> = InfinitePolynomialRing(QQ['t'])
sage: R('a_0*t')
t*a_0
sage: _.parent()
Infinite polynomial ring in a, b over Univariate Polynomial Ring in t over
Rational Field
sage: R._P
Multivariate Polynomial Ring in a_1, a_0, b_1, b_0 over Univariate
Polynomial Ring in t over Rational Field
sage: type(_)
<class
'sage.rings.polynomial.multi_polynomial_ring.MPolynomialRing_polydict_domain'>
sage: R._P('a_0*t')
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
...
TypeError: unable to convert string
}}}
This is what I mean by "bug in {{{MPolynomialRing_polydict}}}"! And this
is why I use string evaluation as a last resort, since this works much
better:
{{{
sage: R.gens_dict()
GenDict of Infinite polynomial ring in a, b over Univariate Polynomial
Ring in t over Rational Field
sage: _._D
[InfiniteGenDict defined by ['a', 'b'], {'t': t}, {'1': 1}]
sage: sage_eval('a_0*t',R.gens_dict())
t*a_0
sage: R.gens_dict()['t'].parent()
Univariate Polynomial Ring in t over Rational Field
sage: R.gens_dict()['a_4'].parent()
Infinite polynomial ring in a, b over Univariate Polynomial Ring in t over
Rational Field
}}}
I think that {{{GenDictWithBasering}}} can provide a solution for the
trouble with {{{MPolynomialRing_polydict}}}. As I showed, direct string
conversion was flawed. But the following works:
{{{
sage: from sage.rings.polynomial.infinite_polynomial_ring import
GenDictWithBasering
sage: D = GenDictWithBasering(R._P, R._P.gens_dict())
sage: sage_eval('a_0*t',D)
t*a_0
sage: _.parent()
Multivariate Polynomial Ring in a_1, a_0, b_1, b_0 over Univariate
Polynomial Ring in t over Rational Field
}}}
2.
It is now possible to construct quotient rings of infinite polynomial
rings by symmetric ideals. Here, of course, it is required to have a field
as base ring (for Groebner bases)
{{{
sage: R.<x> = InfinitePolynomialRing(QQ)
sage: I = R.ideal([x[1]*x[2] + x[3]])
}}}
Note that ``I`` is not a symmetric Groebner basis (the symmetric Groebner
basis of a principal symmetric ideal is generally not formed by a single
polynomial!):
{{{
sage: G = R*I.groebner_basis()
sage: G
Symmetric Ideal (x_1^2 + x_1, x_2 - x_1) of Infinite polynomial ring in x
over Rational Field
sage: Q = R.quotient(G)
sage: p = x[3]*x[1]+x[2]^2+3
sage: Q(p)
-2*x_1 + 3
}}}
By the second generator of G, variable x_n is equal to x_1 for any
positive integer n.
By the first generator of G, x_1^3^ is equal to x_1 in Q. Indeed, we have
{{{
sage: Q(p)*x[2] == Q(p)*x[1]*x[3]*x[5]
True
}}}
Note that the one doc test in {{{quotient_ring.py}}} has a doc test
involving symmetric ideals. I don't know who wrote it, but (s)he forgot to
use a symmetric Groebner basis for the ideal.
'''__Coercion__'''
I discovered construction functors and pushout, and now I really
appreciate Sage's coercion system. By consequence, I make extensive use of
it --- hopefully not too much...
1.
I introduced a construction functor for infinite polynomial rings. This
functor, together with a ring, is used as the unique key of an infinite
polynomial ring (as unique parent structure. I don't know if the use of
construction functors for providing unique parents is common --- but I can
recommend it!
{{{
sage: InfinitePolynomialRing.create_key(QQ, ('y1',))
(InfPoly{[y1], "lex", "dense"}(FractionField(...)), Integer Ring)
sage: InfinitePolynomialRing.create_key(QQ, names=['beta'],
order='deglex', implementation='sparse')
(InfPoly{[beta], "deglex", "sparse"}(FractionField(...)), Integer Ring)
sage: InfinitePolynomialRing.create_key(QQ, names=['x','y'],
implementation='dense')
(InfPoly{[x,y], "lex", "dense"}(FractionField(...)), Integer Ring)
}}}
As you can see, the given base ring is generally not used in the unique
key. The reason is explained in the next paragraph.
2.
In a way, an infinite polynomial ring X is just an upgrade of a usual
polynomial ring P: The former has finitely many generators x, y and
infinitely many variables x_0, x_1,..., y_0,y_1,..., while the latter may
have finitely many variables x_0,x_1,x_2.
Now, imagine what happens if you define {{{X =
InfinitePolynomialRing(P,['x','y'])}}}? We can't simply take P as the base
ring of X, since there is a name conflict. But since P can be considered a
sub-structure of X: Why shouldn't one merge it into X?
In fact, this is what I do, still with unique parent structures:
{{{
sage: P.<a,b,x_2,x_0,y_3,y_2> = QQ[]
sage: X.<x,y> = InfinitePolynomialRing(P, order='degrevlex')
sage: X
Infinite polynomial ring in x, y over Multivariate Polynomial Ring in a, b
over Rational Field
sage: P2.<a,b> = QQ[]
sage: X2.<x,y> = InfinitePolynomialRing(P2, order='degrevlex')
sage: X2 is X
True
}}}
However, one has to be cautious: Infinite Polynomial Rings are ''ordered''
rings. Therefore, we only merge P into X if it is not only isomorphic to a
sub-ring of X, but isomorphic to an ''ordered'' sub-ring of X. If this is
not the case, an error will be raised:
{{{
sage: X3.<x,y> = InfinitePolynomialRing(P) # the standard order is lex
---------------------------------------------------------------------------
CoercionException Traceback (most recent call
last)
...
CoercionException: Incompatible term orders lex, degrevlex
sage: X3.<y,x> = InfinitePolynomialRing(P, order='degrevlex')
---------------------------------------------------------------------------
CoercionException Traceback (most recent call
last)
...
CoercionException: Overlapping variables (('y', 'x'),['x_2', 'x_0', 'y_3',
'y_2']) are incompatible
}}}
Note: We attempted to make y_* greater than x_* in X, but x_* is greater
than y_* in P.
{{{
sage: P.<a,b,x_0,x_2,y_3,y_2> = QQ[]
sage: X3.<x,y> = InfinitePolynomialRing(P, order='degrevlex')
---------------------------------------------------------------------------
CoercionException Traceback (most recent call
last)
...
CoercionException: Overlapping variables (('x', 'y'),['x_0', 'x_2', 'y_3',
'y_2']) are incompatible
}}}
Note: In any infinite polynomial ring holds x_2>x_0, but the order in P is
opposite.
The 'magical merging' is based on the multiplication of construction
functors, combined with the fact that functors are used as unique keys for
parent structures.
__Remark__
What I do here could also be a model for polynomial rings. After all, I
think it is a bug that the following does not raise an error:
{{{
sage: QQ['t']['t']
Univariate Polynomial Ring in t over Univariate Polynomial Ring in t over
Rational Field
}}}
3.
The original purpose of the coercion machinery is probably to allow for
flexible use of arithmetic with elements of different rings. There you
are:
{{{
sage: 1/2*x_2+z[3]-a/((3*z[2]+2*z[1]+3)^2).lc()
z_3 - 1/9*a + 1/2*x_2
sage: _.parent()
Infinite polynomial ring in z over Multivariate Polynomial Ring in a, b,
x_2, x_0, y_3, y_2 over Rational Field
}}}
or
{{{
sage: P.<a,b,x_2,x_0,y_3,y_2> = ZZ[]
sage: X.<y,z> = InfinitePolynomialRing(ZZ,order='degrevlex')
sage: 1/2*x_2+z[3]-a/((3*z[2]+2*z[1]+3)^2).lc()
z_3 - 1/9*a + 1/2*x_2
sage: _.parent()
Infinite polynomial ring in y, z over Multivariate Polynomial Ring in a,
b, x_2, x_0 over Rational Field
}}}
Note that the last example only works since P and X both have order
'degrevlex'; otherwise we couldn't fit both P and X into a common ring.
'''__Self-critical comments__'''
* The closed ticket #6854 provides tab completion for elements of
infinite polynomial rings. Here I provide a slightly simpler
implementation. But I wouldn't mind if the implementation from #6854 would
be used instead.
* The patch contains the changes that I suggested on #7620. It is
essential that these changes are done. So, #7620 may be considered a
duplicate (or sub-ticket).
* The new {{{InfinitePolynomialFunctor}}} has rank 9.5; this is since
{{{PolynomialFunctor}}} has rank 9 and should be applied ''before''
{{{InfinitePolynomialFunctor}}} --- but rank 10 is taken by
{{{MatrixFunctor}}}. I hope that fine tuning is ok.
* The doc tests of devel/sage/sage/numerical/mip.pyx will break, since
the name scheme for variables of infinite polynomial rings has changed.
However, #7561 suggests to remove infinite polynomial rings from mip.pyx.
So, I can live with these broken doc tests...
'''__Question to the Reviewer__'''
Can you please test on a 32 bit machine as well? I know that the hash code
on 64 bit has changed, but I have no access to 32 bit and don't know what
hash value to expect.
I hope that you enjoy that patch bomb...
Cheers,
Simon
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7580#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
