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

อ่าน 5 นาที

วิธีการพหุนามในคณิตศาสตร์เชิงการจัดเรียง

เชิงผสม

ในทางคณิตศาสตร์วิธีพหุนามเป็นแนวทางเชิงพีชคณิตสำหรับ ปัญหา การจัดเรียงที่เกี่ยวข้องกับการจับโครงสร้างการจัดเรียงบางอย่างโดยใช้พหุนามและดำเนินการโต้แย้งเกี่ยวกับคุณสมบัติเชิงพีชคณิต...

วิธีการพหุนามในคณิตศาสตร์เชิงการจัดเรียง

ในทางคณิตศาสตร์วิธีพหุนามเป็นแนวทางเชิงพีชคณิตสำหรับ ปัญหา การจัดเรียงที่เกี่ยวข้องกับการจับโครงสร้างการจัดเรียงบางอย่างโดยใช้พหุนามและดำเนินการโต้แย้งเกี่ยวกับคุณสมบัติเชิงพีชคณิตของพหุนามเหล่านั้น เมื่อไม่นานมานี้ (ประมาณปี 2016) วิธีพหุนามได้นำไปสู่การพัฒนาวิธีแก้ปัญหาที่เรียบง่ายอย่างน่าทึ่งสำหรับปัญหาที่ยังไม่ได้รับการแก้ไขมานานหลายปัญหา[ 1 ] วิธีพหุนามครอบคลุมเทคนิคเฉพาะที่หลากหลายสำหรับการใช้พหุนามและแนวคิดจากสาขาต่างๆ เช่น เรขาคณิตเชิงพีชคณิตเพื่อแก้ปัญหาการจัดเรียง ในขณะที่เทคนิคบางอย่างที่ปฏิบัติตามกรอบของวิธีพหุนาม เช่น Combinatorial Nullstellensatz ของ Alon [ 2 ] เป็นที่รู้จัก กันมาตั้งแต่ทศวรรษ 1990 แต่จนกระทั่งประมาณปี 2010 จึงได้มีการพัฒนากรอบที่กว้างขึ้นสำหรับวิธีพหุนาม

ภาพรวมทางคณิตศาสตร์

การนำวิธีพหุนามไปใช้ในหลายๆ กรณีมักใช้แนวทางระดับสูงที่คล้ายคลึงกัน โดยมีแนวทางดังนี้:

  • ฝังปัญหาเชิงการจัดเรียงบางอย่างลงในปริภูมิเวกเตอร์
  • แสดงสมมติฐานของปัญหาโดยการสร้างพหุนามดีกรีต่ำที่มีค่าเป็นศูนย์บนเซตที่กำหนด
  • หลังจากสร้างพหุนามแล้ว ให้พิจารณาคุณสมบัติทางพีชคณิตของพหุนามนั้น เพื่อสรุปว่าโครงสร้างดั้งเดิมจะต้องมีคุณสมบัติตามที่ต้องการ

ตัวอย่าง

ตัวอย่างเช่น เราจะสรุปการพิสูจน์ของ Dvir เกี่ยวกับทฤษฎีบท Kakeya ของฟิลด์จำกัดโดยใช้วิธีพหุนาม[ 3 ]

สมมติฐานคาเคยะเกี่ยวกับฟิลด์จำกัด : ให้เอฟq{\displaystyle \mathbb {F} _{q}}เป็นฟิลด์จำกัดที่มีq{\displaystyle q}องค์ประกอบต่างๆ ปล่อยให้เคเอฟqn{\displaystyle K\subseteq \mathbb {F} _{q}^{n}}เป็นเซตคาเคยะ กล่าวคือ สำหรับแต่ละเวกเตอร์yเอฟqn{\displaystyle y\in \mathbb {F} _{q}^{n}}มีอยู่จริงxเอฟqn{\displaystyle x\in \mathbb {F} _{q}^{n}}โดยที่เค{\displaystyle K}ประกอบด้วยบรรทัด{x+ทีy,ทีเอฟq}{\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}}จากนั้นชุดก็เค{\displaystyle K}มีขนาดอย่างน้อยnqn{\displaystyle c_{n}q^{n}}ที่ไหนn>0{\displaystyle c_{n}>0}เป็นค่าคงที่ที่ขึ้นอยู่กับเท่านั้นn{\displaystyle n}.

