ลำดับเอกนาม
ในทางคณิตศาสตร์ลำดับเอกนาม (บางครั้งเรียกว่าลำดับเทอมหรือลำดับที่ยอมรับได้ ) คือลำดับสมบูรณ์บนเซตของเอก นาม (เอก นามเดี่ยว ) ทั้งหมด ในวงแหวนพหุนาม ที่กำหนด ซึ่งสอดคล้องกับคุณสมบัติของการเคารพการคูณ กล่าวคือ
- ถ้าและเป็นเอกนามอื่นใด แล้ว.
ลำดับเอกนามมักใช้ร่วมกับฐานกรอบเนอร์และการหารหลายตัวแปรโดยเฉพาะอย่างยิ่ง คุณสมบัติของการเป็นฐานกรอบเนอร์นั้นสัมพันธ์กับลำดับเอกนามเฉพาะเสมอ
คำจำกัดความ รายละเอียด และรูปแบบต่างๆ
นอกจากจะต้องเคารพการคูณแล้ว ลำดับเอกนามมักจะต้องเป็นลำดับที่ดี (well-orders ) ด้วย เนื่องจากจะทำให้กระบวนการหารหลายตัวแปรสิ้นสุดลงได้ อย่างไรก็ตาม ยังมีการประยุกต์ใช้ในทางปฏิบัติสำหรับความสัมพันธ์ลำดับที่เคารพการคูณบนเซตของเอกนามที่ไม่ใช่ลำดับที่ดีด้วยเช่นกัน
ในกรณีที่มีตัวแปรจำนวนจำกัด การเรียงลำดับที่ดีของลำดับเอกนามนั้นเทียบเท่ากับการรวมกันของเงื่อนไขสองข้อต่อไปนี้:
- คำสั่งซื้อนี้เป็น คำสั่ง ซื้อทั้งหมด
- ถ้าuเป็นเอกนามใดๆ แล้ว.
เนื่องจากเงื่อนไขเหล่านี้อาจตรวจสอบได้ง่ายกว่าสำหรับลำดับเอกนามที่กำหนดผ่านกฎที่ชัดเจน มากกว่าการพิสูจน์โดยตรงว่าเป็นลำดับที่ดี จึงมักนิยมใช้เงื่อนไขเหล่านี้ในการกำหนดนิยามของลำดับเอกนาม
เอกนามนำหน้า พจน์ และสัมประสิทธิ์
การเลือกอันดับรวมของเอกนามช่วยให้สามารถเรียงลำดับพจน์ของพหุนามได้ ดังนั้น พจน์นำของพหุนามจึงเป็นพจน์ของเอกนามที่ใหญ่ที่สุด (สำหรับลำดับเอกนามที่เลือกไว้)
โดยเฉพาะอย่างยิ่ง ให้Rเป็นวงแหวนของพหุนามใดๆ เซตMของเอกนาม (เอกนามเอกภาค) ในRจะเป็นฐานของRซึ่งถือว่าเป็นปริภูมิเวกเตอร์เหนือฟิลด์ของสัมประสิทธิ์ ดังนั้น พหุนามp ใดๆ ที่ไม่เป็นศูนย์ ในRจะมีนิพจน์ที่ไม่ซ้ำกัน ในรูปของการรวมเชิงเส้นของเอกนาม โดยที่Sเป็นเซตย่อยจำกัดของMและc ทั้งหมดไม่เป็นศูนย์ เมื่อเลือกอันดับเอกนามแล้ว เอก นามนำหน้า คือ uที่ใหญ่ที่สุดในSสัมประสิทธิ์นำหน้า คือ c ที่สอดคล้องกันและพจน์นำหน้าคือc u ที่สอดคล้องกัน บางครั้งคำว่า "เอกนาม นำหน้า " หรือ "สัมประสิทธิ์นำหน้า" ถูกใช้เป็นคำพ้องความหมายของ "นำหน้า" ผู้เขียนบางคนใช้คำ ว่า"เอกนาม" แทน "พจน์" และ "ผลคูณกำลัง" แทน "เอกนาม" ในบทความนี้ ถือว่าเอกนามไม่รวมสัมประสิทธิ์
คุณสมบัติสำคัญของการเรียงลำดับเอกนามคือ ลำดับของพจน์จะคงเดิมเมื่อคูณพหุนามกับเอกนาม นอกจากนี้ พจน์นำของผลคูณของพหุนามคือผลคูณของพจน์นำของตัวประกอบ
ตัวอย่าง
ในเซต ของกำลังของตัวแปร xใดๆลำดับเอกนามเพียงอย่างเดียวคือลำดับธรรมชาติ 1 < x < x² < x³ < ... และลำดับผกผันของมัน ซึ่งลำดับผกผันนี้ไม่ใช่ลำดับที่ดี ดังนั้น แนวคิดเรื่องลำดับเอกนามจึงน่าสนใจเฉพาะในกรณีที่มีหลายตัวแปรเท่านั้น
ลำดับเอกนามบ่งบอกถึงลำดับของตัวแปรแต่ละตัว เราสามารถลดความซับซ้อนของการจำแนกลำดับเอกนามได้โดยการสมมติว่าตัวแปรเหล่านั้นมีชื่อว่าx₂ , x₃ , ... ลดลงสำหรับลำดับเอกนามที่พิจารณา ดังนั้น x₁ > x₂ > x₃ > ... เสมอ( มีตัวแปรจำนวนข้อตกลงนี้จะไม่สอดคล้องกับเงื่อนไขของการเป็นลำดับที่ดี และเราจะต้องใช้ลำดับตรงกันข้าม อย่างไรก็ตามกรณีของพหุนามในตัวแปรจำนวนอนันต์นั้นไม่ค่อยได้รับการพิจารณา) ในตัวอย่างด้านล่าง เราใช้x , y และ z แทน x₁ , x₂ และ x₃ ข้อนี้ ก็ยังมีตัวอย่างมากมายของลำดับเอกนามที่แตกต่าง
ลำดับตามพจนานุกรม
ลำดับพจนานุกรม (lex) จะเปรียบเทียบเลขชี้กำลังของx ในเอกนามก่อน และในกรณีที่เท่ากันก็จะเปรียบเทียบเลขชี้กำลังของx และต่อไปเรื่อยๆ ชื่อนี้ได้มาจากความคล้ายคลึงกับลำดับตัวอักษรที่ใช้กันทั่วไปในพจนานุกรมหากเอกนามถูกแทนด้วยลำดับของเลขชี้กำลังของตัวแปร หากจำนวนตัวแปรคงที่ (ซึ่งมักจะเป็นเช่นนั้น) ลำดับพจนานุกรมจะเป็นลำดับที่ดีแม้ว่านี่จะไม่ใช่กรณีสำหรับลำดับพจนานุกรมที่ใช้กับลำดับที่มีความยาวต่างกันก็ตาม
สำหรับเอกนามที่มีดีกรีไม่เกินสองในตัวแปรไม่กำหนดสองตัว ลำดับพจนานุกรม (โดยที่) คือ
สำหรับ การคำนวณ ฐาน Gröbnerการเรียงลำดับตามพจนานุกรมมักจะมีค่าใช้จ่ายสูงที่สุด ดังนั้นจึงควรหลีกเลี่ยงให้มากที่สุดเท่าที่จะเป็นไปได้ ยกเว้นสำหรับการคำนวณที่ง่ายมาก ๆ
ลำดับชั้นตามพจนานุกรม
ลำดับพจนานุกรมแบบไล่ระดับ (grlex หรือ deglex สำหรับลำดับพจนานุกรมตามดีกรี ) จะเปรียบเทียบดีกรีรวม (ผลรวมของเลขชี้กำลังทั้งหมด) ก่อน และในกรณีที่เท่ากันจะใช้ลำดับพจนานุกรม ลำดับนี้ไม่เพียงแต่เป็นลำดับที่ดีเท่านั้น แต่ยังมีคุณสมบัติที่ว่าเอกนามใดๆ จะมีเอกนามอื่นๆ นำหน้าเพียงจำนวนจำกัดเท่านั้น ซึ่งแตกต่างจากลำดับพจนานุกรมตรงที่กำลังของy ทั้งหมด (ซึ่งมีจำนวนอนันต์) จะน้อยกว่าx (อย่างไรก็ตาม ลำดับพจนานุกรมเป็นลำดับที่ดีเนื่องจากเป็นไปไม่ได้ที่จะสร้างสายโซ่เอกนามที่ลดลงอย่างไม่มีที่สิ้นสุด)
สำหรับเอกนามที่มีดีกรีไม่เกินสองในตัวแปรไม่กำหนดสองตัว ลำดับพจนานุกรมแบบไล่ระดับ (โดยมี) คือ
แม้ว่าการเรียงลำดับนี้จะเป็นธรรมชาติมาก แต่ก็ไม่ค่อยได้ใช้กัน: ฐานของ Gröbnerสำหรับการเรียงลำดับแบบย้อนกลับตามลำดับชั้น ซึ่งจะกล่าวถึงต่อไปนั้น คำนวณได้ง่ายกว่าและให้ข้อมูลเดียวกันเกี่ยวกับชุดพหุนามที่ป้อนเข้ามา
เรียงลำดับย้อนกลับตามพจนานุกรม
ลำดับพจนานุกรมย้อนกลับแบบไล่ระดับ (grevlex หรือ degrevlex สำหรับลำดับพจนานุกรมย้อนกลับตามระดับ ) จะเปรียบเทียบระดับรวมก่อน จากนั้นใช้ลำดับพจนานุกรมเป็นตัวตัดสิน แต่จะกลับผลลัพธ์ของการเปรียบเทียบพจนานุกรมเพื่อให้เอกนามที่มีระดับเดียวกันซึ่งมีระดับพจนานุกรมใหญ่กว่าจะถือว่ามีระดับ degrevlex น้อยกว่า สำหรับลำดับสุดท้ายที่จะแสดงลำดับแบบดั้งเดิมx > x > ... > x ของตัวแปรที่ไม่กำหนด จำเป็นอย่างยิ่งที่ลำดับพจนานุกรมตัวตัดสินก่อนการกลับลำดับจะต้องพิจารณาตัวแปรที่ไม่กำหนดตัวสุดท้ายx ว่ามีค่ามากที่สุด ซึ่งหมายความว่าต้องเริ่มต้นด้วยตัวแปรที่ไม่กำหนดตัวนั้น สูตรที่เป็นรูปธรรมสำหรับการจัดลำดับย้อนกลับตามพจนานุกรมแบบไล่ระดับคือ การเปรียบเทียบโดยใช้ดีกรีรวมก่อน จากนั้นเปรียบเทียบเลขชี้กำลังของตัวแปรไม่แน่นอนตัวสุดท้ายx แต่กลับผลลัพธ์ (ดังนั้นเอกนามที่มีเลขชี้กำลังน้อยกว่าจะมีค่ามากกว่าในลำดับ) ตามด้วย (เช่นเดียวกับกรณีที่เสมอกันเฉพาะในกรณีที่มีค่าเท่ากัน) การเปรียบเทียบที่คล้ายกันของx และทำเช่นนี้ต่อไปเรื่อย ๆ จนกระทั่งจบด้วยx
ความแตกต่างระหว่างลำดับพจนานุกรมแบบไล่ระดับและลำดับพจนานุกรมแบบย้อนกลับไล่ระดับนั้นค่อนข้างละเอียดอ่อน เนื่องจากในความเป็นจริงแล้วมันตรงกันสำหรับตัวแปรไม่แน่นอน 1 และ 2 ตัว ความแตกต่างแรกเกิดขึ้นกับเอกนามระดับ 2 ในตัวแปรไม่แน่นอน 3 ตัว ซึ่งเรียงลำดับตามพจนานุกรมแบบไล่ระดับได้เป็นแต่เรียงลำดับตามพจนานุกรมแบบย้อนกลับไล่ระดับได้เป็นแนวโน้มโดยทั่วไปคือ ลำดับแบบย้อนกลับจะแสดงตัวแปรทั้งหมดในบรรดาเอกนามขนาดเล็กของระดับใด ๆ ในขณะที่ลำดับที่ไม่ใช่แบบย้อนกลับ ช่วงของเอกนามที่เล็กที่สุดของระดับใด ๆ จะถูกสร้างขึ้นจากตัวแปรที่เล็กที่สุดเท่านั้น
คำสั่งกำจัด
ลำดับบล็อกหรือลำดับการกำจัด (lexdeg) สามารถกำหนดได้สำหรับจำนวนบล็อกใดๆ ก็ได้ แต่เพื่อความง่าย เราจะพิจารณาเฉพาะกรณีที่มีสองบล็อกเท่านั้น (อย่างไรก็ตาม หากจำนวนบล็อกเท่ากับจำนวนตัวแปร ลำดับนี้ก็คือลำดับพจนานุกรม) สำหรับลำดับนี้ ตัวแปรจะถูกแบ่งออกเป็นสองบล็อกx ,..., x และy ,..., y และจะเลือกการเรียงลำดับเอกนามสำหรับแต่ละบล็อก โดยปกติจะเป็นลำดับพจนานุกรมย้อนกลับแบบไล่ระดับ เอกนามสองตัวจะถูกเปรียบเทียบโดยการเปรียบเทียบ ส่วน x ของพวกมัน และในกรณีที่เท่ากัน จะเปรียบเทียบ ส่วน y ของพวกมัน ลำดับนี้มีความสำคัญเนื่องจากช่วยให้สามารถกำจัดได้ซึ่งเป็นการดำเนินการที่สอดคล้องกับการฉายภาพในเรขาคณิต เชิง พีชคณิต
ลำดับน้ำหนัก
ลำดับน้ำหนักขึ้นอยู่กับเวกเตอร์ที่เรียกว่าเวกเตอร์น้ำหนัก โดยจะเปรียบเทียบผลคูณดอทของลำดับเลขชี้กำลังของเอกนามกับเวกเตอร์น้ำหนักนี้ก่อน และในกรณีที่มีค่าเท่ากัน จะใช้ลำดับเอกนามคงที่อื่นแทน ตัวอย่างเช่น ลำดับที่แสดงข้างต้นเป็นลำดับน้ำหนักสำหรับเวกเตอร์น้ำหนัก "ดีกรีรวม" (1,1,...,1) ถ้าa เป็น จำนวนตรรกยะ อิสระ (โดยเฉพาะอย่างยิ่งไม่มีตัวใดเป็นศูนย์และเศษส่วนทั้งหมดเป็นจำนวนอตรรกยะ) จะไม่มีทางเกิดค่าเท่ากันได้ และเวกเตอร์น้ำหนักเองจะระบุลำดับเอกนาม ในทางตรงกันข้าม อาจใช้เวกเตอร์น้ำหนักอื่นเพื่อแก้ปัญหาค่าเท่ากัน และทำเช่นนี้ต่อไปเรื่อยๆ จนกระทั่งใช้ เวกเตอร์น้ำหนักอิสระเชิงเส้น nตัวแล้ว จะไม่มีค่าเท่ากันเหลืออยู่ ในความเป็นจริง เราสามารถกำหนด ลำดับเอกนาม ใดๆ ได้ ด้วยลำดับของเวกเตอร์น้ำหนัก ( Cox et al. หน้า72–73) ตัวอย่างเช่น (1,0,0,...,0), (0,1,0,...,0), ... (0,0,...,1) สำหรับ lex หรือ (1,1,1,...,1), (1,1,..., 1,0), ... (1,0,...,0) สำหรับ grevlex
ตัวอย่างเช่น พิจารณาเอกนาม, , , และ; ลำดับเอกนามข้างต้นจะเรียงลำดับเอกนามทั้งสี่นี้ดังนี้:
- เล็กซ์: (พลังแห่งการครอบงำ)
- Grlex: (ระดับรวมเป็นตัวกำหนด; พลังที่สูงกว่าจะทำลายการเสมอกันระหว่างสองอันดับแรก)
- Grevlex: (ระดับรวมเป็นตัวกำหนด; กำลังที่ต่ำกว่าในกรณีที่เสมอกันระหว่างสองอันดับแรก)
- ลำดับน้ำหนักที่มีเวกเตอร์น้ำหนัก (1,2,4): (ผลคูณดอท 10 > 9 > 8 > 3 ไม่ทำให้เกิดการเสมอกันที่ต้องตัดสินในที่นี้)
แนวคิดที่เกี่ยวข้อง
- ลำดับการกำจัดรับประกันว่าเอกนามที่เกี่ยวข้องกับตัวแปรใดๆ ในชุดตัวแปรที่ไม่กำหนด จะมีค่ามากกว่าเอกนามที่ไม่เกี่ยวข้องกับตัวแปรใดๆ เหล่านั้นเสมอ
- ลำดับผลคูณเป็นตัวอย่างที่ง่ายกว่าของลำดับการกำจัด โดยประกอบด้วยการรวมลำดับเอกนามบนเซตของตัวแปรสุ่มที่ไม่ซ้ำกันเข้าด้วยกันเป็นลำดับเอกนามบนผลรวมของเซตเหล่านั้น วิธีการนี้เปรียบเทียบเลขชี้กำลังของตัวแปรสุ่มในเซตแรกโดยใช้ลำดับเอกนามแรก จากนั้นจึงใช้ลำดับเอกนามอื่นบนตัวแปรสุ่มในเซตที่สองเพื่อตัดสินในกรณีที่มีค่าเท่ากัน เห็นได้ชัดว่าวิธีการนี้สามารถขยายไปสู่ผลรวมของเซตของตัวแปรสุ่มที่ไม่ซ้ำกันใดๆ ได้ เช่น ลำดับพจนานุกรมสามารถหาได้จากเซตที่มีตัวแปรเดียว { x }, { x }, { x }, ... (โดยแต่ละเซตจะมีลำดับเอกนามที่ไม่ซ้ำกัน)
เมื่อใช้การเรียงลำดับเอกนามในการคำนวณฐาน Gröbner ลำดับที่แตกต่างกันอาจนำไปสู่ผลลัพธ์ที่แตกต่างกัน และความยากในการคำนวณอาจแตกต่างกันอย่างมาก ตัวอย่างเช่น การเรียงลำดับแบบย้อนกลับตามพจนานุกรมแบบแบ่งระดับนั้นมีชื่อเสียงในด้านการสร้างฐาน Gröbner ที่คำนวณได้ง่ายที่สุดเกือบทุกครั้ง (ซึ่งได้รับการยืนยันจากข้อเท็จจริงที่ว่า ภายใต้เงื่อนไขทั่วไปเกี่ยวกับอุดมคติ พหุนามในฐาน Gröbner มีดีกรีที่มากที่สุดเป็นเลขชี้กำลังของจำนวนตัวแปรเท่านั้น ไม่มีผลลัพธ์ความซับซ้อนเช่นนี้สำหรับการเรียงลำดับอื่นใด) ในทางกลับกัน จำเป็นต้องใช้ลำดับการกำจัดสำหรับ ปัญหา การกำจัดและปัญหาเชิงสัมพันธ์