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:  sageduplicate/invalid/wontfix 
Component:  algebra  Keywords:  FreeNilpotentLieAlgebra, LieAlgebra, nilpotent, free 
Cc:  ghehaka, 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) <ipythoninput58672234ea66b> in <module>() > 1 LieAlgebra(QQ, Integer(11), step=Integer(3), names='X', naming='linear') /opt/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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/sagemath8.5/local/lib/python2.7/sitepackages/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
 Cc ghehaka tscrim added
comment:2 Changed 7 weeks ago by
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 followups: ↓ 5 ↓ 7 Changed 7 weeks ago by
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
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
 Branch set to public/lie_elem_indexing27018
 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 themonomial_coefficients()
do the translation to theindex_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 wordbased comparisons all be changed to use the indexbased comparisons?
If they should behave the same, then is it the case that only graded_basis
has incorrect behavior?
New commits:
4e27c06  added _index attribute to LieGenerator

comment:6 Changed 5 weeks ago by
 Milestone changed from sage8.6 to sage8.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 sagepending or sagewishlist.
comment:7 in reply to: ↑ 3 Changed 5 weeks ago by
 Branch changed from public/lie_elem_indexing27018 to public/freenilp_lie_gens_fix27018
 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:
f086e53  trac #27018: bandaid fix for free nilpotent Lie algebras with many generators

comment:8 Changed 5 weeks ago by
 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
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 bandaid, and a very flimsy one at that. But having the test case helps.
comment:10 Changed 5 weeks ago by
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
 Branch public/freenilp_lie_gens_fix27018 deleted
 Commit f086e53e1404d0d0bcc63ca0385f3890061772fa deleted
 Dependencies set to #27069
 Milestone changed from sage8.7 to sageduplicate/invalid/wontfix
 Status changed from needs_info to needs_review
comment:12 Changed 2 weeks ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Something strange is going on because there is no such class
sage.algebras.lie_algebras.lie_algebra_element.Lie
. Further investigation is needed.