|
#############################################################################
##
#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]);
#############################################################################
[ zur Elbe Produktseite wechseln0.52Quellennavigators
Analyse erneut starten
]
|
