การนับองค์ประกอบของความยาวที่กำหนดในกลุ่มผ่าน GAP

Question

ฉันมีกลุ่ม G ที่นำเสนออย่างละเอียดใน GAP ตัวอย่างเช่นเครื่องกำเนิดไฟฟ้าและความสัมพันธ์ต่อไปนี้: เครื่องกำเนิดไฟฟ้า = $[ f1, f2, f3, f4 ]$ รีเลเตอร์ = $[ f1^2, f2^2, f3^2, f4^2, (f3*f2)^2, (f2*f1)^3, (f1*f4)^3, (f3*f1)^3, (f4*f3)^3, (f2*f4)^3 ]$

คำถาม: ฉันจะนับจำนวนองค์ประกอบ G ที่มีความยาวเท่ากับ $i$ (ซึ่งหมายความว่าองค์ประกอบนั้นเป็นผลิตภัณฑ์ที่ไม่ใช่ศูนย์ใน G ของทุกประการ $i$ เครื่องกำเนิดไฟฟ้า $f_i$ อย่างน้อยที่สุด)?

Answer 1

สิ่งนี้ไม่สามารถทำได้สำหรับกลุ่มที่นำเสนออย่างละเอียดโดยทั่วไปเนื่องจากมีกลุ่มที่มีปัญหาเกี่ยวกับคำที่ไม่สามารถตัดสินใจได้ แต่สำหรับกลุ่มที่นำเสนอแบบไม่มีที่สิ้นสุดซึ่งอาจเป็น shortlex อัตโนมัติหรือมีระบบการเขียนซ้ำที่สมบูรณ์คุณสามารถใช้แพ็คเกจ KBMAG เพื่อทำสิ่งนี้ได้

นี่คือตัวอย่างง่ายๆสำหรับกลุ่ม Coxeter ที่ไม่มีที่สิ้นสุด

gap> LoadPackage("kbmag");
true
gap> F := FreeGroup(3);;
gap> G := F/[F.1^2, F.2^2, F.3^2, (F.1*F.2)^2, (F.1*F.3)^3, (F.2*F.3)^7];;
gap> R := KBMAGRewritingSystem(G);;
gap> A := AutomaticStructure(R);;

คุณสามารถใช้ฟังก์ชัน $\mathsf{EnumerateReducedWords}$เพื่อแสดงรายการ shortlex ตัวแทนอย่างน้อยขององค์ประกอบกลุ่มที่มีความยาวที่ระบุ ตัวอย่างเช่น

gap> Length(EnumerateReducedWords(R,0,3));
16
gap> Length(EnumerateReducedWords(R,4,4));
9

บอกเราว่ามี 16 องค์ประกอบของความยาว 0 ถึง 3 และ 9 องค์ประกอบของความยาวเท่ากับ 4

คุณยังสามารถคำนวณฟังก์ชันการเติบโตที่แน่นอนของกลุ่มเป็นฟังก์ชันเชิงเหตุผล

gap> GrowthFunction(R);
(x_1^10+4*x_1^9+8*x_1^8+11*x_1^7+12*x_1^6+12*x_1^5+12*x_1^4+11*x_1^3+8*x_1^2+4\
*x_1+1)/(x_1^10+x_1^9-x_1^7-x_1^6-x_1^5-x_1^4-x_1^3+x_1+1)

ค่าสัมประสิทธิ์ $a_n$ ของส่วนขยายชุดเทย์เลอร์ $\sum_{n=0}^\infty a_nx^n$ ซึ่งจะให้จำนวนองค์ประกอบของความยาว $n$แต่ฉันไม่รู้ว่า GAP มีฟังก์ชันคำนวณการขยายซีรีส์หรือไม่

Answer 2

หากกลุ่มของคุณมีขนาดเล็กพอ (ตามตัวอย่าง) และคุณสามารถแปลงเป็นกลุ่มการเปลี่ยนแปลงได้คุณสามารถใช้GrowthFunctionOfGroup:

gap> p:=Image(IsomorphismPermGroup(G));
Group([ (2,3)(4,5)(6,8), (1,2)(5,7)(8,9), (2,4)(3,5)(9,10), (4,6)(5,8)(7,9) ])
gap> GrowthFunctionOfGroup(p);
[ 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1 ]

ดังนั้นจึงมี 4 องค์ประกอบของความยาว 1, 9 ของความยาว 2 และอื่น ๆ

หากกลุ่มมีขนาดใหญ่ขึ้นมาก (ดังนั้นการจัดเก็บองค์ประกอบจึงทำได้ยาก) หรือแม้แต่ไม่มีที่สิ้นสุดนี่เป็นปัญหาที่หนักกว่ามาก