อ่าน 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และxzy ≡ zxyเมื่อใดก็ตามที่x ≤ y < z
ความเท่าเทียมกันของ Knuth
คำสองคำจะเรียกว่าเทียบเท่ากันตามหลัก Knuthหากคำทั้งสองนั้นแสดงถึงองค์ประกอบเดียวกันของโมโนอิดแบบพลาสติก หรือกล่าวอีกนัยหนึ่งคือ หากคำหนึ่งสามารถได้มาจากอีกคำหนึ่งโดยลำดับของการแปลง Knuth ขั้นพื้นฐาน
คุณสมบัติหลายประการได้รับการรักษาไว้โดยหลักสมดุลของ Knuth
- ถ้าคำใดเป็นคำที่มีโครงสร้างแลตทิซแบบย้อนกลับคำใดๆ ที่เทียบเท่ากับคำนั้นในรูปแบบ Knuth ก็เป็นคำที่มีโครงสร้างแลตทิซแบบย้อนกลับเช่นกัน
- ถ้าคำสองคำมีความสมมูลกันตามทฤษฎีของ Knuth แล้ว คำที่ได้จากการลบองค์ประกอบที่ใหญ่ที่สุดทางด้านขวาสุดออกไป ก็จะมีความสมมูลกันตามทฤษฎีของ Knuth เช่นกัน เช่นเดียวกับคำที่ได้จากการลบองค์ประกอบที่เล็กที่สุดทางด้านซ้ายสุดออกไป
- ความสมมูลของ Knuth จะรักษาระยะความยาวของลำดับย่อยที่ไม่ลดลง ที่ยาวที่สุด และโดยทั่วไปแล้วจะรักษาค่าสูงสุดของผลรวมของความยาวของลำดับย่อยที่ไม่ลดลงที่ไม่ซ้ำกันk ลำดับ สำหรับค่า kที่ กำหนดไว้
การติดต่อกับตาราง Young กึ่งมาตรฐาน

ทุกคำมีค่าเทียบเท่าแบบ 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
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ โมโนอิดพลาสติก
ในทางคณิตศาสตร์ พลาติกโมโนอิด (plactic monoid) คือโมโนอิดของคำทั้งหมดในอักษรของจำนวนเต็มบวก โดยพิจารณาโมดูลัสความสมมูลของคนุธ( Knuth equivalence )...
คำนิยาม
โมโนอิดแบบพลาสติกเหนือตัวอักษรที่มีลำดับสมบูรณ์ (มักเป็นจำนวนเต็มบวก) คือโมโนอิดที่มี การนำเสนอ ในรูปแบบต่อไปนี้ :
ความเท่าเทียมกันของ Knuth
คำสองคำจะเรียกว่า เทียบเท่ากันตามหลัก Knuth หากคำทั้งสองนั้นแสดงถึงองค์ประกอบเดียวกันของโมโนอิดแบบพลาสติก หรือกล่าวอีกนัยหนึ่งคือ หากคำหนึ่งสามารถได้มาจากอีกคำหนึ่งโดยลำดับของการแปลง Knuth ขั้นพื้นฐาน
การติดต่อกับตาราง Young กึ่งมาตรฐาน
ทุกคำมีค่าเทียบเท่าแบบ Knuth กับคำใน ตาราง Young กึ่งมาตรฐานที่ไม่ซ้ำ กัน (ซึ่งหมายความว่าแต่ละแถวไม่ลดลงและแต่ละคอลัมน์เพิ่มขึ้นอย่างเคร่งครัด) บนตัวอักษรเรียงลำดับเดียวกัน โดยที่ตารางนั้นสามารถอ่านได้ทีละแถวหรือทีละคอลัมน์...