กลับไปหน้าบทความ

อ่าน 6 นาที

ไม่มีชื่อบทความ

ทฤษฎีบทของเบิร์นไซด์ บางครั้งเรียกว่า ทฤษฎีบทการนับของเบิร์นไซด์ ทฤษฎีบท โค ชี-โฟรเบนิ อุส หรือ ทฤษฎีบทการนับวงโคจร เป็นผลลัพธ์ใน ทฤษฎีกลุ่ม ที่มักมีประโยชน์ในการพิจารณา สมมาตร...

บทพิสูจน์ของเบิร์นไซด์

ทฤษฎีบทของเบิร์นไซด์บางครั้งเรียกว่าทฤษฎีบทการนับของเบิร์นไซด์ ทฤษฎีบท โคชี-โฟรเบนิ อุส หรือทฤษฎีบทการนับวงโคจรเป็นผลลัพธ์ในทฤษฎีกลุ่มที่มักมีประโยชน์ในการพิจารณาสมมาตรเมื่อนับวัตถุทางคณิตศาสตร์ ทฤษฎีบทนี้ถูกค้นพบโดยออกัสติน หลุยส์ โคชีและเฟอร์ดินานด์ จอร์จ โฟรเบนิอุสและเป็นที่รู้จักกันดีหลังจากวิลเลียม เบิร์นไซด์อ้างถึง[ 1 ]ผลลัพธ์นี้แจกแจงวงโคจรของกลุ่มสมมาตรที่กระทำต่อวัตถุบางอย่าง กล่าวคือ มันนับวัตถุที่แตกต่างกัน โดยพิจารณาวัตถุที่สมมาตรกันเป็นสิ่งเดียวกัน หรือนับวัตถุที่แตกต่างกันจนถึงความสัมพันธ์สมมูลสมมาตรหรือนับเฉพาะวัตถุในรูปแบบมาตรฐานตัวอย่างเช่น ในการอธิบายสารประกอบอินทรีย์ที่เป็นไปได้ของบางประเภท เราจะพิจารณาสารประกอบเหล่านั้นจนถึงสมมาตรการหมุนเชิงพื้นที่ ภาพวาดที่หมุนต่างกันของโมเลกุลที่กำหนดจะเหมือนกันทางเคมี (ในขณะที่ภาพสะท้อนอาจให้สารประกอบที่แตกต่างกัน )

คำแถลง

อนุญาตจี{\displaystyle G}เป็นกลุ่มจำกัด ที่กระทำต่อเซตX{\displaystyle X}สำหรับแต่ละจี{\displaystyle g}ในจี{\displaystyle G}, อนุญาตXจี{\displaystyle X^{g}}แทนเซตขององค์ประกอบในX{\displaystyle X}ที่ได้รับการแก้ไขโดยจี{\displaystyle g}( ไม่เปลี่ยนแปลง ทางซ้าย โดย)จี{\displaystyle g}): นั่นคือXจี={xX:จีx=x}.{\displaystyle X^{g}=\{x\in X:g\cdot x=x\}.} ทฤษฎีบทของเบิร์นไซด์ยืนยันสูตรต่อไปนี้สำหรับจำนวนวงโคจรซึ่งแสดงด้วยสัญลักษณ์|X/จี|{\displaystyle |X/G|}: [ 2 ]

|X/จี|=1|จี|จีจี|Xจี|.{\displaystyle |X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|.}

ดังนั้น จำนวนวงโคจร ( จำนวนธรรมชาติหรือ+∞ ) จึงเท่ากับ จำนวนจุด เฉลี่ยที่ถูกตรึงโดยสมาชิกของGสำหรับกลุ่มอนันต์จี{\displaystyle G}ยังคงมีการจับคู่แบบหนึ่งต่อหนึ่ง อยู่ :

จี×X/จี  จีจีXจี.{\displaystyle G\times X/G\ \longleftrightarrow \ \coprod _{g\in G}X^{g}.}

