A 3-digit ticket: Should there be a coercion from S[x,y] to S[x][y], for any ring S?

[Simon King]

Hi!

Being interested in palaeontology, I came accross trac ticket #813.

The ticket first boils down to the following question: Should there be
a coercion from a bivariate polynomial ring in x and y over QQ to the
polynomial ring in y over the fraction field of QQ[x]?

Note that there IS a coercion from QQ[x][y] to Frac(QQ[x])[y], but
there is no such coercion from QQ[x,y]:

sage: from sage.structure.element import get_coercion_model
sage: cm = get_coercion_model()
sage: cm.explain(Frac(QQ['x'])['y'], QQ['x']['y'])
Coercion on right operand via
Conversion map:
From: Univariate Polynomial Ring in y over Univariate Polynomial
Ring in x over Rational Field
To: Univariate Polynomial Ring in y over Fraction Field of
Univariate Polynomial Ring in x over Rational Field
Arithmetic performed after coercions.
Result lives in Univariate Polynomial Ring in y over Fraction Field of
Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in y over Fraction Field of Univariate
Polynomial Ring in x over Rational Field
sage: cm.explain(Frac(QQ['x'])['y'], QQ['x','y'])
Will try _r_action and _l_action
Unknown result parent.

But I think the question can be reduced even further. Let S and R be
rings.

Note that there is a coercion from S[x][y] to S[x,y], such as here:
sage: QQ['x','y'].has_coerce_map_from(QQ['x']['y']) # case 1
True

By consequence, if there is a coercion from S[x,y] to a ring R then
there must be a coercion from S[x][y] to R.

But should there also be a coercion in the opposite direction? There
currently isn't, and also one is not allowed to switch the variables
in a stacked polynomial ring, while it IS allowed to switch variables
for bivariate rings:
sage: QQ['x']['y'].has_coerce_map_from(QQ['x','y']) # case 2
False
sage: QQ['x']['y'].has_coerce_map_from(QQ['y']['x']) # case 3
False
sage: QQ['x','y'].has_coerce_map_from(QQ['y','x']) # case 4
True

What is the reason why cases 2 and 3 are not enabled? Is there a
striking example that shows why it would be troublesome to have "True"
in all four cases?

If we can not allow a coercion from QQ[x,y] to QQ[x][y] then #813
should probably be resolved as invalid.

Best regards,
Simon

[Simon King]

PS:

On 31 Jul., 17:10, Simon King <simon.k...@uni-jena.de> wrote:
> Note that there is a coercion from S[x][y] to S[x,y], such as here:
>   sage: QQ['x','y'].has_coerce_map_from(QQ['x']['y'])   # case 1
>   True

>...

>
> But should there also be a coercion in the opposite direction? There
> currently isn't, and also one is not allowed to switch the variables
> in a stacked polynomial ring, while it IS allowed to switch variables
> for bivariate rings:

> ...

>   sage: QQ['x']['y'].has_coerce_map_from(QQ['y']['x'])  # case 3
>   False

Here, I should better do

sage: cm.explain(QQ['x']['y'], QQ['y']['x'])

Will try _r_action and _l_action
Unknown result parent.

> What is the reason why cases 2 and 3 are not enabled? Is there a
> striking example that shows why it would be troublesome to have "True"
> in all four cases?

I think having a coercion in both directions means that the parent of
an arithmetic operation is not unique. That would be a compelling
reason to ban some of the coercions, right?

Do you agree that #813 is "wontfix" resp. "invalid"?

[Simon King]

Hi!

On 31 Jul., 20:10, Simon King <simon.k...@uni-jena.de> wrote:
> I think having a coercion in both directions means that the parent of
> an arithmetic operation is not unique. That would be a compelling
> reason to ban some of the coercions, right?
>
> Do you agree that #813 is "wontfix" resp. "invalid"?

Meanwhile I not only think that #813 is valid, but I provided a patch,
and I'd appreciate a review.

Let P=QQ['x','y'] and Q=Frac(QQ['x'])['y']. The rationale for my patch
is:

1. There already is a pushout for P and Q: pushout(P,Q) is Q.

2. Conversion from P into Q already works: Elements of P are expressed
as univariate polynomials in y, and its coefficients are then coerced
into the base ring of Q.

3. Nevertheless, Q.has_coerce_map_from(P) currently returns False.

The fact that pushout(P,Q).has_coerce_map_from(P) returns False is
certainly a bug. Hence, I tried to modify _coerce_map_from_ of
univariate rings.

