Difference between revisions of "ApCoCoA-1:Free groups"

From ApCoCoAWiki
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
=== <div id="Free_groups">[[:ApCoCoA:Symbolic data#Free_groups|Free groups]]</div> ===
+
=== <div id="Free_groups">[[:ApCoCoA:Symbolic data#Free_groups|Free Groups]]</div> ===
 
==== Description ====
 
==== Description ====
 
The relations of a free group with n generators only consists of the existence of the invers elements. Any element of a
 
The relations of a free group with n generators only consists of the existence of the invers elements. Any element of a
 
free group has a unique representation.
 
free group has a unique representation.
 
   F(n) = <a_{1},...,a_{n} | a_{i}a_{i}^{-1} = a_{i}^{-1}a_{i} = 1>
 
   F(n) = <a_{1},...,a_{n} | a_{i}a_{i}^{-1} = a_{i}^{-1}a_{i} = 1>
(Reference: Kharlampovich, Olga; Myasnikov, Alexei (2006). "Elementary theory of free non-abelian groups". J. Algebra 302 (2): 451–552)
+
 
 +
==== Reference ====
 +
Kharlampovich, Olga; Myasnikov, Alexei, "Elementary theory of free non-abelian groups". J. Algebra 302 (2): 451–552, 2006.
  
 
==== Computation ====
 
==== Computation ====
Line 10: Line 12:
 
    
 
    
 
   // Number of free group
 
   // Number of free group
 
 
 
   MEMORY.N:=4;
 
   MEMORY.N:=4;
 
    
 
    
 
   Use ZZ/(2)[x[1..MEMORY.N],y[1..MEMORY.N]];
 
   Use ZZ/(2)[x[1..MEMORY.N],y[1..MEMORY.N]];
 
   NC.SetOrdering("LLEX");
 
   NC.SetOrdering("LLEX");
 +
 
 
   Define CreateRelationsFree()
 
   Define CreateRelationsFree()
 
     Relations:=[];
 
     Relations:=[];
Line 26: Line 28:
 
   Relations:=CreateRelationsFree();
 
   Relations:=CreateRelationsFree();
 
   Relations;
 
   Relations;
   GB:=NC.GB(Relations);
+
    
   GB;
+
  Gb:=NC.GB(Relations);
 +
   Gb;
 +
====Examples in Symbolic Data Format====
 +
=====Free group 4=====
 +
  <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 +
  <vars>x1,x2,x3,x4,y1,y2,y3,y4</vars>
 +
  <basis>
 +
  <ncpoly>x1*y1-1</ncpoly>
 +
  <ncpoly>y1*x1-1</ncpoly>
 +
  <ncpoly>x2*y2-1</ncpoly>
 +
  <ncpoly>y2*x2-1</ncpoly>
 +
  <ncpoly>x3*y3-1</ncpoly>
 +
  <ncpoly>y3*x3-1</ncpoly>
 +
  <ncpoly>x4*y4-1</ncpoly>
 +
  <ncpoly>y4*x4-1</ncpoly>
 +
  </basis>
 +
  <Comment>Free_group_4</Comment>
 +
  </FREEALGEBRA>
 +
=====Free group 5=====
 +
  <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 +
  <vars>x1,x2,x3,x4,x5,y1,y2,y3,y4,y5</vars>
 +
  <basis>
 +
  <ncpoly>x1*y1-1</ncpoly>
 +
  <ncpoly>y1*x1-1</ncpoly>
 +
  <ncpoly>x2*y2-1</ncpoly>
 +
  <ncpoly>y2*x2-1</ncpoly>
 +
  <ncpoly>x3*y3-1</ncpoly>
 +
  <ncpoly>y3*x3-1</ncpoly>
 +
  <ncpoly>x4*y4-1</ncpoly>
 +
  <ncpoly>y4*x4-1</ncpoly>
 +
  <ncpoly>x5*y5-1</ncpoly>
 +
  <ncpoly>y5*x5-1</ncpoly>
 +
  </basis>
 +
  <Comment>Free_group_5</Comment>
 +
  </FREEALGEBRA>
 +
=====Free group 6=====
 +
  <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 +
  <vars>x1,x2,x3,x4,x5,x6,y1,y2,y3,y4,y5,y6</vars>
 +
  <basis>
 +
  <ncpoly>x1*y1-1</ncpoly>
 +
  <ncpoly>y1*x1-1</ncpoly>
 +
  <ncpoly>x2*y2-1</ncpoly>
 +
  <ncpoly>y2*x2-1</ncpoly>
 +
  <ncpoly>x3*y3-1</ncpoly>
 +
  <ncpoly>y3*x3-1</ncpoly>
 +
  <ncpoly>x4*y4-1</ncpoly>
 +
  <ncpoly>y4*x4-1</ncpoly>
 +
  <ncpoly>x5*y5-1</ncpoly>
 +
  <ncpoly>y5*x5-1</ncpoly>
 +
  <ncpoly>x6*y6-1</ncpoly>
 +
  <ncpoly>y6*x6-1</ncpoly>
 +
  </basis>
 +
  <Comment>Free_group_6</Comment>
 +
  </FREEALGEBRA>
 +
=====Free group 7=====
 +
  <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 +
  <vars>x1,x2,x3,x4,x5,x6,x7,y1,y2,y3,y4,y5,y6,y7</vars>
 +
  <basis>
 +
  <ncpoly>x1*y1-1</ncpoly>
 +
  <ncpoly>y1*x1-1</ncpoly>
 +
  <ncpoly>x2*y2-1</ncpoly>
 +
  <ncpoly>y2*x2-1</ncpoly>
 +
  <ncpoly>x3*y3-1</ncpoly>
 +
  <ncpoly>y3*x3-1</ncpoly>
 +
  <ncpoly>x4*y4-1</ncpoly>
 +
  <ncpoly>y4*x4-1</ncpoly>
 +
  <ncpoly>x5*y5-1</ncpoly>
 +
  <ncpoly>y5*x5-1</ncpoly>
 +
  <ncpoly>x6*y6-1</ncpoly>
 +
  <ncpoly>y6*x6-1</ncpoly>
 +
  <ncpoly>x7*y7-1</ncpoly>
 +
  <ncpoly>y7*x7-1</ncpoly>
 +
  </basis>
 +
  <Comment>Free_group_7</Comment>
 +
  </FREEALGEBRA>
 +
=====Free group 8=====
 +
  <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 +
  <vars>x1,x2,x3,x4,x5,x6,x7,x8,y1,y2,y3,y4,y5,y6,y7,y8</vars>
 +
  <basis>
 +
  <ncpoly>x1*y1-1</ncpoly>
 +
  <ncpoly>y1*x1-1</ncpoly>
 +
  <ncpoly>x2*y2-1</ncpoly>
 +
  <ncpoly>y2*x2-1</ncpoly>
 +
  <ncpoly>x3*y3-1</ncpoly>
 +
  <ncpoly>y3*x3-1</ncpoly>
 +
  <ncpoly>x4*y4-1</ncpoly>
 +
  <ncpoly>y4*x4-1</ncpoly>
 +
  <ncpoly>x5*y5-1</ncpoly>
 +
  <ncpoly>y5*x5-1</ncpoly>
 +
  <ncpoly>x6*y6-1</ncpoly>
 +
  <ncpoly>y6*x6-1</ncpoly>
 +
  <ncpoly>x7*y7-1</ncpoly>
 +
  <ncpoly>y7*x7-1</ncpoly>
 +
  <ncpoly>x8*y8-1</ncpoly>
 +
  <ncpoly>y8*x8-1</ncpoly>
 +
  </basis>
 +
  <Comment>Free_group_8</Comment>
 +
  </FREEALGEBRA>
 +
=====Free group 9=====
 +
  <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 +
  <vars>x1,x2,x3,x4,x5,x6,x7,x8,x9,y1,y2,y3,y4,y5,y6,y7,y8,y9</vars>
 +
  <basis>
 +
  <ncpoly>x1*y1-1</ncpoly>
 +
  <ncpoly>y1*x1-1</ncpoly>
 +
  <ncpoly>x2*y2-1</ncpoly>
 +
  <ncpoly>y2*x2-1</ncpoly>
 +
  <ncpoly>x3*y3-1</ncpoly>
 +
  <ncpoly>y3*x3-1</ncpoly>
 +
  <ncpoly>x4*y4-1</ncpoly>
 +
  <ncpoly>y4*x4-1</ncpoly>
 +
  <ncpoly>x5*y5-1</ncpoly>
 +
  <ncpoly>y5*x5-1</ncpoly>
 +
  <ncpoly>x6*y6-1</ncpoly>
 +
  <ncpoly>y6*x6-1</ncpoly>
 +
  <ncpoly>x7*y7-1</ncpoly>
 +
  <ncpoly>y7*x7-1</ncpoly>
 +
  <ncpoly>x8*y8-1</ncpoly>
 +
  <ncpoly>y8*x8-1</ncpoly>
 +
  <ncpoly>x9*y9-1</ncpoly>
 +
  <ncpoly>y9*x9-1</ncpoly>
 +
  </basis>
 +
  <Comment>Free_group_9</Comment>
 +
  </FREEALGEBRA>
 +
=====Free group 10=====
 +
  <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 +
  <vars>x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,y1,y2,y3,y4,y5,y6,y7,y8,y9,y10</vars>
 +
  <basis>
 +
  <ncpoly>x1*y1-1</ncpoly>
 +
  <ncpoly>y1*x1-1</ncpoly>
 +
  <ncpoly>x2*y2-1</ncpoly>
 +
  <ncpoly>y2*x2-1</ncpoly>
 +
  <ncpoly>x3*y3-1</ncpoly>
 +
  <ncpoly>y3*x3-1</ncpoly>
 +
  <ncpoly>x4*y4-1</ncpoly>
 +
  <ncpoly>y4*x4-1</ncpoly>
 +
  <ncpoly>x5*y5-1</ncpoly>
 +
  <ncpoly>y5*x5-1</ncpoly>
 +
  <ncpoly>x6*y6-1</ncpoly>
 +
  <ncpoly>y6*x6-1</ncpoly>
 +
  <ncpoly>x7*y7-1</ncpoly>
 +
  <ncpoly>y7*x7-1</ncpoly>
 +
  <ncpoly>x8*y8-1</ncpoly>
 +
  <ncpoly>y8*x8-1</ncpoly>
 +
  <ncpoly>x9*y9-1</ncpoly>
 +
  <ncpoly>y9*x9-1</ncpoly>
 +
  <ncpoly>x10*y10-1</ncpoly>
 +
  <ncpoly>y10*x10-1</ncpoly>
 +
  </basis>
 +
  <Comment>Free_group_10</Comment>
 +
  </FREEALGEBRA>
 +
=====Free group 11=====
 +
  <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 +
  <vars>x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,y1,y2,y3,y4,y5,y6,y7,y8,y9,y10,y11</vars>
 +
  <basis>
 +
  <ncpoly>x1*y1-1</ncpoly>
 +
  <ncpoly>y1*x1-1</ncpoly>
 +
  <ncpoly>x2*y2-1</ncpoly>
 +
  <ncpoly>y2*x2-1</ncpoly>
 +
  <ncpoly>x3*y3-1</ncpoly>
 +
  <ncpoly>y3*x3-1</ncpoly>
 +
  <ncpoly>x4*y4-1</ncpoly>
 +
  <ncpoly>y4*x4-1</ncpoly>
 +
  <ncpoly>x5*y5-1</ncpoly>
 +
  <ncpoly>y5*x5-1</ncpoly>
 +
  <ncpoly>x6*y6-1</ncpoly>
 +
  <ncpoly>y6*x6-1</ncpoly>
 +
  <ncpoly>x7*y7-1</ncpoly>
 +
  <ncpoly>y7*x7-1</ncpoly>
 +
  <ncpoly>x8*y8-1</ncpoly>
 +
  <ncpoly>y8*x8-1</ncpoly>
 +
  <ncpoly>x9*y9-1</ncpoly>
 +
  <ncpoly>y9*x9-1</ncpoly>
 +
  <ncpoly>x10*y10-1</ncpoly>
 +
  <ncpoly>y10*x10-1</ncpoly>
 +
  <ncpoly>x11*y11-1</ncpoly>
 +
  <ncpoly>y11*x11-1</ncpoly>
 +
  </basis>
 +
  <Comment>Free_group_11</Comment>
 +
  </FREEALGEBRA>

Latest revision as of 20:48, 22 April 2014

Description

The relations of a free group with n generators only consists of the existence of the invers elements. Any element of a free group has a unique representation.

 F(n) = <a_{1},...,a_{n} | a_{i}a_{i}^{-1} = a_{i}^{-1}a_{i} = 1>

Reference

Kharlampovich, Olga; Myasnikov, Alexei, "Elementary theory of free non-abelian groups". J. Algebra 302 (2): 451–552, 2006.

Computation

 /*Use the ApCoCoA package ncpoly.*/
 
 // Number of free group
 MEMORY.N:=4;
 
 Use ZZ/(2)[x[1..MEMORY.N],y[1..MEMORY.N]];
 NC.SetOrdering("LLEX");
 
 Define CreateRelationsFree()
   Relations:=[];
   For Index1 := 1 To MEMORY.N Do
     Append(Relations,[[x[Index1],y[Index1]],[1]]);
     Append(Relations,[[y[Index1],x[Index1]],[1]]);
   EndFor;
   Return Relations;
 EndDefine;
 
 Relations:=CreateRelationsFree();
 Relations;
 
 Gb:=NC.GB(Relations);
 Gb;

Examples in Symbolic Data Format

Free group 4
 <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 	<vars>x1,x2,x3,x4,y1,y2,y3,y4</vars>
 	<basis>
 	<ncpoly>x1*y1-1</ncpoly>
 	<ncpoly>y1*x1-1</ncpoly>
 	<ncpoly>x2*y2-1</ncpoly>
 	<ncpoly>y2*x2-1</ncpoly>
 	<ncpoly>x3*y3-1</ncpoly>
 	<ncpoly>y3*x3-1</ncpoly>
 	<ncpoly>x4*y4-1</ncpoly>
 	<ncpoly>y4*x4-1</ncpoly>
 	</basis>
 	<Comment>Free_group_4</Comment>
 </FREEALGEBRA>
Free group 5
 <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 	<vars>x1,x2,x3,x4,x5,y1,y2,y3,y4,y5</vars>
 	<basis>
 	<ncpoly>x1*y1-1</ncpoly>
 	<ncpoly>y1*x1-1</ncpoly>
 	<ncpoly>x2*y2-1</ncpoly>
 	<ncpoly>y2*x2-1</ncpoly>
 	<ncpoly>x3*y3-1</ncpoly>
 	<ncpoly>y3*x3-1</ncpoly>
 	<ncpoly>x4*y4-1</ncpoly>
 	<ncpoly>y4*x4-1</ncpoly>
 	<ncpoly>x5*y5-1</ncpoly>
 	<ncpoly>y5*x5-1</ncpoly>
 	</basis>
 	<Comment>Free_group_5</Comment>
 </FREEALGEBRA>
Free group 6
 <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 	<vars>x1,x2,x3,x4,x5,x6,y1,y2,y3,y4,y5,y6</vars>
 	<basis>
 	<ncpoly>x1*y1-1</ncpoly>
 	<ncpoly>y1*x1-1</ncpoly>
 	<ncpoly>x2*y2-1</ncpoly>
 	<ncpoly>y2*x2-1</ncpoly>
 	<ncpoly>x3*y3-1</ncpoly>
 	<ncpoly>y3*x3-1</ncpoly>
 	<ncpoly>x4*y4-1</ncpoly>
 	<ncpoly>y4*x4-1</ncpoly>
 	<ncpoly>x5*y5-1</ncpoly>
 	<ncpoly>y5*x5-1</ncpoly>
 	<ncpoly>x6*y6-1</ncpoly>
 	<ncpoly>y6*x6-1</ncpoly>
 	</basis>
 	<Comment>Free_group_6</Comment>
 </FREEALGEBRA>
Free group 7
 <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 	<vars>x1,x2,x3,x4,x5,x6,x7,y1,y2,y3,y4,y5,y6,y7</vars>
 	<basis>
 	<ncpoly>x1*y1-1</ncpoly>
 	<ncpoly>y1*x1-1</ncpoly>
 	<ncpoly>x2*y2-1</ncpoly>
 	<ncpoly>y2*x2-1</ncpoly>
 	<ncpoly>x3*y3-1</ncpoly>
 	<ncpoly>y3*x3-1</ncpoly>
 	<ncpoly>x4*y4-1</ncpoly>
 	<ncpoly>y4*x4-1</ncpoly>
 	<ncpoly>x5*y5-1</ncpoly>
 	<ncpoly>y5*x5-1</ncpoly>
 	<ncpoly>x6*y6-1</ncpoly>
 	<ncpoly>y6*x6-1</ncpoly>
 	<ncpoly>x7*y7-1</ncpoly>
 	<ncpoly>y7*x7-1</ncpoly>
 	</basis>
 	<Comment>Free_group_7</Comment>
 </FREEALGEBRA>
Free group 8
 <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 	<vars>x1,x2,x3,x4,x5,x6,x7,x8,y1,y2,y3,y4,y5,y6,y7,y8</vars>
 	<basis>
 	<ncpoly>x1*y1-1</ncpoly>
 	<ncpoly>y1*x1-1</ncpoly>
 	<ncpoly>x2*y2-1</ncpoly>
 	<ncpoly>y2*x2-1</ncpoly>
 	<ncpoly>x3*y3-1</ncpoly>
 	<ncpoly>y3*x3-1</ncpoly>
 	<ncpoly>x4*y4-1</ncpoly>
 	<ncpoly>y4*x4-1</ncpoly>
 	<ncpoly>x5*y5-1</ncpoly>
 	<ncpoly>y5*x5-1</ncpoly>
 	<ncpoly>x6*y6-1</ncpoly>
 	<ncpoly>y6*x6-1</ncpoly>
 	<ncpoly>x7*y7-1</ncpoly>
 	<ncpoly>y7*x7-1</ncpoly>
 	<ncpoly>x8*y8-1</ncpoly>
 	<ncpoly>y8*x8-1</ncpoly>
 	</basis>
 	<Comment>Free_group_8</Comment>
 </FREEALGEBRA>
Free group 9
 <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 	<vars>x1,x2,x3,x4,x5,x6,x7,x8,x9,y1,y2,y3,y4,y5,y6,y7,y8,y9</vars>
 	<basis>
 	<ncpoly>x1*y1-1</ncpoly>
 	<ncpoly>y1*x1-1</ncpoly>
 	<ncpoly>x2*y2-1</ncpoly>
 	<ncpoly>y2*x2-1</ncpoly>
 	<ncpoly>x3*y3-1</ncpoly>
 	<ncpoly>y3*x3-1</ncpoly>
 	<ncpoly>x4*y4-1</ncpoly>
 	<ncpoly>y4*x4-1</ncpoly>
 	<ncpoly>x5*y5-1</ncpoly>
 	<ncpoly>y5*x5-1</ncpoly>
 	<ncpoly>x6*y6-1</ncpoly>
 	<ncpoly>y6*x6-1</ncpoly>
 	<ncpoly>x7*y7-1</ncpoly>
 	<ncpoly>y7*x7-1</ncpoly>
 	<ncpoly>x8*y8-1</ncpoly>
 	<ncpoly>y8*x8-1</ncpoly>
 	<ncpoly>x9*y9-1</ncpoly>
 	<ncpoly>y9*x9-1</ncpoly>
 	</basis>
 	<Comment>Free_group_9</Comment>
 </FREEALGEBRA>
Free group 10
 <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 	<vars>x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,y1,y2,y3,y4,y5,y6,y7,y8,y9,y10</vars>
 	<basis>
 	<ncpoly>x1*y1-1</ncpoly>
 	<ncpoly>y1*x1-1</ncpoly>
 	<ncpoly>x2*y2-1</ncpoly>
 	<ncpoly>y2*x2-1</ncpoly>
 	<ncpoly>x3*y3-1</ncpoly>
 	<ncpoly>y3*x3-1</ncpoly>
 	<ncpoly>x4*y4-1</ncpoly>
 	<ncpoly>y4*x4-1</ncpoly>
 	<ncpoly>x5*y5-1</ncpoly>
 	<ncpoly>y5*x5-1</ncpoly>
 	<ncpoly>x6*y6-1</ncpoly>
 	<ncpoly>y6*x6-1</ncpoly>
 	<ncpoly>x7*y7-1</ncpoly>
 	<ncpoly>y7*x7-1</ncpoly>
 	<ncpoly>x8*y8-1</ncpoly>
 	<ncpoly>y8*x8-1</ncpoly>
 	<ncpoly>x9*y9-1</ncpoly>
 	<ncpoly>y9*x9-1</ncpoly>
 	<ncpoly>x10*y10-1</ncpoly>
 	<ncpoly>y10*x10-1</ncpoly>
 	</basis>
 	<Comment>Free_group_10</Comment>
 </FREEALGEBRA>
Free group 11
 <FREEALGEBRA createdAt="2014-03-02" createdBy="strohmeier">
 	<vars>x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,y1,y2,y3,y4,y5,y6,y7,y8,y9,y10,y11</vars>
 	<basis>
 	<ncpoly>x1*y1-1</ncpoly>
 	<ncpoly>y1*x1-1</ncpoly>
 	<ncpoly>x2*y2-1</ncpoly>
 	<ncpoly>y2*x2-1</ncpoly>
 	<ncpoly>x3*y3-1</ncpoly>
 	<ncpoly>y3*x3-1</ncpoly>
 	<ncpoly>x4*y4-1</ncpoly>
 	<ncpoly>y4*x4-1</ncpoly>
 	<ncpoly>x5*y5-1</ncpoly>
 	<ncpoly>y5*x5-1</ncpoly>
 	<ncpoly>x6*y6-1</ncpoly>
 	<ncpoly>y6*x6-1</ncpoly>
 	<ncpoly>x7*y7-1</ncpoly>
 	<ncpoly>y7*x7-1</ncpoly>
 	<ncpoly>x8*y8-1</ncpoly>
 	<ncpoly>y8*x8-1</ncpoly>
 	<ncpoly>x9*y9-1</ncpoly>
 	<ncpoly>y9*x9-1</ncpoly>
 	<ncpoly>x10*y10-1</ncpoly>
 	<ncpoly>y10*x10-1</ncpoly>
 	<ncpoly>x11*y11-1</ncpoly>
 	<ncpoly>y11*x11-1</ncpoly>
 	</basis>
 	<Comment>Free_group_11</Comment>
 </FREEALGEBRA>