مسألة إردوش للمسافة الواحدة في المستوى

تُعد مسألة إردوش للمسافة الواحدة (Erdős Unit Distance Problem) من أشهر الأسئلة المفتوحة في الهندسة المتقطعة. صاغها عالم الرياضيات المجري بول إردوش عام 1946، وما زالت حتى اليوم دون حل كامل.

ما السؤال بالضبط؟

إذا وضعنا عددًا قدره (n) من النقاط في المستوى الإقليدي، فما هو أكبر عدد ممكن من الأزواج من هذه النقاط التي تبعد مسافة تساوي 1 بالضبط؟

بصيغة أخرى: نبحث عن الترتيب الهندسي للنقاط الذي يحقق أكبر عدد من "المسافات الواحدة" بينها.

حدسية إردوش

اقترح إردوش أن الحد الأقصى الحقيقي لعدد هذه الأزواج يقترب من قيمة شبه خطية في (n)، أي تقريبًا:

[
n^{1+o(1)}
]

وهو استنتاج مستند إلى أمثلة تعتمد على شبكات النقاط المنتظمة (lattices) مثل شبكة النقاط الصحيحة في المستوى، حيث تظهر العديد من المسافات المتساوية بطول 1.

أفضل النتائج المعروفة حتى الآن

حتى اليوم لم يتم إثبات حدسية إردوش. ما يعرفه الباحثون هو حدود تقريبية فقط:

• الحد الأدنى المعروف: تقريبًا

[
n^{1+\Omega(1/\log\log n)}
]

• أفضل حد علوي عام:

[
O(n^{4/3})
]

وقد أثبت هذا الحد العلوي جويل سبنسر، إندريه سيميريدي، وويليام تروتر عام 1984 باستخدام أدوات من نظرية التلاقيات الهندسية (incidence geometry).