lquo/rquo (XFreeAlgebra)

[Kurt Pagani]

Either my understanding of lquo/rquo (Category XFreeAlgebra) is wrong or there is a bug in the implementation of these functions in XDistributedPolynomial (XDPOLY).  

p1:= 3*x*y*x*z -->  3 x y x z

lquo(p1,3*x*y) --> 9 x z (expected: x z) 

I think that by "left simplification" is meant mult by a left inverse/recip, similiar as in group theory, although there is no leftRecip of 3*x*y in XDPOLY, of course.  Am I off the track?

Details below:

-- Cat XFreeAlgebra (xpoly.spad, L28)

-- lquo  : (%, %) -> %
-- ++ \spad{lquo(x, y)} returns the left simplification of \spad{x} by \spad{y}.
--
-- https://github.com/fricas/fricas/blob/master/src/algebra/xpoly.spad
-- lines 400-404
--
--      lquo(p : %, q : %) : % ==
--         +/ [t.c * r  for t in q | (r := lquo(p, t.k)) ~= 0]
--
--       rquo(p : %, q : %) : % ==
--         +/ [r * t.c for t in q | (r := rquo(p, t.k)) ~= 0]



XDP:=XDPOLY(Symbol,Fraction Integer)
--
[x,y,z]:=[s::XDP for s in [x,y,z]@List Symbol]
--
p1:= 3*x*y*x*z -->  3 x y x z
--
lquo(p1,x*y) --> 3 x z
rquo(p1,x*z) --> 3 x y
-- however
lquo(p1,3*x*y) --> 9 x z (expected: x z)
rquo(p1,2*x*z) --> 6 x y (expected: (3/2) x y)
--
leftRecip(3)$XDP --> 1/3

)clear all
XDP:=XDPOLY(Symbol,Expression Integer)
[x,y,z]:=[s::XDP for s in [x,y,z]@List Symbol]
a:EXPR INT
p1:=a*x*y*x*z --> a x y x z
--
lquo(p1,x*y) --> a x z
rquo(p1,x*z) --> a x y
lquo(p1,a*x*y) --> a^2 x z
-- ...

[Ralf Hemmecke]

> p1:= 3*x*y*x*z --> 3 x y x z
> lquo(p1,3*x*y) --> 9 x z (expected: x z)

Obviously, the coefficients are not taken into account. Even worse, they
are multiplied.

The docs speaks about "simplification".

> -- Cat XFreeAlgebra (xpoly.spad, L28)
> -- lquo : (%, %) -> %
> -- ++ \spad{lquo(x, y)} returns the left simplification of \spad{x} by
> \spad{y}.

