Difference between `subst` and `evaluate` for univariate polynomials

[fingolfin]

Docstring for the former:

    subst(f::PolyRingElem{T}, a::Any) where T <: RingElement

Evaluate the polynomial $f$ at $a$. Note that $a$ can be anything, whether
a ring element or not.

Docstring for the latter:

    evaluate(a::PolyRingElem, b::T) where T <: RingElement

Evaluate the polynomial expression $a$ at the value $b$ and return the result.

That sounds almost the same, except for...

• "polynomial expression" in the second one, what's up with that???
• that evaluate is more restrictive in what it accepts as second argument.

This matteres in practice as shown by this manual example:

julia> R, x = polynomial_ring(ZZ, :x)
(Univariate polynomial ring in x over integers, x)

julia> S, y = polynomial_ring(R, :y)
(Univariate polynomial ring in y over univariate polynomial ring, y)

julia> f = x*y^2 + (x + 1)*y + 3
x*y^2 + (x + 1)*y + 3

julia> g = (x + 1)*y + (x^3 + 2x + 2)
(x + 1)*y + x^3 + 2*x + 2

julia> M = R[x + 1 2x; x - 3 2x - 1]
[x + 1       2*x]
[x - 3   2*x - 1]

julia> k = evaluate(f, 3)
12*x + 6

julia> m = evaluate(f, x^2 + 2x + 1)
x^5 + 4*x^4 + 7*x^3 + 7*x^2 + 4*x + 4

julia> n = compose(f, g; inner = :second)
(x^3 + 2*x^2 + x)*y^2 + (2*x^5 + 2*x^4 + 4*x^3 + 9*x^2 + 6*x + 1)*y + x^7 + 4*x^5 + 5*x^4 + 5*x^3 + 10*x^2 + 8*x + 5

julia> p = subst(f, M)
[3*x^3 - 3*x^2 + 3*x + 4       6*x^3 + 2*x^2 + 2*x]
[3*x^3 - 8*x^2 - 2*x - 3   6*x^3 - 8*x^2 + 2*x + 2]

julia> q = f(M)
[3*x^3 - 3*x^2 + 3*x + 4       6*x^3 + 2*x^2 + 2*x]
[3*x^3 - 8*x^2 - 2*x - 3   6*x^3 - 8*x^2 + 2*x + 2]

Note that evaluate(f, M) does not work.

But that's only due to the restriction on the second argument. If I loosen the second argument to Any then it works just the same. Likewise for composition.

So do we really need subst? If so it'd be great to document the reasons. If not, I'd suggest to generalize evaluate a bit by allowing Any for the second argument, then turn subst into a deprecated alias for evaluate (and replace existing calls to it).

[fieker]

Historicall, subst was meant more like compose: evaluate at polynomials, ala maple while evaluate was for ring elements. I never quite got this dinstinction....

On Thu, Nov 07, 2024 at 03:20:16AM -0800, Max Horn wrote:

Docstring for the former:

    subst(f::PolyRingElem{T}, a::Any) where T <: RingElement

Evaluate the polynomial $f$ at $a$. Note that $a$ can be anything, whether
a ring element or not.

Docstring for the latter:

    evaluate(a::PolyRingElem, b::T) where T <: RingElement

Evaluate the polynomial expression $a$ at the value $b$ and return the result.

That sounds almost the same, except for...

• "polynomial expression" in the second one, what's up with that???
• that evaluate is more restrictive in what it accepts as second argument.

This matteres in practice as shown by this manual example:

julia> R, x = polynomial_ring(ZZ, :x)
(Univariate polynomial ring in x over integers, x)

julia> S, y = polynomial_ring(R, :y)
(Univariate polynomial ring in y over univariate polynomial ring, y)

julia> f = x*y^2 + (x + 1)*y + 3
x*y^2 + (x + 1)*y + 3

julia> g = (x + 1)*y + (x^3 + 2x + 2)
(x + 1)*y + x^3 + 2*x + 2

julia> M = R[x + 1 2x; x - 3 2x - 1]
[x + 1       2*x]
[x - 3   2*x - 1]

julia> k = evaluate(f, 3)
12*x + 6

julia> m = evaluate(f, x^2 + 2x + 1)
x^5 + 4*x^4 + 7*x^3 + 7*x^2 + 4*x + 4

julia> n = compose(f, g; inner = :second)
(x^3 + 2*x^2 + x)*y^2 + (2*x^5 + 2*x^4 + 4*x^3 + 9*x^2 + 6*x + 1)*y + x^7 + 4*x^5 + 5*x^4 + 5*x^3 + 10*x^2 + 8*x + 5

julia> p = subst(f, M)
[3*x^3 - 3*x^2 + 3*x + 4       6*x^3 + 2*x^2 + 2*x]
[3*x^3 - 8*x^2 - 2*x - 3   6*x^3 - 8*x^2 + 2*x + 2]

julia> q = f(M)
[3*x^3 - 3*x^2 + 3*x + 4       6*x^3 + 2*x^2 + 2*x]
[3*x^3 - 8*x^2 - 2*x - 3   6*x^3 - 8*x^2 + 2*x + 2]

Note that evaluate(f, M) does not work.

But that's only due to the restriction on the second argument. If I loosen the second argument to Any then it works just the same. Likewise for composition.

So do we really need subst? If so it'd be great to document the reasons. If not, I'd suggest to generalize evaluate a bit by allowing Any for the second argument, then turn subst into a deprecated alias for evaluate (and replace existing calls to it).

-- Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/1893 You are receiving this because you are subscribed to this thread.

Message ID: @.***>

[fingolfin]

I also just stumbled over issue #1219 which points out this bug (return value should have different type):

julia> Qx, (x, y) = QQ["x", "y"];

julia> typeof(zero(Qx)(x, y))
Rational{BigInt}

Note that evaluate gets this right:

julia> typeof(evaluate(f,[x,y]))
AbstractAlgebra.Generic.MPoly{Rational{BigInt}}

The problem is in the custom (a::MPoly{T})(vals::Union{NCRingElem, RingElement}...) where T <: RingElement method which even includes this in its docstring:

Note that this evaluation is more general than those provided by the evaluate function. The values do not need to be in the same ring, just in compatible rings.

I find it highly surprising that it is "more general" than evaluate. I mean, it clearly easy as it accepts NCRingElem arguments. But why? I would naively expect this just to be a convenient shorthand form.

And then compose is also just a special case for evaluate.

Of course one can (and should) still have custom method for certain cases that are optimized.

[thofma]

Yes, everything is "evaluate".

At the beginning evaluate was supposed to only implement the evaluation map $K[x] -> K$. I hope that answers the "why" question. The dedicated compose and subst functions were there simultaneously or were added later. In particular subst and f(...) is more tricky in a generic, since

• one has to get the domain of the result right (which can be complicated in the multivariate version if the evaluation point is not homogenous)
• one does not want degraded performance, e.g. if one evaluates polynomials at polynomials.

I agree that things can be consolidated and I am happy to see subst be deprecated in favor of a generic evaluate. Since we agree, I don't think there is anything to triage here.

[fingolfin]

OK, so as @thofma predicated correctly, we didn't really need to discuss this in triage as everyone just agreed that having subst === evaluate would be good to have.

[SoongNoonien]

The userfriendly syntax we discussed in triage would actually be something like f(x=3,y=4), so without the need for the semicolon. The semicolon is only necessary if one writes it like f(; :x => 3, y => 4). See this PR for reference.