ตัวอย่าง

สร้อยคอ

มีสตริงบิต ที่เป็นไปได้ 8 แบบ ที่มีความยาว 3 แต่เมื่อนำปลายสตริงมาต่อกัน จะได้สร้อยคอ สองสี ที่มีความยาว 3 เพียงสี่แบบที่แตกต่างกัน ซึ่งกำหนดโดยรูปแบบมาตรฐาน 000, 001, 011, 111: สตริงอื่นๆ เช่น 100 และ 010 จะเทียบเท่ากับ 001 โดยการหมุน ในขณะที่ 110 และ 101 จะเทียบเท่ากับ 011 กล่าวคือ ความเท่าเทียมกันของการหมุนจะแบ่งเซตออกเป็นสองส่วนX{\displaystyle X}ของสายต่างๆ ออกเป็นสี่วงโคจร:X={000}{001,010,100}{011,101,110}{111}.{\displaystyle X=\{{000}\}\cup \{{001},{010},{100}\}\cup \{{011},{101},{110}\}\cup \{{111}\}.}สูตรของเบิร์นไซด์ใช้จำนวนการหมุน ซึ่งคือ 3 ครั้ง รวมทั้งการหมุนศูนย์ และจำนวนสตริงบิตที่ยังคงไม่เปลี่ยนแปลงจากการหมุนแต่ละครั้ง เวกเตอร์ทั้งแปดตัวไม่เปลี่ยนแปลงจากการหมุนศูนย์ และสองตัว (000 และ 111) ไม่เปลี่ยนแปลงจากการหมุนอีกสองครั้ง ดังนั้นจำนวนวงโคจรคือ: 4=13(8+2+2).{\displaystyle 4={\frac {1}{3}}(8+2+2).}

สำหรับความยาว 4 จะมีสตริงบิตที่เป็นไปได้ 16 แบบ; มีการหมุน 4 แบบ; การหมุนแบบศูนย์จะไม่เปลี่ยนแปลงสตริงทั้ง 16 แบบ; การหมุน 1 รอบและการหมุน 3 รอบแต่ละแบบจะไม่เปลี่ยนแปลงสตริงสองแบบ (0000 และ 1111); การหมุน 2 รอบจะไม่เปลี่ยนแปลงสตริงบิต 4 แบบ (0000, 0101, 1010, 1111) ดังนั้นจำนวนสร้อยคอที่แตกต่างกันจึงเป็นดังนี้:6=14(16+2+4+2){\displaystyle 6={\tfrac {1}{4}}(16+2+4+2)}ซึ่งแสดงโดยรูปแบบมาตรฐาน 0000, 0001, 0011, 0101, 0111, 1111

กรณีทั่วไปของข้อมูลnบิตและkสี จะแสดงด้วยพหุนามสร้อยคอ

การระบายสีลูกบาศก์

ทฤษฎีบทของเบิร์นไซด์สามารถคำนวณจำนวนการระบายสีที่แตกต่างกันโดยการหมุนของหน้าลูกบาศก์โดยใช้สีสามสีได้

อนุญาตX{\displaystyle X}เป็นเซตของการผสมสีหน้าที่เป็นไปได้ 3 6แบบ ที่สามารถนำไปใช้กับลูกบาศก์คงที่ และให้กลุ่มการหมุนGของลูกบาศก์กระทำต่อเซตดังกล่าวX{\displaystyle X}โดยการขยับหน้าสี: การระบายสีสองแบบในX{\displaystyle X}ทั้งสองกลุ่มจะอยู่ในวงโคจรเดียวกันก็ต่อเมื่อกลุ่มหนึ่งเป็นการหมุนของอีกกลุ่มหนึ่งเท่านั้น การระบายสีที่แตกต่างกันตามการหมุนจะสอดคล้องกับวงโคจรของกลุ่ม และสามารถหาได้โดยการนับขนาดของเซตคงที่สำหรับองค์ประกอบทั้ง 24 ของGซึ่งเป็นการระบายสีที่ไม่เปลี่ยนแปลงในแต่ละการหมุน:

ลูกบาศก์ที่มีหน้าสีต่างๆ
  • องค์ประกอบเอกลักษณ์จะกำหนดค่าสีทั้ง 3 และ 6สี
  • การหมุนใบหน้า 90 องศาจำนวนหกครั้ง โดยแต่ละครั้งจะแก้ไขการระบายสี 3 3 ครั้ง
  • การหมุนใบหน้า 180 องศา 3 ครั้ง โดยแต่ละครั้งแก้ไขการระบายสี 3 และ 4สี
  • การหมุนจุดยอด 120 องศาแปดครั้ง โดยแต่ละครั้งจะกำหนดค่าสี 3 2 ค่า
  • การหมุนขอบ 180 องศาจำนวนหกครั้งแต่ละครั้งจะแก้ไขการระบายสี 3 3สี

สามารถดูรายละเอียดการตรวจสอบได้ ที่นี่

ดังนั้นขนาดชุดคงที่โดยเฉลี่ยจึงเป็นดังนี้:

|X/จี|=124(36+633+334+832+633)=57.{\displaystyle |X/G|={\frac {1}{24}}\left(3^{6}+6\cdot 3^{3}+3\cdot 3^{4}+8\cdot 3^{2}+6\cdot 3^{3}\right)=57.}

มีวิธีการระบายสีหน้าของลูกบาศก์สามสีที่แตกต่างกันโดยการหมุน 57 วิธี โดยทั่วไปแล้ว จำนวนวิธีการระบายสีหน้าของลูกบาศก์ที่มีnสีที่แตกต่างกันโดยการหมุน คือ:

124(n6+3n4+12n3+8n2).{\displaystyle {\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right).}

คลาสการผันคำกริยา

อนุญาตจี{\displaystyle G}เป็นกลุ่มจำกัด พิจารณาการกระทำของกลุ่มจี{\displaystyle G}โดยตัวมันเองกำหนดโดยแผนที่การผันคำกริยาจีϕจี{\displaystyle g\mapsto \phi _{g}}ที่ไหนϕจี(ชม.)=จีชม.จี1{\displaystyle \phi _{g}(h)=ghg^{-1}}วงโคจรเหล่านี้คือชั้นการสมมูลของจี{\displaystyle G}และเซตของจุดคงที่ขององค์ประกอบจี{\displaystyle g}คือตัวรวมศูนย์ซีจี(จี){\displaystyle C_{G}(g)}ดังนั้น ตามทฤษฎีบทของเบิร์นไซด์ จำนวนชั้นสมมูลของจี{\displaystyle G}เท่ากับ1|จี|จี|ซีจี(จี)|{\displaystyle {\frac {1}{|G|}}\sum _{g}|C_{G}(g)|}นั่นคือ ขนาดเฉลี่ยของตัวจัดตำแหน่งศูนย์กลาง

การพิสูจน์

ในการพิสูจน์ทฤษฎีบทของเบิร์นไซด์ ขั้นตอนแรกคือการแสดงผลรวมของสมาชิกกลุ่มg G ใหม่ ให้เป็นผลรวมที่เทียบเท่ากันของเซตของสมาชิกxX :   

จีจี|Xจี|=#{(จี,x)จี×Xจีx=x}=xX|จีx|.{\displaystyle \sum _{g\in G}|X^{g}|=\#\{(g,x)\in G\times X\mid g\cdot x=x\}=\sum _{x\in X}|G_{x}|.}