It is tempting to says: "There is a coercion if
P.remove_var(Q.variable_name()) coerces into Q.base_ring()". However,
that would imply that there is a coercion from QQ['x','y'] to QQ['x']
['y'], which is a bad idea, since there already is a coercion in the
opposite direction. Bidirectional coercions are generally dangerous,
and in fact many doc tests would fail.

So, I used a modified rule that avoids circular coercions: "There is a
coercion if P.remove_var(Q.variable_name()) is different from
Q.base_ring(), but coerces into it".

In other words, if you ever dreamed of being reviewer for a three
digit ticket -- here is your chance!

Cheers,
Simon

[John Cremona]

Simon,

I'm neither answering your question nor being helpful by reviewing
#813, but asking a question: I have a polynomial in QQ[u][x] and I
want to convert it into an element of QQ[u,x], simply because I want
to factor it. (I will want to move the factors back). I get the
impression from this ticket that there is no coercion to do that --
fine. But I cannot even define a Homomorphism:

sage: R.<x> = PolynomialRing(QQ)
sage: S.<u> = PolynomialRing(R)
sage: T.<X,U> = PolynomialRing(QQ,2)
sage: Hom(S,T)([U])
TypeError: images do not define a valid homomorphism
sage: Hom(S,T)([X,U])
TypeError: images do not define a valid homomorphism

How do I define the natural map sending x,u to X,U?

John

[Simon King]

Hi John,

On 4 Aug., 17:58, John Cremona <john.crem...@gmail.com> wrote:
> I'm neither answering your question nor being helpful by reviewing
> #813

