Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

8 Algebras
 8.1 Creators for FR algebras
 8.2 Operations for FR algebras

8 Algebras

Self-similar algebras and algebras with one (below FR algebras) are simply algebras [with one] whose elements are linear FR machines. They naturally act on the alphabet of their elements, which is a vector space.

Elements may be added, subtracted and multiplied. They can be vector or algebra linear elements; the vector elements are in general preferable, for efficiency reasons.

Finite-dimensional approximations of self-similar algebras can be computed; they are given as matrix algebras.

8.1 Creators for FR algebras

The most straightforward creation method for FR algebras is Algebra(), applied with linear FR elements as arguments. There are shortcuts to this somewhat tedious method:

8.1-1 FRAlgebra
‣ FRAlgebra( ring, {definition, } )( operation )
‣ FRAlgebraWithOne( ring, {definition, } )( operation )

Returns: A new self-similar algebra [with one].

This function constructs a new FR algebra [with one], generated by linear FR elements. It receives as argument any number of strings, each of which represents a generator of the object to be constructed.

ring is the acting domain of the vector space on which the algebra will act.

Each definition is of the form "name=[[...],...,[...]]" or of the form "name=[[...],...,[...]]:out", namely a matrix whose entries are algebraic expressions in the names, possibly using 0,1, optionally followed by a scalar. The matrix entries specify the decomposition of the element being defined, and the optional scalar specifies the output of that element, by default assumed to be one.

The option IsVectorElement asks for the resulting algebra to be generated by vector elements, see example below. The generators must of course be finite-state.

gap> m := FRAlgebra(Rationals,"a=[[1,a],[a,0]]");
<self-similar algebra on alphabet Rationals^2 with 1 generator>
gap> Display(Activity(m.1,2));
[ [  1,  0,  1,  1 ],
  [  0,  1,  1,  0 ],
  [  1,  1,  0,  0 ],
  [  1,  0,  0,  0 ] ]
gap> m2 := FRAlgebra(Rationals,"a=[[1,a],[a,0]]":IsVectorElement);;
gap> m.1=m2.1;

8.1-2 SCAlgebra
‣ SCAlgebra( m )( operation )
‣ SCLieAlgebra( m )( operation )
‣ SCAlgebraWithOne( m )( operation )
‣ SCAlgebraNC( m )( operation )
‣ SCAlgebraWithOneNC( m )( operation )

Returns: The state-closed algebra [with one] generated by the machine m.

This function constructs a new FR algebra [vith one] a, generated by all the states of the FR machine m. There is a bijective correspondence between GeneratorsOfFRMachine(m) and the generators of a, which is accessible via Correspondence(a) (See Correspondence (7.1-4)); it is a homomorphism from the stateset of m to a, or a list indicating for each state of m a corresponding generator index in the generators of a (with 0 for identity).

In the non-NC forms, redundant (equal, zero or one) states are removed from the generating set of a.

gap> a := SCAlgebra(AsLinearMachine(Rationals,I4Machine));
<self-similar algebra on alphabet Rationals^2 with 3 generators>
gap> a.1 = AsLinearElement(Rationals,I4Monoid.1);

8.1-3 NucleusOfFRAlgebra
‣ NucleusOfFRAlgebra( a )( attribute )
‣ Nucleus( a )( operation )

Returns: The nucleus of the contracting algebra a.

This function returns the nucleus of the contracting algebra a, i.e. the smallest subspace N of a such that the LimitStates (4.2-11) of every element of a belong to N.

This function returns fail if no such N exists. Usually, it loops forever without being able to decide whether N is finite or infinite. It succeeds precisely when IsContracting(g) succeeds.

gap> > a := GrigorchukThinnedAlgebra(2);
<self-similar algebra-with-one on alphabet GF(2)^2 with 4 generators, of dimension infinity>
gap> NucleusOfFRAlgebra(a);
<vector space over GF(2), with 4 generators>

8.1-4 BranchingIdeal
‣ BranchingIdeal( A )( operation )

Returns: An ideal I that contains matrices over itself.

gap> R := GrigorchukThinnedAlgebra(2);;
gap> I := BranchingIdeal(R);
<two-sided ideal in <self-similar algebra-with-one on alphabet GF(2)^2
 with 4 generators, of dimension infinity>, (3 generators)>
gap> e := EpimorphismMatrixQuotient(R,3);;
gap> eI := Ideal(Range(e),List(GeneratorsOfIdeal(I),x->x^e));
<two-sided ideal in <algebra-with-one of dimension 22 over GF(2)>, (3 generators)>
gap> Dimension(Range(e)/eI);

8.2 Operations for FR algebras

8.2-1 MatrixQuotient
‣ MatrixQuotient( a, l )( operation )
‣ EpimorphismMatrixQuotient( a, l )( operation )

Returns: The matrix algebra of a's action on level l.

The first function returns the matrix algebra generated by the activities of a on level l (see the examples in 6.1-7). The second functon returns an algebra homomorphism from a to the matrix algebra.

gap> a := ThinnedAlgebraWithOne(GF(2),GrigorchukGroup);
<self-similar algebra-with-one on alphabet GF(2)^2 with 4 generators>
gap> List([0..4],i->Dimension(MatrixQuotient(a,i)));
[ 1, 2, 6, 22, 78 ]

8.2-2 ThinnedAlgebra
‣ ThinnedAlgebra( r, g )( operation )
‣ ThinnedAlgebraWithOne( r, g )( operation )

Returns: The thinned algebra [with one] associated with g.

The first function returns the thinned algebra of a FR group/monoid/semigroup g, over the domain r. This is the linear envelope of g in its natural action on sequences.

The embedding of g in its thinned algebra is returned by Embedding(g,a).

gap> a := ThinnedAlgebraWithOne(GF(2),GrigorchukGroup);
<self-similar algebra on alphabet GF(2)^2 with 5 generators>
gap> a.1 = GrigorchukGroup.1^Embedding(GrigorchukGroup,a);
gap> Dimension(VectorSpace(GF(2),[One(a),a.2,a.3,a.4]));

8.2-3 Nillity
‣ Nillity( x )( attribute )
‣ IsNilElement( x )( property )

Returns: The smallest n such that x^n=0.

The first command computes the nillity of x, i.e. the smallest n such that x^n=0. The command is not guaranteed to terminate.

The second command returns whether x is nil, that is, whether its nillity is finite.

8.2-4 DegreeOfHomogeneousElement
‣ DegreeOfHomogeneousElement( x )( attribute )
‣ IsHomogeneousElement( x )( property )

Returns: The degree of x in its parent.

If x belongs to a graded algebra A, then the second command returns whether x belongs to a homogeneous component of Grading(A), and the first command returns the degree of that component (or fail if no such component exists).

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind

generated by GAPDoc2HTML