CoCalc -- lieBasis.ipynb

Download

jupyter workbook developing Python functions to make bases for Lie algebras and Lie coalgebras

Hopf Invariants

lieBasis.ipynb

²⁴ views
License: GPL3

unlisted

ubuntu2204

Kernel: Python 3 (system-wide)

Making Bases!

Below, I'll convert my old pairing.html javascript code from the Lie Algebra / coalgebra pairing calculator to python. I'll also write a new algorithm to generate the star basis for symbols.

This section will mostly target Lie algebra - coalgebra pairings. The next section will look at finitely presented groups and bases for configuration braiding invariants.

Note: this code requires the coLie.py library of coLie objects.

Lyndon-Shirshov words

The Lyndon words (or Lyndon-Shirshov acknowledging Anatoly Shirshov using them in 1953 vs Roger Lyndon's use in 1954) appear in algebra, combinatorics, and computer science. They can be used for data compression, are a basis for the shuffle algebra, index irreducible monic polynomials, and give rise to a Hall basis for Lie algebras.

Given an ordered alphabet, we consider necklaces -- words modulo cyclic permutation. We identify necklaces by writing a representative (modulo cyclic permutation) which is minimal in lexicographic ordering.
A necklace $a_1a_2\cdots a_N$ is periodic if there is $n<N$ so that $a_i = a_{n+i}$ for all $i$ (where this makes sense). This implies that the necklace is a repetition of multiple copies of some (letter or) subword $\omega = \alpha \alpha \cdots \alpha$ .
An LS-word is a representative of an aperiodic necklace. Note that in this case, the representative choice is unique!

Two other characterizations of Lyndon words are helpful when making proofs:

$w$ is LS iff for any (nontrivial) factorization $w=ab$ we have $a < b$ lexicographically
$w$ is LS iff for any (nontrivial) factorization $w=ab$ we have $w < b$ lexicographically (" $w$ less than its suffixes")

Using the characterizations above we define the "standard factorization" of an LS word to be $w=ab$ where $b$ is the maximal length LS suffix (in which case $a$ is also LS). This is used to make the standard bracketing... though there are other good factorizations which lead to interesting bracketings as well.

There are a couple of different ways to generate LS words.

In 1988 Duval proposed an algorithm which generates all words of length $n$ by repeating a prefix string and then incrementing the final letter. This will generate all LS words in increasing order. This algorithm frequently generates words which are too small during its search, but the average cost of generating the next letter is linear.
In 2000 Cattal et al propose an alternate algorithm which generates all LS words up to a given length in reverse order, modifying one letter at a time. This algorithm uses the factorization characterization of LS words to iteratively build words which could be prefixes of an LS word.
Afterwards the coauthor J.Sawada modified the algorithm to efficiently target only LS words which contain specified multiplicities of letters. This is best for our purposes, and is considerably faster than generating all LS words and then tossing out the ones with the wrong multiplicities.
There are other algorithms as well - see Kopparty et al

Lyndon words are pretty nice and extensively studied and used, but there are also other ways to choose representatives of words modulo shuffles... which can lead to useful and interesting constructions. Probably any basis of coLie (Eil) words must give a complete set of representatives. So hunting for bases could be a fruitful way to look for / prove that you've found other rules for making representatives. The "deg-lex minimal" (DL) words is one other choice (natural from the viewpoint of left-greedy brackets and star symbols).

In [3]:

import math   # Duval's algorithm genLS_old() uses math.ceil()

#######################################################################
def genLS_old(word):
    """Use Duval's algorithm (1988) to generate all Lyndon(-Shirshov) words using given alphabet and multiplicities
       Duval's algorithm generates all words of a given length.  We ignore words with incorrect multiplicities.
    """
    
    # create alphabet = list of (letter,count) pairs
    alphabet = sorted(list(set(word)))
    count    = [word.count(letter) for letter in alphabet]

    
    if alphabet == []:
        return
    
    N = len(word)
   
    LSWord = [alphabet[0]]
    
    # apply algorithm from Duval (1988)
    
    while LSWord != []:
        if len(LSWord) == len(word) and all([LSWord.count(l)==n for l,n in zip(alphabet,count)]):
            yield(''.join(LSWord))
            
        LSWord = LSWord * math.ceil(N/len(LSWord))
                
        n = N-1
        
        while n >= 0 and LSWord[n] == alphabet[-1]:
            n -= 1
            
        LSWord = LSWord[:n+1]
        
        if n >= 0:
            LSWord[n] = alphabet[alphabet.index(LSWord[n])+1]
            
    return


#######################################################################
# An alternate algorithm is given by Cattell et al (2000) 
#   https://www.cis.uoguelph.ca/~sawada/papers/un.pdf
#
# This seems to be about the same speed as Duval's algorithm
#
def genLS_all(word, t=1, p=1, N=None, K=None, root=True, LSWord=None):
    """Cattell et al (2000) algorithm generating all LS words of a given length
       Running time is similar to Duval (1998)
    """
    if root:
        N = len(word)
        if N < 2:
            yield word
        
        LSWord = [0] * (N + 1)    # Cattell's algorithm uses 1-indexing... ugh
        word   = sorted(list(set(word)))  # later iterations need alphabet
        K      = len(word)
        
        
    if t > N:
        if p == N:
            yield(''.join(word[num] for num in LSWord[1:]))
    else:
        LSWord[t] = LSWord[t-p]
        yield from genLS_all(word, t+1, p, N, K, False, LSWord)
        
        for j in range(LSWord[t-p]+1, K):
            LSWord[t] = j
            yield from genLS_all(word, t+1, t, N, K, False, LSWord)


#######################################################################
#######################################################################            
# It is possible to modify this algorithm to generate only words with specific multiplicies of letters
#  below is modification of Joe Sawada's C code (2019) available at http://combos.org/necklace
#
# This is considerably faster than generating everything and throwing out ones with wrong multiplicity
#
# We use a linked list to track multiplicity and availability of letters in the alphabet
#  Once all of a letter's multiplicity is used up, we modify the linked list to skip it
# As we build a LS word, the alphabet linked list will be continually updated adding and removing letters
#
######################################################
# The LListElement class has attributes
#   value = multiplicity of an letter
#   index = index of the letter
#   prev  = previous element in alphabet
#   next  = next element in alphabet
###########################################################
class LListElement:
    def __init__(self,value=0,index=0,n=None,p=None):
        self.value , self.index = value , index
        self._prev , self._next = p , n
        
    def __bool__(self):
        return self.value != 0

#######################################################
# The ValuedList class will be used to store the alphabet
# Attributes:
#   _nodes = array containing all linked list elements 
#   head   = first available element in alphabet 
#
# Methods:
#   mult(n)      = remaining multiplicity of letter n
#   decrement(n) = lowers available multiplicity of n (and maybe removes from alphabet)
#   increment(n) = raises available multiplicity of n (and maybe reinserts in alphabet)
#   nextval(n)   = get next available letter (after n)
###########################################################
class ValuedLList:
    def __init__(self,count):
        if len(count) < 1:
            return
         
        self._nodes  = [LListElement(count[0])]
        for n in range(1,len(count)):
            self._nodes.append(LListElement(count[n],n,self._nodes[n-1]))
            self._nodes[n-1]._prev = self._nodes[n]
            
        self.head = self._nodes[-1]
    
    def mult(self,n):
        return self._nodes[n].value
    
    def decrement(self,n):
        self._nodes[n].value -= 1
        
        if not self._nodes[n]:
            if self.head == self._nodes[n]:
                self.head = self._nodes[n]._next
                
            if self._nodes[n]._next:
                self._nodes[n]._next._prev = self._nodes[n]._prev
            if self._nodes[n]._prev:
                self._nodes[n]._prev._next = self._nodes[n]._next

    def increment(self,n):
        if not self._nodes[n]:
            if self._nodes[n]._next:
                self._nodes[n]._next._prev = self._nodes[n]
            if self._nodes[n]._prev:
                self._nodes[n]._prev._next = self._nodes[n]
            else:
                self.head = self._nodes[n]
                
        self._nodes[n].value += 1

    def nextval(self,n):
        if self._nodes[n]._next:
            return self._nodes[n]._next.index
        return -1
    
###########################################################
# TODO:  allow alphabet with multiplicity to be specified in other ways
#
#  currently:   "aaabbbcc"
#  also allow:  [ ("a",3) , ("b",3) , ("c",2) ]  
#      (dictionary, list of tuples, list of lists)
###########################################################
def genLS(word, t=2, p=1, s=2, N=None, K=None, root=True, LSWord=None, count=None, tmp=None):
    """genLS(word)  is generator for Lyndon-(Shirshov) words with a given grading
       Words are generated with the same multiplicities of letters as the input word, using the algorithm of Cattell and Sawada.
       
       Note: Words are generated in reverse lexicographic order!
       
       Example: genLS("aaabbc") will generate all LS words with 3x 'a', 2x 'b', and 1x 'c'
        --> 'ababac', 'aacbab', 'aacabb', 'aabcab', 'aabbac', 'aabacb', 'aababc', 'aaacbb', 'aaabcb', 'aaabbc'
    """
    if root:
        N = len(word)
        if N < 2:
            yield word
        
        tmp    = sorted(list(set(word)))
        count  = ValuedLList([word.count(letter) for letter in tmp])
        word   = tmp              # later iterations need alphabet
        K      = len(word)
        LSWord = [K-1] * (N + 1)    # Cattell's algorithm uses 1-indexing... ugh
        tmp    = [0] * (N + 1)
        
        LSWord[1] = 0             # Cattell's algorithm uses 1-indexing... ugh
        count.decrement(0)
        
    if count.mult(-1) == N-t+1:
        if count.mult(-1) == tmp[t-p] and N == p:
            yield(''.join(word[num] for num in LSWord[1:]))
        elif count.mult(-1) > tmp[t-p]:
            yield(''.join(word[num] for num in LSWord[1:]))
            
    elif count.mult(0) != N-t+1:
        j = count.head.index
        ss = s
        while j >= LSWord[t-p]:
            tmp[s]    = t-s
            LSWord[t] = j
            
            count.decrement(j)
            
            if j != K-1:
                ss = t+1
            if j == LSWord[t-p]:
                yield from genLS(word,t+1,p,ss,N,K,False,LSWord,count,tmp)
            else:
                yield from genLS(word,t+1,t,ss,N,K,False,LSWord,count,tmp)
                
            count.increment(j)
            
            j = count.nextval(j)
            
        LSWord[t] = K-1



#######################################################
#######################################################
#  Lyndon words are minimal in their cyclic ordering class
#   usually we use lexicographic ordering
#   alternately we could use deg-lex ordering
###########################################################
def genDL():
    passs

#   JavaScript code:   (TODO: clean and convert this to Python!)
#//////////////////////////////////////////////////////////////////////////////// 
#// toDLWord
#//   converts LS word to DL word 
#//
#function toDLWord( word ) {
#	return toDL( word.split(''), word.charAt(0) );
#}
#function toDL( word, wordMin ) {
#	if (word.length <=1 )
#			return word[0];
#
#	var i, j;
#	var newWord = [];
#	var newMin = "999999999999999999";
#
#	for (i=0; (i < word.length) && (word[i] != wordMin); i++) ;
#
#	j = i;
#
#	while (i < word.length+j)  {
#
#		var subWord = word[i];
#
#		for (i++ ; (i < word.length) && (word[i] == wordMin); i++)  {
#			subWord = subWord+word[i];
#		}
#		
#		if (i != word.length)
#			subWord = subWord+word[i];
#		else 
#			i--;
#
#		for (i++ ; (i < word.length + j) && (word[i] != wordMin); i++)
#			subWord = subWord+word[(i % word.length)];
#
#		newWord.push( subWord );
#		if (parseInt(subWord.replace(/\D/g,'')) < parseInt(newMin.replace(/\D/g,''))) 
#			newMin = subWord;
#	}
#
#	return toDL( newWord, newMin );
#}

Test the code!

In [4]:

#################################################
#     TESTING BLOCK!!!!                         #
#################################################

import timeit


start = timeit.default_timer()
print(list(genLS_old("aaaabbbd")))
stop = timeit.default_timer()

print('Time: ', stop - start)  


start = timeit.default_timer()
print(list(genLS("aaaabbbd")))
stop = timeit.default_timer()

print('Time: ', stop - start)

Out[4]:

['aaaabbbd', 'aaaabbdb', 'aaaabdbb', 'aaaadbbb', 'aaababbd', 'aaababdb', 'aaabadbb', 'aaabbabd', 'aaabbadb', 'aaabbbad', 'aaabbdab', 'aaabdabb', 'aaabdbab', 'aaadabbb', 'aaadbabb', 'aaadbbab', 'aabaabbd', 'aabaabdb', 'aabaadbb', 'aabababd', 'aababadb', 'aababbad', 'aababdab', 'aabadabb', 'aabadbab', 'aabbaabd', 'aabbaadb', 'aabbabad', 'aabbadab', 'aabbbaad', 'aabdabab', 'aadababb', 'aadabbab', 'aadbabab', 'abababad']
Time:  0.0016990799995255657
['abababad', 'aadbabab', 'aadabbab', 'aadababb', 'aabdabab', 'aabbbaad', 'aabbadab', 'aabbabad', 'aabbaadb', 'aabbaabd', 'aabadbab', 'aabadabb', 'aababdab', 'aababbad', 'aababadb', 'aabababd', 'aabaadbb', 'aabaabdb', 'aabaabbd', 'aaadbbab', 'aaadbabb', 'aaadabbb', 'aaabdbab', 'aaabdabb', 'aaabbdab', 'aaabbbad', 'aaabbadb', 'aaabbabd', 'aaabadbb', 'aaababdb', 'aaababbd', 'aaaadbbb', 'aaaabdbb', 'aaaabbdb', 'aaaabbbd']
Time:  0.0005849759982083924

Making Lie bases from LS words!

Once you have a list of LS words basically any reasonable method you come up with for systematically creating (nonzero) brackets will yield a Lie basis. There is a long and honorable tradition in algebra of coming up with new Lie bases. There are lots of different ones.

In [5]:

#######################################################################
# Code below makes Lie bases from LS words using different rules      #
#                                                                     #
# Most of this code is directly translated from my old Javascript     # 
#  code from 2015 without any optimazation or cleaning....            #
#    (see pairing.html)                                               
#######################################################################

from coLie import *

############################################################
# This makes the classical bracketing on an LS word - recursively defined as
#    B(w) = [ B(a) , B(b) ]  where w = ab and b is a maximal LS subword
#
# There are two standard approaches to making this bracketing --
#   Inside->out (inductive): finding the inner-most bracket first  
#                                (look for "right-most inversion")
#   Outside->in (recursive): finding outer-most bracket first
#                                (look for largest Lyndon suffix)
#
#  ... the code below is outside-in... this looks unnecessarily complex??? oh well.
###########################################################
def bracketStd(word):
    """Convert Lyndon word to standard Lie bracketing"""
    if len(word) == 1:
        return LieTree(word)
    
    end = len(word)-1
    newprefix , myprefix = 1 , 0     # number of times initial letter is repeated
    split = end
    
    repeat = True
    
    for j in range(end-1, 0, -1):
        if repeat:                     # if current word is repeating suffix
            if word[j] == word[end]:   # if repeat continues
                end -= 1               #   move repeat pointer 
            else:
                repeat = False         # no longer repeating suffix
                end = len(word) - 1    #   reset repeat pointer
                
        if word[j] < word[split]:       # found new low -- better suffix start!
            newprefix , myprefix = 1 , 1
            split = j
            repeat = True               # start checking for repeats again
            
        elif word[j] > word[split]:     # not a possible Lyndon suffix start!
            myprefix = 0                # reset repeats to 0
            
        else:                        # possible cutpoint! (word[j] == word[split])
            myprefix += 1            #  count # repeating letters at cutpoint
                
            if not repeat:
                if myprefix == newprefix: # compare new cutpoint to old cutpoint
                    i = 1
                    while split+i < len(word) and word[j+i] == word[split+i]:
                        i += 1
                    if split+i < len(word) and word[j+i] < word[split+i]:
                        split  = j
                        repeat = True
                elif myprefix > newprefix: # found longer prefix -- new cutpoint
                    newprefix = myprefix
                    split = j
                    repeat = True                             
                
    
    bracket = LieTree()
    bracket.bracket = [ bracketStd(word[:split]) , bracketStd(word[split:]) ]
    
    return bracket  



#########################################################
# see also algorithm by Sawada and Ruskey (2002) .. generating words and brackets at same time
#  https://webhome.cs.uvic.ca/~ruskey/Publications/LieBasis/LieBasis.pdf
#          Journal of Algorithms 46 (2003) 21-26
#
# algorithm is implemented in C at http://combos.org/necklace
##########################################################



###########################################################
# code below is translated from my javascript code
#
# Note: this is a basis by [WaSh15] and pairs diagonally with the star basis for symbols!!!
# 
# TODO: modify this so that it will also left-greedy bracket non-Lyndon words!
###########################################################
def bracketLeft(word):
    """Convert Lyndon word to left-greedy bracketing"""
    if len(word) <= 1:
        return LieTree(word)
    
    i , j = 0 , 1

# Idea:  look for repeated subword in topmost partition  ww..wx
#  by moving two pointers across the word and looking for repetitions

# current code requires word to be LS. more general version?
#
#    while j < len(word)-1 and word[i] <= word[j]: # 2nd condition only needed for deg-lex words?
    while j < len(word)-1:                         # 2nd condition never fails for LS words.
        if word[i] == word[j]:
            i += 1
        else:
#            if word[i] > word[j]:    # test necessity of 2nd condition
#                print("oops") 
            i = 0
        j += 1
    
    bracket = LieTree()
    bracket.bracket = [ bracketLeft(word[:j-i]) , bracketLeft(word[j-i:]) ]
    
    return bracket



###########################################################
# code below is translated from my old javascript code
#
# I'm pretty sure this is a basis, but I don't remember if I/anyone ever proved it....
#
# TODO: verify whether this will right-greedy bracket non-Lyndon words!
###########################################################
def bracketRight(word):
    """Convert Lyndon word to right-greedy bracketing"""
    return bracketRG(list(word))

def bracketRG(word):
    if len(word) == 1:
        return word[0] if isinstance(word[0],LieTree) else LieTree(word[0])

    newWord = []
    
    i = 1
    while i < len(word):
        subbracket = bracketRG([word[i-1]])
        
        while i < len(word) and str(word[i]) != str(word[0]):
            tmpbracket = LieTree()
            tmpbracket.bracket = [ bracketRG([subbracket]) , bracketRG([word[i]]) ]
            subbracket = tmpbracket
            i += 1
        
        newWord.append(subbracket)
        i += 1
        
    return bracketRG(newWord)



###########################################################        
# "Configuration basis"  This is a basis by:
#   B. Walter.  The configuration basis of a Lie algebra and its dual
#      https://arxiv.org/abs/1010.4765
#
# this is a direct translation of my javascript code to python
###########################################################
def bracketCfg(word):
    """Convert Lyndon word to Configuration bracketing"""
    return LieTree(bracketConfig(list(word)))


def bracketConfig(word):
    if len(word) == 1:
        return word[0]
    
    newWord = []
    
    start , i = 0 , 1 
    
    while i < len(word):
        bracket = ['[', word[start] ]
        
        while word[i] == word[0]:
            bracket.extend([ ',[' , word[i] ])
            i += 1
        bracket.extend(["," , word[i]])
        bracket.extend(["]"] * (i-start))
                
        i += 1
        while i < len(word) and word[i] != word[0]:
            bracket.insert(0, '[')
            bracket.extend([',' , word[i] , ']'])
            i += 1
            
        newWord.append(''.join(bracket))
                
        start = i
        i += 1
        
    return bracketConfig(newWord)
    


###########################################################
# "right normed" basis of Chibrikov:
#   https://core.ac.uk/download/pdf/82357333.pdf
#
# this is a direct translation of my javascript code to python
###########################################################
def bracketChib(word):
    """Convert Lyndon word to Chibrikov's bracketing"""
    return LieTree(bracketChibrikov(list(word)))

def bracketChibrikov(word):
    if len(word) == 1:
        return word[0]
    
    newWord = []
    
    end , i = len(word)-1 , len(word)-2     

    while i>=0:
        bracket = [word[end], ']']
        
        while word[i] != word[0]:
            bracket.insert(0,']')
            bracket.insert(0,word[i])
            i -= 1

        bracket.insert(0,word[i])
        
        while end > i:
            bracket.insert(0,'[')
            end -= 1
        
        i -= 1
        while i >= 0 and word[i] == word[0]:
            bracket.insert(0,word[i])
            bracket.insert(0,'[')
            bracket.append(']')
            i -= 1
            
        newWord.insert(0,''.join(bracket))
        
        end = i
        i -= 1
        
    return bracketChibrikov(newWord)

Test the code!

In [6]:

#################################################
#     TESTING BLOCK!!!!                         #
#################################################

from coLie import *

print(" Standard:")

for word in genLS("abababb"):   # check bracket creation
    print(f'{word} -> {bracketStd(word)}')
for eil in genLS("abababb"):    # verify pairing matrix (invertible = basis)
    print([EilWord(eil) * bracketStd(lie) for lie in genLS("abababb")])
    
print("\n Left-Greedy:")

for word in genLS("abababb"):   # check bracket creation
    print(f'{word} -> {bracketLeft(word)}')
for eil in genLS("abababb"):    # verify pairing matrix (invertible = basis)
    print([EilWord(eil) * bracketLeft(lie) for lie in genLS("abababb")])   
    
print("\n Right-Greedy:")

for word in genLS("abababb"):   # check bracket creation
    print(f'{word} -> {bracketRight(word)}')
for eil in genLS("abababb"):    # verify pairing matrix (invertible = basis)
    print([EilWord(eil) * bracketRight(lie) for lie in genLS("abababb")])

print("\n Configuration")

for word in genLS("abababb"):   # check bracket creation
    print(f'{word} -> {bracketCfg(word)}')
for eil in genLS("abababb"):    # verify pairing matrix (invertible = basis)
    print([EilWord(eil) * bracketCfg(lie) for lie in genLS("abababb")])

print("\n  Chibrikov")

for word in genLS("abababb"):   # check bracket creation
    print(f'{word} -> {bracketChib(word)}')
for eil in genLS("abababb"):
    print([EilWord(eil) * bracketChib(lie) for lie in genLS("abababb")])

Out[6]:

 Standard:
abababb -> [[a,b],[[a,b],[[a,b],b]]]
aabbbab -> [[a,[[[a,b],b],b]],[a,b]]
aabbabb -> [[a,[[a,b],b]],[[a,b],b]]
aababbb -> [a,[[a,b],[[[a,b],b],b]]]
aaabbbb -> [a,[a,[[[[a,b],b],b],b]]]
[1, 3, -2, 3, 0]
[0, 1, -2, 2, -4]
[0, 0, 1, -3, 6]
[0, 0, 0, 1, -4]
[0, 0, 0, 0, 1]

 Left-Greedy:
abababb -> [[a,b],[[a,b],[[a,b],b]]]
aabbbab -> [[[[a,[a,b]],b],b],[a,b]]
aabbabb -> [[[[a,[a,b]],b],[a,b]],b]
aababbb -> [[[[a,[a,b]],[a,b]],b],b]
aaabbbb -> [[[[a,[a,[a,b]]],b],b],b]
[1, 2, 0, 4, 0]
[0, 1, -1, 0, 0]
[0, 0, 1, -1, 0]
[0, 0, 0, 1, -3]
[0, 0, 0, 0, 1]

 Right-Greedy:
abababb -> [[a,b],[[a,b],[[a,b],b]]]
aabbbab -> [[a,[[[a,b],b],b]],[a,b]]
aabbabb -> [[a,[[a,b],b]],[[a,b],b]]
aababbb -> [[a,[a,b]],[[[a,b],b],b]]
aaabbbb -> [a,[a,[[[[a,b],b],b],b]]]
[1, 3, -2, 6, 0]
[0, 1, -2, 3, -4]
[0, 0, 1, -3, 6]
[0, 0, 0, 1, -4]
[0, 0, 0, 0, 1]

 Configuration
abababb -> [[a,b],[[a,b],[[a,b],b]]]
aabbbab -> [[[[a,[a,b]],b],b],[a,b]]
aabbabb -> [[[a,[a,b]],b],[[a,b],b]]
aababbb -> [[a,[a,b]],[[[a,b],b],b]]
aaabbbb -> [[[[a,[a,[a,b]]],b],b],b]
[1, 2, -2, 6, 0]
[0, 1, -2, 3, 0]
[0, 0, 1, -3, 0]
[0, 0, 0, 1, -3]
[0, 0, 0, 0, 1]

  Chibrikov
abababb -> [[a,b],[[a,b],[[a,b],b]]]
aabbbab -> [[a,[[[a,b],b],b]],[a,b]]
aabbabb -> [[a,[[a,b],b]],[[a,b],b]]
aababbb -> [[a,[a,b]],[[[a,b],b],b]]
aaabbbb -> [a,[a,[[[[a,b],b],b],b]]]
[1, 3, -2, 6, 0]
[0, 1, -2, 3, -4]
[0, 0, 1, -3, 6]
[0, 0, 0, 1, -4]
[0, 0, 0, 0, 1]

Note that the pairing matrices above are all upper triangular. This is a general fact, and is the essential ingredient in the proof that they are bases (though the original authors didn't use this language).

Symbol Bases

The LS and deg-lex LS words are bases for Eil words.

Alternatively we can use the "Star Symbol" basis for Eil symbols!

The star symbol basis is connected to the left-greedy recursive partitioning of a word (and the left-greedy Lie bracketing above).

An $a$ -simple word is $a^nx$ where $x\neq a$
An $a$ -simple partition of a word is $w=\alpha_1\alpha_2\cdots\alpha_n$ where each $\alpha_i$ is an $a$ -simple word. Note that LS words have unique $a$ -simple partitions.
Viewing $a$ -simple words as a new alphabet we can repeat (if you order lexicographically then $a$ -simple partitions are themselves LS words in the alphabet of $a$ -simple words.)
The left greedy bracketing is defined (recursively) by
- $[a^nx] = [a,\,[a,\,\cdots[a,\,x]\;]]$
- $[\alpha^n\beta] = \bigl[[\alpha],\,\bigl[[\alpha],\,\cdots\bigl[[\alpha],[\beta]\bigr]\;\bigr]\bigr]$
The star symbol is defined (recursively) by
- $\star a^nx = (a)(a)\cdots(a)x$
- $\star \alpha^n \beta = \bigl(\star \alpha\bigr)\,\bigl(\star \alpha\bigr)\cdots\bigl(\star\alpha\bigr)\,\star\!\beta$

Note: We can make star symbols out of non-LS words as well!

Note: Star symbols have the very special property that their cobrackets are also star symbols! (Compare to LS words, whose cobrackets will usually not be LS!)

Other symbol bases???

I don't know... I showed that the star symbols make a basis. They should also be a "dual monomial basis" to left greedy brackets (we'll test this in the code below!). I was satisfied enough with that, so I didn't search for any other bases.... I guess, the star symbols are so perfect that I didn't bother looking for others.

In [7]:

from coLie import *

###########################################################
# code below is modification of bracketLeft() code
#
# Note: this is a basis by [WaSh15] and pairs nicely with the leftGreedy basis for Lie algebras
###########################################################
def symbolStar(word):
    """Convert Lyndon word into coLie star symbol"""
    if len(word) <= 1:
        return EilTree(word)
    
    i , j = 0 , 1
    N = len(word)
    
    # look for repeated subword in topmost partition  ww..wx
    #  by moving two pointers across the word and looking for repetitions
    #
    while j != N-1:    # current code requires word to be LS. more general version?
        if word[i] == word[j]: 
            i += 1
        else:
            i = 0
        j += 1
    
    k = j - i       # width of subword w in top partition ww..wx
    
    subsymbols = [symbolStar(word[:k])]  # this is subword w
    
    n = k         
    while n < N-k:  # attach repetitions of subword (if any)
        subsymbols[:0] = [subsymbols[0].copy()]
        n += k
    
    symbol = symbolStar(word[n:]) # this is the suffix word x
    symbol.extend(subsymbols)     # stick the w's onto the x
    
    return symbol

Test the code!

In [8]:

#################################################
#     TESTING BLOCK!!!!                         #
#################################################

eil = symbolStar("abacabacabad")

print(f'{str(eil)} has weight {eil.weight}')

for subsymbol in eil.subsymbols:
    print(f'{ str(subsymbol)} has weight {subsymbol.weight}')
    
print(f'\n{str(eil)} has cobracket:')
for cobr in eil.cobracket():
    print(f' {str(cobr[0])} x {str(cobr[1])}')

print()

print(symbolStar("aaaab"))
print(bracketLeft("aaaab"))
print(f' pair to {symbolStar("aaaab") * bracketLeft("aaaab")}\n')

print(symbolStar("abababb"))
print(bracketLeft("abababb"))
print(f' pair to {symbolStar("abababb") * bracketLeft("abababb")}\n')

print(symbolStar("abacabacabad"))
print(bracketLeft("abacabacabad"))
print(f' pair to {symbolStar("abacabacabad") * bracketLeft("abacabacabad")}\n')
  
print()

for word in genLS("abababb"):
    print(f'{word} -> {str(symbolStar(word))}')
    
for eil in genLS("abababb"):
    print([symbolStar(eil) * bracketLeft(lie) for lie in genLS("abababb")])

Out[8]:

(((a)b)(a)c)(((a)b)(a)c)((a)b)(a)d has weight 11
((a)b)(a)c has weight 3
((a)b)(a)c has weight 3
(a)b has weight 1
a has weight 0

(((a)b)(a)c)(((a)b)(a)c)((a)b)(a)d has cobracket:
 ((a)b)(a)c x (((a)b)(a)c)((a)b)(a)d
 (a)b x ((a)c)(((a)b)(a)c)((a)b)(a)d
 a x ((b)(a)c)(((a)b)(a)c)((a)b)(a)d
 a x (((a)b)c)(((a)b)(a)c)((a)b)(a)d
 ((a)b)(a)c x (((a)b)(a)c)((a)b)(a)d
 (a)b x (((a)b)(a)c)((a)c)((a)b)(a)d
 a x (((a)b)(a)c)((b)(a)c)((a)b)(a)d
 a x (((a)b)(a)c)(((a)b)c)((a)b)(a)d
 (a)b x (((a)b)(a)c)(((a)b)(a)c)(a)d
 a x (((a)b)(a)c)(((a)b)(a)c)(b)(a)d
 a x (((a)b)(a)c)(((a)b)(a)c)((a)b)d

(a)(a)(a)(a)b
[a,[a,[a,[a,b]]]]
 pair to 24

((a)b)((a)b)((a)b)b
[[a,b],[[a,b],[[a,b],b]]]
 pair to 6

(((a)b)(a)c)(((a)b)(a)c)((a)b)(a)d
[[[a,b],[a,c]],[[[a,b],[a,c]],[[a,b],[a,d]]]]
 pair to 2


abababb -> ((a)b)((a)b)((a)b)b
aabbbab -> ((((a)(a)b)b)b)(a)b
aabbabb -> ((((a)(a)b)b)(a)b)b
aababbb -> ((((a)(a)b)(a)b)b)b
aaabbbb -> ((((a)(a)(a)b)b)b)b
[6, 0, 0, 0, 0]
[0, 2, 0, 0, 0]
[0, 0, 2, 0, 0]
[0, 0, 0, 2, 0]
[0, 0, 0, 0, 6]

Projection onto Basis!

Note that the pairing matrix for star symbols and left greedy brackets is diagonal! This means we can quickly write general brackets in terms of left greedy brackets by computing pairings with corresponding star symbols.

For other Lie bases we would need to invert the upper-triangular pairing matrix. But for star and left greedy we are doing orthogonal projection!

In [30]:

def bracket_to_left(bracket,short=False):
    """Use orthogonal projection and star symbols to write Lie brackets in terms of Left-Greedy Basis
       
       Arguments:
       ----------
        bracket : string or LieTree
           Lie bracket expression to convert
        short   : boolean  [False]
           Write output brackets in 'short form' (i.e. without ,)
           
       Result:
       -------
        dictionary { bracket : coefficient }
           
    """
    if not isinstance(bracket,LieTree):
        bracket = LieTree(bracket)
    
    result = dict()
    
    for word in genLS(bracket.letters()):
        eil, lie = symbolStar(word) , bracketLeft(word)
        
        coeff = (eil * bracket) / (eil * lie)
        
        if coeff != 0:
            if short:
                result[lie.short] = int(coeff)
            else: 
                result[str(lie)] = int(coeff)
            
    return result

In [32]:

#################################################
#     TESTING BLOCK!!!!                         #
#################################################

# Example: Write [[[b,c],[a,c]],[a,b]] in terms of left-greedy basis

bracket = "[[[b,c],[a,c]],[a,b]]"

print(f'{bracket} = ')

#print(bracket_to_left(bracket))

for lie , coeff in bracket_to_left(bracket).items():
    if coeff == 1:
        coeff = " +"
    elif coeff == -1:
        coeff = " -"
    print(f' {coeff} {lie}')

Out[32]:

[[[b,c],[a,c]],[a,b]] = 
  + [[[[a,b],c],b],[a,c]]
  - [[[[a,b],b],c],[a,c]]
  - [[[[a,b],[a,c]],c],b]
  + [[[[a,b],[a,c]],b],c]

Making Bases!

Lyndon-Shirshov words

Making Lie bases from LS words!

Symbol Bases

Other symbol bases???

Projection onto Basis!

Product

Resources

Company