Inconsistencies with FreeAlgebra

[ppurka]

This ticket is "inspired" by this ask.sagemath question.

1. First, there should be an easy way to get the variables out of an expression in FreeAlgebra. Compare with the output of polynomial ring.

sage: F.<x,y>=FreeAlgebra(ZZ)  
sage: g=4+3*x^7*y^10*x^13
sage: g.variables()            # <------------   Need this
sage: h=g._FreeAlgebraElement__monomial_coefficients # This is what we need to do currently
sage: h.items()[1][0]._element_list     # and do more post processing on the output.
[(0, 7), (1, 10), (0, 13)]

# Compare with polynomial ring
sage: F.<x,y> = PolynomialRing(ZZ)
sage: g=4+3*x^7*y^10*x^13
sage: g.variables()
(x, y)
sage: g=4+3*x^7
sage: g.variables()
(x,)

2. The element x<sup>7*y</sup>10*x^13 does not belong to the FreeAlgebra class once it is extracted from the expression. It belongs to FreeMonoid. I think the parent of it should be the same even after we extract it.

sage: F.<x,y>=FreeAlgebra(ZZ)  
sage: g=4+3*x^7*y^10*x^13
sage: h=g._FreeAlgebraElement__monomial_coefficients
sage: h
{1: 4, x^7*y^10*x^13: 3}
sage: hh = h.items()[1][0]; hh
x^7*y^10*x^13
sage: hh.parent()
Free monoid on 2 generators (x, y)

CC: @nthiery

Component: algebra

Author: Travis Scrimshaw

Branch/Commit: 0f9bf9d

Reviewer: Punarbasu Purkayastha

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

[99bed503-835f-49d4-8291-da3c802e501a]

comment:1

In regards to my question on ask.sagemath, what I would have really liked was if elements supported indexing. So for example, g[0] should return 4. g[1] should return 3x⁷y10x^13 and then g[1][0] should return 3 i guess, g[1][1] should return x^7 and so on. After that, it would be nice to have a way to iterate over 4+3x^7y10x^13. Maybe we would need len() for that? Has there ever been any talk about implementing something like this?

[ppurka]

comment:2

I think this kind of indexing has never been discussed or implemented. There could be several reasons, one of the foremost being that the order in which you enter the expression is not preserved.

sage: F.<x,y>=FreeAlgebra(ZZ)
sage: g = x^5 * y^4 + 3
sage: g
3 + x^5*y^4

[0f82a673-411f-43c9-9998-4108d32e3a4e]

comment:3

elements support iteration, but not indexing, which is appropriate because as ppurka said there is no real ordering on the expressions.

sage: F.<x,y> = FreeAlgebra(ZZ)
sage: g = x^5 * y^4 + 3
sage: for m in g:
....:     print m
....: 
(3, 1)
(1, x^5*y^4)
sage: list(g)
[(3, 1), (1, x^5*y^4)]

all works fine.

[ppurka]

comment:4

Marking as invalid.

[ppurka]

comment:5

Oh. Sorry. I forgot that the original questions were very different from the discussion that ensued.

[nbruin]

comment:6

Regarding point 1: Accessing underscore methods is bound to make your life hard: the underscore marks that these are methods/attributes for internal use. The interface is via iteration and using that one can easily accomplish the task:

sage: tuple({n[0] for m in g for n in m[1]})
(y, x)

(i.e., iterate over the terms making up the algebra element, extract the monomial and iterate over that to extract the variables that occur in them).

Whether this needs to be wrapped in a method: The operation isn't very natural: The parent will naturally tell you which variables CAN occur in in algebra elements. Are the ones that don't have all those variables really so special that there needs to be a method to query about that?

For polynomials, the same argument holds, but there it was probably added because some beginners will tend to think of polynomials in terms of SR, where the variables occurring is really a property of the expression and not really of SR.

Concerning point 2: The nested operation above shows why it's natural to return monomials NOT as elements of the algebra: iterating over an algebra element gives the pairs, iterating over a monomial gives variable-exponent pairs. The separation actually provides easier access to the underlying data.

For normal polynomial rings this is probably avoided for efficiency reasons, but you quickly notice that it's a little inconvenient: you end up testing quite a bit whether given polynomials are actually monomials, where doing this via a type check would often in principle be quite doable.

[ppurka]

comment:7

1. The iteration operation was not clear to me at all, and it definitely not possible for beginner to figure it out. By a beginner, I don't mean a beginner to programming - more like a beginner to Sage, or this specific implementation in Sage. I don't find this kind of iteration documented anywhere, even for polynomial rings - maybe it is hidden somewhere. Secondly, the parent FreeAlgebra does have variable_name and variable_names methods. Both are undocumented. The first one, for some weird reason, returns only the first variable as a string. The second one returns all the variables as strings. This is quite useless for programming purposes. It is maybe ok for interactive use, where one can look at this output and then decide to run the F.inject_variables() once one is sure it won't clobber existing variables.

2. Checking for monomials can be easily done using the list comprehension you provided. Or, even better for efficiency reasons - a for loop with an enumerate that returns False as soon as it encounters a second tuple.

def is_monomial(self):
    for i,_ in enumerate(self):
        if i == 1:
             return False
    return True

[tscrim]

Branch: public/algebras/fix_free_algebras-14848

[tscrim]

comment:8