:(

> , but asking a question:  I have a polynomial in QQ[u][x] and I
> want to convert it into an element of QQ[u,x], simply because I want
> to factor it.  (I will want to move the factors back).  I get the
> impression from this ticket that there is no coercion to do that --
> fine.  But I cannot even define a Homomorphism:
>
> sage: R.<x> = PolynomialRing(QQ)
> sage: S.<u> = PolynomialRing(R)
> sage: T.<X,U> = PolynomialRing(QQ,2)

It would be easier if the variable names of S and T would coincide.
So, let me modify your example:

sage: R.<x> = QQ[]
sage: S.<u> = R[]
sage: T = QQ['x','u']
sage: p = S.random_element()
sage: p
(-8*x - 7/3)*u^2 + (1/16*x - 2)*u - 7*x^2 - 1/3
sage: T(p)
-8*x*u^2 - 7*x^2 + 1/16*x*u - 7/3*u^2 - 2*u - 1/3
sage: q = T.random_element()
sage: q
21*x*u + u + 5
sage: S(q)
(21*x + 1)*u + 5

In other words, if the variable names are the same then the usual
conversion does the job.

> How do I define the natural map sending x,u to X,U?

Probably it is not possible to define it in the usual S.hom(...)
notation. But you can simply compose conversions, as follows:

sage: R.<x> = QQ[]
sage: S.<u> = R[]
sage: T = QQ['X','U']

# 1. Map S to QQ['X']['Y']
sage: S2 = QQ['X']['U']
sage: f0 = S2.convert_map_from(S); f0
Conversion map:
From: Univariate Polynomial Ring in u over Univariate Polynomial

Ring in x over Rational Field

To: Univariate Polynomial Ring in U over Univariate Polynomial
Ring in X over Rational Field

#2. Map QQ['X']['Y'] to QQ['X','Y']
sage: f1 = T.convert_map_from(S2); f1
Call morphism:
From: Univariate Polynomial Ring in U over Univariate Polynomial
Ring in X over Rational Field
To: Multivariate Polynomial Ring in X, U over Rational Field

#3. Compose
sage: f = f1*f0
sage: f
Composite map:
From: Univariate Polynomial Ring in u over Univariate Polynomial

Ring in x over Rational Field

To: Multivariate Polynomial Ring in X, U over Rational Field
Defn: Conversion map:
From: Univariate Polynomial Ring in u over Univariate

Polynomial Ring in x over Rational Field

To: Univariate Polynomial Ring in U over Univariate
Polynomial Ring in X over Rational Field
then
Call morphism:
From: Univariate Polynomial Ring in U over Univariate
Polynomial Ring in X over Rational Field
To: Multivariate Polynomial Ring in X, U over Rational
Field
sage: f.parent()
Set of Homomorphisms from Univariate Polynomial Ring in u over
Univariate Polynomial Ring in x over Rational Field to Multivariate
Polynomial Ring in X, U over Rational Field
sage: f.parent().category()
Category of hom sets in Category of rings

#4. Enjoy
sage: p = S.random_element()
sage: p
(-3*x^2 + 1/10*x + 1/11)*u^2 + (-1/10*x^2 - x)*u + x^2 - 2*x + 1/44
sage: f(p)
-3*X^2*U^2 - 1/10*X^2*U + 1/10*X*U^2 + X^2 - X*U + 1/11*U^2 - 2*X +
1/44

Cheers,
Simon

[John Cremona]

Simon,

Thank you very much for your help! I had discovered that by reusing a
variable name the conversion was possible, so had got over this
particular block in my computation. But your extended example is very
helpful indeed, so I will keep it for a future occasion. How is it
that I had never heard of the convert_map_from() function?

To sum up your 2-step construction, to go from QQ[x][u] to QQ[X,U]
mapping x,u to X,U respectively we form the composite

QQ[x][u] --> QQ[X][U] --> QQ[X,U]

where the first map (which is called a "conversion map" but not a
homomorphism for some reason) is the obvious one, and the second map
(which is a genuine Homomorphism) works because the variable names are
the same.

I seem to remember that in Magma one could define a homomorphism
QQ[x][u] --> QQ[X,U] but it is also a little contrived; first map
QQ[x] to QQ[X,U] by mapping x to X, and then map QQ[x][u] to QQ[X,U]
using both the already-defined map for the coefficients in QQ[x] and
also specifying that u maps to U. Which is not at all easy until you
get used to it!

John

[Nicolas M. Thiery]

On Sun, Jul 31, 2011 at 11:10:17AM -0700, Simon King wrote:
> I think having a coercion in both directions means that the parent of
> an arithmetic operation is not unique.

Nope. It just means that two parents having a coercion in both
directions between them are (or should be!) canonically
isomorphic. Yet we may not want to identify them, typically because
the representation of their respective elements are quite different.
Since efficient algorithm in computer algebra often rely on switching
between different representations, such switching should be easy,
which non identified parents + bidirectional coercion supports. It
turns out that, at the moment, the coercion model does not handle a
conversion graph with cycles as well as it should. But that's just a
bug with the current coercion model; cycles in the conversion graph
should be used whenever meaningful.

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

[Simon King]

Hi Nicolas,

On 8 Aug., 13:57, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:

> On Sun, Jul 31, 2011 at 11:10:17AM -0700, Simon King wrote:
> > I think having a coercion in both directions means that the parent of
> > an arithmetic operation is not unique.
>
> Nope. It just means that two parents having a coercion in both
> directions between them are (or should be!) canonically
> isomorphic.

I disagree.

If you have p in QQ[x,y] and q in QQ[x][y] and you WOULD have
coercions in both directions, then IIRC the parent of the result of an
arithmetic operation on p and q would be the left operand. Hence, p+q
would be an element of QQ[x,y], while q+p would be an element of QQ[x]
[y]. That is what I call "the parent of an arithmetic operation
[addition being commutative] is not unique". It would be bug prone and
should be avoided, IMHO.

Currently, we only have a coercion from QQ[x][y] to QQ[x,y], and thus
both p+q and q+p live in QQ[x,y].

That's why I proposed a mechanism that, on the one hand, fixes the bug
that pushout(QQ[x,y], Frac(QQ[x])[y]) exists but has no coercion from
QQ[x,y], and, on the other hand, does not introduce new bidirectional
coercions between isomorphic rings whose implementations differ in far
more than just details.

Do you see a canonical (i.e., independent of the order of operands)
and algorithmic way to choose a representative for the isomorphism
class of pushouts of the operands' parents?

Cheers,
Simon

[John Cremona]

I for one always need to be reminded of the difference between a
coercion, which happens automatically behind the scenes as with
Simon's p+q example, and a conversion, where one explicitly pushes an
object from one structure (say Q[x,y]) into another (say Q[x][y]);
and lastly the ability to easily define a map f from the first
structure to the second, which is mathematically the "natural
identification" a human would do, but which can then be applied
explicitly so one could do f(p)+q even if p+q did not work
automatically.

John

[Simon King]

On 9 Aug., 00:11, Simon King <simon.k...@uni-jena.de> wrote:
> If you have p in QQ[x,y] and q in QQ[x][y] and you WOULD have
> coercions in both directions, then IIRC the parent of the result of an
> arithmetic operation on p and q would be the left operand.

I meant to write "left operand's parent".

Here is an example of a situation with a bidirectional coercion:

sage: R = QQ['x','y']
sage: S = QQ['y','x']
sage: R.0+S.0 == S.0+R.0
True
sage: parent(R.0+S.0) is R
True
sage: parent(S.0+R.0) is S
True

So, the parent of the result is not unique, in the sense of "the
results are equal, but live in different parents".

Here, the two parents are similar enough (in fact, the same Cython
class), so that it is also justified FROM THE POINT OF VIEW OF
IMPLEMENTATION to consider them being canonically isomorphic and thus
interchangeable.

However, the situation of R=QQ['x','y'] versus S=QQ['x']['y'] is
different. While certainly R and S are canonically isomorphic from a
mathematical point of view and have conversions in both directions,
they are rather different in their features (see below).

One could argue that one should implement the missing features of R
resp. S, and choose a common name for methods that have the same
purpose but are called differently for R and S. However, that would
require an awful lot of work.

I thus think that adding a coercion from QQ['x','y'] to QQ['x']['y']
is bad - I already tried it, and MANY doc tests break in a fairly non-
trivial way. But a coercion from QQ['x','y'] to Frac(QQ['x'])['y']
should be fine - that's what #813 is about (hint hint...).

Cheers,
Simon

PS:
Here is evidence how different S and R are

sage: R=QQ['x','y']
sage: S=QQ['x']['y']
sage: [s for s in dir(R) if s not in dir(S)]
['__eq__', '__ge__', '__gt__', '__le__', '__lt__', '__ne__',
'_extract_polydict', '_macaulay2_set_ring', '_magma_cache',
'_magma_gens', '_monomial_order_function', '_precomp_counts',
'_random_monomial_upto_degree_class',
'_random_monomial_upto_degree_uniform', '_to_monomial',
'irrelevant_ideal', 'monomial_all_divisors', 'monomial_divides',
'monomial_lcm', 'monomial_pairwise_prime', 'monomial_quotient',
'monomial_reduce', 'remove_var', 'repr_long', 'term_order']
sage: [s for s in dir(S) if s not in dir(R)]
['_PolynomialRing_general__cyclopoly_cache',
'_PolynomialRing_general__generator',
'_PolynomialRing_general__is_sparse', '__cmp__',
'_implementation_repr', '_monics_degree', '_monics_max',
'_polynomial_class', '_polys_degree', '_polys_max', '_sage_input_',
'change_var', 'cyclotomic_polynomial', 'extend_variables',
'is_integrally_closed', 'is_sparse', 'monics', 'parameter',
'polynomials', 'quotient_by_principal_ideal']
sage: [s for s in dir(R.0) if s not in dir(S.0)]
['_complex_double_', '_complex_mpfr_field_', '_homogenize', '_mpfr_',
'_norm_over_nonprime_finite_field', '_polynomial_', '_real_double_',
'_repr_short_', '_repr_with_changed_varnames', '_variable_indices_',
'add_m_mul_q', 'coefficient', 'content', 'degrees', 'gcd', 'gradient',
'homogenize', 'is_generator', 'is_homogeneous', 'is_univariate',
'jacobian_ideal', 'lc', 'lift', 'lm', 'lt', 'map_coefficients',
'monomial_coefficient', 'monomials', 'newton_polytope', 'nvariables',
'quo_rem', 'reduce', 'sub_m_mul_q', 'total_degree',
'univariate_polynomial', 'variable']
sage: [s for s in dir(S.0) if s not in dir(R.0)]
['__delitem__', '__getslice__', '__lshift__', '__rlshift__',
'__rrshift__', '__rshift__', '__setitem__', '_compile',
'_dict_to_list', '_factor_pari_helper', '_lcm', '_mul_fateman',
'_mul_generic', '_mul_karatsuba', '_new_constant_poly',
'_pari_with_name', '_pow', '_repr', '_sage_input_', '_square_generic',
'_unsafe_mutate', '_xgcd', 'change_variable_name', 'coeffs',
'complex_roots', 'discriminant', 'hamming_weight', 'integral',
'is_gen', 'is_irreducible', 'is_monic', 'is_primitive', 'is_square',
'leading_coefficient', 'list', 'monic', 'name', 'newton_raphson',
'newton_slopes', 'norm', 'ord', 'padded_list', 'plot', 'prec',
'radical', 'real_roots', 'reverse', 'root_field', 'roots', 'shift',
'square', 'squarefree_decomposition', 'valuation', 'variable_name']