วิธีการพหุนามในคณิตศาสตร์เชิงการจัดเรียง
ในทางคณิตศาสตร์วิธีพหุนามเป็นแนวทางเชิงพีชคณิตสำหรับ ปัญหา การจัดเรียงที่เกี่ยวข้องกับการจับโครงสร้างการจัดเรียงบางอย่างโดยใช้พหุนามและดำเนินการโต้แย้งเกี่ยวกับคุณสมบัติเชิงพีชคณิตของพหุนามเหล่านั้น เมื่อไม่นานมานี้ (ประมาณปี 2016) วิธีพหุนามได้นำไปสู่การพัฒนาวิธีแก้ปัญหาที่เรียบง่ายอย่างน่าทึ่งสำหรับปัญหาที่ยังไม่ได้รับการแก้ไขมานานหลายปัญหา[ 1 ] วิธีพหุนามครอบคลุมเทคนิคเฉพาะที่หลากหลายสำหรับการใช้พหุนามและแนวคิดจากสาขาต่างๆ เช่น เรขาคณิตเชิงพีชคณิตเพื่อแก้ปัญหาการจัดเรียง ในขณะที่เทคนิคบางอย่างที่ปฏิบัติตามกรอบของวิธีพหุนาม เช่น Combinatorial Nullstellensatz ของ Alon [ 2 ] เป็นที่รู้จัก กันมาตั้งแต่ทศวรรษ 1990 แต่จนกระทั่งประมาณปี 2010 จึงได้มีการพัฒนากรอบที่กว้างขึ้นสำหรับวิธีพหุนาม
ภาพรวมทางคณิตศาสตร์
การนำวิธีพหุนามไปใช้ในหลายๆ กรณีมักใช้แนวทางระดับสูงที่คล้ายคลึงกัน โดยมีแนวทางดังนี้:
- ฝังปัญหาเชิงการจัดเรียงบางอย่างลงในปริภูมิเวกเตอร์
- แสดงสมมติฐานของปัญหาโดยการสร้างพหุนามดีกรีต่ำที่มีค่าเป็นศูนย์บนเซตที่กำหนด
- หลังจากสร้างพหุนามแล้ว ให้พิจารณาคุณสมบัติทางพีชคณิตของพหุนามนั้น เพื่อสรุปว่าโครงสร้างดั้งเดิมจะต้องมีคุณสมบัติตามที่ต้องการ
ตัวอย่าง
ตัวอย่างเช่น เราจะสรุปการพิสูจน์ของ Dvir เกี่ยวกับทฤษฎีบท Kakeya ของฟิลด์จำกัดโดยใช้วิธีพหุนาม[ 3 ]
สมมติฐานคาเคยะเกี่ยวกับฟิลด์จำกัด : ให้เป็นฟิลด์จำกัดที่มีองค์ประกอบต่างๆ ปล่อยให้เป็นเซตคาเคยะ กล่าวคือ สำหรับแต่ละเวกเตอร์มีอยู่จริงโดยที่ประกอบด้วยบรรทัดจากนั้นชุดก็มีขนาดอย่างน้อยที่ไหนเป็นค่าคงที่ที่ขึ้นอยู่กับเท่านั้น.
หลักฐาน: หลักฐานที่เราจะนำเสนอจะแสดงให้เห็นว่ามีขนาดอย่างน้อยขอบเขตของสามารถทำได้โดยใช้วิธีเดียวกัน แต่ต้องเพิ่มขั้นตอนอีกเล็กน้อย
สมมติว่าเรามีเซตคาเคยะกับ
พิจารณาเซตของเอกนามที่มีรูปแบบดังนี้ของระดับที่แน่นอนมีอยู่ทั้งหมดเอกนามดังกล่าว ดังนั้นจึงมีพหุนามเอกพันธุ์ ที่ไม่เป็นศูนย์อยู่ของปริญญาที่หายไปในทุกจุดโปรด ทราบว่านี่เป็นเพราะการหาพหุนามดังกล่าวจะลดลงเหลือเพียงการแก้ระบบสมการสมการเชิงเส้นสำหรับสัมประสิทธิ์
ตอนนี้เราจะใช้คุณสมบัติที่ว่าเป็นชุดคาเคยะที่จะแสดงให้เห็นว่าต้องหายไปจากทุกสิ่งชัดเจนต่อไป สำหรับมีอยู่โดยที่เส้นนั้นบรรจุอยู่ใน. เนื่องจากเป็นเนื้อเดียวกัน ถ้าสำหรับบางคนแล้วสำหรับใดๆโดยเฉพาะอย่างยิ่ง
สำหรับทุกค่าที่ไม่เป็นศูนย์. อย่างไรก็ตาม,เป็นพหุนามดีกรีในแต่อย่างน้อยมันก็มีรากที่สอดคล้องกับองค์ประกอบที่ไม่เป็นศูนย์ของดังนั้นมันจึงต้องเป็นศูนย์โดยสมบูรณ์ โดยเฉพาะอย่างยิ่ง การเสียบปลั๊กเข้าไปเราสรุปได้ว่า.
เราได้แสดงให้เห็นแล้วว่าสำหรับทุกคนแต่มีระดับน้อยกว่าในแต่ละตัวแปร ดังนั้นจึงเป็นไปไม่ได้ตามทฤษฎีบทของ Schwartz–Zippelเราจึงสรุปได้ว่าเราต้องมีจริงๆ
การแบ่งพหุนาม
วิธีการพหุนามรูปแบบหนึ่ง ซึ่งมักเรียกว่าการแบ่งส่วนพหุนาม ได้รับการแนะนำโดย Guth และ Katz ในการแก้ปัญหาระยะทางที่แตกต่างกันของ Erdős [ 4 ] การแบ่งส่วนพหุนามเกี่ยวข้องกับการใช้พหุนามเพื่อแบ่งพื้นที่พื้นฐานออกเป็นภูมิภาค และโต้แย้งเกี่ยวกับโครงสร้างทางเรขาคณิตของการแบ่งส่วน การโต้แย้งเหล่านี้อาศัยผลลัพธ์จากเรขาคณิตเชิงพีชคณิตที่จำกัดจำนวนเหตุการณ์ระหว่างเส้นโค้งเชิงพีชคณิตต่างๆ เทคนิคการแบ่งส่วนพหุนามได้ถูกนำมาใช้เพื่อพิสูจน์ทฤษฎีบทSzemerédi–Trotter ในรูป แบบใหม่ ผ่านทฤษฎีบทแซนด์วิชแฮมพหุนามและได้ถูกนำไปใช้กับปัญหาต่างๆ ในเรขาคณิตเหตุการณ์[ 5 ] [ 6 ]
แอปพลิเคชัน
ตัวอย่างบางส่วนของปัญหาที่ยังไม่ได้รับการแก้ไขมาเป็นเวลานาน ซึ่งได้รับการแก้ไขโดยใช้วิธีพหุนาม ได้แก่:
- การคาดการณ์ของ Kakeya ในฟิลด์จำกัด[ 3 ]โดย Dvir
- ปัญหาชุดหมวกโดย Ellenberg และ Gijswijt [ 7 ]พร้อมกรอบงานดั้งเดิมที่พัฒนาขึ้นจากปัญหาที่คล้ายคลึงกันเหนือโดย Croot, Lev และ Pach [ 8 ]
- ปัญหาระยะทางที่แตกต่างกันของ ErdőโดยGuth และ Katz [ 4 ]
- ปัญหาข้อต่อใน 3 มิติโดย Guth และ Katz [ 9 ]ข้อโต้แย้งของพวกเขาได้รับการทำให้ง่ายขึ้นในภายหลังโดย Elekes, Kaplan และ Sharir [ 10 ]
ดูเพิ่มเติม
ลิงก์ภายนอก
- บทสำรวจเกี่ยวกับวิธีการพหุนามโดย เทเรนซ์ เทา
- บทสำรวจเกี่ยวกับวิธีการพหุนามโดย แลร์รี กัทธ์