OrderedAbelianMonoid vs OrderedAbelianMonoidSup

[Ralf Hemmecke]

Hello,

FriCAS does not have LaurentPolynomial. However, one can easily create
(a simple approximation of) them as

(1) -> PolynomialRing(Fraction(Integer),DirectProduct(3,Integer))

PolynomialRing(Fraction(Integer),DirectProduct(3,Integer)) is not a
valid type.

Ooops... why doesn't that work?

The reason is the line

https://github.com/hemmecke/fricas/blob/master-hemmecke/src/algebra/vector.spad#L295

if R has OrderedAbelianMonoidSup then OrderedAbelianMonoidSup

in DirectProductCategory. Although only OrderedAbelianMonoid would be
required for the above creation via PolynomialRing, it cannot yet be done.

Easiest way to solve that problem, is to add

if R has OrderedAbelianMonoid then OrderedAbelianMonoid

to DirectProductCategory.

Easy patch, but I do not propose it right now, because there is more and
I want to hear opinions.

DirectProduct(n,R) only exports OrderedAbelianMonoidSup, if R is of type
OrderedAbelianMonoidSup. Clearly, this sup function

http://fricas.github.io/api/OrderedAbelianMonoidSup.html#l-ordered-abelian-monoid-sup-sup

sup: (%, %) -> %
sup(x, y) returns the least element from which both x and y can be
subtracted.

is mainly used for reductions. But the specification is a bit vague.
Why doesn't have Integer such a function? Yes, there would be no "least"
element. But what does "least" in this specification mean anyway? Is it
the smallest with respect to the < order of the domain?
Then clearly, Integer cannot have this.

However, the idea of this function is to achieve "positiveness", i.e.,
if c = sup(a, b) then c-a>=0 and c-b>=0. Right? Wouldn't it make sense
to add this condition to the "sup" specification. Then also Integer and
Fraction Integer can be of type OrderedAbelianMonoidSup.

Furthermore, I don't see a good reason why OrderedDirectProduct,
HomogeneousDirectProduct and SplitHomogeneousDirectProduct require
their argument to be of type OrderedAbelianMonoidSup. Without the "Sup"
would be sufficient.

What is your opinion?

Ralf

=====================================================================


diff --git a/src/algebra/gdirprod.spad b/src/algebra/gdirprod.spad
index e6133360..c89b3209 100644
--- a/src/algebra/gdirprod.spad
+++ b/src/algebra/gdirprod.spad
@@ -83,7 +83,7 @@ OrderingFunctions(dim, S) : T == C where
++ \spadtype{GeneralDistributedMultivariatePolynomial}.

