Polynomial rings are not unique parents

[Simon King]

Hi!

Currently, dense polynomial rings and sparse polynomial rings over the
same base and with the same variable name are equal, but are of course
not identical. Hence, they violate the unique parent assumption.

That violation hit me while working on #9944: With some of the changes
that I did,
sage: R.<x> = QQ[]
sage: 1/x
1/x
sage: R.<x> = PolynomialRing(QQ, sparse=True)
sage: 1/x
goes BOOOOM, because sage.structure.coerce_actions.ModuleAction
verifies the uniqueness of parents.

The reason, to my understanding, is that the polynomial ring is used
as a key for a cached method, probably returning a conversion map.
Obviously it asks for trouble if the codomain of the cached conversion
map is different from the ring into which the conversion map should
yield.

Do people feel strongly about QQ['x'] == PolynomialRing(QQ,
sparse=True) ?

I would prefer that they would not evaluate equal. Of course, there
would still be coercions in both directions.

Best regards,
Simon

[Nicolas M. Thiery]

+1 on sparse and dense polynomial rings being distinct.

(but typically bearing coercions in both directions)

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[John Cremona]

Does it makes sense to treat a sparse poly ring over R as if it had a
different variable? I mean, R[x] and R[y] are different but with
canonical coercions in both directions, and we could think of the
situations under discussion as if we had R[x_dense] and R[x_sparse].

I may be talking nonsense, of course!

John

> Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
> http://Nicolas.Thiery.name/
>

[Nicolas M. Thiery]

On Tue, May 10, 2011 at 02:08:19PM +0100, John Cremona wrote:
> I mean, R[x] and R[y] are different but with canonical coercions in
> both directions,

Just commenting on this statement; there is no canonical coercion
between R[x] and R[y]; just a conversion:

sage: Rx = QQ[x]
sage: Ry = QQ['y']
sage: Ry.has_coerce_map_from(Rx)
False
sage: Ry.convert_map_from(Rx)
Conversion map:
From: Univariate Polynomial Ring in x over Rational Field
To: Univariate Polynomial Ring in y over Rational Field

This is good, for otherwise, the diagram:

R[x] ----> R[y]
| |
\/ \/
R[x,y] ----> R[x,y]

would not commute.

On the other hand, coercions between sparse / dense polynomial rings
over the same variables would seem natural.

Cheers,
Nicolas
--

[Simon King]

Hi Nicolas and John,

thank you for your encouragement!

On 10 Mai, 15:28, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:

> On Tue, May 10, 2011 at 02:08:19PM +0100, John Cremona wrote:
> > I mean, R[x] and R[y] are different but with canonical coercions in
> > both directions,
>
> Just commenting on this statement; there is no canonical coercion
> between R[x] and R[y]; just a conversion:

OK, then I'll try it like this:
* Conversion in both directions between R[x] and R[y], regardless
whether it is sparse or dense.
* Coercion in both directions between R[x]_sparse and R[x]_dense
* R[x]_sparse and R[x]_dense are not equal.

It will be in an updated patch for #9944. Aim of #9944 is to use the
category framework for all polynomial rings, aim of the new patch is
to use faster coercion from the base ring into the polynomial ring
(providing a big speedup in many examples). On top of it, #9138 shall
use the category framework for all rings and the new coercion model
for a lot more rings.

Best regards,
Simon

[Nicolas M. Thiery]

On Tue, May 10, 2011 at 07:20:16AM -0700, Simon King wrote:
> OK, then I'll try it like this:
> * Conversion in both directions between R[x] and R[y], regardless
> whether it is sparse or dense.
> * Coercion in both directions between R[x]_sparse and R[x]_dense
> * R[x]_sparse and R[x]_dense are not equal.
>
> It will be in an updated patch for #9944. Aim of #9944 is to use the
> category framework for all polynomial rings, aim of the new patch is
> to use faster coercion from the base ring into the polynomial ring
> (providing a big speedup in many examples). On top of it, #9138 shall
> use the category framework for all rings and the new coercion model
> for a lot more rings.

