7.10.1 fpadim_lib

Library:

fpadim.lib

Purpose:

Vector space dimension, basis and Hilbert series for finitely presented algebras (Letterplace)

Authors:

Grischa Studzinski, grischa.studzinski at rwth-aachen.de
Viktor Levandovskyy, viktor.levandovskyy at math.rwth-aachen.de
Karim Abou Zeid, karim.abou.zeid at rwth-aachen.de

Support: Joint projects LE 2697/2-1 and KR 1907/3-1 of the Priority Programme SPP 1489: 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie' of the German DFG (2010-2013)
and Project II.6 of the transregional collaborative research centre SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG (from 2017 on)

Note:

- basering is a Letterplace ring
- all intvecs correspond to Letterplace monomials
- if a degree bound d is specified, d <= attrib(basering,uptodeg) holds

In the procedures below, 'iv' stands for intvec representation and 'lp' for the letterplace representation of monomials

Overview:

Given the free associative algebra A = K<x_1,...,x_n> and a (finite or truncated) Groebner basis GB, one is interested in the following data:
- the K-dimension of A/<GB> (check for finiteness or explicit value) - the Hilbert series of A/<GB>
- the explicit monomial K-basis of A/<GB>
In order to determine these, we need
- the Ufnarovskij graph induced by GB
- the mistletoes of A/<GB> (which are special monomials in a basis)

The Ufnarovskij graph is used to determine whether A/<GB> has finite K-dimension. One has to check if the graph contains cycles. For the whole theory we refer to [Ufn]. 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 K-basis. 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 [Stu]. This package uses the Letterplace format introduced by [LL09]. 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 the approach in this library does not need an algorithm for computing the normal form. Note that fpa is an acronym for Finitely Presented Algebra.

References:

[Ufn] V. Ufnarovskij: Combinatorial and asymptotic methods in algebra, 1990. [LL09] R. La Scala, V. Levandovskyy: Letterplace ideals and non-commutative Groebner bases, Journal of Symbolic Computation, 2009. [Stu] G. Studzinski: Dimension computations in non-commutative, associative algebras, Diploma thesis, RWTH Aachen, 2010.

Procedures:

7.10.1.1 teach_lpKDimCheck		deprecated, kept for teaching purposes. checks whether the K-dimension of A/<G> is finite. use dim(G) == 0 instead.
7.10.1.2 lpKDim		alias for vdim(G)
7.10.1.3 teach_lpKDim		deprecated, kept for teaching purposes. computes the K-dimension of A/<G>. use vdim(G) instead.
7.10.1.4 lpMonomialBasis		computes a list of monomials not contained in J
7.10.1.5 lpHilbert		computes the truncated Hilbert series of A/<G>
7.10.1.6 teach_lpSickleDim		deprecated, kept for teaching purposes. computes the mistletoes and the K-dimension of A/<G>. use vdim(G) instead.