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

อ่าน 3 นาที

โมโนอิดพลาสติก

ข้อผิดพลาด CS1: ไม่มีชื่อ/การรวมกันกับคำ/ทฤษฎีเซมิกรุ๊ป

ในทางคณิตศาสตร์ พลาติกโมโนอิด (plactic monoid) คือโมโนอิดของคำทั้งหมดในอักษรของจำนวนเต็มบวก โดยพิจารณาโมดูลัสความสมมูลของคนุธ( Knuth equivalence )...

โมโนอิดพลาสติก

ในทางคณิตศาสตร์ พลาติกโมโนอิด (plactic monoid) คือโมโนอิดของคำทั้งหมดในอักษรของจำนวนเต็มบวก โดยพิจารณาโมดูลัสความสมมูลของคนุธ( Knuth equivalence ) องค์ประกอบของมันสามารถระบุได้ด้วยตารางยัง (Young tableaux ) กึ่งมาตรฐาน มันถูกค้นพบโดยโดนัลด์ คนุธ ( Donald Knuth ) ( 1970 ) (ซึ่งเรียกมันว่าพีชคณิตตาราง ) โดยใช้การดำเนินการที่เสนอโดยเครกเชนสเตด( Craige Schensted) ( 1961 )ในการศึกษาลำดับย่อยที่เพิ่มขึ้นยาวที่สุดของการเรียงสับเปลี่ยน  

Lascoux & Schützenberger (1981)ตั้งชื่อว่า " monoïde plaxique " โดยอนุญาตให้ใช้อักษรที่มีลำดับสมบูรณ์ใดๆ ก็ได้ในคำจำกัดความ ที่มาของคำว่า " plaxique " นั้นไม่ชัดเจน อาจหมายถึงธรณีแปรสัณฐาน ("tectonique des plaques" ในภาษาฝรั่งเศส) เนื่องจากความสัมพันธ์พื้นฐานที่สร้างความเท่าเทียมกัน นั้น อนุญาตให้มีการสลับตำแหน่งแบบมีเงื่อนไขของสัญลักษณ์ตัวสร้าง: พวกมันสามารถเลื่อนผ่านกันได้ในบางครั้ง (ในลักษณะที่คล้ายกับแผ่นเปลือกโลก) แต่ไม่ใช่โดยอิสระ

คำนิยาม

โมโนอิดแบบพลาสติกเหนือตัวอักษรที่มีลำดับสมบูรณ์ (มักเป็นจำนวนเต็มบวก) คือโมโนอิดที่มีการนำเสนอ ในรูปแบบต่อไปนี้ :

  • ตัวสร้างคือตัวอักษรในภาษาอังกฤษ
  • ความสัมพันธ์ดังกล่าวคือการแปลง Knuth ขั้นพื้นฐานyzx yxzเมื่อใดก็ตามที่x < y zและxzyzxyเมื่อใดก็ตามที่x y < z           

ความเท่าเทียมกันของ Knuth

คำสองคำจะเรียกว่าเทียบเท่ากันตามหลัก Knuthหากคำทั้งสองนั้นแสดงถึงองค์ประกอบเดียวกันของโมโนอิดแบบพลาสติก หรือกล่าวอีกนัยหนึ่งคือ หากคำหนึ่งสามารถได้มาจากอีกคำหนึ่งโดยลำดับของการแปลง Knuth ขั้นพื้นฐาน

คุณสมบัติหลายประการได้รับการรักษาไว้โดยหลักสมดุลของ Knuth

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

การติดต่อกับตาราง Young กึ่งมาตรฐาน

การคูณองค์ประกอบที่มีรูปแบบตาราง (38)(1257) กับตัวสร้าง 4 ซึ่งแสดงโดยใช้สัญกรณ์ตารางของ Young: • โดยใช้ความสัมพันธ์แบบพลาสติก (1257)*4 = 5*(1247) • (38)*5 = 8*(35) ดังนั้น (5) แทนที่ (8) ในแถวที่สอง • (8) สร้างแถวที่สาม • ผลคูณจึงมีรูปแบบตาราง (8)(35)(1247)

ทุกคำมีค่าเทียบเท่าแบบ Knuth กับคำในตาราง Young กึ่งมาตรฐานที่ไม่ซ้ำ กัน (ซึ่งหมายความว่าแต่ละแถวไม่ลดลงและแต่ละคอลัมน์เพิ่มขึ้นอย่างเคร่งครัด) บนตัวอักษรเรียงลำดับเดียวกัน โดยที่ตารางนั้นสามารถอ่านได้ทีละแถวหรือทีละคอลัมน์ ดังนั้นองค์ประกอบของโมโนอิดแบบพลาสติกจึงสามารถระบุได้กับตาราง Young กึ่งมาตรฐาน ซึ่งจึงก่อตัวเป็นโมโนอิดเช่นกัน

การคูณคำในตาราง Young กึ่งมาตรฐานทางด้านขวาด้วยตัวสร้าง (generator) เทียบเท่ากับการแทรกแบบ Schenstedลงในตาราง Young ตามลำดับแถว คำในตารางจะเทียบเท่ากับผลคูณของลำดับตัวสร้างที่ไม่ลดลงซึ่งยาวขึ้นเรื่อยๆ สามารถแทรกตัวสร้างใหม่ในตำแหน่งที่เหมาะสมได้โดยการเพิ่มต่อท้ายหากมีขนาดใหญ่กว่า หรือโดยการใช้ความสัมพันธ์แบบยืดหยุ่นซ้ำๆ เพื่อย้ายองค์ประกอบที่อยู่นอกลำดับไปยังแถวถัดไป ในกรณีหลัง องค์ประกอบที่อยู่นอกลำดับจะแทนที่รายการซ้ายสุดที่ใหญ่กว่าในแต่ละแถว และองค์ประกอบที่ถูกแทนที่นั้นจะถูกแทรกในแถวถัดไป

