Free associative unital algebras, implemented via Singular’s letterplace rings

Free associative unital algebras, implemented via Singular’s letterplace rings

AUTHOR:

With this implementation, Groebner bases out to a degree bound and normal forms can be computed for twosided weighted homogeneous ideals of free algebras. For now, all computations are restricted to weighted homogeneous elements, i.e., other elements can not be created by arithmetic operations.

EXAMPLES:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F
sage: I
Twosided Ideal (x*y + y*z, x*x + x*y - y*x - y*y) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
sage: x*(x*I.0-I.1*y+I.0*y)-I.1*y*z
x*y*x*y + x*y*y*y - x*y*y*z + x*y*z*y + y*x*y*z + y*y*y*z
sage: x^2*I.0-x*I.1*y+x*I.0*y-I.1*y*z in I
True

The preceding containment test is based on the computation of Groebner bases with degree bound:

sage: I.groebner_basis(degbound=4)
Twosided Ideal (y*z*y*y - y*z*y*z + y*z*z*y - y*z*z*z, y*z*y*x + y*z*y*z + y*z*z*x + y*z*z*z, y*y*z*y - y*y*z*z + y*z*z*y - y*z*z*z, y*y*z*x + y*y*z*z + y*z*z*x + y*z*z*z, y*y*y - y*y*z + y*z*y - y*z*z, y*y*x + y*y*z + y*z*x + y*z*z, x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field

When reducing an element by \(I\), the original generators are chosen:

sage: (y*z*y*y).reduce(I)
y*z*y*y

However, there is a method for computing the normal form of an element, which is the same as reduction by the Groebner basis out to the degree of that element:

sage: (y*z*y*y).normal_form(I)
y*z*y*z - y*z*z*y + y*z*z*z
sage: (y*z*y*y).reduce(I.groebner_basis(4))
y*z*y*z - y*z*z*y + y*z*z*z

The default term order derives from the degree reverse lexicographic order on the commutative version of the free algebra:

sage: F.commutative_ring().term_order()
Degree reverse lexicographic term order

A different term order can be chosen, and of course may yield a different normal form:

sage: L.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace', order='lex')
sage: L.commutative_ring().term_order()
Lexicographic term order
sage: J = L*[a*b+b*c,a^2+a*b-b*c-c^2]*L
sage: J.groebner_basis(4)
Twosided Ideal (2*b*c*b - b*c*c + c*c*b, a*c*c - 2*b*c*a - 2*b*c*c - c*c*a, a*b + b*c, a*a - 2*b*c - c*c) of Free Associative Unital Algebra on 3 generators (a, b, c) over Rational Field
sage: (b*c*b*b).normal_form(J)
1/2*b*c*c*b - 1/2*c*c*b*b

Here is an example with degree weights:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[1,2,3])
sage: (x*y+z).degree()
3

TEST:

sage: TestSuite(F).run()
sage: TestSuite(L).run()
sage: loads(dumps(F)) is F
True

TODO:

The computation of Groebner bases only works for global term orderings, and all elements must be weighted homogeneous with respect to positive integral degree weights. It is ongoing work in Singular to lift these restrictions.

We support coercion from the letterplace wrapper to the corresponding generic implementation of a free algebra (FreeAlgebra_generic), but there is no coercion in the opposite direction, since the generic implementation also comprises non-homogeneous elements.

We also do not support coercion from a subalgebra, or between free algebras with different term orderings, yet.

class sage.algebras.letterplace.free_algebra_letterplace.FreeAlgebra_letterplace

Bases: sage.rings.ring.Algebra

Finitely generated free algebra, with arithmetic restricted to weighted homogeneous elements.

NOTE:

The restriction to weighted homogeneous elements should be lifted as soon as the restriction to homogeneous elements is lifted in Singular’s “Letterplace algebras”.

EXAMPLE:

sage: K.<z> = GF(25)
sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators (a, b, c) over Finite Field in z of size 5^2
sage: P = F.commutative_ring()
sage: P
Multivariate Polynomial Ring in a, b, c over Finite Field in z of size 5^2

