Difference between revisions of "ApCoCoA-1:NC.KernelOfHomomorphism"

From ApCoCoAWiki
m (replaced <quotes> tag by real quotes)
 
(16 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
{{Version|1}}
 
<command>
 
<command>
 
<title>NC.KernelOfHomomorphism</title>
 
<title>NC.KernelOfHomomorphism</title>
 
<short_description>
 
<short_description>
Enumerate a (partial) Groebner basis of the kernel of a <tt>K</tt>-algebra homomorphism.
+
The kernel of an algebra homomorphism.
 
</short_description>
 
</short_description>
<syntax>
+
<syntax></syntax>
NC.KernelOfHomomorphism(X1:STRING, X2:STRING, Images:LIST):LIST
 
NC.KernelOfHomomorphism(X1:STRING, X2:STRING, Images:LIST, DegreeBound:INT, LoopBound:INT, Flag:INT):LIST
 
</syntax>
 
 
<description>
 
<description>
<em>Please note:</em> The function(s) explained on this page is/are using the <em>ApCoCoAServer</em>. You will have to start the ApCoCoAServer in order to use it/them.
+
<em>Proposition (Kernel of an Algebra Homomorphism):</em> Let <tt>I</tt> be a two-sided ideal in the free monoid ring <tt>K&lt;x[1],...,x[n]&gt;</tt>, and let <tt>J</tt> be a two-sided ideal in the free monoid ring <tt>K&lt;y[1],...,y[m]&gt;</tt>. Moreover, let <tt>g_1,...,g_m</tt> be polynomials in <tt>K&lt;x[1],...,x[n]&gt;</tt>, and let <tt>phi: K&lt;y[1],...,y[m]&gt;/J--&gt;K&lt;x[1],...,x[n]&gt;/I</tt> be a homomorphism of <tt>K</tt>-algebras defined by <tt>phi(y[i]+J)=g_i+I</tt> for <tt>i=1,...,m</tt>. We form the free monoid ring <tt>K&lt;x[1],...,x[n],y[1],...,y[m]&gt;</tt>, and let <tt>D</tt> be the diagonal ideal generated by the set <tt>{y[1]-g_1,...,y[m]-g_m}</tt>. Then we have <tt>ker(phi)=((D+J) intersets K&lt;y[1],...,y[m]&gt;)+I</tt>.
<par/>
 
Please set the <em>coefficient field</em> <tt>K</tt> via the function <ref>NC.SetFp</ref> before calling the function. The default coefficient field is <tt>Q</tt>. For more information, please check the relevant function.
 
<itemize>
 
<item>@param <em>X1:</em> a finite alphabet or finite set of indeterminates. It is of STRING type. Note that every letter in X1 MUST appear only once.The order of letters in X1 is very important, since <tt>X1</tt> together with <tt>Images</tt> determinates a K-algebra homomorphism.</item>
 
<item>@param <em>X2:</em> another finite alphabet or finite set of indeterminates. It is of STRING type. Note that X1 and X2 are disjoint.</item>
 
<item>@param <em>Images:</em> a LIST of polynomials in <tt>K&lt;X2&gt;</tt>. Each polynomial is represented as a LIST of monomials, which are pairs of the form [C, W] where W is a word in <tt>&lt;X2&gt;</tt> and C is the coefficient of W. For example, the polynomial <tt>F=xy-y+1</tt> is represented as F:=[[1,<quotes>xy</quotes>], [-1, <quotes>y</quotes>], [1,<quotes></quotes>]]. The zero polynomial <tt>0</tt> is represented as an empty LIST []. Note that the number of polynomials in <tt>Images</tt> should be equal to the number of letters in <tt>X1</tt>. Also note that the order of polynomials in Images is very important, since <tt>Images</tt> together with <tt>X1</tt> defines a K-algebra homomorphism. For example, X1:=<quotes>abc</quotes>; X2:=<quotes>xy</quotes>; F1 := [[1,<quotes>x</quotes>], [1,<quotes>y</quotes>]]; F2 := [[1,<quotes>xx</quotes>],[1,<quotes>xy</quotes>]]; F3 := [[1,<quotes>yy</quotes>],[1,<quotes>yx</quotes>]]; Images := [F1, F2, F3]; then the K-algebra homomorphism is defined by mapping a to F1, b to F2 and c to F3.</item>
 
</itemize>
 
Since this function is based on Groebner basis computations, we refer users to <ref>NC.GB</ref> or <ref>NC.ReducedGB</ref> for information about the following three optional parameters:
 
<itemize>
 
<item>@param <em>DegreeBound</em></item>
 
<item>@param <em>LoopBound</em></item>
 
<item>@param <em>Flag</em></item>
 
<item>@return: a LIST of polynomials, which is a Groebner basis of the kernel of the <tt>K</tt>-algebra homomorphism if a finite Groebner basis exists, and is a partial Groebner basis otherwise.</item>
 
</itemize>
 
 
<example>
 
<example>
X1 := <quotes>abc</quotes>;  
+
Use QQ[x[1..2],y[1..2],a,b];
X2 := <quotes>xy</quotes>;  
+
NC.SetOrdering("ELIM"); -- we want to eliminate x[1..2],y[1..2]
F1 := [[1,<quotes>x</quotes>], [1,<quotes>y</quotes>]];  
+
-- Group ring Q&lt;a,b&gt;/&lt;F11,F12,F13&gt; with the triangle group of order 576
F2 := [[1,<quotes>xx</quotes>],[1,<quotes>xy</quotes>]];  
+
F11:=[[a^2], [-1]];
F3 := [[1,<quotes>yy</quotes>],[1,<quotes>yx</quotes>]];  
+
F12:=[[b^3], [-1]];
Images :=[F1, F2, F3]; -- a |-> F1; b |-> F2; c |-> F3
+
F13:=[[a,b,a,b,a,b^2,a,b^2,a,b,a,b,a,b^2,a,b^2], [-1]];
NC.KernelOfHomomorphism(X1, X2, Images);
+
-- Group ring Q&lt;x[1],y[1],x[2],y[2]&gt;/&lt;F21,F22,F23,F24,F25,F26&gt; with the fundamental group of 3-manifold of order 72
[[[1, <quotes>ab</quotes>], [-1, <quotes>ba</quotes>], [1, <quotes>ac</quotes>], [-1, <quotes>ca</quotes>]], [[1, <quotes>aa</quotes>], [-1, <quotes>b</quotes>], [-1, <quotes>c</quotes>]]]
+
F21:=[[x[1]^3],[y[1]^3]]; --x[1]^3=y[1]^3
 +
F22:=[[x[1]^3],[-y[1],x[2],y[1],x[2]]]; --x[1]^3p=(y[1]x[1]^-1)^2
 +
F23:=[[x[2],x[1]],[-1]];
 +
F24:=[[x[1],x[2]],[-x[2],x[1]]];
 +
F25:=[[y[2],y[1]],[-1]];
 +
F26:=[[y[1],y[2]],[-y[2],y[1]]];
 +
-- Q-group algebra homomorphism phi: Q&lt;a,b&gt;/&lt;F11,F12,F13&gt; --&gt;Q&lt;x[1],y[1],x[2],y[2]&gt;/&lt;F21,F22,F23,F24,F25,F26&gt;  
 +
-- defined by mapping a to x[1] and b to 0
 +
D1:=[[a],[-x[1]]]; -- map a to x[1]
 +
D2:=[[b]]; -- map b to 0
 +
G:=[D1,D2,F21,F22,F23,F24,F25,F26];
 +
Gb:=NC.GB(G);
 +
KGb:=NC.FindPolys(Gb,[a,b]);
 +
Concat(KGb,[F11,F12,F13]); -- a generating sy[1]stem of the ker(phi)
 +
 
 +
[[[b]], [[a^18], [-1]], [[a^2], [-1]], [[b^3], [-1]],  
 +
[[a, b, a, b, a, b^2, a, b^2, a, b, a, b, a, b^2, a, b^2], [-1]]]
 
-------------------------------
 
-------------------------------
 
</example>
 
</example>
 +
<em>Corollary (Minimal Polynomial):</em> Let <tt>phi: K[y]--&gt;K&lt;x[1],...,x[n]&gt;/I</tt> be a <tt>K</tt>-algebra homomorphism given by <tt>phi(y)=g+I</tt>. Then <tt>g+I</tt> is algebraic over <tt>K</tt> if and only if <tt>ker(phi)</tt> is not zero. Moreover, if <tt>g+I</tt> is algebraic over <tt>K</tt>, then the unique monic generating polynomial of the ideal <tt>ker(phi)</tt> is the minimal polynomial of <tt>g+I</tt> over <tt>K</tt>.
 +
<example>
 +
-- The following example shows that a is transcendental over Q in the algebra Q&lt;a,b&gt;/&lt;b^2-1,(ab)^2-1&gt;,
 +
-- hence the group &lt;a,b: b^2=(ab)^2=1&gt; is infinite.
 +
Use QQ[a,b,y];
 +
NC.SetOrdering("ELIM"); -- we want to eliminate a and b
 +
F1:=[[b^2],[-1]]; -- b^2-1
 +
F2:=[[a,b,a,b],[-1]]; -- (ab)^2-1
 +
-- Construct a Q-algebra homomorphism phi: Q[y]--&gt; Q&lt;a,b&gt;/&lt;b^2-1,(ab)^2-1&gt;
 +
-- defined by mapping y to a
 +
D:=[[y],[-a]]; -- y-a
 +
G:=[D,F1,F2];
 +
Gb:=NC.GB(G);
 +
Gb;
 +
NC.FindPolys(Gb,[y]);
 +
 +
[[[a], [-y]], [[b^2], [-1]], [[y, b, y], [-b]]]
 +
-------------------------------
 +
[ ]
 +
-------------------------------
 +
Use QQ[a,b,y];
 +
NC.SetOrdering("ELIM"); -- we want to eliminate a and b
 +
G1:=[[a^3],[-1]]; -- a^3-1
 +
G2:=[[b^2],[-1]]; -- b^2-1
 +
G3:=[[a,b,a,b],[-1]]; -- (ab)^2-1
 +
-- Construct a Q-algebra homomorphism phi: Q[y]--&gt; Q&lt;a,b&gt;/&lt;a^3-1,b^2-1,(ab)^2-1&gt;
 +
-- defined by mapping y to bab
 +
D:=[[y],[-b,a,b]]; -- y-bab
 +
G:=[D,G1,G2,G3];
 +
Gb:=NC.GB(G);
 +
NC.FindPolys(Gb,[y]);
 +
 +
[[[y^3], [-1]]]
 +
-------------------------------
 +
</example>
 +
<par/>
 
</description>
 
</description>
 
<seealso>
 
<seealso>
<see>NC.Add</see>
+
<see>ApCoCoA-1:Use|Use</see>
<see>NC.Deg</see>
+
<see>ApCoCoA-1:NC.FindPolys|NC.FindPolys</see>
<see>NC.FindPolynomials</see>
+
<see>ApCoCoA-1:NC.GB|NC.GB</see>
<see>NC.GB</see>
+
<see>ApCoCoA-1:NC.SetOrdering|NC.SetOrdering</see>
<see>NC.HF</see>
+
<see>ApCoCoA-1:Introduction to CoCoAServer|Introduction to CoCoAServer</see>
<see>NC.Interreduction</see>
 
<see>NC.Intersection</see>
 
<see>NC.IsGB</see>
 
<see>NC.IsHomog</see>
 
<see>NC.KernelOfHomomorphism</see>
 
<see>NC.LC</see>
 
<see>NC.LT</see>
 
<see>NC.LTIdeal</see>
 
<see>NC.MinimalPolynomial</see>
 
<see>NC.Multiply</see>
 
<see>NC.NR</see>
 
<see>NC.ReducedGB</see>
 
<see>NC.SetFp</see>
 
<see>NC.SetOrdering</see>
 
<see>NC.SetRelations</see>
 
<see>NC.SetRules</see>
 
<see>NC.SetX</see>
 
<see>NC.Subtract</see>
 
<see>NC.UnsetFp</see>
 
<see>NC.UnsetOrdering</see>
 
<see>NC.UnsetRelations</see>
 
<see>NC.UnsetRules</see>
 
<see>NC.UnsetX</see>
 
<see>Introduction to CoCoAServer</see>
 
 
</seealso>
 
</seealso>
 
<types>
 
<types>
 
<type>apcocoaserver</type>
 
<type>apcocoaserver</type>
 
<type>ideal</type>
 
<type>ideal</type>
 +
<type>groebner</type>
 
<type>non_commutative</type>
 
<type>non_commutative</type>
 
</types>
 
</types>
<key>gbmr.KernelOfHomomorphism</key>
+
<key>ncpoly.KernelOfHomomorphism</key>
 
<key>NC.KernelOfHomomorphism</key>
 
<key>NC.KernelOfHomomorphism</key>
 
<key>KernelOfHomomorphism</key>
 
<key>KernelOfHomomorphism</key>
<wiki-category>Package_gbmr</wiki-category>
+
<wiki-category>ApCoCoA-1:Package_ncpoly</wiki-category>
 
</command>
 
</command>

Latest revision as of 13:34, 29 October 2020

This article is about a function from ApCoCoA-1.

NC.KernelOfHomomorphism

The kernel of an algebra homomorphism.

Syntax

Description

Proposition (Kernel of an Algebra Homomorphism): Let I be a two-sided ideal in the free monoid ring K<x[1],...,x[n]>, and let J be a two-sided ideal in the free monoid ring K<y[1],...,y[m]>. Moreover, let g_1,...,g_m be polynomials in K<x[1],...,x[n]>, and let phi: K<y[1],...,y[m]>/J-->K<x[1],...,x[n]>/I be a homomorphism of K-algebras defined by phi(y[i]+J)=g_i+I for i=1,...,m. We form the free monoid ring K<x[1],...,x[n],y[1],...,y[m]>, and let D be the diagonal ideal generated by the set {y[1]-g_1,...,y[m]-g_m}. Then we have ker(phi)=((D+J) intersets K<y[1],...,y[m]>)+I.

Example

Use QQ[x[1..2],y[1..2],a,b];
NC.SetOrdering("ELIM"); -- we want to eliminate x[1..2],y[1..2]
-- Group ring Q&lt;a,b&gt;/&lt;F11,F12,F13&gt; with the triangle group of order 576
F11:=[[a^2], [-1]];
F12:=[[b^3], [-1]];
F13:=[[a,b,a,b,a,b^2,a,b^2,a,b,a,b,a,b^2,a,b^2], [-1]];
-- Group ring Q&lt;x[1],y[1],x[2],y[2]&gt;/&lt;F21,F22,F23,F24,F25,F26&gt; with the fundamental group of 3-manifold of order 72
F21:=[[x[1]^3],[y[1]^3]]; --x[1]^3=y[1]^3
F22:=[[x[1]^3],[-y[1],x[2],y[1],x[2]]]; --x[1]^3p=(y[1]x[1]^-1)^2
F23:=[[x[2],x[1]],[-1]];
F24:=[[x[1],x[2]],[-x[2],x[1]]];
F25:=[[y[2],y[1]],[-1]];
F26:=[[y[1],y[2]],[-y[2],y[1]]];
-- Q-group algebra homomorphism phi: Q&lt;a,b&gt;/&lt;F11,F12,F13&gt; --&gt;Q&lt;x[1],y[1],x[2],y[2]&gt;/&lt;F21,F22,F23,F24,F25,F26&gt; 
-- defined by mapping a to x[1] and b to 0
D1:=[[a],[-x[1]]]; -- map a to x[1]
D2:=[[b]]; -- map b to 0
G:=[D1,D2,F21,F22,F23,F24,F25,F26];
Gb:=NC.GB(G);
KGb:=NC.FindPolys(Gb,[a,b]);
Concat(KGb,[F11,F12,F13]); -- a generating sy[1]stem of the ker(phi)

[[[b]], [[a^18], [-1]], [[a^2], [-1]], [[b^3], [-1]], 
[[a, b, a, b, a, b^2, a, b^2, a, b, a, b, a, b^2, a, b^2], [-1]]]
-------------------------------

Corollary (Minimal Polynomial): Let phi: K[y]-->K<x[1],...,x[n]>/I be a K-algebra homomorphism given by phi(y)=g+I. Then g+I is algebraic over K if and only if ker(phi) is not zero. Moreover, if g+I is algebraic over K, then the unique monic generating polynomial of the ideal ker(phi) is the minimal polynomial of g+I over K.

Example

-- The following example shows that a is transcendental over Q in the algebra Q&lt;a,b&gt;/&lt;b^2-1,(ab)^2-1&gt;,
-- hence the group &lt;a,b: b^2=(ab)^2=1&gt; is infinite.
Use QQ[a,b,y];
NC.SetOrdering("ELIM"); -- we want to eliminate a and b
F1:=[[b^2],[-1]]; -- b^2-1
F2:=[[a,b,a,b],[-1]]; -- (ab)^2-1
-- Construct a Q-algebra homomorphism phi: Q[y]--&gt; Q&lt;a,b&gt;/&lt;b^2-1,(ab)^2-1&gt;
-- defined by mapping y to a
D:=[[y],[-a]]; -- y-a
G:=[D,F1,F2];
Gb:=NC.GB(G);
Gb;
NC.FindPolys(Gb,[y]);

[[[a], [-y]], [[b^2], [-1]], [[y, b, y], [-b]]]
-------------------------------
[ ]
-------------------------------
Use QQ[a,b,y];
NC.SetOrdering("ELIM"); -- we want to eliminate a and b
G1:=[[a^3],[-1]]; -- a^3-1
G2:=[[b^2],[-1]]; -- b^2-1
G3:=[[a,b,a,b],[-1]]; -- (ab)^2-1
-- Construct a Q-algebra homomorphism phi: Q[y]--&gt; Q&lt;a,b&gt;/&lt;a^3-1,b^2-1,(ab)^2-1&gt;
-- defined by mapping y to bab
D:=[[y],[-b,a,b]]; -- y-bab
G:=[D,G1,G2,G3];
Gb:=NC.GB(G);
NC.FindPolys(Gb,[y]);

[[[y^3], [-1]]]
-------------------------------


See also

Use

NC.FindPolys

NC.GB

NC.SetOrdering

Introduction to CoCoAServer