I've made FreeAlgebra inherit from CombinatorialFreeModule; it was close enough to it to begin with and is something Nicolas and I have wanted to do. I've had to hack together a combination of CombinatorialFreeModuleElement and AlgebraElement to pass a doctest in matrix0.pyx where FreeAlgebra is used as a base ring (this inspired #15947). So iterating through an element of FreeAlgera gives index,coeff now (finally consistency! this had bugged me a few times). I've also added a variables method as I don't think it does much harm to have it and support returns the monomials that occur.

Regarding point 2, you can now use the monomial_coefficients() to iterate over pairs (monomial in free algebra, coefficient)] (well...TBH actually it's a dict, so you need an additional items()). Also I agree with Nils' opinion.

---

New commits:

771ac4c	Converted FreeAlgebra to inherit from CombinatrialFreeModule.
a2d1f8d	Fixes for coercion maps.
5045cc5	pyflakes cleanup of free_algebra.py.
b52e779	Merge branch 'develop' into public/algebras/fix_free_algebras-14848
c250702	(Hack) Fix for making FreeAlgebraElement work as a base ring for matrices.
0de106a	Added variables() method to free module elements.

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Commit: 0de106a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0de106a to 23d8c7b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

23d8c7b

Merge branch 'develop' into public/algebras/fix_free_algebras-14848

[nthiery]

comment:10

Replying to @tscrim:

I've made FreeAlgebra inherit from CombinatorialFreeModule; it was close enough to it to begin with and is something Nicolas and I have wanted to do.

Yeah!

I've had to hack together a combination of CombinatorialFreeModuleElement and AlgebraElement to pass a doctest in matrix0.pyx where FreeAlgebra is used as a base ring (this inspired #15947).

Any chance to get rid of the use of AlgebraElement there altogether?

Cheers, Nicolas

[tscrim]

comment:11

Replying to @nthiery:

Any chance to get rid of the use of AlgebraElement there altogether?

Alas, no. We'd have to do something with _rmul_ and _lmul_ of the matrices without introducing a speed regression, which IDK what the best way to do it will be. The alternative would be to remove/change those failing doctests. I've posted an idea I've just had to #15947.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

51b2e5f	Merge branch 'develop' into public/algebras/fix_free_algebras-14848
9f49f2f	Merge branch 'develop' into public/algebras/fix_free_algebras-14848

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 23d8c7b to 9f49f2f

[ppurka]

comment:13

I got one error in doctests:

sage -t --long src/sage/algebras/algebra.py
**********************************************************************
File "src/sage/algebras/algebra.py", line 29, in sage.algebras.algebra.is_Algebra
Failed example:
    is_Algebra(R)
Expected:
    True
Got:
    False
**********************************************************************

Point 1. in description is fixed, but I guess it is harder to fix point 2. So, other than this doctest, the patch looks OK to me.

[ppurka]

Work Issues: fix doctests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

74734db

Fixed failing doctests.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9f49f2f to 74734db

[tscrim]

comment:15

Fixed (and also some doctests in categories/rings.py that I found).

[ppurka]

comment:16

I am surprised. I have two questions

1. Why does this patch affect categories/rings.py?
2. Can you be more specific with Exception? In which case did you run into the Exception? AttributeError? Can you include it in a doctest?

[tscrim]

comment:17

Replying to @ppurka:

I am surprised. I have two questions

1. Why does this patch affect categories/rings.py?

It's just a doctest and it's because I swapped the order when iterating over the objects (i.e., it became index, coefficient whereas before it was coefficient, index).

2. Can you be more specific with Exception? In which case did you run into the Exception? AttributeError? Can you include it in a doctest?

There's a doctest in categories/commutative_ring_ideals.py which tries to pass off (incorrectly) Partitions(4) as a commutative ring, but the is_Algebra fails with a TypeError. However, it could also fail with other errors and I didn't want the is_Algebra to error out for similar reasoning to a __contains__() check. We can add additional doctests to is_Algebra but I think we're already covered by other parts of the library.

[tscrim]

Changed work issues from fix doctests to none

[ppurka]

comment:19

Ok. Then. Setting it to positive review.

[ppurka]

Reviewer: Punarbasu Purkayastha

[tscrim]

comment:20

Thank you for doing the review.

[vbraun]

comment:21

Lots of doctests failures

[tscrim]

comment:22

Can you list which files?

[vbraun]

comment:23

Sorry, too late. But there was enough breakage that you should run the whole testsuite.

[tscrim]

comment:24

This is mostly for my records. Here's the list I got that were "bad" errors:

sage -t rings/quotient_ring.py  # 8 doctests failed
sage -t rings/ring.pyx  # 3 doctests failed
sage -t structure/sage_object.pyx  # 1 doctest failed
sage -t structure/factorization.py  # 1 doctest failed

The pickling one is going to be the most fun to deal with.

These were from dictionary orderings (likely from hash values):

sage -t libs/singular/groebner_strategy.pyx  # 2 doctests failed
sage -t rings/polynomial/plural.pyx  # 5 doctests failed
sage -t rings/polynomial/multi_polynomial_ideal.py  # 13 doctests failed

One I don't think is related:

sage -t doctest/test.py  # 1 doctest failed

These seem to be maxima related (i.e. local to my setup so I'm going to ignore them):

sage -t tests/french_book/integration_doctest.py  # 1 doctest failed
sage -t calculus/desolvers.py  # 8 doctests failed
sage -t /home/travis/sage/src/doc/en/prep/Quickstarts/Differential-Equations.rst  # 2 doctests failed
sage -t /home/travis/sage/src/doc/en/constructions/calculus.rst  # 4 doctests failed

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 74734db to 0f9bf9d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9899a9c	Fixing doctests in quotient_ring.py and ring.pyx.
073b577	Fixed dict ordering doctests.
0f9bf9d	Fixed remaining doctests.

[tscrim]

comment:26

Volker, double-check that I got them all please.

[vbraun]

Changed branch from public/algebras/fix_free_algebras-14848 to 0f9bf9d