ที่นี่Xจี={xX:จีx=x}{\displaystyle X^{g}=\{x\in X:g\cdot x=x\}}คือเซตของจุดของX{\displaystyle X}ถูกกำหนดโดยองค์ประกอบจี{\displaystyle g}ของจี{\displaystyle G}, ในทางตรงกันข้ามจีx={จีจี:จีx=x}{\displaystyle G_{x}=\{g\in G:g\cdot x=x\}}เป็นกลุ่มย่อยที่มีเสถียรภาพของจี{\displaystyle G}ซึ่งประกอบด้วยสมมาตรเหล่านั้นที่ตรึงจุดไว้xX{\displaystyle x\in X}.

ทฤษฎีการรักษาเสถียรภาพวงโคจรกล่าวว่า สำหรับแต่ละxX{\displaystyle x\in X}มีการจับคู่แบบหนึ่งต่อ หนึ่งตามธรรมชาติ ระหว่างวงโคจรจีx={จีx:จีจี}{\displaystyle G\cdot x=\{g\cdot x:g\in G\}}และเซตของโคเซตซ้ายจี/จีx{\displaystyle G/G_{x}}ทฤษฎีบทของลากรองจ์บ่งชี้ ว่า

|จีx|=[จี:จีx]=|จี|/|จีx|.{\displaystyle |G\cdot x|=[G:G_{x}]=|G|/|G_{x}|.}

ดังนั้น ผลรวมจึงสามารถเขียนใหม่ได้ดังนี้

xX|จีx|=xX|จี||จีx|=|จี|xX1|จีx|.{\displaystyle \sum _{x\in X}|G_{x}|=\sum _{x\in X}{\frac {|G|}{|G\cdot x|}}=|G|\sum _{x\in X}{\frac {1}{|G\cdot x|}}.}

การเขียนX{\displaystyle X}เป็นการรวมกันที่ไม่ต่อเนื่องของวงโคจรในX/จี{\displaystyle X/G}ให้

|จี|xX1|จีx|=|จี|เอX/จีxเอ1|เอ|=|จี|เอX/จี1=|จี||X/จี|.{\displaystyle |G|\sum _{x\in X}{\frac {1}{|G\cdot x|}}=|G|\sum _{A\in X/G}\sum _{x\in A}{\frac {1}{|A|}}=|G|\sum _{A\in X/G}1=|G|\cdot |X/G|.}

เมื่อนำทุกอย่างมารวมกัน จะได้ผลลัพธ์ที่ต้องการ:

จีจี|Xจี|=|จี||X/จี|.{\displaystyle \sum _{g\in G}|X^{g}|=|G|\cdot |X/G|.}

นี่คล้ายกับการพิสูจน์สมการชั้นการสมมูลซึ่งพิจารณาการกระทำการสมมูลของจี{\displaystyle G}โดยตัวมันเอง นั่นคือ เป็นเช่นนั้นX=จี{\displaystyle X=G}และจีx=จีxจี1{\displaystyle g\cdot x=gxg^{-1}}ดังนั้นตัวกันสั่นของx{\displaystyle x}คือตัวรวมศูนย์จีx=จี(x){\displaystyle G_{x}=Z_{G}(x)}.

การแจงนับเทียบกับการสร้าง

ทฤษฎีบทของเบิร์นไซด์นับจำนวนวัตถุที่แตกต่างกัน แต่ไม่ได้สร้างวัตถุเหล่านั้นขึ้นมา โดยทั่วไป การสร้างเชิงการจัดเรียงที่มีการปฏิเสธไอโซมอร์ฟจะพิจารณาสมมาตรของจี{\displaystyle g}บนวัตถุx{\displaystyle x}แต่แทนที่จะตรวจสอบว่าจีx=x{\displaystyle g\cdot x=x}มันจะตรวจสอบว่าจีx{\displaystyle g\cdot x}ยังไม่ได้ถูกสร้างขึ้น วิธีหนึ่งในการทำเช่นนี้คือการตรวจสอบว่าจีx{\displaystyle g\cdot x}ไม่น้อยกว่าในเชิงพจนานุกรมx{\displaystyle x}โดยใช้สมาชิกที่น้อยที่สุดตามลำดับตัวอักษรของแต่ละคลาสสมมูลเป็นรูปแบบมาตรฐานของคลาส[ 3 ]การนับวัตถุที่สร้างขึ้นด้วยเทคนิคดังกล่าวสามารถตรวจสอบได้ว่าบทพิสูจน์ของ Burnside ถูกนำไปใช้อย่างถูกต้อง

