Is this a bug in the FreeAlgebra Class?

[Adam Mullins]

Hi, I create a free algebra like such:

R.<q1,q2,q3> = FreeAlgebra(Integers(2))

When I try to check if the constant polynomial 1 is in R, it returns false. But this should return true.

i.e. 1 in R returns false

It also returns false when I write the code

0 in R

Is this a bug?

[Simon King]

Hi!

I believe it is a bug. By default, "1 in R" defaults to "R(1)==1 is True
and doesn't raise an error, which is the case here.
sage: R.<x,y,z> = FreeAlgebra(Integers(2))
sage: R(1) == 1
True

The problem is that someone decided to override the default __contains__
method for CombinatorialFreeModule, so that only equality of parents is
tested (a very bad notion of containment, IMHO!).

If it is OK for you to only work with graded homogeneous elements, you
could use the letterplace implementation of free algebras:
sage: R.<x,y,z> = FreeAlgebra(Integers(2),
implementation='letterplace')
sage: 1 in R
True
but note that really only homogeneous elements can be created:
sage: 1+x
...
ArithmeticError: Can only add elements of the same weighted degree

Third solution *should* be to implement a free algebra as a path algebra.
It would have the advantage of allowing inhomogenous elements. But alas,
it inherits from CombinatorialFreeModule and thus provides the same bug.

I will open a trac ticket for it.

Best regards,
Simon

[Simon King]

Hi!

Am Mittwoch, 29. März 2017 14:14:28 UTC+2 schrieb Simon King:

I will open a trac ticket for it.

I opened https://trac.sagemath.org/ticket/22707. With the branch from there (that hasn't been tested yet, so, handle with care!), one has

sage: R.<x,y,z> = FreeAlgebra(Integers(2))

sage: 1 in R
True
sage: %timeit (x+y+z)*(x+y+z)
10000 loops, best of 3: 99.2 µs per loop

sage: R.<x,y,z> = FreeAlgebra(Integers(2), implementation='letterplace')
sage: 1 in R
True

sage: %timeit (x+y+z)*(x+y+z)
10000 loops, best of 3: 31.7 µs per loop

sage: R = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(Integers(2))
sage: R.inject_variables()
Defining e_1, x, y, z

sage: 1 in R
True

sage: %timeit (x+y+z)*(x+y+z)
100000 loops, best of 3: 4.5 µs per loop

So, if you care for the speed of arithmetic operations, you shouldn't use the current default implementation of FreeAlgebra. I guess changing the default should be another trac ticket.

Best regards,
Simon

[Adam Mullins]

Thank you so much for your speedy response and quick fix! I can't thank you enough!

[Adam Mullins]

Hi Simon, 

Shouldn't 0 in R return true as well?

Thank you

[Simon King]

Hi Adam,

On 2017-03-30, Adam Mullins <mullin...@gmail.com> wrote:
> Shouldn't 0 in R return true as well?

Does it not?? That should certainly work with the fix from
the ticket that I mentioned.

Best regards,
Simon

[Adam Mullins]

Can you explain how i run the updated version? I'm still a bit of a novice, and right now i'm currently running SageMath cloud. 

Again, I thank you for your help!