Cool! This all sounds good!

[John Cremona]

On Tue, May 10, 2011 at 3:56 PM, Nicolas M. Thiery
<Nicolas...@u-psud.fr> wrote:
> On Tue, May 10, 2011 at 07:20:16AM -0700, Simon King wrote:
>> OK, then I'll try it like this:
>>  * Conversion in both directions between R[x] and R[y], regardless
>> whether it is sparse or dense.
>>  * Coercion in both directions between R[x]_sparse and R[x]_dense
>>  * R[x]_sparse and R[x]_dense are not equal.
>>
>> It will be in an updated patch for #9944. Aim of #9944 is to use the
>> category framework for all polynomial rings, aim of the new patch is
>> to use faster coercion from the base ring into the polynomial ring
>> (providing a big speedup in many examples). On top of it, #9138 shall
>> use the category framework for all rings and the new coercion model
>> for a lot more rings.
>
> Cool! This all sounds good!

Agreed!

John

>
> Cheers,
>                                Nicolas
> --

[Simon King]

Hi!

I just wonder: Do we really want coercions in both directions? That
might actually not desirable, since the parent of a sum depends on the
order of summands if there is a bidirectional coercion.

The current behaviour is:

sage: R.<x> = PolynomialRing(QQ, sparse=True)

sage: S.<x> = QQ[]
sage: (R.0+S.0).parent()
Sparse Univariate Polynomial Ring in x over Rational Field
sage: (S.0+R.0).parent()

Univariate Polynomial Ring in x over Rational Field

What we have discussed in the previous posts would not change it.

But there is an alternative: We could say that there is no coercion
between S and R in either direction. Instead, we could use the pushout
construction. That's to say, we could achieve that the sum of a dense
polynomial with a sparse polynomial is always dense (regardless of the
order of summation), and so the result will be sparse only if all
summands are sparse.

I just noticed that there is a bug related with pushout anyway:
sage: F,B = R.construction()
sage: F(B) is R
False
sage: F(B) is S
True

Hence, the construction functor obtained from a sparse ring creates
dense rings.

My impression is that the pushout approach is cleaner than a
bidirectional coercion approach. What do you think?

Cheers,
Simon

[Simon King]

Let me elaborate a bit more on dense versus sparse.

Do we agree that the dense representation of univariate polynomials
should be the default? Then, there should be a coercion from sparse to
dense, but not vice versa.

If you say that (even in the univariate case) the sparse
implementation should be the default then the rule above must be
reversed.

In the multivariate case, of course Sage does not offer a dense
implementation. However, the polynomial ring constructor accepts the
argument "sparse" in the multivariate case -- which results in another
violation of the unique parent assumption:
sage: R.<x,y> = PolynomialRing(QQ, sparse=False)
sage: S.<x,y> = PolynomialRing(QQ, sparse=True)
sage: R is S
False
sage: R == S
True

So, one should either raise an error when the "sparse" argument is
used in the multivariate case, or ignore it in the cache key. Which
one would you prefer?

Cheers,
Simon

[Simon King]

... and I guess a similar argument applies to other implementation
details: ZZ[x] can be implemented using FLINT or NTL. FLINT is the
default implementation. Hence, I suggest that we have:

sage: R.<x> = PolynomialRing(ZZ, implementation = 'NTL')
sage: S.<x> = PolynomialRing(ZZ, implementation = 'FLINT')
sage: R
Univariate Polynomial Ring in x over Integer Ring (using NTL)
sage: S
Univariate Polynomial Ring in x over Integer Ring
sage: R == S
False
sage: R.has_coerce_map_from(S)
False
sage: S.has_coerce_map_from(R)
True

There is no sparse representation using NTL:

sage: R.<x> = PolynomialRing(ZZ, implementation = 'NTL',
sparse='True')
sage: R
Sparse Univariate Polynomial Ring in x over Integer Ring

Therefore I suggest that the "implementation" argument is ignored if a
sparse ring is requested, for otherwise there would be yet another
violation of the unique parent assumption.

Cheers,
Simon