Now it is a question how "simplification" actually is defined. :-(

Kurt, now you have to do some detective work to find out where those
lquo and rquo are actually used. I hope nowhere in the library.

To fix it, one must take into account that the domain parameter R is
only of type Ring.

Ralf

[Kurt Pagani]

On Sunday, 6 April 2025 at 16:36:37 UTC+2 ra...@hemmecke.org wrote:

> p1:= 3*x*y*x*z --> 3 x y x z
> lquo(p1,3*x*y) --> 9 x z (expected: x z)

Obviously, the coefficients are not taken into account. Even worse, they
are multiplied.

It's comforting that you interpret this as an "oddity" too.

 

The docs speaks about "simplification".

> -- Cat XFreeAlgebra (xpoly.spad, L28)
> -- lquo : (%, %) -> %
> -- ++ \spad{lquo(x, y)} returns the left simplification of \spad{x} by
> \spad{y}.

Now it is a question how "simplification" actually is defined. :-(

Indeed, I would see it more as left/right cancellation (then the coefficients must be taken reciprocal of course, i.e. if possible).

 

Kurt, now you have to do some detective work to find out where those
lquo and rquo are actually used. I hope nowhere in the library.

Unfortunately in some other x*.spad files, but I believe there are each time new implementations ... to be checked.

 

To fix it, one must take into account that the domain parameter R is
only of type Ring.

That's a point. When I used "Integer" in the first place, recip(3) is useless anyway, although it would be nice to have (left or right) cancellation in this case as well.

I hope Waldek can save it :)

 

Ralf

[Waldek Hebisch]

On Sun, Apr 06, 2025 at 07:11:03AM -0700, Kurt Pagani wrote:
> Either my understanding of lquo/rquo (Category XFreeAlgebra) is wrong or
> there is a bug in the implementation of these functions in
> XDistributedPolynomial (XDPOLY).
>
> p1:= 3*x*y*x*z --> 3 x y x z
> lquo(p1,3*x*y) --> 9 x z (expected: x z)
>
> I think that by "left simplification" is meant mult by a left
> inverse/recip, similiar as in group theory, although there is no leftRecip
> of 3*x*y in XDPOLY, of course. Am I off the track?

Current definition of 'lquo' looks odd, I have noticed this some
time ago. OTOH there are some odd looking operations on XFreeAlgebra-s
which actually make a lot of sense. So, it requires some investigative
work to decide if this is a bug or an unfortunate name of operation
needed elsewhere.

--
Waldek Hebisch

[Kurt Pagani]

Thanks, yes, who knows. It seems that it's also used in xdfact, xdpolyf, whereas in xlpoly (e.g. LiePolynomial) are new ones, apparently in the same spirit, though.

 

I can use factor from XPFACT in the meantime ... which seems to work for my purpose.

(6) -> factor (3*x*y-3*x*z)$XPFACT(Symbol,EXPR INT)

   (6)  [- 3 x, - y + z]
               Type: List(XDistributedPolynomial(Symbol,Expression(Integer)))

 

--
Waldek Hebisch

[Waldek Hebisch]

A little update: this does not look like a bug, there are two different
implementations in 'xpoly.spad' and similar implementation in
'xlpoly.spad'. There are also similar implementations of 'rquo'.

I do not know why 'lquo' and 'rquo' are defined in this way. One
possible explanation could be that in Lie case there are multiple
possibilities for "base" words and maybe the definition tries do
do something for words expressed in different basis.

AFAICS strange definitions of 'lquo' and 'rquo' are not used by
other code, so in principle we could remove them the reduce
confusion.

--
Waldek Hebisch

[Waldek Hebisch]

On Sun, Apr 06, 2025 at 11:54:52AM -0700, Kurt Pagani wrote:
>
> I can use factor from XPFACT in the meantime ... which seems to work for my
> purpose.
> (6) -> factor (3*x*y-3*x*z)$XPFACT(Symbol,EXPR INT)
>
> (6) [- 3 x, - y + z]
> Type:
> List(XDistributedPolynomial(Symbol,Expression(Integer)))

'xpfact.spad' also contains 'ldivide':

ldivide : (XDP, XDP) -> d_rec
++ ldivide(a, b) returns [c, r] such that a = b*c + r, r is
++ is of minimal possible degree and homogeneous part of
++ of r of maximal degree contains no terms divisible from
++ left by leading term of b.

When a is divisible by b, then r is 0 and c gives left quotient.
In general c is analogous to quotient from euclidean division.

If quotient alone seems useful, we could export it. We could also
add right versions of related operatons.

--
Waldek Hebisch

[Kurt Pagani]

On Monday, 7 April 2025 at 16:06:42 UTC+2 Waldek Hebisch wrote:

On Sun, Apr 06, 2025 at 06:38:32PM +0200, Waldek Hebisch wrote:
> On Sun, Apr 06, 2025 at 07:11:03AM -0700, Kurt Pagani wrote:
> > Either my understanding of lquo/rquo (Category XFreeAlgebra) is wrong or
> > there is a bug in the implementation of these functions in
> > XDistributedPolynomial (XDPOLY).
> >
> > p1:= 3*x*y*x*z --> 3 x y x z
> > lquo(p1,3*x*y) --> 9 x z (expected: x z)
> >
> > I think that by "left simplification" is meant mult by a left
> > inverse/recip, similiar as in group theory, although there is no leftRecip
> > of 3*x*y in XDPOLY, of course. Am I off the track?
>
> Current definition of 'lquo' looks odd, I have noticed this some
> time ago. OTOH there are some odd looking operations on XFreeAlgebra-s
> which actually make a lot of sense. So, it requires some investigative
> work to decide if this is a bug or an unfortunate name of operation
> needed elsewhere.

A little update: this does not look like a bug, there are two different
implementations in 'xpoly.spad' and similar implementation in
'xlpoly.spad'. There are also similar implementations of 'rquo'.

I do not know why 'lquo' and 'rquo' are defined in this way. One
possible explanation could be that in Lie case there are multiple
possibilities for "base" words and maybe the definition tries do
do something for words expressed in different basis.

Ralf showed me another weird result:

%%% (15) -> lquo(x*y, x*y+x)

    (15)  1 + y

AFAICS strange definitions of 'lquo' and 'rquo' are not used by
other code, so in principle we could remove them the reduce
confusion.

Yes, as long as there is no reasonable definition I would advocate for removal.

 

--
Waldek Hebisch

[Kurt Pagani]

On Monday, 7 April 2025 at 16:14:17 UTC+2 Waldek Hebisch wrote:

On Sun, Apr 06, 2025 at 11:54:52AM -0700, Kurt Pagani wrote:
>
> I can use factor from XPFACT in the meantime ... which seems to work for my
> purpose.
> (6) -> factor (3*x*y-3*x*z)$XPFACT(Symbol,EXPR INT)
>
> (6) [- 3 x, - y + z]
> Type:
> List(XDistributedPolynomial(Symbol,Expression(Integer)))

'xpfact.spad' also contains 'ldivide':

ldivide : (XDP, XDP) -> d_rec
++ ldivide(a, b) returns [c, r] such that a = b*c + r, r is
++ is of minimal possible degree and homogeneous part of
++ of r of maximal degree contains no terms divisible from
++ left by leading term of b.

Ralf already suggested to me to use this and it works fine (I overlooked it, presumably because I didn't trust XPFACT either).

 

When a is divisible by b, then r is 0 and c gives left quotient.
In general c is analogous to quotient from euclidean division.

If quotient alone seems useful, we could export it. We could also
add right versions of related operatons.

Thanks, it's  reasonably defined, so adding a 'rdivide' would be desirable.

 

--
Waldek Hebisch

[Waldek Hebisch]

What about:

lquo : (%, %) -> %

++ \spad{lquo(x, y)} is a bilinear extention of \spad{lquo} from
++ words to \spad{%}.

--
Waldek Hebisch

[Kurt Pagani]

On Monday, 7 April 2025 at 19:05:58 UTC+2 Waldek Hebisch wrote:

On Mon, Apr 07, 2025 at 08:45:26AM -0700, Kurt Pagani wrote:
>
>
> On Monday, 7 April 2025 at 16:06:42 UTC+2 Waldek Hebisch wrote:
>
> On Sun, Apr 06, 2025 at 06:38:32PM +0200, Waldek Hebisch wrote:
> > On Sun, Apr 06, 2025 at 07:11:03AM -0700, Kurt Pagani wrote:
>

...

>
> Yes, as long as there is no reasonable definition I would advocate for
> removal.

What about:

lquo : (%, %) -> %
++ \spad{lquo(x, y)} is a bilinear extention of \spad{lquo} from
++ words to \spad{%}.

Well, the association of  'lquo'  to leftQuotient is quite strong, so another name might be more adequate.

I admit that I still can't see any meaning to this 'lquo/rquo' pair, but this carries no weight at all. I'm happy with the 'ldivide' by now.

https://en.wikipedia.org/wiki/Quotient_of_a_formal_language

 

--
Waldek Hebisch