หลักฐาน: หลักฐานที่เราจะนำเสนอจะแสดงให้เห็นว่าเค{\displaystyle K}มีขนาดอย่างน้อยnqn1{\displaystyle c_{n}q^{n-1}}ขอบเขตของnqn{\displaystyle c_{n}q^{n}}สามารถทำได้โดยใช้วิธีเดียวกัน แต่ต้องเพิ่มขั้นตอนอีกเล็กน้อย

สมมติว่าเรามีเซตคาเคยะเค{\displaystyle K}กับ

|เค|<(q+n3n1){\displaystyle |K|<{q+n-3 \choose n-1}}

พิจารณาเซตของเอกนามที่มีรูปแบบดังนี้x11x22xnn{\displaystyle x_{1}^{d_{1}}x_{2}^{d_{2}}\dots x_{n}^{d_{n}}}ของระดับที่แน่นอนq2{\displaystyle q-2}มีอยู่ทั้งหมด(q+n3n1){\displaystyle {q+n-3 \choose n-1}}เอกนามดังกล่าว ดังนั้นจึงมีพหุนามเอกพันธุ์ ที่ไม่เป็นศูนย์อยู่พี(x1,x2,,xn){\displaystyle P(x_{1},x_{2},\dots ,x_{n})}ของปริญญาq2{\displaystyle q-2}ที่หายไปในทุกจุดเค{\displaystyle K}โปรด ทราบว่านี่เป็นเพราะการหาพหุนามดังกล่าวจะลดลงเหลือเพียงการแก้ระบบสมการ|เค|{\displaystyle |K|}สมการเชิงเส้นสำหรับสัมประสิทธิ์

ตอนนี้เราจะใช้คุณสมบัติที่ว่าเค{\displaystyle K}เป็นชุดคาเคยะที่จะแสดงให้เห็นว่าพี{\displaystyle P}ต้องหายไปจากทุกสิ่งเอฟqn{\displaystyle \mathbb {F} _{q}^{n}}ชัดเจนพี(0,0,0)=0{\displaystyle P(0,0\dots ,0)=0}ต่อไป สำหรับy0{\displaystyle y\neq 0}มีอยู่x{\displaystyle x}โดยที่เส้นนั้น{x+ทีy,ทีเอฟq}{\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}}บรรจุอยู่ในเค{\displaystyle K}. เนื่องจากพี{\displaystyle P}เป็นเนื้อเดียวกัน ถ้าพี(z)=0{\displaystyle P(z)=0}สำหรับบางคนzเอฟqn{\displaystyle z\in \mathbb {F} _{q}^{n}}แล้วพี(z)=0{\displaystyle P(cz)=0}สำหรับใดๆเอฟq{\displaystyle c\in \mathbb {F} _{q}}โดยเฉพาะอย่างยิ่ง

พี(ทีx+y)=พี(ที(x+ที1y))=0{\displaystyle P(tx+y)=P(t(x+t^{-1}y))=0}

สำหรับทุกค่าที่ไม่เป็นศูนย์ทีเอฟq{\displaystyle t\in \mathbb {F} _{q}}. อย่างไรก็ตาม,พี(ทีx+y){\displaystyle P(tx+y)}เป็นพหุนามดีกรีq2{\displaystyle q-2}ในที{\displaystyle t}แต่อย่างน้อยมันก็มีq1{\displaystyle q-1}รากที่สอดคล้องกับองค์ประกอบที่ไม่เป็นศูนย์ของเอฟq{\displaystyle \mathbb {F} _{q}}ดังนั้นมันจึงต้องเป็นศูนย์โดยสมบูรณ์ โดยเฉพาะอย่างยิ่ง การเสียบปลั๊กเข้าไปที=0{\displaystyle t=0}เราสรุปได้ว่าพี(y)=0{\displaystyle P(y)=0}.

