🔢 mathematics

Prime Certificates for Exact Vertex-Coprime Ramsey Numbers

यह शोधपत्र प्राथमिक-आधारित प्रमाणों (elementary prime-based certificates) का उपयोग करते हुए को-प्राइम ग्राफ पर मिश्रित शीर्ष-और-किनारा-रंगण (mixed vertex- and edge-coloring) को-प्राइम रामसे संख्याओं के लिए सटीक सूत्र स्थापित करता है, विशेष रूप से यह सिद्ध करता है कि शीर्ष-रंगण संख्या $m$ -वीं अभाज्य संख्या के बराबर है जहाँ $m$ क्लीक आकारों का योग घटा एक है, और किनारा-रंगण संख्या एक अभाज्य-सूचकांक हस्तांतरण (prime-index transfer) के माध्यम से एक शास्त्रीय रामसे संख्या में परिवर्तित हो जाती है।

मूल लेखक: Zhicheng Du, Wenji Xi, Zhuo Deng, Lan Ma

प्रकाशित 2026-05-27

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Zhicheng Du, Wenji Xi, Zhuo Deng, Lan Ma

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास एक विशाल कमरा है जो लोगों से भरा हुआ है, जिन्हें 1 से $n$ तक नंबर दिए गए हैं। इस कमरे में, दो लोगों को तब "दोस्त" माना जाता है जब उनके नंबरों के बीच 1 के अलावा कोई अन्य साझा गुणनखंड (common factor) न हो (गणितज्ञ इसे "कोप्राइम" या सह-अभाज्य कहते हैं)। उदाहरण के लिए, 3 और 4 दोस्त हैं, लेकिन 4 और 6 नहीं हैं (दोनों का 2 एक साझा गुणनखंड है)।

यह शोध पत्र एक पहेली को हल करता है जिसमें इन लोगों को अलग-अलग रंगों की शर्ट (मान लीजिए लाल, नीला, हरा, आदि) पहनाने के बारे में है, ताकि एक विशिष्ट "वर्जित" (forbidden) पैटर्न न बने। वर्जित पैटर्न दोस्तों का एक ऐसा समूह है जो सभी एक ही रंग की शर्ट पहनते हैं।

मुख्य प्रश्न

लेखक पूछते हैं: कमरे का आकार ( $n$ ) कितना बड़ा होना चाहिए, इससे पहले कि आप एक ही रंग के $k$ आपसी दोस्तों का एक समूह होने के लिए मजबूर हो जाएं?

मानक गणितीय पहेलियों (जिन्हें रामसे थ्योरी कहा जाता है) की दुनिया में, इसका उत्तर आमतौर पर एक बहुत बड़ा, जटिल नंबर होता है जिसे गणना करना अविश्वसनीय रूप से कठिन होता है। अक्सर छोटे समूहों के लिए भी उत्तर का अनुमान लगाने के लिए आपको सुपरकंप्यूटर चलाने पड़ते हैं।

आश्चर्यजनक खोज

लेखकों ने पाया कि इस विशिष्ट "कोप्राइम" कमरे के लिए, उत्तर आश्चर्यजनक रूप से सरल और सटीक है। यह पूरी तरह से अभाज्य संख्याओं (prime numbers) (जैसे 2, 3, 5, 7, 11... जो केवल स्वयं से या 1 से विभाजित हो सकते हैं) पर निर्भर करता है।

उन्होंने जो सूत्र खोजा वह है:

उत्तर $M$ -वीं अभाज्य संख्या है।

जहाँ $M$ की गणना प्रत्येक रंग के लिए आवश्यक अतिरिक्त दोस्तों की संख्या को जोड़कर, उसमें से एक घटाकर की जाती है।

यदि आप 3 लाल दोस्तों और 3 नीले दोस्तों के समूह से बचना चाहते हैं, तो आप $(3-1) + (3-1) = 4$ की गणना करते हैं।
उत्तर 4थी अभाज्य संख्या, यानी 7 है।
इसका अर्थ है कि यदि आपके पास 7 लोग हैं, तो आप उन्हें चाहे कैसे भी रंग दें, आपके पास एक ही रंग के 3 आपसी दोस्तों का समूह अवश्य होगा। यदि आपके पास केवल 6 लोग हैं, तो आप इसे इस तरह के समूह से बचने के लिए रंग सकते हैं।

