Implement substitution in InfinitePolynomialRing

[trevorkarn]

Add the ability to substitute variables in InfinitePolynomialRing.

sage: R.<z> = InfinitePolynomialRing(QQ)
sage: f = z[1] + z[1]*z[2]*z[3]
sage: f.subs({z[1]:z[0]})
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Input In [3], in <cell line: 1>()
----> 1 f.subs({z[Integer(1)]:z[Integer(0)]})

File ~/Applications/sage/src/sage/structure/element.pyx:830, in sage.structure.element.Element.subs()
    828 if str(gen) in kwds:
    829     variables.append(kwds[str(gen)])
--> 830 elif in_dict and gen in in_dict:
    831     variables.append(in_dict[gen])
    832 else:

TypeError: unhashable type: 'InfinitePolynomialGen'

CC: @tscrim @mwhansen @simon-king-jena

Component: algebra

Keywords: polynomial infinite substitution subs

Author: Trevor K. Karn

Branch/Commit: a56e345

Reviewer: Tomer Bauer, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/34581

[trevorkarn]

New commits:

2ec0f39

Add subs method

[trevorkarn]

Commit: 2ec0f39

[trevorkarn]

Branch: u/tkarn/inf-poly-subs-34581

[tscrim]

comment:2

There are some bad behaviors that this implements:

• It forces the inputs to be in the polynomial ring. I should be able to substitute anything I want where the computation makes such, such as square matrices. This should be a simple redirection.
• It forces the output to be in the infinite polynomial ring. Instead, the output should be the common parent of the input and the base ring.

The "standard" thing to do is redirect everything through __call__ after parsing the inputs a bit, and probably should be done here too. Although I am a bit tempted to just instead do a simple redirect to self._p.subs(*args, **kwds). Actually, there probably is a general problem of not expanding the input polynomial to be large enough to handle the input.

sage: f(x_10=f)
KeyError
sage: f(x_2=f)
x_3^2*x_2*x_1^2 + x_3*x_1^2 + x_1
sage: x[12]  # make it big enough
x_12
sage: f(x_10=f)
x_3*x_2*x_1 + x_1

Probably the input parsing of subs and __call__ should be refactored out into a helper method, and then both of these methods redirect to their finite polynomial counterparts.

[fchapoton]

comment:3

beware of #34542

[mathzeta]

comment:4

This might answer this question from 4 years ago. Thanks!

[sagetrac-git]

Changed commit from 2ec0f39 to 623021f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7491113	Add subs method
623021f	Punt to call and add doctests

[trevorkarn]

comment:6

It looks like __call__ took care of everything, so the .subs() method now does all of the preparsing and passes to __call__. I don't like the variable name fixed, but it is consistent with MPolynomial_libsingular.subs().

[sagetrac-git]

Changed commit from 623021f to 0082d03

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0082d03

PEP8 compliance

[trevorkarn]

comment:9

Green bot :)

[mathzeta]

comment:10

LGTM. positive review.

Almost unrelated to this ticket, already in the __call__ method we can substitute all variables from a "finite" polynomial ring:

sage: R.<x> = InfinitePolynomialRing(QQ)
sage: S.<z, w> = QQ[]
sage: f = x[1] + x[1]*x[2]*x[3]
sage: f(x_1=w, x_2=z^2+1, x_3=z)
z^3*w + z*w + w

But it is a pity we do not have a canonical coercion when substituting only some of the variables:

sage: f(x_1=w)
[...]
TypeError: no canonical coercion from Multivariate Polynomial Ring in z, w over Rational Field to Multivariate Polynomial Ring in x_5, x_4, x_3, x_2, x_1, x_0 over Rational Field

During handling of the above exception, another exception occurred:
[...]
TypeError: unsupported operand parent(s) for *: 'Multivariate Polynomial Ring in x_5, x_4, x_3, x_2, x_1, x_0 over Rational Field' and 'Multivariate Polynomial Ring in z, w over Rational Field'

[mathzeta]

Reviewer: Tomer Bauer

