Singular

7.7.7 fpadim_lib

Library:

fpadim.lib

Purpose:

Algorithms for quotient algebras in the letterplace case

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
and Project II.6 of the transregional collaborative research centre SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG

Overview:

Given the free associative algebra A = K<x_1,...,x_n> and a (finite) Groebner basis GB = {g_1,..,g_w}, one is interested in the K-dimension and in the explicit K-basis of A/<GB>.
Therefore one is interested in the following data:
- the Ufnarovskij graph induced by GB
- the mistletoes of A/<GB> (special monomials in a basis) - the K-dimension of A/<GB>
- the Hilbert series of A/<GB>

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 [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 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 [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 the
approach in this library does not need an algorithm for computing the normal
form yet. 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 non-commutative Groebner bases, 2009
[studzins] Studzinski: Dimension computations in non-commutative, associative algebras, Diploma thesis, RWTH Aachen, 2010

Note:

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

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

Procedures:

7.7.7.0. lpMis2Dim		computes the K-dimension of the monomial factor algebra
7.7.7.0. lpKDim		computes the K-dimension of A/<G>
7.7.7.0. lpDimCheck		checks if the K-dimension of A/<G> is infinite
7.7.7.0. lpMis2Base		computes a K-basis of the factor algebra
7.7.7.0. lpHilbert		computes the Hilbert series of A/<G> in lp format
7.7.7.0. lpDHilbert		computes the K-dimension and Hilbert series of A/<G>
7.7.7.0. lpDHilbertSickle		computes mistletoes, K-dimension and Hilbert series
7.7.7.0. ivDHilbert		computes the K-dimension and the Hilbert series
7.7.7.0. ivDHilbertSickle		computes mistletoes, K-dimension and Hilbert series
7.7.7.0. ivDimCheck		checks if the K-dimension of A/<L> is infinite
7.7.7.0. ivHilbert		computes the Hilbert series of A/<L> in intvec format
7.7.7.0. ivKDim		computes the K-dimension of A/<L> in intvec format
7.7.7.0. ivMis2Base		computes a K-basis of the factor algebra
7.7.7.0. ivMis2Dim		computes the K-dimension of the factor algebra
7.7.7.0. ivOrdMisLex		orders a list of intvecs lexicographically
7.7.7.0. ivSickle		computes the mistletoes of A/<L> in intvec format
7.7.7.0. ivSickleHil		computes the mistletoes and Hilbert series of A/<L>
7.7.7.0. ivSickleDim		computes the mistletoes and the K-dimension of A/<L>
7.7.7.0. lpOrdMisLex		orders an ideal of lp-monomials lexicographically
7.7.7.0. lpSickle		computes the mistletoes of A/<G> in lp format
7.7.7.0. lpSickleHil		computes the mistletoes and Hilbert series of A/<G>
7.7.7.0. lpSickleDim		computes the mistletoes and the K-dimension of A/<G>
7.7.7.0. sickle		can be used to access all lp main procedures
7.7.7.0. ivMaxIdeal		computes a list of free monomials in intvec presentation
7.7.7.0. lpMaxIdeal		computes a list of free monomials
7.7.7.0. monomialBasis		computes a list of free monomials not contained in J
7.7.7.0. ivL2lpI		transforms a list of intvecs into an ideal of lp monomials
7.7.7.0. iv2lp		transforms an intvec into the corresponding monomial
7.7.7.0. iv2lpList		transforms a list of intmats into an ideal of lp monomials
7.7.7.0. iv2lpMat		transforms an intmat into an ideal of lp monomials
7.7.7.0. lp2iv		transforms a polynomial into the corresponding intvec
7.7.7.0. lp2ivId		transforms an ideal into the corresponding list of intmats
7.7.7.0. lpId2ivLi		transforms a lp-ideal into the corresponding list of intvecs