उन्होंने इसे कैसे हल किया? ("प्राइम बिन" सादृश्य)

लेखकों ने सुपरकंप्यूटर का उपयोग नहीं किया। उन्होंने दो विचारों पर आधारित एक चतुर "प्रमाणपत्र" (प्रूफ) का उपयोग किया:

"प्राइम क्लीक" (ऊपरी सीमा - Upper Bound):
कमरे में लोगों के एक विशेष समूह की कल्पना करें: संख्या 1 और सभी अभाज्य संख्याएँ (2, 3, 5, 7...)।
- संख्या 1 सभी का दोस्त है।
- हर अभाज्य संख्या अन्य सभी अभाज्य संख्याओं की दोस्त है (क्योंकि उनका कोई साझा गुणनखंड नहीं है)।
- यह पूरी तरह से अभाज्य संख्याओं से बना एक आदर्श "मित्र मंडल" (क्लीक) बनाता है।
- यदि कमरे में पर्याप्त अभाज्य संख्याएँ हैं, तो पिजनहोल सिद्धांत (Pigeonhole Principle) लागू हो जाता है: यदि आप इन अभाज्य-दोस्तों को रंगीन डिब्बों (bins) में डालने की कोशिश करते हैं, तो एक डिब्बा अनिवार्य रूप से बहुत अधिक भर जाएगा। वह डिब्बा आपका वर्जित समूह बन जाएगा। यह सिद्ध करता है कि उत्तर एक निश्चित अभाज्य संख्या से अधिक नहीं हो सकता।
"प्राइम बिन" कलरिंग (निचली सीमा - Lower Bound):
यह सिद्ध करने के लिए कि उत्तर उस अभाज्य संख्या से कम नहीं है, उन्होंने दिखाया कि आप कमरे को रंग सकते हैं ताकि वर्जित समूह से बचा जा सके।
- उन्होंने सभी अभाज्य संख्याओं को लिया और उन्हें रंगों के अनुरूप "बिनों" (समूहों) में विभाजित किया।
- अन्य सभी संख्याओं (भाज्य संख्याएँ जैसे 4, 6, 8, 9) को उनके एक अभाज्य गुणनखंड के आधार पर रंगा गया।
- सादृश्य: कल्पना करें कि हर भाज्य संख्या एक बच्चा है। बच्चा एक "अभिभावक" (एक अभाज्य गुणनखंड) चुनता है और उसी रंग की शर्ट पहनता है जो उसका अभिभावक पहनता है।
- क्योंकि प्रत्येक बिन में अभाज्य संख्याओं की संख्या सीमित है, और हर भाज्य संख्या एक विशिष्ट अभिभावक से जुड़ी हुई है, आप किसी भी एक रंग में आपसी दोस्तों का बड़ा समूह कभी नहीं बना सकते।

यह क्यों महत्वपूर्ण है

यह एक विशाल खोज को छोटा कर देता है: आमतौर पर, इन समस्याओं को हल करने के लिए लाखों संभावनाओं की जांच करनी पड़ती है (जैसे कि SAT सॉल्वर)। यहाँ, "खोज" अभाज्य संख्याओं की एक सरल जांच में सिमट जाती है।
यह यादृच्छिक (random) नहीं है: कई गणितीय समस्याओं में, उत्तर एक अराजक, यादृच्छिक ढेर जैसा लगता है। यहाँ, संरचना बहुत व्यवस्थित है और अभाज्य संख्याओं के "कंकाल" द्वारा नियंत्रित है।
यह पिछली गलतियों को सुधारता है: शोध पत्र नोट करता है कि 10 के समूह आकार के लिए पिछले कंप्यूटर प्रयासों ने गलत उत्तर (53) दिया था। लेखकों ने सिद्ध किया कि सही उत्तर 61 (18वीं अभाज्य संख्या) है, जिससे पता चला कि कंप्यूटर गलत संरचना को देख रहा था।

अन्य परिदृश्य क्या हैं?

लेखक ने इसके विभिन्न रूपों को भी देखा:

एज कलरिंग (Edge Coloring): यदि आप लोगों के बजाय उनके संबंधों (दोस्ती) को रंगते हैं, तो उत्तर अभी भी एक अभाज्य संख्या ही है, लेकिन यह एक अलग, क्लासिक गणितीय पहेली के उत्तर से संबंधित अभाज्य संख्या है। यह एक अनुवाद की तरह है।
संतुलित रंग (Balanced Colors): यदि आप मांग करते हैं कि लाल और नीले समूह का आकार बिल्कुल समान होना चाहिए? आश्चर्यजनक रूप से, उत्तर अभी भी वही अभाज्य संख्या है। लेखकों ने समूहों को संतुलित करने के लिए "बच्चों" (भाज्य संख्याओं) को व्यवस्थित करने का एक विशेष तरीका खोजा, बिना नियमों को तोड़े।
कमरे को बदलना: यदि आप कमरे को 1 के बजाय 100 से शुरू करते हैं (एक "शिफ्टेड इंटरवल"), तो यह जादू टूट जाता है। सरल सूत्र अब काम नहीं करता क्योंकि आप विशेष "संख्या 1" और अभाज्य अनुक्रम की आदर्श शुरुआत को खो देते हैं। यह दर्शाता है कि सूत्र शुरुआती स्थितियों के प्रति बहुत संवेदनशील है।

सारांश में

यह शोध पत्र एक जासूसी कहानी है जहाँ जासूसों को एहसास हुआ कि संख्याओं का एक अराजक दिखने वाला कमरा वास्तव में एक बहुत ही व्यवस्थित रहस्य रखता है: अभाज्य संख्याएँ ही बॉस हैं। यह समझकर कि अभाज्य संख्याएँ कमरे को कैसे व्यवस्थित करती हैं, उन्होंने एक सरल, सटीक सूत्र खोजा जो आमतौर पर भारी कंप्यूटिंग शक्ति की मांग करता है। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने एक "प्राइम बिन" प्रणाली बनाई जो ठीक से बताती है कि रेखा कहाँ खींची गई है।

तकनीकी सारांश: सटीक वर्टेक्स-कोप्राइम रामसे संख्याओं के लिए अभाज्य प्रमाणपत्र (Prime Certificates)

समस्या विवरण
यह शोध पत्र मिश्रित वर्टेक्स-कोप्राइम रामसे संख्या (mixed vertex-coprime Ramsey number) की जांच करता है, जिसे $R_{cop}(k_1, \dots, k_c)$ द्वारा दर्शाया गया है, जो कोप्राइम ग्राफ $G_n$ पर परिभाषित है। $G_n$ का शीर्ष समुच्चय (vertex set) $\{1, \dots, n\}$ है, जहाँ दो भिन्न शीर्षों $a$ और $b$ के बीच एक किनारा (edge) तब होता है जब $\gcd(a, b) = 1$ हो। यह समस्या उस लघुतम पूर्णांक $n$ की खोज करती है जिसके लिए $G_n$ के शीर्षों का प्रत्येक $c$ -रंगण (c-coloring) किसी $i \in \{1, \dots, c\}$ के लिए आकार $k_i$ का एक मोनोक्रोमैटिक क्लिक (monochromatic clique) समाहित करता है। समतुल्य रूप से, यह उस थ्रेशोल्ड (threshold) की खोज करता है जहाँ $\{1, \dots, n\}$ का $c$ समुच्चयों में कोई भी विभाजन कम से कम एक भाग में $k_i$ परस्पर सह-अभाज्य (pairwise coprime) पूर्णांकों के एक सेट को अनिवार्य रूप से समाहित करता है।

कार्यप्रणाली और मुख्य तंत्र
लेखक इस समस्या को एक संरचनात्मक "प्रमाणपत्र" (certificate) की पहचान करके हल करते हैं जो खोज क्षेत्र को संकुचित कर देता है, जो प्रत्यक्ष SAT एन्कोडिंग की घातीय जटिलता (exponential complexity) के विपरीत है। कार्यप्रणाली अभाज्य विभाजकों (prime divisors) पर आधारित दो पूरक निर्माणों पर निर्भर करती है:

ऊपरी सीमा (अभाज्य क्लिक - Prime Clique): समुच्चय $\{1\} \cup \{p \le n : p \text{ एक अभाज्य संख्या है}\}$ $G_n$ में आकार $\pi(n) + 1$ का एक क्लिक बनाता है, जहाँ $\pi(n)$ अभाज्य गणना फलन (prime-counting function) है। पिजनहोल सिद्धांत (pigeonhole principle) द्वारा, यदि रंगों की कुल क्षमता (कुल $\sum (k_i - 1)$ ) इस क्लिक के आकार से कम है, तो एक आवश्यक आकार का मोनोक्रोमैटिक क्लिक अनिवार्य हो जाता है।
अभाज्य-बिन विभाजन (Prime-Bin Partition): $n$ के थ्रेशोल्ड से नीचे होने पर, लेखक एक वैध रंगण का निर्माण करते हैं जो मोनोक्रोमैटिक क्लिक से बचता है। यह उपलब्ध अभाज्य संख्याओं को उनकी क्षमताओं (क्षमता $k_i - 1$ के साथ, 1 के सार्वभौमिक शीर्ष के समायोजन सहित) के अनुसार "बिनों" (bins) में विभाजित करके प्राप्त किया जाता है। प्रत्येक भाज्य संख्या (composite number) को उसके एक चुने हुए अभाज्य विभाजक के आधार पर रंग दिया जाता है जो इन बिनों में से एक में आता है। चूंकि परस्पर सह-अभाज्य पूर्णांक एक अभाज्य विभाजक साझा नहीं कर सकते, इसलिए किसी भी मोनोक्रोमैटिक क्लिक का आकार उनके साक्षी अभाज्य संख्याओं (witness primes) वाले बिन की क्षमता द्वारा सीमित होता है।

इस दृष्टिकोण को सपोर्ट-डिस्जॉइंटनेस ग्राफ (support-disjointness graphs) के लिए सामान्यीकृत किया गया है, जहाँ शीर्ष 'सपोर्ट' (परमाणुओं के उपसमुच्चय) रखते हैं और आसन्नता (adjacency) विसंयुक्त सपोर्ट द्वारा परिभाषित होती है। कोप्राइम ग्राफ इसका एक विशिष्ट उदाहरण है जहाँ परमाणु अभाज्य संख्याएँ हैं।

प्रमुख योगदान और परिणाम

सटीक मिश्रित सूत्र: शोध पत्र मिश्रित वर्टेक्स-कोप्राइम रामसे संख्या के लिए सटीक सूत्र सिद्ध करता है:
$R_{cop}(k_1, \dots, k_c) = p_M$
जहाँ $M = \sum_{i=1}^c (k_i - 1)$ और $p_M$ $M$ -वीं अभाज्य संख्या है। यह परिणाम सभी $c \ge 1$ और $k_i \ge 2$ के लिए मान्य है।
एज-कलरिंग न्यूनीकरण (Edge-Coloring Reduction): शोध पत्र उसी होस्ट ग्राफ पर वर्टेक्स कलरिंग और एज कलरिंग के बीच अंतर स्पष्ट करता है। यह शास्त्रीय पूर्ण-ग्राफ रामसे संख्याओं $R_{cl}$ के लिए एक सटीक न्यूनीकरण स्थापित करता है:
$R_{cop}^{edge}(k_1, \dots, k_c) = p_{R_{cl}(k_1, \dots, k_c) - 1}$
यह दर्शाता है कि एज-कोप्राइम मान नए अंकगणितीय स्थिरांक नहीं हैं, बल्कि एक अभाज्य-इंडेक्स मानचित्र के माध्यम से देखे गए शास्त्रीय रामसे संख्याएँ हैं।
संतुलित द्वि-रंग थ्रेशोल्ड (Balanced Two-Color Threshold): लेखक इस चिंता का समाधान करते हैं कि क्या निचली-सीमा निर्माण अत्यधिक असंतुलित रंग वर्गों पर निर्भर हो सकता है। वे सिद्ध करते हैं कि दो-रंग डायगोनल मामले के लिए, संतुलित थ्रेशोल्ड (जहाँ रंग वर्ग का आकार अधिकतम 1 के अंतर से भिन्न होता है) अनियंत्रित थ्रेशोल्ड के समान ही है: $L_{bal}(k; 2) = p_{2k-2} - 1$ । यह एक नियतात्मक अभाज्य-बिन विभाजन और एक कमजोर अभाज्य-इंडेक्स गैप असमानता ( $2p_m < p_{2m} < 3p_m$ ) के माध्यम से प्राप्त किया गया है।
बहु-रंग संतुलन और सीमा मामले (Multicolor Balance and Boundary Cases):
- $c \ge 3$ के लिए, संतुलित थ्रेशोल्ड छोटे $k$ के लिए सटीक नहीं है, लेकिन यह सभी पर्याप्त बड़े $k$ के लिए सटीक हो जाता है (इवेंचुअल एक्सैक्टनेस), जिसे हॉल-प्रकार के तर्क और सेल्बर्ग-डेलांगे अनुमानों (Selberg–Delange estimates) के माध्यम से सिद्ध किया गया है।
- शोध पत्र शिफ्टेड इंटरवल्स (shifted intervals) $\{m+1, \dots, m+n\}$ का विश्लेषण करता है। सार्वभौमिक शीर्ष 1 और प्रारंभिक अभाज्य क्लिक के बिना, सटीक सूत्र विफल हो जाता है, और थ्रेशोल्ड स्थानीय अभाज्य-कारक संरचनाओं पर निर्भर करता है।
एल्गोरिद्मिक प्रिमिटिव (Algorithmic Primitive): एक बहुपद-समय (polynomial-time) प्रमाणपत्र-निष्कर्षण प्रिमिटिव प्रस्तावित किया गया है जो सत्यापित करता है कि क्या कोई दिया गया ग्राफ सपोर्ट-डिस्जॉइंटनेस प्रमाणपत्र को स्वीकार करता है। यदि सत्यापित किया जाता है, तो रामसे थ्रेशोल्ड और चरम रंगण (extremal colorings) बिना खोज के निर्धारित किए जाते हैं।