[trevorkarn]

comment:11

Thanks! Where should the canonical coercion live? I recall seeing something that there is no coercion between polynomials from say QQ[x] and QQ[y] because it could live in any of QQ[x,y], QQ[x][y], QQ[y][x]. This seems like a similar problem to me. Should the substitution of some of the variables be in QQ[x_0, x_1,...][w] or QQ[w][x_0, x_1,...] (since I don't think QQ[w,x_0,x_1,...] exists in Sage yet).

[tscrim]

Changed reviewer from Tomer Bauer to Tomer Bauer, Travis Scrimshaw

[tscrim]

comment:12

Sorry for not being able to review this sooner.

A few things need to be addressed before a positive review from me.

Some doc changes:

-        Substitute variables in an infinite polynomial.
+        Substitute variables in ``self``.
 
         INPUT:
 
-        - ``fixed`` - (optional) dict with variable:value pairs
-        - ``**kwargs`` - names parameters
-        - ``fixed`` -- (optional) ``dict`` with ``{variable:value}`` pairs
-        - ``**kwargs`` -- named parameters
 
         OUTPUT:
-            a new polynomial
+
+        the resulting substitution

-If you want to substitute variables more generally, use the ``.subs``
-method::
+If you want to substitute variables, you can use the
+standard polynomial methods, such as
+:meth:`~sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial_sparse.subs`::

This documentation is not quite correct and make this change:

-       The substitution can also handle matrices. It will
-       return a matrix whose entries are polynomials in countably
-       many variables::
+       The substitution can also handle matrices::

It is more complicated than that as it does the substitution and then does the addition by coercion. You can check things by looking at the parent of the outputs (or doing additional substitutions).

This sentence seems incomplete:

        Passing ``fixed={x[1]: x[0]}``. Note that the keys::

            sage: f.subs({x[1]: x[0]})
            x_3*x_2*x_0 + x_0

I am not sure I would want to prohibit the mixing of the two types of inputs. I would just do kwargs.update(fixed), which would be in line with what (some) other implementations do:

sage: R.<x,y> = PolynomialRing(QQ)
sage: x.subs({x:1})
1
sage: x.subs(x=5)
5
sage: x.subs({x:1}, x=5)
1

[tscrim]

comment:13

Coercion among polynomial rings is notoriously tricky to make consistent (there are some sage-devel threads about this). For example, how do you deal with QQ[x][y,z] versus QQ[x,y][z], or a more complicated one, the ordering of the variables matters for Gröbner basis computations. So Sage just avoids doing it except in some trivial cases IIRC.

[sagetrac-git]

Changed commit from 0082d03 to 5e8977f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5e8977f

Add reviewer suggestions to docs and change behavior of conflicting subs

[trevorkarn]

comment:15

Thanks for the input!

[tscrim]

comment:16

Thank you. One last little thing (an idiosyncrasy most likely), I generally try to avoid referencing Python double-underscore methods. So I would change

         Passing ``fixed={x[1]: x[0]}``. Note that the keys may be given
-        using the ``.__getitem__`` method of the infinite polynomial
-        generator ``x_*`` or as a string::
+        using the generators of the infinite polynomial ring
+        or as a string::

After you make this change (or a similar one), you can set a positive review on my behalf if you want.

[sagetrac-git]

Changed commit from 5e8977f to a56e345

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a56e345

Doc change

[trevorkarn]

comment:18

Replying to Travis Scrimshaw:

Thank you. One last little thing (an idiosyncrasy most likely), I generally try to avoid referencing Python double-underscore methods. So I would change

         Passing ``fixed={x[1]: x[0]}``. Note that the keys may be given
-        using the ``.__getitem__`` method of the infinite polynomial
-        generator ``x_*`` or as a string::
+        using the generators of the infinite polynomial ring
+        or as a string::

Thanks!

After you make this change (or a similar one), you can set a positive review on my behalf if you want.

[vbraun]

Changed branch from u/tkarn/inf-poly-subs-34581 to a56e345