
7.7.7 fpadim_lib
 Library:
 fpadim.lib
 Purpose:
 Algorithms for quotient algebras in the letterplace case
 Authors:
 Grischa Studzinski, grischa.studzinski@rwthaachen.de
Support: Joint projects LE 2697/21 and KR 1907/31 of the Priority Programme SPP 1489:
'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
of the German DFG
 Overview:
 Given the free algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
GB = {g_1,..,g_w}, one is interested in the Kdimension and in the
explicit Kbasis of A/<GB>.
Therefore one is interested in the following data:
 the Ufnarovskij graph induced by GB
 the mistletoes of A/<GB>
 the Kdimension of A/<GB>
 the Hilbert series of A/<GB>
The Ufnarovskij graph is used to determine whether A/<GB> has finite
Kdimension. One has to check if the graph contains cycles.
For the whole theory we refer to [ufna]. Given a
reduced set of monomials GB one can define the basis tree, whose vertex
set V consists of all normal monomials w.r.t. GB. For every two
monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
set M = {m in V  there is no edge from m to another monomial in V} is
called the set of mistletoes. As one can easily see it consists of
the endpoints of the graph. Since there is a unique path to every
monomial in V the whole graph can be described only from the knowledge
of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
knowing the mistletoes we know a Kbasis. The name mistletoes was given
to those points because of these miraculous value and the algorithm is
named sickle, because a sickle is the tool to harvest mistletoes.
For more details see [studzins]. This package uses the Letterplace
format introduced by [lls]. The algebra can either be represented as a
Letterplace ring or via integer vectors: Every variable will only be
represented by its number, so variable one is represented as 1,
variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
be stored as (1,3,2). Multiplication is concatenation. Note that there
is no algorithm for computing the normal form needed for our case.
Note that the name fpadim.lib is short for dimensions of finite
presented algebras.
 References:
[ufna] Ufnarovskij: Combinatorical and asymptotic methods in algebra, 1990
[lls] Levandovskyy, La Scala: Letterplace ideals and noncommutative
Groebner bases, 2009
[studzins] Studzinski: Dimension computations in noncommutative,
associative algebras, Diploma thesis, RWTH Aachen, 2010
Assumptions:
 basering is always a Letterplace ring
 all intvecs correspond to Letterplace monomials
 if you specify a different degree bound d,
d <= attrib(basering,uptodeg) should hold.
In the procedures below, 'iv' stands for intvec representation
and 'lp' for the letterplace representation of monomials
Procedures:
See also:
freegb_lib.
