Erdős–Szemerédi theorem
अंकगणितीय संयोजन विज्ञान में, एर्दोस-ज़ेमेरेडी प्रमेय बताता है कि पूर्णांकों के प्रत्येक परिमित समुच्चय के लिए, कम से कम एक, जोड़ीदार योगों का समुच्चय या जोड़ीदार उत्पादों का समुच्चय काफी बड़ा समुच्चय बनाता है। अधिक सटीक रूप से, एर्दोस-स्ज़ेमेरेडी प्रमेय बताता है कि किसी भी गैर-खाली समुच्चय के लिए सकारात्मक स्थिरांक c और ऐसे मौजूद हैं। यह 1983 में पॉल एर्दोस और एंड्रे स्ज़ेमेरेडी द्वारा साबित किया गया था। संकेतन समूह की प्रधानता को दर्शाता है। जोड़ीदार राशियों का समुच्चय है और इसे राशियों का समुच्चय कहा जाता है। जोड़ीदार उत्पादों का समूह है और इसे उत्पाद समूह कहा जाता है। प्रमेय उस सिद्धांत का एक संस्करण है कि योगात्मक संरचना और गुणक संरचना सह-अस्तित्व में नहीं हो सकते हैं। इसे एक दावे के रूप में भी देखा जा सकता है कि वास्तविक रेखा में एक परिमित सबरिंग या परिमित सबफील्ड जैसा कोई सेट नहीं होता है; यह अब योग-उत्पाद घटना के रूप में जाना जाने वाला पहला उदाहरण है, जिसे अब सीमित क्षेत्रों सहित विभिन्न प्रकार के रिंग और क्षेत्रों में रखने के लिए जाना जाता है। सम-प्रोडक्ट अनुमान सम-प्रोडक्ट अनुमान अनौपचारिक रूप से कहता है कि किसी भी सेट के सम सेट या प्रोडक्ट सेट में से एक लगभग जितना संभव हो उतना बड़ा होना चाहिए। यह मूल रूप से एर्दोस और स्ज़ेमेरेडी द्वारा पूर्णांकों पर अनुमान लगाया गया था, लेकिन माना जाता है कि यह वास्तविक संख्याओं को पकड़ता है। अनुमानः किसी भी समूह के लिए एक है ओ (1) संकेतन में एसिम्प्टोटिक पैरामीटर |A। है। उदाहरण यदि फिर एसिम्प्टोटिक संकेतन का उपयोग करते हुए, एसिम्प्टोटिक पैरामीटर के साथ। अनौपचारिक रूप से, यह कहता है कि का योग सेट नहीं बढ़ता है। दूसरी ओर, उत्पाद समूह सभी के लिए रूप की एक सीमा को संतुष्ट करता है। यह एर्डोस गुणन तालिका समस्या से संबंधित है। इस सेट के लिए सबसे अच्छी निचली सीमा केविन फोर्ड के कारण है। यह उदाहरण ग्योरगी एलेक्स और इमरे जेड. रुज़ा की सम-प्रोडक्ट समस्या के कई उत्पादों के संस्करण, फ़्यू सम का एक उदाहरण है। उनके परिणाम का एक परिणाम यह है कि छोटे योगात्मक दोहरीकरण के साथ कोई भी सेट, उदाहरण के लिए एक अंकगणितीय प्रगति उत्पाद सेट पर निचली सीमा होती है। शू और झोउ ने साबित किया कि पूर्णांक में एक अंकगणितीय प्रगति के किसी भी घने सबसेट के लिए, जो प्रतिपादक में कारक तक तेज है। इसके विपरीत, सेट संतुष्ट करता है, लेकिन इसमें कई योग होते हैंः यह सीमा एक संख्या के द्विआधारी प्रतिनिधित्व पर विचार करने से आती है। सेट एक ज्यामितीय प्रगति का एक उदाहरण है। संख्याओं के यादृच्छिक सेट के लिए, उत्पाद सेट और योग सेट दोनों में कार्डिनलिटी होती है; यानी, उच्च संभावना के साथ योग सेट कोई दोहराए गए तत्व उत्पन्न नहीं करता है, और उत्पाद सेट के लिए समान होता है। अनुमान एर्दोस और स्ज़ेमेरेडी की तीक्ष्णता बाध्य पूर्णांकों के पर्याप्त रूप से चिकने समूह का एक उदाहरण देती हैः इससे पता चलता है कि अनुमान में ओ (1) शब्द आवश्यक है। अत्यधिक मामलों का अक्सर अध्ययन परिकल्पना के चरम मामले होते हैंः कुछ राशि, कई उत्पाद (एफ. एस. एम. पी.): यदि, तो कुछ उत्पाद, कई राशि (एफ. पी. एम. एस.): यदि, तो। इतिहास और वर्तमान परिणाम निम्नलिखित तालिका वास्तविक पर योग-उत्पाद समस्या पर प्रगति का सारांश देती है। ग्योरगी एलेक्स के 1/4 और जोज़ेफ़ सोलिमोसी के 1/3 को उद्धृत साहित्य के भीतर मील का पत्थर माना जाता है। 2009 के बाद सभी सुधार रूप के हैं, और कोन्यागिन और श्क्रेदोव के तर्कों के परिष्करण का प्रतिनिधित्व करते हैं। जटिल संख्या प्रमाण तकनीक जिसमें केवल स्ज़ेमेरेडी-ट्रॉटर प्रमेय शामिल है, स्वचालित रूप से जटिल संख्याओं तक फैलती है, क्योंकि स्ज़ेमेरेडी-ट्रॉटर प्रमेय टोथ के एक प्रमेय द्वारा धारण करता है। कोन्यागिन और रुडनेव ने जटिल संख्याओं पर 3/4 के घातांक का मिलान किया। रूप के घातांक के साथ परिणामों का जटिल संख्याओं पर मिलान नहीं किया गया है। परिमित क्षेत्रों में योग-उत्पाद समस्या का विशेष रूप से सीमित क्षेत्रों में अच्छी तरह से अध्ययन किया जाता है। परिमित क्षेत्र केकिया अनुमान से प्रेरित होकर, वोल्फ ने अनुमान लगाया कि प्रत्येक उपसमुच्चय के लिए, जहां एक (बड़ा) अभाज्य है, वह एक निरपेक्ष स्थिरांक के लिए है। इस अनुमान को 1990 के दशक में यादृच्छिक निष्कर्षकों से प्रेरित विगडरसन द्वारा भी तैयार किया गया था। ध्यान दें कि योग-उत्पाद समस्या निम्नलिखित उदाहरण के कारण बिना शर्त सीमित क्षेत्रों में नहीं रह सकती हैः उदाहरण के लिएः एक सीमित क्षेत्र होने दें और लें। तब से जोड़ और गुणन के तहत बंद किया जाता है, और इसलिए। यह रोगजनक उदाहरण विचाराधीन क्षेत्र के किसी भी उप-क्षेत्र को लेने तक फैला हुआ है। गुणात्मक रूप से, योग-उत्पाद समस्या को सीमित क्षेत्रों में हल किया गया हैः प्रमेय (बोर्गैन, काट्ज़, ताओ (2004)): आइए अभाज्य रहें और कुछ के लिए छोड़ दें। फिर कुछ के लिए एक है। बोर्गेन, काट्ज़ और ताओ ने इस प्रमेय को मनमाने क्षेत्रों तक विस्तारित किया। अनौपचारिक रूप से, निम्नलिखित प्रमेय कहता है कि यदि एक पर्याप्त रूप से बड़ा समूह जोड़ या गुणन के तहत नहीं बढ़ता है, तो यह ज्यादातर एक उप-क्षेत्र के फैलाव में निहित होता है। प्रमेय (बोर्गैन, काट्ज़, ताओ (2004)): मान लीजिए कि यह एक परिमित क्षेत्र का उपसमुच्चय है ताकि कुछ लोगों के लिए ऐसा हो। फिर इसके साथ एक उप-क्षेत्र मौजूद है, और इसके साथ एक सेट है। उनका सुझाव है कि स्थिरांक स्वतंत्र हो सकता है। परिमित क्षेत्र योग-उत्पाद समस्या की ओर मात्रात्मक परिणाम आम तौर पर दो श्रेणियों में आते हैंः जब विशेषता के संबंध में छोटा होता है और जब विशेषता के संबंध में बड़ा होता है। ऐसा इसलिए है क्योंकि प्रत्येक सेटिंग में विभिन्न प्रकार की तकनीकों का उपयोग किया जाता है। छोटे समूह इस व्यवस्था में, विशेषता का एक क्षेत्र होने दें। ध्यान दें कि क्षेत्र हमेशा सीमित नहीं होता है। जब ऐसा होता है, और इसकी विशेषता शून्य होती है, तो-बाधा को हटा दिया जाता है। गैर-प्राथमिक क्रम वाले क्षेत्रों में,-बाधा को इस धारणा के साथ प्रतिस्थापित किया जा सकता है जिसमें किसी भी उपक्षेत्र के साथ बहुत बड़ा प्रतिच्छेदन नहीं होता है। इस दिशा में सबसे अच्छा काम ली और रोश-न्यूटन के उपरोक्त तालिका के संकेतन में एक प्रतिपादक प्राप्त करने के कारण है। बड़े समुच्चय जब अभाज्य के लिए, गरायेव के निम्नलिखित परिणाम के कारण योग-उत्पाद समस्या को हल माना जाता हैः प्रमेय (गरायेव (2007)): मान लीजिए। फिर. यह सीमा में इष्टतम है। इस परिणाम को 2011 में विन द्वारा गैर-प्राथमिक क्रम के सीमित क्षेत्रों में विस्तारित किया गया था। भिन्नताएँ और सामान्यीकरण संचालक बोर्गेन और चांग के अन्य संयोजनों ने सेटों के लिए बिना शर्त वृद्धि साबित की, जब तक कि कोई पर्याप्त राशि या उत्पादों पर विचार करता हैः प्रमेय (बोर्गेन, चांग (2003): चलो। फिर वहाँ मौजूद है ताकि सभी के लिए, एक है। कई कृतियों में, जोड़ और गुणन को एक अभिव्यक्ति में जोड़ा जाता है। आदर्श वाक्य के साथ जोड़ और गुणन सह-अस्तित्व में नहीं हो सकते हैं, कोई भी उम्मीद करता है कि एक समूह के जोड़ और गुणन के किसी भी गैर-तुच्छ संयोजन से विकास की गारंटी मिलनी चाहिए। ध्यान दें कि सीमित सेटिंग्स में, या गैर-तुच्छ उपक्षेत्रों वाले क्षेत्रों में, इस तरह के कथन के लिए आगे की बाधाओं की आवश्यकता होती है। रुचि के सेट में शामिल हैं (परिणाम के लिए):-स्टीवंस और वारेन दिखाते हैं कि-मर्फी, रोश-न्यूटन और श्क्रेडोव दिखाते हैं कि-स्टीवंस और वारेन दिखाते हैं कि-स्टीवंस और रुडनेव दिखाते हैं कि सम-फ्री सेट संदर्भ भी देखें बाहरी लिंक कॉम्बिनेटोरिक्स संख्या सिद्धांत में असतत गणित प्रमेय में प्रमेय का सारांश देता है।