We can do arithmetic as usual, as long as we stay (weighted) homogeneous:

sage: (z*a+(z+1)*b+2*c)^2
(z + 3)*a*a + (2*z + 3)*a*b + (2*z)*a*c + (2*z + 3)*b*a + (3*z + 4)*b*b + (2*z + 2)*b*c + (2*z)*c*a + (2*z + 2)*c*b - c*c
sage: a+1
Traceback (most recent call last):
...
ArithmeticError: Can only add elements of the same weighted degree
commutative_ring()

Return the commutative version of this free algebra.

NOTE:

This commutative ring is used as a unique key of the free algebra.

EXAMPLE:

sage: K.<z> = GF(25)
sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators (a, b, c) over Finite Field in z of size 5^2
sage: F.commutative_ring()
Multivariate Polynomial Ring in a, b, c over Finite Field in z of size 5^2
sage: FreeAlgebra(F.commutative_ring()) is F
True
current_ring()

Return the commutative ring that is used to emulate the non-commutative multiplication out to the current degree.

EXAMPLE:

sage: F.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.current_ring()
Multivariate Polynomial Ring in a, b, c over Rational Field
sage: a*b
a*b
sage: F.current_ring()
Multivariate Polynomial Ring in a, b, c, a_1, b_1, c_1 over Rational Field
sage: F.set_degbound(3)
sage: F.current_ring()
Multivariate Polynomial Ring in a, b, c, a_1, b_1, c_1, a_2, b_2, c_2 over Rational Field
degbound()

Return the degree bound that is currently used.

NOTE:

When multiplying two elements of this free algebra, the degree bound will be dynamically adapted. It can also be set by set_degbound().

EXAMPLE:

In order to avoid we get a free algebras from the cache that was created in another doctest and has a different degree bound, we choose a base ring that does not appear in other tests:

sage: F.<x,y,z> = FreeAlgebra(ZZ, implementation='letterplace')
sage: F.degbound()
1
sage: x*y
x*y
sage: F.degbound()
2
sage: F.set_degbound(4)
sage: F.degbound()
4
gen(i)

Return the \(i\)-th generator.

INPUT:

\(i\) – an integer.

OUTPUT:

Generator number \(i\).

EXAMPLE:

sage: F.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.1 is F.1  # indirect doctest
True
sage: F.gen(2)
c
generator_degrees()
ideal_monoid()

Return the monoid of ideals of this free algebra.

EXAMPLE:

sage: F.<x,y> = FreeAlgebra(GF(2), implementation='letterplace')
sage: F.ideal_monoid()
Monoid of ideals of Free Associative Unital Algebra on 2 generators (x, y) over Finite Field of size 2
sage: F.ideal_monoid() is F.ideal_monoid()
True
is_commutative()

Tell whether this algebra is commutative, i.e., whether the generator number is one.

EXAMPLE:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.is_commutative()
False
sage: FreeAlgebra(QQ, implementation='letterplace', names=['x']).is_commutative()
True
is_field()

Tell whether this free algebra is a field.

NOTE:

This would only be the case in the degenerate case of no generators. But such an example can not be constructed in this implementation.

TEST:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.is_field()
False
ngens()

Return the number of generators.

EXAMPLE:

sage: F.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.ngens()
3
set_degbound(d)

Increase the degree bound that is currently in place.

NOTE:

The degree bound can not be decreased.

EXAMPLE:

In order to avoid we get a free algebras from the cache that was created in another doctest and has a different degree bound, we choose a base ring that does not appear in other tests:

sage: F.<x,y,z> = FreeAlgebra(GF(251), implementation='letterplace')
sage: F.degbound()
1
sage: x*y
x*y
sage: F.degbound()
2
sage: F.set_degbound(4)
sage: F.degbound()
4
sage: F.set_degbound(2)
sage: F.degbound()
4
term_order_of_block()

Return the term order that is used for the commutative version of this free algebra.

