Opened 9 years ago

Closed 8 years ago

# Inconsistencies with FreeAlgebra

Reported by: Owned by: ppurka AlexGhitza major sage-6.2 algebra nthiery Travis Scrimshaw Punarbasu Purkayastha N/A 0f9bf9d 0f9bf9dbdd714429fd290f8c42811e143ca5d70e

### Description

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^7*y^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)
```

### comment:1 Changed 9 years ago by broken_symlink

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 3*x7*y10*x13 and then g[1][0] should return 3 i guess, g[1][1] should return x7 and so on. After that, it would be nice to have a way to iterate over 4+3*x7*y10*x13. Maybe we would need len() for that? Has there ever been any talk about implementing something like this?

### comment:2 Changed 9 years ago by ppurka

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
```

### comment:3 Changed 9 years ago by sam

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.

Last edited 9 years ago by sam (previous) (diff)

### comment:4 Changed 9 years ago by ppurka

• Milestone changed from sage-5.13 to sage-duplicate/invalid/wontfix
• Status changed from new to needs_review

Marking as invalid.

### comment:5 Changed 9 years ago by ppurka

• Milestone sage-duplicate/invalid/wontfix deleted
• Status changed from needs_review to needs_work

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

### comment:6 Changed 9 years ago by nbruin

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.

### comment:7 Changed 9 years ago by ppurka

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.
1. 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
```

### comment:8 follow-up: ↓ 10 Changed 8 years ago by tscrim

• Authors set to Travis Scrimshaw
• Branch set to public/algebras/fix_free_algebras-14848
• Commit set to 0de106a5831e0a06e9f8f050f35b15d2d3494981
• Milestone set to sage-6.2
• Status changed from needs_work to needs_review

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.`

### comment:9 Changed 8 years ago by git

• Commit changed from 0de106a5831e0a06e9f8f050f35b15d2d3494981 to 23d8c7b0b0204d3b93e67969bfc7f4dccaeb5be6

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

 ​23d8c7b `Merge branch 'develop' into public/algebras/fix_free_algebras-14848`

### comment:10 in reply to: ↑ 8 ; follow-up: ↓ 11 Changed 8 years ago by nthiery

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

### comment:11 in reply to: ↑ 10 Changed 8 years ago by tscrim

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.

### comment:12 Changed 8 years ago by git

• Commit changed from 23d8c7b0b0204d3b93e67969bfc7f4dccaeb5be6 to 9f49f2f52c1125c8fd32f79a0f25f0032bd6ead3

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`

### comment:13 Changed 8 years ago by ppurka

• Status changed from needs_review to needs_work
• Work issues set to fix doctests

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.

### comment:14 Changed 8 years ago by git

• Commit changed from 9f49f2f52c1125c8fd32f79a0f25f0032bd6ead3 to 74734db11fe788440775741de7519e9f2b7f7956

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

 ​74734db `Fixed failing doctests.`

### comment:15 Changed 8 years ago by tscrim

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

### comment:16 follow-up: ↓ 17 Changed 8 years ago by ppurka

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?

### comment:17 in reply to: ↑ 16 ; follow-up: ↓ 19 Changed 8 years ago by tscrim

• Status changed from needs_work to needs_review

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).

1. 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.

### comment:18 Changed 8 years ago by tscrim

• Work issues fix doctests deleted

### comment:19 in reply to: ↑ 17 Changed 8 years ago by ppurka

• Reviewers set to Punarbasu Purkayastha
• Status changed from needs_review to positive_review

Ok. Then. Setting it to positive review.

### comment:20 Changed 8 years ago by tscrim

Thank you for doing the review.

### comment:21 Changed 8 years ago by vbraun

• Status changed from positive_review to needs_work

Lots of doctests failures

### comment:22 Changed 8 years ago by tscrim

Can you list which files?

### comment:23 Changed 8 years ago by vbraun

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

### comment:24 Changed 8 years ago by tscrim

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
```

### comment:25 Changed 8 years ago by git

• Commit changed from 74734db11fe788440775741de7519e9f2b7f7956 to 0f9bf9dbdd714429fd290f8c42811e143ca5d70e

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.`

### comment:26 Changed 8 years ago by tscrim

• Status changed from needs_work to positive_review

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

### comment:27 Changed 8 years ago by vbraun

• Branch changed from public/algebras/fix_free_algebras-14848 to 0f9bf9dbdd714429fd290f8c42811e143ca5d70e
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.