เนื่องจากการแทรกแบบ Schenstedรักษาตาราง Young ไว้ได้ จึงทำให้ได้การพิสูจน์แบบอุปนัยว่าองค์ประกอบของโมโนอิดพลาสติกสามารถเขียนได้ในรูปแบบมาตรฐานที่สอดคล้องกับตาราง Young และการสร้างนี้ยังกำหนดผลคูณตามธรรมชาติของตารางกึ่งมาตรฐานอีกด้วย

เกมทาควิน

ตาราง Young Tableaux สองตารางที่เอียงจะ เทียบเท่ากันในแบบ Jeu de taquinก็ต่อเมื่อการอ่านคำของตารางเหล่านั้นเทียบเท่ากันในแบบ Knuth กล่าวคือ สอดคล้องกับองค์ประกอบที่เทียบเท่ากันของกลุ่ม plactic นี่เป็นการให้นิยามทางเลือกของผลคูณของกลุ่ม plactic โดยตรงในแง่ของตาราง Young Tableaux สามารถคูณตารางสองตารางได้โดยการวาดตารางทั้งสองรอบสี่เหลี่ยมผืนผ้าว่างเพื่อสร้างตารางที่เอียง และใช้สไลด์ Jeu de taquin เพื่อปรับให้ตรง

แหวนตาราง

วงแหวนตาราง (tableau ring)คือวงแหวนโมโนอิดของโมโนอิดพลาสติก (plactic monoid) ดังนั้นจึงมี ฐาน Zที่ประกอบด้วยองค์ประกอบของโมโนอิดพลาสติก โดยมีผลคูณเหมือนกับในโมโนอิดพลาสติก

มีโฮโมมอร์ฟิซึมจากวงแหวนพลาสติกบนตัวอักษรไปยังวงแหวนของพหุนาม (โดยที่ตัวแปรมีดัชนีตามตัวอักษร) ซึ่งแปลงตารางใดๆ ให้เป็นผลคูณของตัวแปรของสมาชิกในตารางนั้น ซึ่งสอดคล้องกับการทำให้เป็นกลุ่มอาเบลของเซมิกรุปพลาสติก

การเจริญเติบโต

ฟังก์ชันก่อกำเนิดของพลาติกโมโนอิดบนตัวอักษรขนาดnคือ

แสดงให้เห็นว่ามิติมีการเติบโตแบบพหุนาม

ดูเพิ่มเติม

อ่านเพิ่มเติม

  • กรีน, เจมส์ เอ. (2007), การนำเสนอพหุนามของ GL n , บันทึกการบรรยายทางคณิตศาสตร์, เล่มที่ 830, พร้อมภาคผนวกเกี่ยวกับความสอดคล้องของ Schensted และเส้นทาง Littelmann โดย เค. เอิร์ดมันน์, เจ.เอ. กรีน และ เอ็ม. ช็อคเกอร์ (ฉบับแก้ไขและเพิ่มเติมครั้งที่ 2  ), เบอร์ลิน: สปริงเกอร์-เวอร์แลก , ISBN 978-3-540-46944-5, Zbl 1108.20044 
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Plactic_monoid&oldid=1314400952 "

สรุปเนื้อหา

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

ข้อมูลสำคัญเกี่ยวกับ โมโนอิดพลาสติก

ในทางคณิตศาสตร์ พลาติกโมโนอิด (plactic monoid) คือโมโนอิดของคำทั้งหมดในอักษรของจำนวนเต็มบวก โดยพิจารณาโมดูลัสความสมมูลของคนุธ( Knuth equivalence )...

คำนิยาม

โมโนอิดแบบพลาสติกเหนือตัวอักษรที่มีลำดับสมบูรณ์ (มักเป็นจำนวนเต็มบวก) คือโมโนอิดที่มี การนำเสนอ ในรูปแบบต่อไปนี้ :

ความเท่าเทียมกันของ Knuth

คำสองคำจะเรียกว่า เทียบเท่ากันตามหลัก Knuth หากคำทั้งสองนั้นแสดงถึงองค์ประกอบเดียวกันของโมโนอิดแบบพลาสติก หรือกล่าวอีกนัยหนึ่งคือ หากคำหนึ่งสามารถได้มาจากอีกคำหนึ่งโดยลำดับของการแปลง Knuth ขั้นพื้นฐาน

การติดต่อกับตาราง Young กึ่งมาตรฐาน

ทุกคำมีค่าเทียบเท่าแบบ Knuth กับคำใน ตาราง Young กึ่งมาตรฐานที่ไม่ซ้ำ กัน (ซึ่งหมายความว่าแต่ละแถวไม่ลดลงและแต่ละคอลัมน์เพิ่มขึ้นอย่างเคร่งครัด) บนตัวอักษรเรียงลำดับเดียวกัน โดยที่ตารางนั้นสามารถอ่านได้ทีละแถวหรือทีละคอลัมน์...