Opened 7 weeks ago

Last modified 2 weeks ago

#27018 positive_review defect

Cannot construct FreeNilpotentLieAlgebra of step > 2 with > 10 generators

Reported by: rburing Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: algebra Keywords: FreeNilpotentLieAlgebra, LieAlgebra, nilpotent, free
Cc: gh-ehaka, tscrim Merged in:
Authors: Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #27069 Stopgaps:

Description

As reported on Ask SageMath, this works:

LieAlgebra(QQ, 10, step=3, names='X', naming='linear')

and this works:

LieAlgebra(QQ, 11, step=2, names='X', naming='linear')

but this doesn't work:

LieAlgebra(QQ, 11, step=3, names='X', naming='linear')

The traceback is as follows:

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-5-8672234ea66b> in <module>()
----> 1 LieAlgebra(QQ, Integer(11), step=Integer(3), names='X', naming='linear')

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1701)()
    328         """
    329         if cls.classcall is not None:
--> 330             return cls.classcall(cls, *args, **kwds)
    331         else:
    332             # Fast version of type.__call__(cls, *args, **kwds)

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/algebras/lie_algebras/lie_algebra.py in __classcall_private__(cls, R, arg0, arg1, names, index_set, abelian, nilpotent, category, **kwds)
    439                 from sage.algebras.lie_algebras.nilpotent_lie_algebra import FreeNilpotentLieAlgebra
    440                 del kwds["step"]
--> 441                 return FreeNilpotentLieAlgebra(R, arg1, step, names=names, **kwds)
    442             elif nilpotent:
    443                 raise ValueError("free nilpotent Lie algebras must have a"

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1701)()
    328         """
    329         if cls.classcall is not None:
--> 330             return cls.classcall(cls, *args, **kwds)
    331         else:
    332             # Fast version of type.__call__(cls, *args, **kwds)

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/algebras/lie_algebras/nilpotent_lie_algebra.py in __classcall_private__(cls, R, r, s, names, naming, category, **kwds)
    325         return super(FreeNilpotentLieAlgebra, cls).__classcall__(
    326             cls, R,r, s, names=tuple(names), naming=naming,
--> 327             category=category, **kwds)
    328
    329     def __init__(self, R, r, s, names, naming, category, **kwds):

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6068)()
   1003                 return self.cache[k]
   1004         except KeyError:
-> 1005             w = self.f(*args, **kwds)
   1006             self.cache[k] = w
   1007             return w

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/structure/unique_representation.py in __classcall__(cls, *args, **options)
   1025             True
   1026         """
-> 1027         instance = typecall(cls, *args, **options)
   1028         assert isinstance( instance, cls )
   1029         if instance.__class__.__reduce__ == CachedRepresentation.__reduce__:

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:2151)()
    495             TypeError: Argument 'cls' has incorrect type (expected type, got classobj)
    496     """
--> 497     return (<PyTypeObject*>type).tp_call(cls, args, kwds)
    498
    499 # Class for timing::

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/algebras/lie_algebras/nilpotent_lie_algebra.py in __init__(self, R, r, s, names, naming, category, **kwds)
    398                     for X_ind, X in basis_by_deg[dx]:
    399                         for Y_ind, Y in basis_by_deg[dy]:
--> 400                             Z = L[X, Y]
    401                             if not Z.is_zero():
    402                                 s_coeff[(X_ind, Y_ind)] = {W_ind: Z[W.leading_support()]

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/algebras/lie_algebras/lie_algebra.py in __getitem__(self, x)
    573                 return x[1].ideal(x[0])
    574             # Otherwise it is the bracket of two elements
--> 575             return self(x[0])._bracket_(self(x[1]))
    576         return super(LieAlgebra, self).__getitem__(x)
    577

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/algebras/lie_algebras/lie_algebra_element.pyx in sage.algebras.lie_algebras.lie_algebra_element.FreeLieAlgebraElement._bracket_ (build/cythonized/sage/algebras/lie_algebras/lie_algebra_element.c:18483)()
   1452                     a, b = mr, ml
   1453                     cr = -cr
-> 1454                 for b_elt, coeff in self.parent()._rewrite_bracket(a, b).iteritems():
   1455                     d[b_elt] = d.get(b_elt, zero) + cl * cr * coeff
   1456                     if d[b_elt] == zero:

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10324)()
   1950                 return cache[k]
   1951         except KeyError:
