-- $Id: algmorph.cpkg,v 4.5 2004/07/26 16:37:51 cocoa Exp $ Package $contrib/algmorph -- K-algebra homomorphism Alias Alg := $contrib/algmorph; /* Save in lib/contrib/algmorph.pkg Alias Alg := $contrib/algmorph; Alg.Man(); */ Define About() PrintLn " KeyWords : algebra homomorphism, subalgebra Author : A.M.Bigatti Version : CoCoA3.7 Date : 15 June 1999 " EndDefine; -- About ------[ Manual ]-------- Define Man() PrintLn " Suggested alias for this package: Alias Alg := $contrib/algmorph; SYNTAX Alg.Map(RFrom: STRING, RTo: STRING, MapList: LIST): TAGGED('Map') Alg.Ker( Phi: TAGGED('Map')): IDEAL Alg.IsInjective( Phi: TAGGED('Map')): BOOL Alg.IsSurjective(Phi: TAGGED('Map')): BOOL Alg.IsInImage( F: POLY, Phi: TAGGED('Map')): BOOL Alg.PreImage( F: POLY, Phi: TAGGED('Map')): POLY Alg.Image( F: POLY, Phi: TAGGED('Map')): POLY Alg.SubAlgebra(L: LIST): TAGGED('Map') Alg.IsInSubAlgebra(F: POLY, SA: TAGGED('Map')): BOOL Alg.SubAlgebraRepr(F: POLY, SA: TAGGED('Map')): POLY DESCRIPTION Let R and S be polynomial rings on the same coefficient field K. Let Phi be a K-algebra homomorphism: Phi: R --> S, Phi(x_i) := F_i . The function Alg.Map('R', 'S', [F[1],..., F[N]]) returns the representation of Phi expected by the following functions: Alg.Ker(Phi) --> Kernel of Phi (in R) Alg.IsInjective(Phi) --> is Phi injective? Alg.IsSurjective(Phi) --> is Phi surjective? Alg.IsInImage(F, Phi) --> F (in S) is in Phi(R)? Alg.PreImage(F, Phi) --> G (in R) such that Phi(G) = F Alg.Image(F, Phi) --> Phi(F) (in S) [similar to 'Image', but only for polynomials] The function Alg.SubAlgebra([F[1],..., F[N]]) returns the representation of a subalgebra expected by the following functions: Alg.IsInSubAlgebra(F, SA) --> F is in K[F[1],...,F[N]]? Alg.SubAlgebraRepr(F, SA) --> G (in K[y[1],...,y[N]]) such that G(F[1],...,F[N]) = F >EXAMPLE< R1 ::= Q[xyz]; R2 ::= Q[ab]; Use R2; -- like RMap + the ring names Phi := Alg.Map('R1', 'R2', [a+1, ab+3, b^2]); -- or, in any ring Use Z/(2)[w]; Phi := Alg.Map('R1', 'R2', R2::[a+1, ab+3, b^2]); Alg.Ker(Phi); Alg.IsInjective(Phi); Alg.IsSurjective(Phi); Use R2; Alg.IsInImage(a^2, Phi); Alg.PreImage(a^2, Phi); Alg.Image(R1 :: x^2 - 2x + 1, Phi); -- linear maps M := Mat[[1,2,3],[2,3,4],[1,0,1]]; Det(M); -- invertible Use R ::= Q[x[1..3]]; L := [ Sum([ Row[I]x[I] | I In 1..Len(Row)]) | Row In M ]; Psi := Alg.Map('R', 'R', L); -- linear map defined by M Alg.IsInjective(Psi); Alg.IsSurjective(Psi); Inv := [Alg.PreImage(x[I], Psi) | I In 1..3]; MM := Mat([ [ CoeffOfTerm(x[I], Inv[J]) | I In 1..3 ] | J In 1..3]); M MM; Use R1; -- elementary symmetric polynomials S0 := 1; S1 := x+y+z; S2 := xy + xz + yz; S3 := xyz; SA := Alg.SubAlgebra([S0, S1, S2, S3]); -- x^4 + y^4 + z^4 is a symmetric polynomial Alg.IsInSubAlgebra(x^4 + y^4 + z^4, SA); Repr := Alg.SubAlgebraRepr(x^4 + y^4 + z^4, SA); Repr; Image(Repr, RMap([S0, S1, S2, S3])); -- equivalent to Alg.Image(Repr, SA); "; EndDefine; -- Man ---------------[ functions ]--------------- Define Initialize() PKG.AlgMorph := Record[]; /* TODO: REMOVE */ PKG.AlgMorph.RingNo := 0; EndDefine; -- Initialize Define Map(R1, R2, MapList) -- Checks If Not SubSet([R1,R2], RingEnvs()) Then Error("Alg.Map: R1, R2 must be names of existing rings"); EndIf; If Var(R1)::NumIndets() <> Len(MapList) Then Error("Alg.Map: wrong number of elements in MapList"); EndIf; If Not $hilop.ListRingEnv(MapList) IsIn [R2] Then Error("Alg.Map: elements in MapList must be in R2") EndIf; -- Definition of AlgMorphRing Using Var(R2) Do Repeat -- TAPPULLO: problems on linux with repeated names PKG.AlgMorph.RingNo := PKG.AlgMorph.RingNo+1; RingName := 'AlgMorphRing'+Sprint(PKG.AlgMorph.RingNo); Until Not RingName IsIn RingEnvs(); Var(RingName) ::= CoeffRing[x[1..NumIndets(Var(R1))]y[1..NumIndets()]], Weights(Concat(Var(R1)::WeightsList(), WeightsList())), Elim(y); EndUsing; -- Representation of the homomorphism Using Var(RingName) Do I := Ideal([ x[I]-Image(MapList[I], RMap(y)) | I In 1..Len(x)]) EndUsing; Return Alg.Tagged([Var(R1)::Indets(), Var(R2)::[Poly(MapList[I]) | I In 1..NumIndets(Var(R1))], I]); EndDefine; -- Map Define IsSurjective(Var Phi) Using Var(RingEnv(Phi[3])) Do LTPhi := LT(Phi[3]); Phi := Alg.Tagged(@Phi); -- TAG bug? Foreach Y In y Do If Not Y IsIn LTPhi Then Return FALSE EndIf; EndForeach; Return TRUE; EndUsing; EndDefine; -- IsSurjective Define Ker(Var Phi) Using Var(RingEnv(Phi[3])) Do GBPhi := GBasis(Phi[3]); Phi := Alg.Tagged(@Phi); -- TAG bug? K := Ideal([P In GBPhi | LT(P) < Min(y) ]); L := NewList(Len(y), 0); EndUsing; Using Var(RingEnv(Phi[1,1])) Do Proj1 := RMap(Concat(@Phi[1], L)); Return Image(K, Proj1); EndUsing; EndDefine; -- Ker Define IsInjective(Var Phi) Return Var(RingEnv(Phi[1,1])) :: Alg.Ker(Phi) = Ideal(0); EndDefine; -- IsInjective ---------------------[ element in image ]--------------------- Define IsInImage(F, Var Phi) Using Var(RingEnv(Phi[3])) Do GBPhi := GBasis(Phi[3]); Phi := Alg.Tagged(@Phi); -- TAG bug? NFF := NR(Image(F, RMap(y)), GBPhi); Return LT(NFF) < Min(y) EndUsing; EndDefine; -- IsInImage Define PreImage(F, Var Phi) Using Var(RingEnv(Phi[3])) Do GBPhi := GBasis(Phi[3]); Phi := Alg.Tagged(@Phi); -- TAG bug? NFF := NR(Image(F, RMap(y)), GBPhi); If LT(NFF) >= Min(y) Then Return NULL EndIf; L := NewList(Len(y), 0); EndUsing; Using Var(RingEnv(Phi[1,1])) Do Proj1 := RMap(Concat(@Phi[1], L)); Return Image(NFF, Proj1); EndUsing; EndDefine; -- PreImage Define Image(F, Phi) Return Var(RingEnv(Phi[2,1])) :: Image(F, RMap(Phi[2])) EndDefine; -- Image ---------------------[ Sub-Algebras ]--------------------- Define SubAlgebra(L) R2 := $hilop.ListRingEnv(L); Using Var(R2) Do Ws := [Deg(F) | F In L]; If 0 IsIn Ws Then SubAlgebraRing ::= CoeffRing[x[1..Len(L)]]; Else SubAlgebraRing ::= CoeffRing[x[1..Len(L)]], Weights(Ws); EndIf; Return Alg.Map("SubAlgebraRing", R2, L); EndUsing; EndDefine; -- SubAlgebra Define IsInSubAlgebra(F, Var SA) Return Alg.IsInImage(F, SA) EndDefine; -- IsInSubAlgebra Define SubAlgebraRepr(F, Var SA) Return Alg.PreImage(F, SA) EndDefine; -- SubAlgebraRepr /* M := Mat[[1,2,3],[2,3,4],[1,0,1]]; Det(M); -- invertible Use R ::= Q[x[1..3]]; L := [ Sum([ Row[I]x[I] | I In 1..Len(Row)]) | Row In M ]; Psi := Alg.Map('R', 'R', L); -- linear map defined by M Alg.IsInjective(Psi); Alg.IsSurjective(Psi); PreImages := [Alg.PreImage(x[I], Psi) | I In 1..3]; MM := Mat([ [ CoeffOfTerm(x[I], PreImages[J]) | I In 1..3 ] | J In 1..3]); M MM; */ ------[ pretty printing ]-------- Tag() := Alg.PkgName() + ".Map"; Tagged(X) := X; --Tagged(X) := Tagged(X, Alg.Tag()); Define Print_Map(Map) PrintLn "["; PrintLn " ", Map[1], ","; PrintLn " ", Map[2], ","; Indent := Option(Indentation); Set Indentation; PrintLn Map[3]; Set Indentation := Indent; PrintLn "]"; EndDefine; -- Print_Map EndPackage; -- Package $contrib/intprog