Monochromatic products in random integer sets

तकनीकी सारांश: यादृच्छिक पूर्णांक समुच्चयों में एकरंगी उत्पाद (Monochromatic Products)

समस्या विवरण
यह शोध पत्र उस दहलीज प्रायिकता (threshold probability) $p = p(n)$ की जांच करता है जिस पर द्विपद यादृच्छिक उपसमुच्चय $[n]_p$ (जहाँ प्रत्येक तत्व $\{1, \dots, n\}$ को स्वतंत्र रूप से प्रायिकता $p$ के साथ शामिल किया जाता है) लगभग निश्चित रूप से (a.a.s.) "उत्पाद-शूर" (product-Schur) गुण प्रदर्शित करता है। एक समुच्चय $A$ को $r$-उत्पाद-शूर तब कहा जाता है यदि $A$ का कोई भी $r$-रंगों वाला रंगीकरण (colouring) समीकरण $ab = c$ के लिए एक एकरंगी समाधान (monochromatic solution) देता है, जहाँ $a, b, c \in A$ हैं। रैखिक समीकरणों (जैसे शूर का प्रमेय $a+b=c$ के लिए) के लिए दहलीज (thresholds) रैडो के प्रमेय और उसके बाद के स्थानांतरण सिद्धांतों (transference principles) के माध्यम से अच्छी तरह से समझी जा चुकी हैं, जबकि $ab=c$ जैसे गैर-रैखिक समीकरणों का व्यवहार यादृच्छिक समुच्चयों में काफी हद तक अनछुआ रहा है। लेखक उस महत्वपूर्ण घनत्व (critical density) $p^*$ को निर्धारित करने का लक्ष्य रखते हैं जहाँ यादृच्छिक समुच्चय 'उत्पाद-शूर न होने' से 'उत्पाद-शूर होने' की ओर परिवर्तित होता है।

कार्यप्रणाली (Methodology)
यह शोध पत्र निचली सीमा (lower bound - $(0)$-कथन) और ऊपरी सीमा (upper bound - $(1)$-कथन) के लिए अलग-अलग प्रमाण रणनीतियों का उपयोग करता है, यह देखते हुए कि यादृच्छिक रामसे सिद्धांत (random Ramsey theory) के मानक उपकरण गैर-रैखिक सेटिंग के लिए अपर्याप्त हैं।

1. $(0)$-कथन (निचली सीमा):
   छोटे $p$ के लिए $[n]_p$ के उत्पाद-शूर न होने को दिखाने के लिए, लेखक एक लालची रंगीकरण एल्गोरिदम (greedy colouring algorithm) का उपयोग करते हैं। वे तत्वों को बढ़ते क्रम में पारगमन (iterating) करके यादृच्छिक समुच्चय को दो उत्पाद-मुक्त समुच्चयों (लाल और नीला) में विभाजित करने का प्रयास करते हैं। एक तत्व को एक रंग तब सौंपा जाता है यदि वह पहले से रंगे गए तत्वों के साथ एक एकरंगी उत्पाद नहीं बनाता है।

   • बाधा विश्लेषण (Obstruction Analysis): एल्गोरिदम केवल तभी विफल होता है जब यादृच्छिक समुच्चय के भीतर एक विशिष्ट "वर्जित विन्यास" (forbidden configuration) मौजूद हो। ये विन्यास जटिल गुणात्मक निर्भरताओं (जैसे, $c = ab = def$, $a = xyz$, $b = uvw$) वाले पूर्णांकों को शामिल करते हैं।
   • गणना तर्क (Counting Argument): लेखक इन वर्जित विन्यासों का विस्तृत मामला विश्लेषण (case analysis) करते हैं, उन्हें विशिष्ट तत्वों की संख्या और पुनरावृत्ति के आधार पर वर्गीकृत करते हैं। वे यूनियन बाउंड (union bound) लागू करते हैं, और विभाजक सीमाओं (divisor bounds $D(n) = n^{o(1)}$) का लाभ उठाते हुए यह दिखाने के लिए कि $p \le n^{-1/9 - o(1)}$ के लिए, किसी भी ऐसे विन्यास के प्रकट होने की प्रायिकता $o(1)$ है।

2. $(1)$-कथन (ऊपरी सीमा):
   बड़े $p$ के लिए $[n]_p$ के उत्पाद-शूर होने को दिखाने के लिए, लेखक एक विशिष्ट परिमित उत्पाद-शूर पैटर्न (एक छोटा पूर्णांकों का सेट जो 2-रंगों वाले रंगीकरण के बावजूद एक एकरंगी समाधान को मजबूर करता है) का निर्माण करते हैं।

   • पैटर्न निर्माण: वे चार आधार पूर्णांकों के उत्पादों द्वारा निर्मित 14 तत्वों वाले एक सेट $S_{a,b,c,d}$ को परिभाषित करते हैं। वे मामला विश्लेषण के माध्यम से सिद्ध करते हैं कि इस सेट का कोई भी 2-रंगों वाला रंगीकरण $xy=z$ के लिए एक एकरंगी समाधान देता है।
   • अस्तित्व प्रमाण: वे प्रदर्शित करते हैं कि यदि $p = \omega(n^{-1/11})$, तो यादृच्छिक समुच्चय $[n]_p$ लगभग निश्चित रूप से इस पैटर्न की एक प्रति (copy) रखता है। यह यादृच्छिक समुच्चय को चरणों में प्रकट (reveal) करके और आवश्यक आधार पूर्णांकों ($a, b, c, d$) तथा उनके आवश्यक उत्पादों को खोजने में विफल होने की प्रायिकता को नगण्य दिखाकर प्राप्त किया जाता है।
   • मानक विधियों से विचलन: लेखक स्पष्ट रूप से नोट करते हैं कि मानक स्थानांतरण सिद्धांत और हाइपरग्राफ कंटेनर विधियाँ (जो "सुपरसेचुरेशन" (supersaturation) पर निर्भर करती हैं—वह गुण जहाँ सघन समुच्चय कई एकरंगी समाधानों को समाहित करते हैं) यहाँ विफल हो जाती हैं। उत्पादों के लिए, ऐसे रंगीकरण मौजूद हैं जहाँ केवल समाधानों का एक लुप्त प्रायता (vanishing fraction) ही एकरंगी होता है, जिससे सुपरसेचुरेशन-आधारित प्रमाण अप्रभावी हो जाते हैं।