ประวัติศาสตร์: บทพิสูจน์ที่ไม่ใช่ของเบิร์นไซด์

วิลเลียม เบิร์นไซด์กล่าวและพิสูจน์บทพิสูจน์นี้ในหนังสือเกี่ยวกับกลุ่มจำกัดของเขาในปี 1897 โดยอ้างอิงถึงฟรอเบนิอุสในปี 1887แต่แม้กระทั่งก่อนฟรอเบนิอุส สูตรนี้ก็เป็นที่รู้จักของคอชีในปี 1845 ดังนั้น บทพิสูจน์นี้จึงบางครั้งถูกเรียกว่าบทพิสูจน์ที่ไม่ใช่ของเบิร์นไซด์ [ 4 ] การอ้างอิงบทพิสูจน์ไปยังบุคคลอื่นที่ไม่ใช่ผู้ค้นพบดั้งเดิมเป็นตัวอย่างของกฎของสติกล์เลอร์เกี่ยวกับการตั้งชื่อตามบุคคล

ดูเพิ่มเติม

หมายเหตุ

  1. เบิร์นไซด์ 1897 , §119
  2. ร็อตแมน 1995 บทที่ 3
  3. Cull, Paul; Pandey, Rajeev (1994). "Isomorphism and the N-Queens problem" . ACM SIGCSE Bulletin . 26 (3): 29– 36. doi : 10.1145/187387.187400 . S2CID 207183291 . 
  4. Neumann, Peter M. (1979). "บทพิสูจน์ย่อยที่ไม่ใช่ของ Burnside". The Mathematical Scientist . 4 (2): 133– 141. ISSN 0312-3685 . MR 0562002 .  .

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ไม่มีชื่อบทความ

ทฤษฎีบทของเบิร์นไซด์ บางครั้งเรียกว่า ทฤษฎีบทการนับของเบิร์นไซด์ ทฤษฎีบท โค ชี-โฟรเบนิ อุส หรือ ทฤษฎีบทการนับวงโคจร เป็นผลลัพธ์ใน ทฤษฎีกลุ่ม ที่มักมีประโยชน์ในการพิจารณา สมมาตร...

คำแถลง

อนุญาต จี {\displaystyle G} เป็น กลุ่ม จำกัด ที่ กระทำ ต่อ เซต X {\displaystyle X} สำหรับแต่ละ จี {\displaystyle g} ใน จี {\displaystyle G} , อนุญาต X จี {\displaystyle X^{g}} แทนเซตของ องค์ประกอบ ใน X {\displaystyle X} ที่ได้ รับการแก้ไขโดย จี {\displaystyle...

สร้อยคอ

มี สตริงบิต ที่เป็นไปได้ 8 แบบ ที่มีความยาว 3 แต่เมื่อนำปลายสตริงมาต่อกัน จะได้ สร้อยคอ สองสี ที่มีความยาว 3 เพียงสี่แบบที่แตกต่างกัน ซึ่งกำหนดโดยรูปแบบมาตรฐาน 000, 001, 011, 111: สตริงอื่นๆ เช่น 100 และ 010 จะเทียบเท่ากับ 001 โดยการหมุน ในขณะที่ 110 และ 101...

การระบายสีลูกบาศก์

ทฤษฎีบทของเบิร์นไซด์สามารถคำนวณจำนวนการระบายสีที่แตกต่างกันโดยการหมุนของหน้าลูกบาศก์ โดย ใช้สีสามสีได้