مشكلة المسافات المتميزة في إردو

بدلاً من السماح بوضع النقاط n المختلفة في أي مكان في المستوى، يمكننا أيضاً اشتراط أن تستوفي هذه النقاط قيوداً معينة. وبشكل عام، كلما كانت القيود أكثر صرامة، زاد حجمها.${\displaystyle g}$يحصل.

إذا اشترطنا أن تقع النقاط على خط واحد، فـ${\displaystyle g_{\text{line}}(n)=n-1}$بجعل النقاط متباعدة بمسافات متساوية. إذا أردنا أن تقع النقاط على دائرة واحدة، فـ${\displaystyle g_{\text{circle}}(n)=\lfloor n/2\rfloor }$بوضع النقاط على مسافات متساوية حول الدائرة. وبشكل أعم، إذا أردنا أن تشكل النقاط مضلعًا محدبًا، فإن${\displaystyle g_{\text{convex}}(n)=\lfloor n/2\rfloor }$وينطبق الأمر نفسه إذا اشترطنا أن تشكل النقاط مضلعًا محدبًا تمامًا. ^{[ 15 ] [ 16 ]}

إذا اشترطنا أن تكون النقاط في وضع عام ، أي ألا تكون ثلاث نقاط على استقامة واحدة وألا تكون أربع نقاط على دائرة واحدة، فإن المسألة تبقى مفتوحة. وأفضل نتيجة حالية هي${\displaystyle g_{\text{gen}}(n)\geq \Omega (n)}$و${\displaystyle g_{\text{gen}}\leq n2^{O({\sqrt {\log n}})}}$[ ^{17 ]​}

إذا اشترطنا أن تكون النقاط في وضع عام، وألا تشكل أي أربع نقاط متوازي أضلاع ، فإن المسألة تبقى مفتوحة. وأفضل نتيجة حالية هي${\displaystyle g_{\text{para}}(n)\geq \Omega (n)}$و${\displaystyle g_{\text{para}}\leq O(n^{2}/{\sqrt {\log n}})}$[ ^{18 ] [ 17 ]​}

انظر القسم 3 من ^{[ 19 ]} لمزيد من المشاكل والنتائج من هذا النوع.

كما نظر إردوش في النسخة ذات الأبعاد الأعلى من المشكلة: لـ${\displaystyle d\geq 3}$يترك${\displaystyle g_{d}(n)}$يشير إلى الحد الأدنى الممكن لعدد المسافات المختلفة بين${\displaystyle n}$النقاط في${\displaystyle d}$الفضاء الإقليدي ذو الأبعاد n . وقد أثبت ذلك${\displaystyle g_{d}(n)=\Omega (n^{1/d})}$و${\displaystyle g_{d}(n)=O(n^{2/d})}$وتكهن بأن الحد الأعلى دقيق بالفعل، أي${\displaystyle g_{d}(n)=\Theta (n^{2/d})}$. حصل József Solymosi و Van H. Vu على الحد الأدنى${\displaystyle g_{d}(n)=\أوميغا (n^{2/d-2/d(d+2)})}$في عام 2008. ^{[ 20 ]}

من جهة أخرى، من المعروف حاليًا أن${\displaystyle g_{3}(n)\geq \Omega _{*}(n^{3/5})}$بتطبيق علاقة التكرار الواردة في ^{[ 21 ]} على النتيجة${\displaystyle g_{2}(n)\geq \Omega _{*}(n)}$( غوث وكاتز 2015 ) . ^{[ 19 ]}​

يمكن طرح السؤال نفسه لأي فضاء معياري . بالنظر إلى معيار${\displaystyle \|\cdot \|}$، يُعرِّف${\displaystyle g_{\|\cdot \|}(n)}$وبناءً على ذلك، تُحل المشكلة في الحالة العامة . تحديدًا، عند إعطاء أي عدد صحيح${\displaystyle d\geq 2}$، بالنسبة لجميع المعايير تقريبًا${\displaystyle \|\cdot \|}$،$${\displaystyle g_{\|\cdot \|}(n)=(1-o(1))n}$$أي أن مجموعة المعايير التي تنتهك هذا الشرط ضئيلة في مجموعة جميع معايير${\displaystyle \mathbb {R} ^{d}}$، باعتبارها فضاءً متريًا ، يتم قياسه بواسطة مسافة هاوسدورف بين الكرات ذات المعيار الواحد. ^{[ 19 ] [ 22 ]}