3. $r$ रंगों के लिए विस्तार:
   $r \ge 3$ के लिए, लेखक शूर संख्याओं ($S(r)$) और डबल-सम शूर संख्याओं ($S'(r)$) का उपयोग करके परिणामों का सामान्यीकरण करते हैं।

   • निचली सीमा: वे अंतराल (intervals) के आधार पर एक रंगीकरण का निर्माण करते हैं, जो $n^{1/S'(r)}$ द्वारा स्केल किए गए हैं, जो योग और शिफ्ट किए गए योगों (shifted sums) को टालते हैं, जो एकरंगी योगों से बचने में अनुवादित होता है और यह एकरंगी उत्पादों से बचने में भी मदद करता है।
   • ऊपरी सीमा: वे सेट $U_x = \{x, x^2, \dots, x^{S(r)}\}$ का उपयोग करते हैं, जो $S(r)$ की परिभाषा के अनुसार $r$-उत्पाद-रंगी योग्य (product-colourable) नहीं है। वे दिखाते हैं कि $p = \omega(n^{-1/S(r)^2})$ के लिए, ऐसा सेट a.a.s. प्रकट होता है।

मुख्य परिणाम

• प्रमेय 1.2 (दो रंग): $[n]_p$ के उत्पाद-शूर होने की दहलीज $n^{-1/9 - o(1)}$ और $n^{-1/11}$ के बीच है। विशेष रूप से:
  • यदि $p \le n^{-1/9 - o(1)}$, तो $[n]_p$ a.a.s. उत्पाद-शूर नहीं है।
  • यदि $p \ge \omega(n^{-1/11})$, तो $[n]_p$ a.a.s. उत्पाद-शूर है।
• प्रमेय 1.4 ($r$ रंग): $r \ge 2$ के लिए, दहलीज $p^*_r$ संतुष्ट करती है:
  • $p^*_r \le n^{-1/S'(r)}$ (दहलीज पर निचली सीमा / अस्तित्व के लिए $p$ की ऊपरी सीमा)।
  • $p^*_r \ge n^{-1/S(r)^2}$ (दहलीज पर ऊपरी सीमा / अस्तित्व के लिए निचली सीमा)।
  • महत्वपूर्ण रूप से, रैखिक समीकरणों के विपरीत जहाँ दहलीज $r$ से स्वतंत्र होती है, उत्पादों के लिए दहलीज रंगों की संख्या पर निर्भर करती है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह गैर-रैखिक समीकरणों, विशेष रूप से एकरंगी उत्पादों के संबंध में यादृच्छिक समुच्चयों के रामसे गुणों की खोज करने वाला पहला अध्ययन है। इसके प्राथमिक योगदान हैं:

1. दहलीज सीमाओं को स्थापित करना: उत्पाद-शूर दहलीज के लिए पहले गैर-तुच्छ (non-trivial) सीमाएँ प्रदान करना, यह दिखाना कि यह रैखिक मामले ($n^{-1/2}$) से भिन्न है।
2. पद्धतिगत नवाचार: यह प्रदर्शित करना कि गैर-रैखिक रामसे गुणों के लिए प्रमाण तकनीकें रैखिक वाले से काफी भिन्न होती हैं। लेखक तर्क देते हैं कि उत्पाद समुच्चयों में सुपरसेचुरेशन की कमी, शक्तिशाली स्थानांतरण सिद्धांतों और कंटेनर विधियों को अमान्य कर देती है, जिन्होंने रैखिक रैडो-प्रकार की समस्याओं को हल किया था, जिसके लिए लालची रंगीकरण विश्लेषण और विशिष्ट पैटर्न एम्बेडिंग जैसे नए दृष्टिकोणों की आवश्यकता होती है।
3. रंगों पर निर्भरता: यह उजागर करना कि गैर-रैखिक समीकरणों के लिए, दहलीज रंगों की संख्या $r$ पर निर्भर करती है, जो रैखिक रैडो प्रमेयों में देखे गए रंग-स्वतंत्रता के विपरीत है।

अनुमान और भविष्य की दिशाएँ
लेखक अनुमान लगाते हैं कि वास्तविक दहलीज $n^{-1/11}$ है, जो उनके ऊपरी सीमा से मेल खाती है। वे सुझाव देते हैं कि यह उनके प्रमाण में उपयोग किए गए विशिष्ट सीमित-आकार के विन्यास के प्रकट होने से निर्धारित होता है। वे स्वीकार करते हैं कि निचली सीमा ($n^{-1/9}$) में सुधार करने के लिए परिष्कृत लालची रंगीकरण से परे नए विचारों की आवश्यकता होगी। अंत में, वे प्रस्तावित करते हैं कि उनकी तकनीकों को अन्य गैर-रैखिक समीकरणों, जैसे $a^2 = bc$ या $ab = cd$ पर भी लागू किया जा सकता है।