महत्व और दायरा

शोध पत्र दावा करता है कि वह पूर्णांक कोप्राइम ग्राफ पर वर्टेक्स-कलरिंग समस्या का पूर्ण समाधान प्रदान करता है, जो बड़े पैमाने पर कम्प्यूटेशनल खोजों (जैसे लाखों क्लॉज वाले SAT एन्कोडिंग) को एक छोटे, स्पष्ट अभाज्य-इंडेक्स प्रमाणपत्र से बदल देता है।

संरचनात्मक अंतर्दृष्टि: यह कार्य रेखांकित करता है कि कोप्राइम ग्राफ की अंकगणितीय कठोरता (जो अभाज्य विभाजकों द्वारा नियंत्रित है) रामसे समस्या को अभाज्य बिन-पैकिंग समस्या में सरल बना देती है, जो पूर्ण ग्राफों पर शास्त्रीय एज रामसे समस्याओं की तुलना में विषम है।
पूर्व कार्य का स्पष्टीकरण: लेखक स्पष्ट करते हैं कि "कोप्राइम रामसे संख्याओं" (विशेष रूप से टोवेल द्वारा) पर पिछले कम्प्यूटेशनल परिणाम एज-कलरिंग संस्करण को संदर्भित करते थे, जिसे यह शोध पत्र शास्त्रीय रामसे संख्याओं के रूप में देखता है। यहाँ प्रस्तुत वर्टेक्स-कलरिंग सूत्र सार्वजनिक स्रोतों में उपलब्ध नहीं था।
सीमाएँ: शोध पत्र स्पष्ट रूप से कहता है कि यह शास्त्रीय एज रामसे बाउंड्स में सुधार नहीं करता है या सामान्य AI-सहायता प्राप्त सॉल्वर प्रस्तावित नहीं करता है। परिणाम कोप्राइम ग्राफ और उसके सपोर्ट-डिस्जॉइंटनेस वेरिएंट्स के लिए विशिष्ट हैं। शोध पत्र गैर-पूर्ण एज लक्ष्यों (पथ, चक्र), घनत्व-बाधित बहु-रंग संतुलन, और अन्य अंकगणितीय ग्राफों के लिए रामसे थ्रेशोल्ड के संबंध में खुले प्रश्न भी चिन्हित करता है जहाँ सपोर्ट-डिस्जॉइंटनेस गुण पूरी तरह से आसन्नता (adjacency) को स्पष्ट नहीं करता है।

संक्षेप में, यह शोध पत्र विशिष्ट वर्ग के अंकगणितीय रामसे नंबरों के लिए एक निर्णायक, प्राथमिक प्रमाण प्रदान करता है, यह प्रदर्शित करते हुए कि इस होस्ट ग्राफ के लिए, "बाधा" (obstruction) एक छिपी हुई रैंडम-जैसी संरचना के बजाय एक स्पष्ट अभाज्य क्लिक है।