EXAMPLE:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F.term_order_of_block()
Degree reverse lexicographic term order
sage: L.<a,b,c> = FreeAlgebra(QQ, implementation='letterplace',order='lex')
sage: L.term_order_of_block()
Lexicographic term order
sage.algebras.letterplace.free_algebra_letterplace.poly_reduce(ring=None, interruptible=True, attributes=None, *args)

This function is an automatically generated C wrapper around the Singular function ‘NF’.

This wrapper takes care of converting Sage datatypes to Singular datatypes and vice versa. In addition to whatever parameters the underlying Singular function accepts when called this function also accepts the following keyword parameters:

INPUT:

  • args - a list of arguments

  • ring - a multivariate polynomial ring

  • interruptible - if True pressing Ctrl-C during the

    execution of this function will interrupt the computation (default: True)

  • attributes - a dictionary of optional Singular

    attributes assigned to Singular objects (default: None)

EXAMPLE:

sage: groebner = sage.libs.singular.ff.groebner
sage: P.<x, y> = PolynomialRing(QQ)
sage: I = P.ideal(x^2-y, y+x)
sage: groebner(I)
[x + y, y^2 - y]

sage: triangL = sage.libs.singular.ff.triang__lib.triangL
sage: P.<x1, x2> = PolynomialRing(QQ, order='lex')
sage: f1 = 1/2*((x1^2 + 2*x1 - 4)*x2^2 + 2*(x1^2 + x1)*x2 + x1^2)
sage: f2 = 1/2*((x1^2 + 2*x1 + 1)*x2^2 + 2*(x1^2 + x1)*x2 - 4*x1^2)
sage: I = Ideal(Ideal(f1,f2).groebner_basis()[::-1])
sage: triangL(I, attributes={I:{'isSB':1}})
[[x2^4 + 4*x2^3 - 6*x2^2 - 20*x2 + 5, 8*x1 - x2^3 + x2^2 + 13*x2 - 5],
 [x2, x1^2],
 [x2, x1^2],
 [x2, x1^2]]

The Singular documentation for ‘NF’ is given below.

5.1.119 reduce
--------------

