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

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

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

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

อย่างไรก็ตาม ค่านี้ยังสูงกว่าที่ Erdős คาดการณ์ไว้มาก ทำให้เกิดช่องว่างระหว่างขอบเขตบนและล่าง

ตัวอย่างแบบง่าย

ลองวางจุดบน ตารางจำนวนเต็ม เช่น

• จุดเรียงเป็นกริด (\sqrt{n} \times \sqrt{n})
• จุดที่อยู่ติดกันแนวนอนและแนวตั้งจะห่างกัน 1 หน่วย

การจัดแบบนี้ทำให้เกิดคู่จุดที่มีระยะ 1 จำนวนมาก และเป็นพื้นฐานของตัวอย่างที่ Erdős ใช้ในการคาดการณ์

สถานะของปัญหาในปัจจุบัน

แม้ว่าจะมีงานวิจัยจำนวนมากตลอดหลายทศวรรษที่ผ่านมา แต่

ยังไม่มีการพิสูจน์สมบูรณ์สำหรับข้อคาดการณ์ของ Erdős และปัญหานี้ยังถือเป็น ปัญหาเปิดในเรขาคณิตเชิงไม่ต่อเนื่อง (discrete geometry)

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