Sage: Ticket #27018: Cannot construct FreeNilpotentLieAlgebra of step > 2 with > 10 generators
https://trac.sagemath.org/ticket/27018
<p>
As <a class="ext-link" href="https://ask.sagemath.org/question/44619/free-nilpotent-lie-algebra-of-step-3-with-11-generators/"><span class="icon"></span>reported on Ask SageMath</a>, this works:
</p>
<pre class="wiki">LieAlgebra(QQ, 10, step=3, names='X', naming='linear')
</pre><p>
and this works:
</p>
<pre class="wiki">LieAlgebra(QQ, 11, step=2, names='X', naming='linear')
</pre><p>
but this doesn't work:
</p>
<pre class="wiki">LieAlgebra(QQ, 11, step=3, names='X', naming='linear')
</pre><p>
The traceback is as follows:
</p>
<pre class="wiki">---------------------------------------------------------------------------
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'
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/27018
Trac 1.1.6tscrimFri, 04 Jan 2019 20:34:52 GMTcc set
https://trac.sagemath.org/ticket/27018#comment:1
https://trac.sagemath.org/ticket/27018#comment:1
<ul>
<li><strong>cc</strong>
<em>gh-ehaka</em> <em>tscrim</em> added
</li>
</ul>
<p>
Something strange is going on because there is no such class <code>sage.algebras.lie_algebras.lie_algebra_element.Lie</code>. Further investigation is needed.
</p>
Ticketgh-ehakaFri, 04 Jan 2019 23:09:26 GMT
https://trac.sagemath.org/ticket/27018#comment:2
https://trac.sagemath.org/ticket/27018#comment:2
<p>
Staring at the construction through the debugger, I can recreate the problem more precisely with the following:
</p>
<pre class="wiki">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'
</pre><p>
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.
</p>
<pre class="wiki">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
</pre><p>
I will try to figure out more.
</p>
TickettscrimSat, 05 Jan 2019 05:34:02 GMT
https://trac.sagemath.org/ticket/27018#comment:3
https://trac.sagemath.org/ticket/27018#comment:3
<p>
That is very helpful. So I was thinking it was because <code>F10</code> is not sorted by the integer <code>10</code> but by the string <code>'10'</code>. Thus, we have
</p>
<pre class="wiki">sage: sorted(L.graded_basis(1))
[F0, F1, F10, F2, F3, F4, F5, F6, F7, F8, F9]
</pre><p>
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:
</p>
<pre class="wiki">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
</pre><p>
So what we have to do is during the comparison of the Lie bracketing (most likely in <code>_bracket_</code> and maybe <code>_rewrite_bracket</code>) is look up the index within the generators. Actually, a little more invasive but will likely make the code more maintainable is have the <code>LieGenerator</code> just keep track of the index of the generator and then have the <code>monomial_coefficients()</code> do the translation to the <code>index_set</code>. 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?
</p>
Ticketgh-ehakaSat, 05 Jan 2019 07:01:15 GMT
https://trac.sagemath.org/ticket/27018#comment:4
https://trac.sagemath.org/ticket/27018#comment:4
<p>
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 :)
</p>
<p>
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.
</p>
Ticketgh-ehakaSun, 06 Jan 2019 08:17:29 GMTcommit, branch set
https://trac.sagemath.org/ticket/27018#comment:5
https://trac.sagemath.org/ticket/27018#comment:5
<ul>
<li><strong>commit</strong>
set to <em>4e27c06abf6bfc538f3a21394f2ce86dd4fc26b3</em>
</li>
<li><strong>branch</strong>
set to <em>public/lie_elem_indexing-27018</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/27018#comment:3" title="Comment 3">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Actually, a little more invasive but will likely make the code more maintainable is have the <code>LieGenerator</code> just keep track of the index of the generator and then have the <code>monomial_coefficients()</code> do the translation to the <code>index_set</code>.
</p>
</blockquote>
<p>
I'm afraid I don't understand what you mean by this. Namely, I don't understand at which point <code>monomial_coefficients()</code> comes into play, since <code>FreeLieAlgebra.Lyndon._is_basis_element</code> only uses the word representation of the elements.
</p>
<p>
I started modifying the ordering behavior but ran into some problems.
I added an <code>_index</code> attribute to <code>LieGenerator</code> in the commits and changed <code>LieGenerator.__richcmp__</code> to order by indices instead of name. I did not change comparisons in <code>LyndonBracket.__richcmp__</code> or <code>_is_basis_element</code> 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.
</p>
<p>
What should be the desired behavior?
Was the idea that <code>Lxyz</code> and <code>Lzxy</code> should or should not behave the same?
</p>
<p>
If they should behave differently, then should all the word-based comparisons all be changed to use the index-based comparisons?
</p>
<p>
If they should behave the same, then is it the case that only <code>graded_basis</code> has incorrect behavior?
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=4e27c06abf6bfc538f3a21394f2ce86dd4fc26b3"><span class="icon"></span>4e27c06</a></td><td><code>added _index attribute to LieGenerator</code>
</td></tr></table>
TicketembrayTue, 15 Jan 2019 18:15:21 GMTmilestone changed
https://trac.sagemath.org/ticket/27018#comment:6
https://trac.sagemath.org/ticket/27018#comment:6
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.6</em> to <em>sage-8.7</em>
</li>
</ul>
<p>
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.
</p>
Ticketgh-ehakaWed, 16 Jan 2019 20:39:06 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/27018#comment:7
https://trac.sagemath.org/ticket/27018#comment:7
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>4e27c06abf6bfc538f3a21394f2ce86dd4fc26b3</em> to <em>f086e53e1404d0d0bcc63ca0385f3890061772fa</em>
</li>
<li><strong>branch</strong>
changed from <em>public/lie_elem_indexing-27018</em> to <em>public/freenilp_lie_gens_fix-27018</em>
</li>
</ul>
<p>
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.
</p>
<p>
I opened a new ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/27069" title="defect: Inconsistent behavior with generator ordering in free Lie algebras (closed: fixed)">#27069</a> to address the underlying issue.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=f086e53e1404d0d0bcc63ca0385f3890061772fa"><span class="icon"></span>f086e53</a></td><td><code>trac #27018: bandaid fix for free nilpotent Lie algebras with many generators</code>
</td></tr></table>
TicketembrayFri, 18 Jan 2019 10:27:41 GMTstatus changed
https://trac.sagemath.org/ticket/27018#comment:8
https://trac.sagemath.org/ticket/27018#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
I don't understand what this is supposed to be fixing:
</p>
<div class="wiki-code"><div class="code"><pre><span class="gu">@@ -348,7 +355,7 @@ class FreeNilpotentLieAlgebra(NilpotentLieAlgebra_dense):
</span> # free Lie algebra, and store the corresponding elements in a dict
from sage.algebras.lie_algebras.lie_algebra import LieAlgebra
<span class="gd">- free_gen_names = ['F%d' % k for k in range(r)]
</span><span class="gi">+ free_gen_names = sorted('F%d' % k for k in range(r))
</span></pre></div></div><p>
Originally it was just generating the sequence <code>'F0'</code>, <code>'F1'</code>, <code>'F2'</code>, ... <code>'F<r>'</code>.
The only difference here is that if <code>r >= 10</code> you'll get something like <code>'F0'</code>, <code>'F1'</code>, <code>'F10'</code>, <code>'F2'</code>, ...
</p>
TicketembrayFri, 18 Jan 2019 10:29:38 GMT
https://trac.sagemath.org/ticket/27018#comment:9
https://trac.sagemath.org/ticket/27018#comment:9
<p>
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.
</p>
Ticketgh-ehakaFri, 18 Jan 2019 10:51:55 GMT
https://trac.sagemath.org/ticket/27018#comment:10
https://trac.sagemath.org/ticket/27018#comment:10
<p>
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 <code>FreeNilpotentLieAlgebra</code> 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 <code>FreeLieAlgebra</code> structure inside <code>FreeNilpotentLieAlgebra.__init__</code>.
</p>
<p>
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 <code>LieAlgebra(QQ, 11, step=3)</code> while the underlying issue is being figured out.
</p>
TickettscrimFri, 25 Jan 2019 18:57:11 GMTstatus, milestone changed; dependencies set; commit, branch deleted
https://trac.sagemath.org/ticket/27018#comment:11
https://trac.sagemath.org/ticket/27018#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
<em>f086e53e1404d0d0bcc63ca0385f3890061772fa</em> deleted
</li>
<li><strong>dependencies</strong>
set to <em>#27069</em>
</li>
<li><strong>branch</strong>
<em>public/freenilp_lie_gens_fix-27018</em> deleted
</li>
<li><strong>milestone</strong>
changed from <em>sage-8.7</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
Sorry for taking so long to get to this. I figured it was easier to fix the problem on <a class="closed ticket" href="https://trac.sagemath.org/ticket/27069" title="defect: Inconsistent behavior with generator ordering in free Lie algebras (closed: fixed)">#27069</a> instead of the temporary patch here. So please review <a class="closed ticket" href="https://trac.sagemath.org/ticket/27069" title="defect: Inconsistent behavior with generator ordering in free Lie algebras (closed: fixed)">#27069</a>, and then we can close this one.
</p>
TickettscrimThu, 07 Feb 2019 00:42:11 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/27018#comment:12
https://trac.sagemath.org/ticket/27018#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Travis Scrimshaw</em>
</li>
</ul>
TicketembrayTue, 26 Feb 2019 13:58:00 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/27018#comment:13
https://trac.sagemath.org/ticket/27018#comment:13
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>invalid</em>
</li>
</ul>
<p>
Presuming these are all correctly reviewed as either duplicate, invalid, or wontfix.
</p>
Ticket