Quelle  algebra.gd   Sprache: Shell

#############################################################################
##
#W algebra.gd                                               Laurent Bartholdi
##
##
#Y Copyright (C) 2007, Laurent Bartholdi
##
#############################################################################
##
##  This file declares self-similar associative algebras.
##
#############################################################################

#############################################################################
##
#C IsFRAlgebra
#C IsFRAlgebraWithOne
##
## <#GAPDoc Label="IsFRAlgebra">
## <ManSection>
##   <Filt Name="IsFRAlgebra" Arg="obj"/>
##   <Filt Name="IsFRAlgebraWithOne" Arg="obj"/>
##   <Returns><K>true</K> if <A>obj</A> is a FR algebra [with one].</Returns>
##   <Description>
##     These functions accept <E>self-similar algebras [with one]</E>,
##     i.e. algebras whose elements are linear FR elements.
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
#DeclareSynonym("IsFRAlgebra", IsLinearFRElementCollection and IsAlgebra);
#DeclareSynonym("IsFRAlgebraWithOne", IsLinearFRElementCollection and IsAlgebraWithOne);
DeclareSynonym("IsFRAlgebra", IsFRElementCollection and IsAlgebra);
DeclareSynonym("IsFRAlgebraWithOne", IsFRElementCollection and IsAlgebraWithOne);
DeclareAttribute("AlphabetOfFRAlgebra", IsFRAlgebra);
DeclareAttribute("NucleusMachine", IsFRAlgebra);
DeclareProperty("IsStateClosed", IsFRAlgebra);
#############################################################################

#############################################################################
##
#F FRAlgebra
#F FRAlgebraWithOne
##
## <#GAPDoc Label="FRAlgebra">
## <ManSection>
##   <Oper Name="FRAlgebra" Arg="ring,{definition,}"/>
##   <Oper Name="FRAlgebraWithOne" Arg="ring,{definition,}"/>
##   <Returns>A new self-similar algebra [with one].</Returns>
##   <Description>
##     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.
##
##     <P/> <A>ring</A> is the acting domain of the vector space on
##     which the algebra will act.
##
##     <P/> Each <A>definition</A> is of the form
##     <C>"name=[[...],...,[...]]"</C>
##     or of the form <C>"name=[[...],...,[...]]:out"</C>,
##     namely a matrix whose entries are algebraic expressions in the
##     <C>names</C>, possibly using <C>0,1</C>, 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.
##
##     <P/> The option <C>IsVectorElement</C> asks for the resulting
##     algebra to be generated by vector elements, see example below.
##     The generators must of course be finite-state.
## <Example><![CDATA[
## 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;
## true
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("FRAlgebra");
DeclareGlobalFunction("FRAlgebraWithOne");
#############################################################################

#############################################################################
##
#O SCAlgebra
#O SCLieAlgebra
#O SCAlgebraWithOne
##
## <#GAPDoc Label="SCAlgebra">
## <ManSection>
##   <Oper Name="SCAlgebra" Arg="m"/>
##   <Oper Name="SCLieAlgebra" Arg="m"/>
##   <Oper Name="SCAlgebraWithOne" Arg="m"/>
##   <Oper Name="SCAlgebraNC" Arg="m"/>
##   <Oper Name="SCAlgebraWithOneNC" Arg="m"/>
##   <Returns>The state-closed algebra [with one] generated by the machine <A>m</A>.</Returns>
##   <Description>
##     This function constructs a new FR algebra [vith one] <C>a</C>,
##     generated by all the states of the FR machine <A>m</A>.
##     There is a bijective correspondence between
##     <C>GeneratorsOfFRMachine(m)</C> and the generators of <C>a</C>, which
##     is accessible via <C>Correspondence(a)</C>
##     (See <Ref Attr="Correspondence" Label="FR semigroup"/>); it is a
##     homomorphism from the stateset of <A>m</A> to <C>a</C>, or a list
##     indicating for each state of
##     <A>m</A> a corresponding generator index in the generators of <C>a</C>
##     (with 0 for identity).
##
##     <P/> In the non-<C>NC</C> forms, redundant (equal, zero or one)
##     states are removed from the generating set of <C>a</C>.
## <Example><![CDATA[
## gap> a := SCAlgebra(AsLinearMachine(Rationals,I4Machine));
## <self-similar algebra on alphabet Rationals^2 with 3 generators>
## gap> a.1 = AsLinearElement(Rationals,I4Monoid.1);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="NucleusOfFRAlgebra" Arg="a"/>
##   <Oper Name="Nucleus" Arg="a" Label="FR algebra"/>
##   <Returns>The nucleus of the contracting algebra <A>a</A>.</Returns>
##   <Description>
##     This function returns the <E>nucleus</E> of the contracting algebra
##     <A>a</A>, i.e. the smallest subspace <C>N</C> of <A>a</A>
##     such that the <Ref Oper="LimitStates"/> of every element of <A>a</A>
##     belong to <C>N</C>.
##
##     <P/> This function returns <K>fail</K> if no such <C>N</C> exists.
##     Usually, it loops forever without being able to decide whether <C>N</C>
##     is finite or infinite. It succeeds precisely when
##     <C>IsContracting(g)</C> succeeds.
## <Example><![CDATA[
## 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>
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="BranchingIdeal" Arg="A"/>
##   <Returns>An ideal <M>I</M> that contains matrices over itself.</Returns>
##   <Description>
## <Example><![CDATA[
## 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);
## 6
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("SCAlgebra", [IsLinearFRMachine]);
DeclareOperation("SCLieAlgebra", [IsLinearFRMachine]);
DeclareOperation("SCAlgebraWithOne", [IsLinearFRMachine]);
DeclareOperation("SCAlgebraNC", [IsLinearFRMachine]);
DeclareOperation("SCAlgebraWithOneNC", [IsLinearFRMachine]);
DeclareAttribute("BranchingIdeal", IsFRAlgebra);
DeclareProperty("IsContracting",IsFRAlgebra);
DeclareAttribute("NucleusOfFRAlgebra",IsFRAlgebra);
#############################################################################

