ปัญหาระยะหนึ่งหน่วยของแอร์ดิช (Erdős Unit Distance Problem)

ปัญหาที่เกี่ยวข้องกับ จุดบนระนาบและระยะทางหนึ่งหน่วย ที่มีชื่อเสียงในคณิตศาสตร์คือ ปัญหาระยะหนึ่งหน่วยของแอร์ดิช (Erdős unit distance problem) ซึ่งถูกเสนอโดยนักคณิตศาสตร์ชาวฮังการี Paul Erdős ตั้งแต่ปี 1946

คำถามของปัญหา

หากเรามีจุด (n) จุดบนระนาบแบบยุคลิด (Euclidean plane) คำถามคือ:

จำนวน คู่ของจุดที่มีระยะห่างเท่ากับ 1 หน่วยพอดี จะมีได้มากที่สุดเท่าไร?

หรือพูดอีกแบบคือ ถ้าเราวาดเส้นเชื่อมทุกคู่จุดที่ห่างกัน 1 หน่วย เราจะได้กราฟที่มีเส้นเชื่อม (edges) มากที่สุดเท่าไร

ข้อคาดการณ์ของ Erdős

Erdős เชื่อว่าค่าสูงสุดจริง ๆ น่าจะเติบโตเกือบเป็นเส้นตรงกับจำนวนจุด กล่าวคือประมาณ

แนวคิดนี้มาจากตัวอย่างการจัดจุดเป็น ตารางสี่เหลี่ยมของจำนวนเต็ม (square lattice) ซึ่งสามารถสร้างคู่ระยะ 1 ได้จำนวนมากกว่าการเติบโตเชิงเส้นเล็กน้อย

ขอบเขตที่รู้ในปัจจุบัน

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

lower bound:  n^(1 + O(1/log log n))
upper bound:  O(n^(4/3))
conjecture:   n^(1+o(1))

ขอบเขตบนที่ดีที่สุดในกรณีทั่วไปคือ

O(n^(4/3))

ซึ่งพิสูจน์โดย Spencer, Szemerédi และ Trotter ในปี 1984 โดยใช้เทคนิคจากทฤษฎี incidence geometry