# How to do low degree computation in a Free Algebra ?

Say $F$ is a free algebra over $n$ generators of degree $1$, and i want to compute in this algebra but i only need to get my expressions up to degree $k$. For example, if $k=2$, $(ab +a)*b$ should be $ab$.

For now, i have been doing the computation and truncating everything above degree $k$, but the time complexity is too high when i launch a big computation.

I am actually asking how to compute in the tensor Algebra $T(V)$ modulo $T_{\geq k}(V)$. For free Lie algebras, this can be done using nilpotent Lie algebras, (for example L = LieAlgebra(QQ, 3, step=3) implements a 3-nilpotent free Lie algebra). How to do this with free algebras ?

edit retag close merge delete

Sort by » oldest newest most voted

Here is a function to produce the desired quotient algebra.

Given generator names, a maximum degree, and a base ring, it builds the free algebra on the generators with the requested names over the requested ring, and outputs the quotient modulo terms of degree higher than the specified maximum degree.

The following function works with one-letter generators.

def my_algebra(gen_names, max_degree=2, base_ring=QQ):
r"""
Return the quotient of the free algebra on these generators
by terms of degree max_degree + 1.
"""
n = max_degree
R = base_ring
words = [w for W in [Words(gen_names, j) for j in range(n + 1)] for w in W]
names = [str(w) for w in words[1:]]
F = FreeAlgebra(R, names=names)
FM = F.monoid()
gens = FM.gens()
mons = (FM.one(),) + gens
r = len(mons)
M = MatrixSpace(R, r)
def row(m, mm):
if len(m) + len(mm) > n:
return  * r
res =  * r
res[words.index(mm * m)] = 1
return res
mats = [M([row(m, mm) for mm in words]) for m in words[1:]]
return FreeAlgebraQuotient(F, mons, mats, names=names)


This variant accepts multicharacter generator names:

def my_algebra(gen_names, max_degree=2, base_ring=QQ):
r"""
Return the quotient of the free algebra on these generators
by terms of degree max_degree + 1.
"""
n = max_degree
R = base_ring
word_options = dict(WordOptions())
WordOptions(letter_separator='')
words = [w for W in [Words(gen_names, j) for j in range(n + 1)] for w in W]
names = [str(w) for w in words[1:]]
F = FreeAlgebra(R, names=names)
FM = F.monoid()
gens = FM.gens()
mons = (FM.one(),) + gens
r = len(mons)
M = MatrixSpace(R, r)
def row(m, mm):
if len(m) + len(mm) > n:
return  * r
res =  * r
res[words.index(mm * m)] = 1
return res
mats = [M([row(m, mm) for mm in words]) for m in words[1:]]
WordOptions(**word_options)
return FreeAlgebraQuotient(F, mons, mats, names=names)


This function gives the multiplication table:

def algebra_table(G):
gens = (G.one(),) + G.gens()
prods = [[x * y for y in gens] for x in gens]
hr = gens
hc = ('*',) + gens


Some trials in the Sage REPL:

sage: G = my_algebra(['a', 'b'], max_degree=2, base_ring=QQ)
sage: a, b = G.gen(0), G.gen(1)
sage: (a * b + a) * b
ab

sage: algebra_table(G)
*  | 1    a    b    aa   ab   ba   bb
+----+----+----+----+----+----+----+----+
1  | 1    a    b    aa   ab   ba   bb
a  | a    aa   ab   0    0    0    0
b  | b    ba   bb   0    0    0    0
aa | aa   0    0    0    0    0    0
ab | ab   0    0    0    0    0    0
ba | ba   0    0    0    0    0    0
bb | bb   0    0    0    0    0    0

sage: G = my_algebra(['x1', 'x2'], max_degree=2, base_ring=QQ)
sage: a, b = G.gen(0), G.gen(1)
sage: (a * b + a) * b
x1x2

sage: algebra_table(G)
*    | 1      x1     x2     x1x1   x1x2   x2x1   x2x2
+------+------+------+------+------+------+------+------+
1    | 1      x1     x2     x1x1   x1x2   x2x1   x2x2
x1   | x1     x1x1   x1x2   0      0      0      0
x2   | x2     x2x1   x2x2   0      0      0      0
x1x1 | x1x1   0      0      0      0      0      0
x1x2 | x1x2   0      0      0      0      0      0
x2x1 | x2x1   0      0      0      0      0      0
x2x2 | x2x2   0      0      0      0      0      0

sage: G = my_algebra(['x_1', 'x_2'], max_degree=2, base_ring=QQ)
sage: a, b = G.gen(0), G.gen(1)
sage: (a * b + a) * b
x_1x_2

sage: algebra_table(G)
*      | 1        x_1      x_2      x_1x_1   x_1x_2   x_2x_1   x_2x_2
+--------+--------+--------+--------+--------+--------+--------+--------+
1      | 1        x_1      x_2      x_1x_1   x_1x_2   x_2x_1   x_2x_2
x_1    | x_1      x_1x_1   x_1x_2   0        0        0        0
x_2    | x_2      x_2x_1   x_2x_2   0        0        0        0
x_1x_1 | x_1x_1   0        0        0        0        0        0
x_1x_2 | x_1x_2   0        0        0        0        0        0
x_2x_1 | x_2x_1   0        0        0        0        0        0
x_2x_2 | x_2x_2   0        0        0        0        0        0


In Jupyter, latexing is off for names such as x1x2 or x_1x_2. Not sure how to fix that.

more

Thank you, it seems to answer my question, i ll try this tomorrow !

For now, the solution only works if your generators names are one letter (for example it does not work with x_1,x_2...).

EDIT : The solution for this is to add the command WordOptions(letter_separator='') before usinfg the words command in the code of slelievre.

Sadly they are still not latexing properly.

Another way (less complete but more efficient for just a quick computation) is to compute directly in the Free algebra, but instead of using the product, use the following:

def fast_product(a,b): res = 0 a = F(a) b = F(b) data_a =[(w.to_word(), cf) for w, cf in a]
data_b =[(w.to_word(), cf) for w, cf in b] for wa,cfa in data_a: for wb,cfb in data_b: if len(wb) + len(wa) <= k: res = res + cfacfbF.monomial(wa)*F.monomial(wb)
return res

To format code blocks in questions, answers, or comments, separate them by a blank line above and below, and indent them by four spaces. Cay you edit your comment to do that?

Another way (less complete than @slelievre's answer but more efficient for just a quick computation) is to compute directly in the free algebra, using the following instead of the product:

def fast_product(a, b):
res = F.zero()
a = F(a)
b = F(b)
data_a = [(w.to_word(), cf) for w, cf in a]
data_b = [(w.to_word(), cf) for w, cf in b]
for wa, cfa  in data_a:
for wb, cfb in data_b:
if len(wb) + len(wa) <= k:
res += cfa * cfb * F.monomial(wa) * F.monomial(wb)
return res

more