เราได้แสดงให้เห็นแล้วว่าพี(y)=0{\displaystyle P(y)=0}สำหรับทุกคนyเอฟqn{\displaystyle y\in \mathbb {F} _{q}^{n}}แต่พี{\displaystyle P}มีระดับน้อยกว่าq1{\displaystyle q-1}ในแต่ละตัวแปร ดังนั้นจึงเป็นไปไม่ได้ตามทฤษฎีบทของ Schwartz–Zippelเราจึงสรุปได้ว่าเราต้องมีจริงๆ

|เค|(q+n3n1)~qn1(n1)!{\displaystyle |K|\geq {q+n-3 \choose n-1}\sim {\frac {q^{n-1}}{(n-1)!}}}

การแบ่งพหุนาม

วิธีการพหุนามรูปแบบหนึ่ง ซึ่งมักเรียกว่าการแบ่งส่วนพหุนาม ได้รับการแนะนำโดย Guth และ Katz ในการแก้ปัญหาระยะทางที่แตกต่างกันของ Erdős [ 4 ] การแบ่งส่วนพหุนามเกี่ยวข้องกับการใช้พหุนามเพื่อแบ่งพื้นที่พื้นฐานออกเป็นภูมิภาค และโต้แย้งเกี่ยวกับโครงสร้างทางเรขาคณิตของการแบ่งส่วน การโต้แย้งเหล่านี้อาศัยผลลัพธ์จากเรขาคณิตเชิงพีชคณิตที่จำกัดจำนวนเหตุการณ์ระหว่างเส้นโค้งเชิงพีชคณิตต่างๆ เทคนิคการแบ่งส่วนพหุนามได้ถูกนำมาใช้เพื่อพิสูจน์ทฤษฎีบทSzemerédi–Trotter ในรูป แบบใหม่ ผ่านทฤษฎีบทแซนด์วิชแฮมพหุนามและได้ถูกนำไปใช้กับปัญหาต่างๆ ในเรขาคณิตเหตุการณ์[ 5 ] [ 6 ]

แอปพลิเคชัน

ตัวอย่างบางส่วนของปัญหาที่ยังไม่ได้รับการแก้ไขมาเป็นเวลานาน ซึ่งได้รับการแก้ไขโดยใช้วิธีพหุนาม ได้แก่:

ดูเพิ่มเติม

  • บทสำรวจเกี่ยวกับวิธีการพหุนามโดย เทเรนซ์ เทา
  • บทสำรวจเกี่ยวกับวิธีการพหุนามโดย แลร์รี กัทธ์
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Polynomial_method_in_combinatorics&oldid=1351521101 "

สรุปเนื้อหา

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

ข้อมูลสำคัญเกี่ยวกับ วิธีการพหุนามในคณิตศาสตร์เชิงการจัดเรียง

ในทางคณิตศาสตร์วิธีพหุนามเป็นแนวทางเชิงพีชคณิตสำหรับ ปัญหา การจัดเรียงที่เกี่ยวข้องกับการจับโครงสร้างการจัดเรียงบางอย่างโดยใช้พหุนามและดำเนินการโต้แย้งเกี่ยวกับคุณสมบัติเชิงพีชคณิต...

ภาพรวมทางคณิตศาสตร์

การนำวิธีพหุนามไปใช้ในหลายๆ กรณีมักใช้แนวทางระดับสูงที่คล้ายคลึงกัน โดยมีแนวทางดังนี้:

ตัวอย่าง

ตัวอย่างเช่น เราจะสรุปการพิสูจน์ของ Dvir เกี่ยวกับ ทฤษฎีบท Kakeya ของฟิลด์จำกัด โดยใช้วิธีพหุนาม [ 3 ]

การแบ่งพหุนาม

วิธีการพหุนามรูปแบบหนึ่ง ซึ่งมักเรียกว่าการแบ่งส่วนพหุนาม ได้รับการแนะนำโดย Guth และ Katz ในการแก้ ปัญหาระยะทางที่แตกต่างกันของ Erdős [ 4 ] การ แบ่งส่วนพหุนามเกี่ยวข้องกับการใช้พหุนามเพื่อแบ่งพื้นที่พื้นฐานออกเป็นภูมิภาค...