`*Syntax:*'
     `reduce (' poly_expression`,' ideal_expression `)'
     `reduce (' poly_expression`,' ideal_expression`,' int_expression
     `)'
     `reduce (' poly_expression`,' poly_expression`,' ideal_expression
     `)'
     `reduce (' vector_expression`,' ideal_expression `)'
     `reduce (' vector_expression`,' ideal_expression`,' int_expression
     `)'
     `reduce (' vector_expression`,' module_expression `)'
     `reduce (' vector_expression`,' module_expression`,'
     int_expression `)'
     `reduce (' vector_expression`,' poly_expression`,'
     module_expression `)'
     `reduce (' ideal_expression`,' ideal_expression `)'
     `reduce (' ideal_expression`,' ideal_expression`,' int_expression
     `)'
     `reduce (' ideal_expression`,' matrix_expression`,'
     ideal_expression `)'
     `reduce (' module_expression`,' ideal_expression `)'
     `reduce (' module_expression`,' ideal_expression`,' int_expression
     `)'
     `reduce (' module_expression`,' module_expression `)'
     `reduce (' module_expression`,' module_expression`,'
     int_expression `)'
     `reduce (' module_expression`,' matrix_expression`,'
     module_expression `)'
     `reduce (' poly/vector/ideal/module`,' ideal/module`,' int`,'
     intvec `)'
     `reduce (' ideal`,' matrix`,' ideal`,' int `)'
     `reduce (' poly`,' poly`,' ideal`,' int `)'
     `reduce (' poly`,' poly`,' ideal`,' int`,' intvec `)'

`*Type:*'
     the type of the first argument

`*Purpose:*'
     reduces a polynomial, vector, ideal  or module to its normal form
     with respect to an ideal or module represented by a standard basis.
     Returns 0 if and only if the polynomial (resp. vector, ideal,
     module) is an element (resp. subideal, submodule) of the ideal
     (resp. module).  The result may have no meaning if the second
     argument is not a standard basis.
     The third (optional) argument of type int modifies the behavior:
        * 0 default

        * 1 consider only the leading term and do no tail reduction.

        * 2 reduce also with bad ecart (in the local case)

        * 4 reduce without division, return possibly a non-zero
          constant multiple of the remainder

     If a second argument `u' of type poly or matrix is given, the
     first argument `p' is replaced by `p/u'.  This works only for zero
     dimensional ideals (resp. modules) in the third argument and
     gives, even in a local ring, a reduced normal form which is the
     projection to the quotient by the ideal (resp. module).  One may
     give a degree bound in the fourth argument with respect to a
     weight vector in the fifth argument in order have a finite
     computation.  If some of the weights are zero, the procedure may
     not terminate!

`*Note_*'
     The commands `reduce' and `NF' are synonymous.

`*Example:*'
            ring r1 = 0,(z,y,x),ds;
            poly s1=2x5y+7x2y4+3x2yz3;
            poly s2=1x2y2z2+3z8;
            poly s3=4xy5+2x2y2z3+11x10;
            ideal i=s1,s2,s3;
            ideal j=std(i);
            reduce(3z3yx2+7y4x2+yx5+z12y2x2,j);
          ==> -yx5+2401/81y14x2+2744/81y11x5+392/27y8x8+224/81y5x11+16/81y2x14
            reduce(3z3yx2+7y4x2+yx5+z12y2x2,j,1);
          ==> -yx5+z12y2x2
            // 4 arguments:
            ring rs=0,x,ds;
            // normalform of 1/(1+x) w.r.t. (x3) up to degree 5
            reduce(poly(1),1+x,ideal(x3),5);
          ==> // ** _ is no standard basis
          ==> 1-x+x2

* Menu:

See
* ideal::
* module::
* std::
* vector::
sage.algebras.letterplace.free_algebra_letterplace.singular_system(ring=None, interruptible=True, attributes=None, *args)

This function is an automatically generated C wrapper around the Singular function ‘system’.

This wrapper takes care of converting Sage datatypes to Singular datatypes and vice versa. In addition to whatever parameters the underlying Singular function accepts when called this function also accepts the following keyword parameters:

INPUT:

  • args - a list of arguments

  • ring - a multivariate polynomial ring

  • interruptible - if True pressing Ctrl-C during the

    execution of this function will interrupt the computation (default: True)

  • attributes - a dictionary of optional Singular

    attributes assigned to Singular objects (default: None)

EXAMPLE:

sage: groebner = sage.libs.singular.ff.groebner
sage: P.<x, y> = PolynomialRing(QQ)
sage: I = P.ideal(x^2-y, y+x)
sage: groebner(I)
[x + y, y^2 - y]

sage: triangL = sage.libs.singular.ff.triang__lib.triangL
sage: P.<x1, x2> = PolynomialRing(QQ, order='lex')
sage: f1 = 1/2*((x1^2 + 2*x1 - 4)*x2^2 + 2*(x1^2 + x1)*x2 + x1^2)
sage: f2 = 1/2*((x1^2 + 2*x1 + 1)*x2^2 + 2*(x1^2 + x1)*x2 - 4*x1^2)
sage: I = Ideal(Ideal(f1,f2).groebner_basis()[::-1])
sage: triangL(I, attributes={I:{'isSB':1}})
[[x2^4 + 4*x2^3 - 6*x2^2 - 20*x2 + 5, 8*x1 - x2^3 + x2^2 + 13*x2 - 5],
 [x2, x1^2],
 [x2, x1^2],
 [x2, x1^2]]

The Singular documentation for ‘system’ is given below.

5.1.141 system
--------------

`*Syntax:*'
     `system (' string_expression `)'
     `system (' string_expression`,' expression `)'

`*Type:*'
     depends on the desired function, may be none

`*Purpose:*'
     interface to internal data and the operating system. The
     string_expression determines the command to execute. Some commands
     require an additional argument (second form) where the type of the
     argument depends on the command. See below for a list of all
     possible commands.

`*Note_*'
     Not all functions work on every platform.

`*Functions:*'

    `system("sh"', string_expression `)'
          shell escape, returns the return code of the shell as int.
          The string is sent literally to the shell.

    `system("pid")'
          returns the process number as int (for creating unique names).

    `system("--cpus")'
          returns the number of cpu cores as int (for using multiple
          cores).

    `system("uname")'
          returns a string identifying the architecture for which
          SINGULAR was compiled.

    `system("getenv",' string_expression`)'
          returns the value of the shell environment variable given as
          the second argument. The return type is string.

    `system("setenv",'string_expression, string_expression`)'
          sets the shell environment variable given as the second
          argument to the value given as the third argument. Returns
          the third argument. Might not be available on all platforms.

    `system("tty")'
          resets the terminal.

    `system("version")'
          returns the version number of  SINGULAR as int.

    `system("contributors")'
          returns names of people who contributed to the SINGULAR
          kernel as string.

    `system("gen")'
          returns the generating element of the multiplicative group of
          (Z/p)\{0} (as int) where p is the characteristic of the
          basering.

    `system("nblocks")'

    `system("nblocks",' ring_name `)'
          returns the number of blocks of the given ring, or the number
          of parameters of the current basering, if no second argument
          is given. The return type is int.

    `system("Singular")'
          returns the absolute (path) name of the running SINGULAR as
          string.

    `system("SingularLib")'
          returns the colon seperated library search path name as
          string.

    `system("'-`")'
          prints the values of all options.

    `system("'-long_option_name`")'
          returns the value of the (command-line) option
          long_option_name. The type of the returned value is either
          string or int.  *Note Command line options::, for more info.

    `system("'-long_option_name`",' expression`)'
          sets the value of the (command-line) option long_option_name
          to the value given by the expression. Type of the expression
          must be string, or int.  *Note Command line options::, for
          more info. Among others, this can be used for setting the
          seed of the random number generator, the used help browser,
          the minimal display time, or the timer resolution.

    `system("browsers");'
          returns a string about available help browsers.  *Note The
          online help system::.  returns the number of cpus as int (for
          creating multiple threads/processes).

    `system("pid")'

`*Example:*'
          // a listing of the current directory:
          system("sh","ls");
          // execute a shell, return to SINGULAR with exit:
          system("sh","sh");
          string unique_name="/tmp/xx"+string(system("pid"));
          unique_name;
          ==> /tmp/xx4711
          system("uname")
          ==> ix86-Linux
          system("getenv","PATH");
          ==> /bin:/usr/bin:/usr/local/bin
          system("Singular");
          ==> /usr/local/bin/Singular
          // report value of all options
          system("--");
          ==> // --batch           0
          ==> // --execute
          ==> // --sdb             0
          ==> // --echo            1
          ==> // --quiet           1
          ==> // --sort            0
          ==> // --random          12345678
          ==> // --no-tty          1
          ==> // --user-option
          ==> // --allow-net       0
          ==> // --browser
          ==> // --cntrlc
          ==> // --emacs           0
          ==> // --no-stdlib       0
          ==> // --no-rc           1
          ==> // --no-warn         0
          ==> // --no-out          0
          ==> // --min-time        "0.5"
          ==> // --cpus            2
          ==> // --MPport
          ==> // --MPhost
          ==> // --link
          ==> // --MPrsh
          ==> // --ticks-per-sec   1
          ==> // --MPtransp
          ==> // --MPmode
          // set minimal display time to 0.02 seconds
          system("--min-time", "0.02");
          // set timer resolution to 0.01 seconds
          system("--ticks-per-sec", 100);
          // re-seed random number generator
          system("--random", 12345678);
          // allow your web browser to access HTML pages from the net
          system("--allow-net", 1);
          // and set help browser to firefox
          system("--browser", "firefox");
          ==> // ** Could not get IdxFile.
          ==> // ** Either set environment variable SINGULAR_IDX_FILE to IdxFile,
          ==> // ** or make sure that IdxFile is at /home/hannes/psico2/doc/singular.id\
             x
          ==> // ** resource `x` not found
          ==> // ** Setting help browser to 'builtin'.

Previous topic

Free algebra elements

Next topic

Weighted homogeneous elements of free algebras, in letterplace implementation.

This Page