-> 1952             w = self._instance_call(*args, **kwds)
   1953             cache[k] = w
   1954             return w

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller._instance_call (build/cythonized/sage/misc/cachefunc.c:9809)()
   1826             True
   1827         """
-> 1828         return self.f(self._instance, *args, **kwds)
   1829
   1830     cdef fix_args_kwds(self, tuple args, dict kwds):

/opt/sagemath-8.5/local/lib/python2.7/site-packages/sage/algebras/lie_algebras/free_lie_algebra.py in _rewrite_bracket(self, l, r)
    690             # For a similar reason, we have b >= c.
    691             # Compute the left summand
--> 692             for m, inner_coeff in iteritems(self._rewrite_bracket(l._right, r)):
    693                 if l._left == m:
    694                     continue

AttributeError: 'sage.algebras.lie_algebras.lie_algebra_element.Lie' object has no attribute '_right'

Change History (12)

comment:1 Changed 7 weeks ago by tscrim

  • Cc gh-ehaka tscrim added

Something strange is going on because there is no such class sage.algebras.lie_algebras.lie_algebra_element.Lie. Further investigation is needed.

comment:2 Changed 7 weeks ago by gh-ehaka

Staring at the construction through the debugger, I can recreate the problem more precisely with the following:

sage: L = LieAlgebra(QQ, ['F%d' % k for k in range(11)]).Lyndon()
sage: L[L.graded_basis(1)[0],L.graded_basis(2)[26]]
Traceback (most recent call last)
...
AttributeError: 'sage.algebras.lie_algebras.lie_algebra_element.Lie' object has no attribute '_right'

The problem seems like it may arise from a mismatch between what the graded basis outputs vs. what the free Lie algebra expects it elements to be like.

sage: L.graded_basis(1)[0]
F0
sage: X=L.graded_basis(2)[26]; X
[F2, F10]
sage: Y=L[L.graded_basis(1)[2],L.graded_basis(1)[10]]; Y
-[F10, F2]
sage: X==Y
False

I will try to figure out more.

comment:3 follow-ups: Changed 7 weeks ago by tscrim

That is very helpful. So I was thinking it was because F10 is not sorted by the integer 10 but by the string '10'. Thus, we have

sage: sorted(L.graded_basis(1))
[F0, F1, F10, F2, F3, F4, F5, F6, F7, F8, F9]

So this is an issue that I was hoping we did not have to address. In other words, the computation does not depend on the generators, i.e., these would do the same computations:

sage: Lxyz = LieAlgebra(QQ, ['x','y','z']).Lyndon()
sage: Lzxy = LieAlgebra(QQ, ['z','x','y']).Lyndon()
sage: Lxyz.graded_basis(2)
([x, y], [x, z], [y, z])
sage: Lzxy.graded_basis(2)
([z, x], [z, y], [x, y])
sage: x,y,z = Lxyz.gens()
sage: a,b,c = Lzxy.gens()
sage: a,b,c
(z, x, y)
sage: b.bracket(a)
[x, z]
sage: x.bracket(z)
[x, z]
sage: Lzxy._is_basis_element(b.leading_support(),a.leading_support())
True
sage: Lzxy._is_basis_element(a.leading_support(),b.leading_support())
False

So what we have to do is during the comparison of the Lie bracketing (most likely in _bracket_ and maybe _rewrite_bracket) is look up the index within the generators. Actually, a little more invasive but will likely make the code more maintainable is have the LieGenerator just keep track of the index of the generator and then have the monomial_coefficients() do the translation to the index_set. Although that might be better long term, but just tweaking the comparison I mentioned above would be the quick fix. What would you like to do?

comment:4 Changed 7 weeks ago by gh-ehaka

Keeping track of the index sounds perhaps more reasonable, considering that bracketing is one of the primary operations of Lie algebra elements. Although I don't have that clear of an understanding of the internals of the elements, so take my opinion with a grain of salt :)

If you want to do the fix you're more than welcome. As I said, I am not quite clear about the internals and am a bit worried about breaking things. Nonetheless I can also do a fix and you can tell me if something should be corrected if that is easier.

comment:5 in reply to: ↑ 3 Changed 7 weeks ago by gh-ehaka

  • Branch set to public/lie_elem_indexing-27018
  • Commit set to 4e27c06abf6bfc538f3a21394f2ce86dd4fc26b3

Replying to tscrim:

Actually, a little more invasive but will likely make the code more maintainable is have the LieGenerator just keep track of the index of the generator and then have the monomial_coefficients() do the translation to the index_set.

I'm afraid I don't understand what you mean by this. Namely, I don't understand at which point monomial_coefficients() comes into play, since FreeLieAlgebra.Lyndon._is_basis_element only uses the word representation of the elements.

I started modifying the ordering behavior but ran into some problems. I added an _index attribute to LieGenerator in the commits and changed LieGenerator.__richcmp__ to order by indices instead of name. I did not change comparisons in LyndonBracket.__richcmp__ or _is_basis_element yet, as I am not in fact sure what should be the desired behavior. Hence the current commit is still very much broken (a lot of tests fail) due to inconsistent ordering behavior.

What should be the desired behavior? Was the idea that Lxyz and Lzxy should or should not behave the same?

If they should behave differently, then should all the word-based comparisons all be changed to use the index-based comparisons?

If they should behave the same, then is it the case that only graded_basis has incorrect behavior?


New commits:

4e27c06added _index attribute to LieGenerator

comment:6 Changed 5 weeks ago by embray

  • Milestone changed from sage-8.6 to sage-8.7

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

comment:7 in reply to: ↑ 3 Changed 5 weeks ago by gh-ehaka

  • Branch changed from public/lie_elem_indexing-27018 to public/freenilp_lie_gens_fix-27018
  • Commit changed from 4e27c06abf6bfc538f3a21394f2ce86dd4fc26b3 to f086e53e1404d0d0bcc63ca0385f3890061772fa
  • Status changed from new to needs_review

Not knowing how to fix the underlying issue at the moment, I wrote up a bandaid fix for the part that concerns the free nilpotent Lie algebras, since the traceback caused by simply inputting the wrong numbers into a constructor is not very helpful.

I opened a new ticket #27069 to address the underlying issue.


New commits:

f086e53trac #27018: bandaid fix for free nilpotent Lie algebras with many generators

comment:8 Changed 5 weeks ago by embray

  • Status changed from needs_review to needs_info

I don't understand what this is supposed to be fixing:

@@ -348,7 +355,7 @@ class FreeNilpotentLieAlgebra(NilpotentLieAlgebra_dense):
         # free Lie algebra, and store the corresponding elements in a dict
         from sage.algebras.lie_algebras.lie_algebra import LieAlgebra
 
-        free_gen_names = ['F%d' % k for k in range(r)]
+        free_gen_names = sorted('F%d' % k for k in range(r))

Originally it was just generating the sequence 'F0', 'F1', 'F2', ... 'F<r>'. The only difference here is that if r >= 10 you'll get something like 'F0', 'F1', 'F10', 'F2', ...

comment:9 Changed 5 weeks ago by embray

Sorry, I actually read the rest of the discussion and now I understand how you came to this solution. But like you said it's just a band-aid, and a very flimsy one at that. But having the test case helps.

comment:10 Changed 5 weeks ago by gh-ehaka

The motivation for the bandaid fix was mainly that the free Lie algebra computations are only used as an auxiliary tool in the initialization of the FreeNilpotentLieAlgebra object. Since it was not clear to me what is the desired behavior in the free Lie algebra setting, it could be argued that this bug is caused by incorrect usage of the FreeLieAlgebra structure inside FreeNilpotentLieAlgebra.__init__.

This is why I considered splitting the underlying issue from this ticket, in order to at least avoid the confusing traceback caused by a call of a simple constructor LieAlgebra(QQ, 11, step=3) while the underlying issue is being figured out.

comment:11 Changed 4 weeks ago by tscrim

  • Branch public/freenilp_lie_gens_fix-27018 deleted
  • Commit f086e53e1404d0d0bcc63ca0385f3890061772fa deleted
  • Dependencies set to #27069
  • Milestone changed from sage-8.7 to sage-duplicate/invalid/wontfix
  • Status changed from needs_info to needs_review

Sorry for taking so long to get to this. I figured it was easier to fix the problem on #27069 instead of the temporary patch here. So please review #27069, and then we can close this one.

comment:12 Changed 2 weeks ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review
Note: See TracTickets for help on using tickets.