#############################################################################
##
#O ThinnedAlgebra
#O ThinnedAlgebraWithOne
##
## <#GAPDoc Label="ThinnedAlgebra">
## <ManSection>
##   <Oper Name="ThinnedAlgebra" Arg="r,g"/>
##   <Oper Name="ThinnedAlgebraWithOne" Arg="r,g"/>
##   <Returns>The thinned algebra [with one] associated with <A>g</A>.</Returns>
##   <Description>
##     The first function returns the thinned algebra of a FR
##     group/monoid/semigroup <A>g</A>, over the domain <A>r</A>. This
##     is the linear envelope of <A>g</A> in its natural action on
##     sequences.
##
##     <P/> The embedding of <A>g</A> in its thinned algebra is returned
##     by <C>Embedding(g,a)</C>.
## <Example><![CDATA[
## 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);
## true
## gap> Dimension(VectorSpace(GF(2),[One(a),a.2,a.3,a.4]));
## 3
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("ThinnedAlgebra", [IsRing, IsFRSemigroup]);
DeclareOperation("ThinnedAlgebraWithOne", [IsRing, IsFRMonoid]);
#############################################################################

#############################################################################
##
#O Nillity
##
## <#GAPDoc Label="Nillity">
## <ManSection>
##   <Attr Name="Nillity" Arg="x"/>
##   <Prop Name="IsNilElement" Arg="x"/>
##   <Returns>The smallest <C>n</C> such that <M>x^n=0</M>.</Returns>
##   <Description>
##     The first command computes the nillity of <A>x</A>, i.e. the smallest
##     <C>n</C> such that <M>x^n=0</M>. The command is not guaranteed to
##     terminate.
##
##     <P/> The second command returns whether <A>x</A> is nil, that is,
##     whether its nillity is finite.
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="DegreeOfHomogeneousElement" Arg="x"/>
##   <Prop Name="IsHomogeneousElement" Arg="x"/>
##   <Returns>The degree of <A>x</A> in its parent.</Returns>
##   <Description>
##     If <A>x</A> belongs to a graded algebra <C>A</C>, then the second
##     command returns whether <A>x</A> belongs to a homogeneous component
##     of <C>Grading(A)</C>, and the first command returns the degree of
##     that component (or <K>fail</K> if no such component exists).
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute("Nillity", IsMultiplicativeElementWithZero);
DeclareProperty("IsNilElement", IsMultiplicativeElementWithZero);
DeclareAttribute("DegreeOfHomogeneousElement", IsLinearFRElement);
DeclareProperty("IsHomogeneousElement", IsLinearFRElement);
#############################################################################

#############################################################################
##
#O MatrixQuotient
##
## <#GAPDoc Label="MatrixQuotient">
## <ManSection>
##   <Oper Name="MatrixQuotient" Arg="a,l"/>
##   <Oper Name="EpimorphismMatrixQuotient" Arg="a,l"/>
##   <Returns>The matrix algebra of <A>a</A>'s action on level <A>l</A>.</Returns>
##   <Description>
##     The first function returns the matrix algebra
##     generated by the activities of <A>a</A> on level <A>l</A> (see
##     the examples in <Ref Label="ActivitySparse"/>).
##
##     The second functon returns an algebra homomorphism
##     from <A>a</A> to the matrix algebra.
## <Example><![CDATA[
## 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 ]
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
## <#GAPDoc Label="AlgebraHomomorphismbyFunction">
## <ManSection>
##   <Oper Name="AlgebraHomomorphismByFunction" Arg="A B f"/>
##   <Oper Name="AlgebraWithOneHomomorphismByFunction" Arg="A B f"/>
##   <Returns>A homomorphism from the algebra <A>A</A> to the algebra <A>B</A>.</Returns>
##   <Description>
##     These functions construct an algebra homomorphism from a one-argument
##     function. They do not check that the function actually defines a
##     homomorphism.
## <Example><![CDATA[
## gap> A := MatrixAlgebra(Rationals,2);
## ( Rationals^[ 2, 2 ] )
## gap> e1 := AlgebraHomomorphismByFunction(Rationals,A,f->[[f,0],[0,0]]);
## MappingByFunction( Rationals, ( Rationals^[ 2, 2 ] ), function( f ) ... end )
## gap> 11^e1;
## [ [ 11, 0 ], [ 0, 0 ] ]
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("MatrixQuotient", [IsFRAlgebra,IsInt]);
# remove this "not IsBound(...)" hack as soon as the declarations have been moved to the main GAP library
if not IsBound(AlgebraHomomorphismByFunction) then
    DeclareOperation("AlgebraHomomorphismByFunction", [IsAlgebra,IsAlgebra,IsFunction]);
fi;
if not IsBound(AlgebraWithOneHomomorphismByFunction) then
    DeclareOperation("AlgebraWithOneHomomorphismByFunction", [IsAlgebraWithOne,IsAlgebraWithOne,IsFunction]);
fi;
DeclareOperation("EpimorphismMatrixQuotient", [IsFRAlgebra,IsInt]);
#############################################################################