# Homogeneous ideals of free algebras.¶

Homogeneous ideals of free algebras.

For twosided ideals and when the base ring is a field, this implementation also provides Groebner bases and ideal containment tests.

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


One can compute Groebner bases out to a finite degree, can compute normal forms and can test containment in the ideal:

sage: I.groebner_basis(degbound=3)
Twosided Ideal (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
sage: (x*y*z*y*x).normal_form(I)
y*z*z*y*z + y*z*z*z*x + y*z*z*z*z
sage: x*y*z*y*x - (x*y*z*y*x).normal_form(I) in I
True


AUTHOR:

class sage.algebras.letterplace.letterplace_ideal.LetterplaceIdeal(ring, gens, coerce=True, side='twosided')

Graded homogeneous ideals in free algebras.

In the two-sided case over a field, one can compute Groebner bases up to a degree bound, normal forms of graded homogeneous elements of the free algebra, and ideal containment.

EXAMPLES:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
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: I.groebner_basis(2)
Twosided Ideal (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
sage: I.groebner_basis(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


Groebner bases are cached. If one has computed a Groebner basis out to a high degree then it will also be returned if a Groebner basis with a lower degree bound is requested:

sage: I.groebner_basis(2)
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


Of course, the normal form of any element has to satisfy the following:

sage: x*y*z*y*x - (x*y*z*y*x).normal_form(I) in I
True


Left and right ideals can be constructed, but only twosided ideals provide Groebner bases:

sage: JL = F*[x*y+y*z,x^2+x*y-y*x-y^2]; JL
Left 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: JR = [x*y+y*z,x^2+x*y-y*x-y^2]*F; JR
Right 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: JR.groebner_basis(2)
Traceback (most recent call last):
...
TypeError: This ideal is not two-sided. We can only compute two-sided Groebner bases
sage: JL.groebner_basis(2)
Traceback (most recent call last):
...
TypeError: This ideal is not two-sided. We can only compute two-sided Groebner bases


Also, it is currently not possible to compute a Groebner basis when the base ring is not a field:

sage: FZ.<a,b,c> = FreeAlgebra(ZZ, implementation='letterplace')
sage: J = FZ*[a^3-b^3]*FZ
sage: J.groebner_basis(2)
Traceback (most recent call last):
...
TypeError: Currently, we can only compute Groebner bases if the ring of coefficients is a field


The letterplace implementation of free algebras also provides integral degree weights for the generators, and we can compute Groebner bases for twosided graded homogeneous ideals:

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


Again, we can compute normal forms:

sage: (z*I.0-I.1).normal_form(I)
0
sage: (z*I.0-x*y*z).normal_form(I)
-y*x*z + z*z

groebner_basis(degbound=None)

Twosided Groebner basis with degree bound.

INPUT:

• degbound (optional integer, or Infinity): If it is provided, a Groebner basis at least out to that degree is returned. By default, the current degree bound of the underlying ring is used.

ASSUMPTIONS:

Currently, we can only compute Groebner bases for twosided ideals, and the ring of coefficients must be a field. A $$TypeError$$ is raised if one of these conditions is violated.

NOTES:

• The result is cached. The same Groebner basis is returned if a smaller degree bound than the known one is requested.
• If the degree bound Infinity is requested, it is attempted to compute a complete Groebner basis. But we can not guarantee that the computation will terminate, since not all twosided homogeneous ideals of a free algebra have a finite Groebner basis.

EXAMPLES:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F


Since $$F$$ was cached and since its degree bound can not be decreased, it may happen that, as a side effect of other tests, it already has a degree bound bigger than 3. So, we can not test against the output of I.groebner_basis():

sage: F.set_degbound(3)
sage: I.groebner_basis()   # not tested
Twosided Ideal (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
sage: I.groebner_basis(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
sage: I.groebner_basis(2) is I.groebner_basis(4)
True
sage: G = I.groebner_basis(4)
sage: G.groebner_basis(3) is G
True


If a finite complete Groebner basis exists, we can compute it as follows:

sage: I = F*[x*y-y*x,x*z-z*x,y*z-z*y,x^2*y-z^3,x*y^2+z*x^2]*F
sage: I.groebner_basis(Infinity)
Twosided Ideal (z*z*z*y*y + z*z*z*z*x, z*x*x*x + z*z*z*y, y*z - z*y, y*y*x + z*x*x, y*x*x - z*z*z, x*z - z*x, x*y - y*x) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field


Since the commutators of the generators are contained in the ideal, we can verify the above result by a computation in a polynomial ring in negative lexicographic order:

sage: P.<c,b,a> = PolynomialRing(QQ,order='neglex')
sage: J = P*[a^2*b-c^3,a*b^2+c*a^2]
sage: J.groebner_basis()
[b*a^2 - c^3, b^2*a + c*a^2, c*a^3 + c^3*b, c^3*b^2 + c^4*a]


Aparently, the results are compatible, by sending $$a$$ to $$x$$, $$b$$ to $$y$$ and $$c$$ to $$z$$.

reduce(G)

Reduction of this ideal by another ideal, or normal form of an algebra element with respect to this ideal.

INPUT:

• G: A list or tuple of elements, an ideal, the ambient algebra, or a single element.

OUTPUT:

• The normal form of G with respect to this ideal, if G is an element of the algebra.
• The reduction of this ideal by the elements resp. generators of G, if G is a list, tuple or ideal.
• The zero ideal, if G is the algebra containing this ideal.

EXAMPLES:

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

sage.algebras.letterplace.letterplace_ideal.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

See
* ideal::
* module::
* std::
* vector::
sage.algebras.letterplace.letterplace_ideal.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

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
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

system("pid")'

*Example:*'
// a listing of the current directory:
system("sh","ls");
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
==> // --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);
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

Weighted homogeneous elements of free algebras, in letterplace implementation.

#### Next topic

Finite dimensional free algebra quotients