OrderedDirectProduct(dim : NonNegativeInteger,
- S : OrderedAbelianMonoidSup,
+ S : OrderedAbelianMonoid,
f : (Vector(S), Vector(S))->Boolean) : T
== C where
T == DirectProductCategory(dim, S)
@@ -108,7 +108,7 @@ OrderedDirectProduct(dim : NonNegativeInteger,

HomogeneousDirectProduct(dim, S) : T == C where
dim : NonNegativeInteger
- S : OrderedAbelianMonoidSup
+ S : OrderedAbelianMonoid

T == DirectProductCategory(dim, S)
C == DirectProduct(dim, S) add
@@ -147,7 +147,7 @@ HomogeneousDirectProduct(dim, S) : T == C where
SplitHomogeneousDirectProduct(dimtot, dim1, S) : T == C where
NNI ==> NonNegativeInteger
dim1, dimtot : NNI
- S : OrderedAbelianMonoidSup
+ S : OrderedAbelianMonoid

T == DirectProductCategory(dimtot, S)
C == DirectProduct(dimtot, S) add


diff --git a/src/algebra/vector.spad b/src/algebra/vector.spad
index 8c9c5aa7..dd9eb665 100644
--- a/src/algebra/vector.spad
+++ b/src/algebra/vector.spad
@@ -292,6 +292,7 @@ DirectProductCategory(dim : NonNegativeInteger, R :
Type) : Category ==
CommutativeRing
if R has unitsKnown then unitsKnown
if R has OrderedSet then OrderedSet
+ if R has OrderedAbelianMonoid then OrderedAbelianMonoid
if R has OrderedAbelianMonoidSup then OrderedAbelianMonoidSup
if R has Field then VectorSpace R
add

[Waldek Hebisch]

On Fri, Feb 14, 2020 at 04:43:12PM +0100, Ralf Hemmecke wrote:
> Hello,
>
> FriCAS does not have LaurentPolynomial.

One can view such domain as localization of polynomials. It
is one of reasons that I would like to have good support
for localizations, a lot of concrete examples could be
covered in that way.

> However, one can easily create
> (a simple approximation of) them as
>
> (1) -> PolynomialRing(Fraction(Integer),DirectProduct(3,Integer))
>
> PolynomialRing(Fraction(Integer),DirectProduct(3,Integer)) is not a
> valid type.
>
> Ooops... why doesn't that work?
>
> The reason is the line
>
> https://github.com/hemmecke/fricas/blob/master-hemmecke/src/algebra/vector.spad#L295
>
> if R has OrderedAbelianMonoidSup then OrderedAbelianMonoidSup
>
> in DirectProductCategory. Although only OrderedAbelianMonoid would be
> required for the above creation via PolynomialRing, it cannot yet be done.
>
> Easiest way to solve that problem, is to add
>
> if R has OrderedAbelianMonoid then OrderedAbelianMonoid
>
> to DirectProductCategory.
>
> Easy patch, but I do not propose it right now, because there is more and
> I want to hear opinions.

For different resons I am looking at similar issue. Namely, there is
redundancy between free monoid and polynomials. I would like to
make polynomials available for tensor products, but limit profileration
of spurious signatures. So I am thinking about introducing some intermediate
categories. Clearly, it is worth looking if DirectProductCategory
deserves some intermediate category.

> DirectProduct(n,R) only exports OrderedAbelianMonoidSup, if R is of type
> OrderedAbelianMonoidSup. Clearly, this sup function
>
> http://fricas.github.io/api/OrderedAbelianMonoidSup.html#l-ordered-abelian-monoid-sup-sup
>
> sup: (%, %) -> %
> sup(x, y) returns the least element from which both x and y can be
> subtracted.
>
> is mainly used for reductions. But the specification is a bit vague.
> Why doesn't have Integer such a function? Yes, there would be no "least"
> element. But what does "least" in this specification mean anyway? Is it
> the smallest with respect to the < order of the domain?
> Then clearly, Integer cannot have this.

My impression is that this is essenially 'gcd', but written in additive
terms (think of multiplicative monoid of a commutaive ring with 1 as
n abelian monoid). Defining it for integers is probably useless,
I would rather avoid requirng it when not necessary.

> However, the idea of this function is to achieve "positiveness", i.e.,
> if c = sup(a, b) then c-a>=0 and c-b>=0. Right? Wouldn't it make sense
> to add this condition to the "sup" specification. Then also Integer and
> Fraction Integer can be of type OrderedAbelianMonoidSup.
>
> Furthermore, I don't see a good reason why OrderedDirectProduct,
> HomogeneousDirectProduct and SplitHomogeneousDirectProduct require
> their argument to be of type OrderedAbelianMonoidSup. Without the "Sup"
> would be sufficient.

Yes, probably previously nobody was thinking about more general
applications.


--
Waldek Hebisch

[Kurt Pagani]

On 14.02.2020 17:24, Waldek Hebisch wrote:
> On Fri, Feb 14, 2020 at 04:43:12PM +0100, Ralf Hemmecke wrote:

>>
>> Easy patch, but I do not propose it right now, because there is more and
>> I want to hear opinions.
>
> For different resons I am looking at similar issue. Namely, there is
> redundancy between free monoid and polynomials. I would like to
> make polynomials available for tensor products, but limit profileration
> of spurious signatures. So I am thinking about introducing some intermediate
> categories. Clearly, it is worth looking if DirectProductCategory
> deserves some intermediate category.
>

I'm using FreeMonoid S also with non-ordered S, so I guess there is no
redundancy? Or do I overlook something? Actually there might be some redundancy
with XFreeAlgebra, XDistributedPolynomial and TensorProduct etc., but the latter
are quite useful.
Accidentally, I tested a domain TensorAlgebra a week ago
(http://fricas-wiki.math.uni.wroc.pl/SandBoxTensorAlgebra2?root=SandBox) based
on XDistributedPolynomial (saves a lot of work compared to implementing it by
FreeMonoid+FreeModule).

[Ralf Hemmecke]

On 2/14/20 5:24 PM, Waldek Hebisch wrote:
> On Fri, Feb 14, 2020 at 04:43:12PM +0100, Ralf Hemmecke wrote:
>> Hello,
>>
>> FriCAS does not have LaurentPolynomial.
>
> One can view such domain as localization of polynomials. It
> is one of reasons that I would like to have good support
> for localizations, a lot of concrete examples could be
> covered in that way.

In fact, I also thought about this, before I wrote my mail. In fact,

PolynomialRing(Fraction(Integer),DirectProduct(3,Integer))

does not allow to divide by variables. That is why I wrote "an
approximation of". However,

Localize(M : Module R, R : CommutativeRing)

basically forms fractions. That would not be needed in the case of
LaurentPolynomial.

Other than that, I agree, that we should have better support for local
structures.

BTW, I would like to change to order of parameters in Localize, i.e., R
should come first, because the "Module(R)" parameter depends on it and I
would like to search for dependencies from left to right.

The second issue with FriCAS' Localize is that one usually write M^(-1)R
with a multiplicative set M and a ring/module R. The multiplicative set
is not present as an explicit domain parameter, it's rather implicit as
all non-zero elements of the "CommutativeRing" parameter of Localize.

> For different resons I am looking at similar issue. Namely, there is
> redundancy between free monoid and polynomials. I would like to
> make polynomials available for tensor products, but limit profileration
> of spurious signatures. So I am thinking about introducing some intermediate
> categories. Clearly, it is worth looking if DirectProductCategory
> deserves some intermediate category.
>
>> DirectProduct(n,R) only exports OrderedAbelianMonoidSup, if R is of type
>> OrderedAbelianMonoidSup. Clearly, this sup function
>>
>> http://fricas.github.io/api/OrderedAbelianMonoidSup.html#l-ordered-abelian-monoid-sup-sup
>>
>> sup: (%, %) -> %
>> sup(x, y) returns the least element from which both x and y can be
>> subtracted.
>>
>> is mainly used for reductions. But the specification is a bit vague.
>> Why doesn't have Integer such a function? Yes, there would be no "least"
>> element. But what does "least" in this specification mean anyway? Is it
>> the smallest with respect to the < order of the domain?
>> Then clearly, Integer cannot have this.
>
> My impression is that this is essenially 'gcd', but written in additive
> terms (think of multiplicative monoid of a commutaive ring with 1 as
> n abelian monoid). Defining it for integers is probably useless,
> I would rather avoid requirng it when not necessary.

You probably meant lcm instead of gcd, but yes, that's what it's
probably supposed to be.

Yes, for Integer, it's probably uninteresting, but what about
DirectProduct(n, Integer) or DirectProduct(n, Fraction Integer)?
If it's available for Integer, then DirectProduct inherits sup via
conditional export in DirectProductCategory.

>> However, the idea of this function is to achieve "positiveness", i.e.,
>> if c = sup(a, b) then c-a>=0 and c-b>=0. Right? Wouldn't it make sense
>> to add this condition to the "sup" specification. Then also Integer and
>> Fraction Integer can be of type OrderedAbelianMonoidSup.

I don't insist on implementing OrderedAbelianMonoidSup for Integer, but
still I would like to add "if c = sup(a, b) then c-a>=0 and c-b>=0" to
the specification of sup, because "least" can only mean the smallest
wrt. < of the domain. But think about lex ordering or degrevlex ordering
of DirectProduct. Cannot there be two different elements depending on
whether the domain implements lex or degrevlex? And, for example, for
DirectProduct(n, Integer), it wouldn't be clear that sup(a,b)-a>=0 and
sup(a,b)-b>=0.

>> Furthermore, I don't see a good reason why OrderedDirectProduct,
>> HomogeneousDirectProduct and SplitHomogeneousDirectProduct require
>> their argument to be of type OrderedAbelianMonoidSup. Without the "Sup"
>> would be sufficient.
>
> Yes, probably previously nobody was thinking about more general
> applications.

Can I commit the patch, that I attached in my last mail? This
generalization would be enough for what I needed it for in the first
place, i.e., creating some pseudo LaurentPolynomial domain.

Ralf

[Waldek Hebisch]

On Fri, Feb 14, 2020 at 11:25:36PM +0100, Ralf Hemmecke wrote:
> On 2/14/20 5:24 PM, Waldek Hebisch wrote:
> > On Fri, Feb 14, 2020 at 04:43:12PM +0100, Ralf Hemmecke wrote:
> >> Hello,
> >>
> >> FriCAS does not have LaurentPolynomial.
> >
> > One can view such domain as localization of polynomials. It
> > is one of reasons that I would like to have good support
> > for localizations, a lot of concrete examples could be
> > covered in that way.
>
> In fact, I also thought about this, before I wrote my mail. In fact,
>
> PolynomialRing(Fraction(Integer),DirectProduct(3,Integer))
>
> does not allow to divide by variables. That is why I wrote "an
> approximation of".

Hmm, cosider:

vL := OrderedVariableList([a, b ,c])
fM := FreeModule(Integer, vL)
lP := PolynomialRing(Integer, fM)

vara := monomial(1, monomial(1, a)$fM)$lP
ivara := (1$lP exquo vara)::lP
vara*ivara

In what sense 'exquo' "does not allow to divide by variables"?
Note that you can not divide by arbitrary elements, so 'exquo'
is right operation for division.

> However,
>
> Localize(M : Module R, R : CommutativeRing)
>
> basically forms fractions. That would not be needed in the case of
> LaurentPolynomial.

Sure, PolynomialRing is probably more efficient. OTOH localization
should know more about ring, for example localization should
know that we got UniqueFactorizationDomain or GcdDomain.
With definition above

lP has GcdDomain

gives false and in general PolynomialRing has too limited
information to say differently.

> Other than that, I agree, that we should have better support for local
> structures.
>
> BTW, I would like to change to order of parameters in Localize, i.e., R
> should come first, because the "Module(R)" parameter depends on it and I
> would like to search for dependencies from left to right.
>
> The second issue with FriCAS' Localize is that one usually write M^(-1)R
> with a multiplicative set M and a ring/module R. The multiplicative set
> is not present as an explicit domain parameter, it's rather implicit as
> all non-zero elements of the "CommutativeRing" parameter of Localize.

Well, Localize is really limited. General approch would specify
multiplicative set via a function from R to Boolean. Representation
would be via fractions, but 'exquo' would look if numerator of dividend
is OK (by calling provided function).

> >> DirectProduct(n,R) only exports OrderedAbelianMonoidSup, if R is of type
> >> OrderedAbelianMonoidSup. Clearly, this sup function
> >>
> >> http://fricas.github.io/api/OrderedAbelianMonoidSup.html#l-ordered-abelian-monoid-sup-sup
> >>
> >> sup: (%, %) -> %
> >> sup(x, y) returns the least element from which both x and y can be
> >> subtracted.
> >>
> >> is mainly used for reductions. But the specification is a bit vague.
> >> Why doesn't have Integer such a function? Yes, there would be no "least"
> >> element. But what does "least" in this specification mean anyway? Is it
> >> the smallest with respect to the < order of the domain?
> >> Then clearly, Integer cannot have this.
> >
> > My impression is that this is essenially 'gcd', but written in additive
> > terms (think of multiplicative monoid of a commutaive ring with 1 as
> > n abelian monoid). Defining it for integers is probably useless,
> > I would rather avoid requirng it when not necessary.
>
> You probably meant lcm instead of gcd, but yes, that's what it's
> probably supposed to be.

Yes, using divisibility it is lcm.

>
> Yes, for Integer, it's probably uninteresting, but what about
> DirectProduct(n, Integer) or DirectProduct(n, Fraction Integer)?
> If it's available for Integer, then DirectProduct inherits sup via
> conditional export in DirectProductCategory.
>
> >> However, the idea of this function is to achieve "positiveness", i.e.,
> >> if c = sup(a, b) then c-a>=0 and c-b>=0. Right? Wouldn't it make sense
> >> to add this condition to the "sup" specification. Then also Integer and
> >> Fraction Integer can be of type OrderedAbelianMonoidSup.
>
> I don't insist on implementing OrderedAbelianMonoidSup for Integer, but
> still I would like to add "if c = sup(a, b) then c-a>=0 and c-b>=0" to
> the specification of sup, because "least" can only mean the smallest
> wrt. < of the domain.

No, documentation clearly say that they mean _partial_ pre-order
corresponding to divisibility. Now, since this is OrderedAbelianMonoid
linear order extends partial pre-order coming from divisibility,
but logically what counts is divisibility. In fact, if you insist
on having 'sup' for groups most natural definition is trivial one,
namely always getting identity element.

> But think about lex ordering or degrevlex ordering
> of DirectProduct. Cannot there be two different elements depending on
> whether the domain implements lex or degrevlex? And, for example, for
> DirectProduct(n, Integer), it wouldn't be clear that sup(a,b)-a>=0 and
> sup(a,b)-b>=0.
>
> >> Furthermore, I don't see a good reason why OrderedDirectProduct,
> >> HomogeneousDirectProduct and SplitHomogeneousDirectProduct require
> >> their argument to be of type OrderedAbelianMonoidSup. Without the "Sup"
> >> would be sufficient.
> >
> > Yes, probably previously nobody was thinking about more general
> > applications.
>
> Can I commit the patch, that I attached in my last mail? This
> generalization would be enough for what I needed it for in the first
> place, i.e., creating some pseudo LaurentPolynomial domain.

Yes, OK. As I wrote, rationalizing categories in the future we may
do it in slightly different way, but for now it is fine.

--
Waldek Hebisch

[Waldek Hebisch]

On Fri, Feb 14, 2020 at 05:57:15PM +0100, Kurt Pagani wrote:
> On 14.02.2020 17:24, Waldek Hebisch wrote:
> > On Fri, Feb 14, 2020 at 04:43:12PM +0100, Ralf Hemmecke wrote:
>
> >>
> >> Easy patch, but I do not propose it right now, because there is more and
> >> I want to hear opinions.
> >
> > For different resons I am looking at similar issue. Namely, there is
> > redundancy between free monoid and polynomials. I would like to
> > make polynomials available for tensor products, but limit profileration
> > of spurious signatures. So I am thinking about introducing some intermediate
> > categories. Clearly, it is worth looking if DirectProductCategory
> > deserves some intermediate category.
> >
> I'm using FreeMonoid S also with non-ordered S, so I guess there is no
> redundancy? Or do I overlook something? Actually there might be some redundancy
> with XFreeAlgebra, XDistributedPolynomial and TensorProduct etc., but the latter
> are quite useful.

Well, several signature in MonoidRing are redundant (introduced earlier).
And with proper intermediate catergories there will be more.

Note: I do not mean that signature is useless. What I mean is that
we have multiple defintions of exactly the same thing. Also,
signature may be conditional and conditions should not prevent
us from removing redundancy.

--
Waldek Hebisch

[Ralf Hemmecke]

>> PolynomialRing(Fraction(Integer),DirectProduct(3,Integer))
>>
>> does not allow to divide by variables. That is why I wrote "an
>> approximation of".
>
> Hmm, cosider:
>
> vL := OrderedVariableList([a, b ,c])
> fM := FreeModule(Integer, vL)
> lP := PolynomialRing(Integer, fM)
>
> vara := monomial(1, monomial(1, a)$fM)$lP
> ivara := (1$lP exquo vara)::lP
> vara*ivara
>
> In what sense 'exquo' "does not allow to divide by variables"?
> Note that you can not divide by arbitrary elements, so 'exquo'
> is right operation for division.

Oh, OK. Then PolynomialRing can perfectly be used for
LaurentPolynomials, however, I would like to have a signature

/: (%, S) -> %

where S is the multiplicative set in the S^{-1}R construction of a local
ring. In that sense I meant that I cannot divide by variables. The
multiplicative set is not known. PolynomialRing behaves like a
polynomial *ring* without knowing about its local nature.

What would be nice would be a "local category". Currently, we oly have
Localize as a domain.

>> However,
>>
>> Localize(M : Module R, R : CommutativeRing)
>>
>> basically forms fractions. That would not be needed in the case of
>> LaurentPolynomial.
>
> Sure, PolynomialRing is probably more efficient. OTOH localization
> should know more about ring, for example localization should
> know that we got UniqueFactorizationDomain or GcdDomain.
> With definition above
>
> lP has GcdDomain
>
> gives false and in general PolynomialRing has too limited
> information to say differently.

Well, I have nothing against a generic implementation of a localization
of a ring/module, but of course it should not be forbidden to use
PolynomialRing as a special implementation for a localization at the
variables. I don't see a big problem to do this, I'm only missing a nice
category for local structures.

> Well, Localize is really limited. General approch would specify
> multiplicative set via a function from R to Boolean.

Why? Why wouldn't you rather give the set itself? Maybe, we should first
collect the common cases, but I somehow feel, that it would be easy to
create one or several constructor that is given a number of generators
of the multiplicative set or considers just the multiplicative structure
of a ring, etc. Well... one would have to program some prototypes to see
what is better, but my feeling is somehow that with a member function as
you suggest above, division always requires a membership test.

>>>> However, the idea of this function is to achieve "positiveness", i.e.,
>>>> if c = sup(a, b) then c-a>=0 and c-b>=0. Right? Wouldn't it make sense
>>>> to add this condition to the "sup" specification. Then also Integer and
>>>> Fraction Integer can be of type OrderedAbelianMonoidSup.
>>
>> I don't insist on implementing OrderedAbelianMonoidSup for Integer, but
>> still I would like to add "if c = sup(a, b) then c-a>=0 and c-b>=0" to
>> the specification of sup, because "least" can only mean the smallest
>> wrt. < of the domain.
>
> No, documentation clearly say that they mean _partial_ pre-order
> corresponding to divisibility. Now, since this is OrderedAbelianMonoid
> linear order extends partial pre-order coming from divisibility,
> but logically what counts is divisibility. In fact, if you insist
> on having 'sup' for groups most natural definition is trivial one,
> namely always getting identity element.

Yes, but that loses the idea of "positiveness".
However, in a sense I agree with you, sup for group structures is
probably not useful enough to introduce such a signature.

>> Can I commit the patch, that I attached in my last mail? This
>> generalization would be enough for what I needed it for in the first
>> place, i.e., creating some pseudo LaurentPolynomial domain.
>
> Yes, OK. As I wrote, rationalizing categories in the future we may
> do it in slightly different way, but for now it is fine.

Thanks. Of course, I'm open to discussions and therefore did not simply
commit it in the first place.

Ralf

[Waldek Hebisch]

Ockham razor. To implement division ('exquo'), we need a
way to decide if arbitrary element of the ring is in the
multiplicative set. In principle with explicit S, we could
require that S has RetractableFrom R, but boolean predicate
is minimal thing.

> Maybe, we should first
> collect the common cases, but I somehow feel, that it would be easy to
> create one or several constructor that is given a number of generators
> of the multiplicative set or considers just the multiplicative structure
> of a ring, etc. Well... one would have to program some prototypes to see
> what is better, but my feeling is somehow that with a member function as
> you suggest above, division always requires a membership test.

Division in localization always require membership test, implicit
or explict. Thinking more about this I see that what we really
need is a test if pair (a, b) is equivalent to valid element
of localization. That is we may need to remove common factors
before membership test for denominator.

--
Waldek Hebisch

[Ralf Hemmecke]

> Division in localization always require membership test, implicit
> or explict. Thinking more about this I see that what we really
> need is a test if pair (a, b) is equivalent to valid element
> of localization. That is we may need to remove common factors
> before membership test for denominator.

Oh, right. In fact, in IntegerLocalizedAtPrime, I also keep the
respective possible denominators factored from the numerator. Maybe
that's not alway the most efficient way. However, you are right, in
general computation is difficult, only for Laurent polynomials with an
implementation as PolynomialRing(C, DirectProduct(n, Integer)) division
would be easy.

Or would you also allow (x+y)^2 / (x+y) ? For this case I would require
the user to call exquo instead of /. The signature of / should already
make it clear by what can be divided.

Ralf