Erdős distinct distances problem
असतत ज्यामिति में, एर्दोस की विशिष्ट दूरी की समस्या बताती है कि समतल में बिंदुओं के प्रत्येक समूह में अलग-अलग दूरी की लगभग रैखिक संख्या होती है। यह 1946 में पॉल एर्दोस द्वारा प्रस्तुत किया गया था और 2015 में लैरी गुथ और नेट्स काट्ज़ द्वारा लगभग साबित किया गया था। निम्नलिखित में आइए समतल में बिंदुओं के बीच अलग-अलग दूरी की न्यूनतम संख्या, या उनके दूरी सेट की सबसे छोटी संभव कार्डिनलिटी को दर्शाते हैं। अपने 1946 के पेपर में, एर्दोस ने कुछ स्थिरांक के अनुमानों को साबित किया। निचली सीमा को एक आसान तर्क द्वारा दिया गया था। ऊपरी सीमा एक वर्गाकार ग्रिड द्वारा दी जाती है। इस तरह के ग्रिड के लिए, n से नीचे की संख्याएँ हैं जो दो वर्गों के योग हैं, जिन्हें बड़े O संकेतन में व्यक्त किया गया है; लैंडौ-रामानुजन स्थिरांक देखें। एर्डोस ने अनुमान लगाया कि ऊपरी सीमा g (n) के सही मूल्य के करीब थी, और विशेष रूप से (बड़े Omega संकेतन का उपयोग करते हुए) प्रत्येक के लिए धारण करती है। आंशिक परिणाम पॉल एर्दोस की 1946 की निचली सीमा में क्रमिक रूप से सुधार किया गयाः 1952 में लियो मोजर द्वारा, 1984 में फैन चुंग द्वारा, फैन चुंग द्वारा, एंड्रे स्ज़ेमेरेडी द्वारा, और 1992 में विलियम टी. ट्रॉटर द्वारा, 1993 में लेज़लो ए. स्ज़ेकली द्वारा, 2001 में जोज़ेफ़ सोलिमोसी और ससाबा डी. टोथ द्वारा, 2003 में गैबर टार्डोस द्वारा, 2004 में नेट्स काट्ज़ और गैबर टार्डोस द्वारा, 2015 में लैरी गुथ और नेट्स काट्ज़ द्वारा। उच्च आयामों वाले एर्दोस ने समस्या के उच्च-आयामी संस्करण पर भी विचार कियाः क्योंकि आइए-आयामी यूक्लिडियन स्थान में बिंदुओं के बीच अलग-अलग दूरी की न्यूनतम संभव संख्या को दर्शाते हैं। उन्होंने यह साबित किया और अनुमान लगाया कि ऊपरी सीमा वास्तव में तेज है, अर्थात। जोज़ेफ़ सोलिमोसी और वान एच. वु ने 2008 में निचली सीमा प्राप्त की। फाल्कनर का अनुमान एर्दोस इकाई दूरी समस्या संदर्भ भी देखें बाहरी लिंक समस्या पर विलियम गैसार्क का पृष्ठ अनुमान पॉल एर्दोस असतत ज्यामिति