🔢 mathematics

Three-color van der Waerden numbers grow super-exponentially

यह शोध पत्र यह स्थापित करता है कि तीन-रंगीन वान डेर वार्डेन संख्या $w(k;3)$ अति-घातांकीय (super-exponentially) रूप से बढ़ती है, क्योंकि यह $2^{k (\log^* k)/4}$ तक के पूर्णांकों का एक ऐसा तीन-रंगीन चित्रण (three-coloring) निर्मित करता है जो एकरंगी $k$ -पदों के अंकगणितीय प्रगतिक्रम (arithmetic progressions) से मुक्त है, और साथ ही एक नई निचली सीमा (lower bound) भी प्रदान करता है जो एर्दोश और ग्राहम के कैनोनिकल वान डेर वार्डेन संख्याओं के संबंध में एक लंबे समय से चले आ रहे प्रश्न को हल करती है।

मूल लेखक: Jacob Fox, Zach Hunter

प्रकाशित 2026-06-02

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

CC BY 4.0

मूल लेखक: Jacob Fox, Zach Hunter

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

कल्पना कीजिए कि आपके पास नंबरों वाली एक बहुत लंबी टाइलों की कतार है, जो 1 से लेकर किसी बहुत बड़ी संख्या $N$ तक है। आप प्रत्येक टाइल को तीन रंगों में से किसी एक रंग (मान लीजिए लाल, नीला और हरा) से पेंट करना चाहते हैं।

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

एक अंकगणितीय प्रगति (arithmetic progression) बस संख्याओं का एक समूह है जो समान मात्रा में आगे बढ़ता है, जैसे 5, 10, 15, 20। यदि आप 5, 10, 15 और 20 को सभी लाल रंग से पेंट करते हैं, तो आपने एक "मोनोक्रोमैटिक" (सभी एक ही रंग के) प्रोग्रेशन बना दिया है।

संख्या $w(k; 3)$ उस लाइन की लंबाई है जहाँ, चाहे आप इसे कितनी भी चतुराई से पेंट करें, आप $k$ टाइलों का एक ऐसा क्रम (समान अंतराल के साथ) बनाने से नहीं बच पाएंगे जो एक ही रंग के हों।

पुराना रहस्य

लंबे समय तक, गणितज्ञों को पता था कि ये संख्याएँ मौजूद हैं, लेकिन वे यह नहीं जानते थे कि $k$ के बढ़ने के साथ ये कितनी तेजी से बढ़ती हैं।

कुछ लोगों को लगा कि ये संख्याएँ एक मानक घातीय फलन (exponential function) की तरह बढ़ती हैं (जैसे $2^k$ )।
अन्य लोगों ने, जिनमें प्रसिद्ध गणितज्ञ पॉल अर्दोस (Paul Erdős) भी शामिल थे, अनुमान लगाया कि तीन या अधिक रंगों के लिए, ये संख्याएँ सुपर-एक्सपोनेंशियल (super-exponentially) रूप से बढ़ती हैं। इसका मतलब है कि वे इतनी तेजी से बढ़ती हैं कि वे सबसे शक्तिशाली घातीय फलनों को भी पीछे छोड़ देती हैं। यह एक घोंघे की तुलना में एक ऐसे रॉकेट से है जो प्रकाश की गति से भी तेज़ भागता है।

एर्दोस ने इस बात को सिद्ध करने के लिए किसी को $500 का पुरस्कार देने की पेशकश की थी कि तीन रंगों के लिए यह सुपर-एक्सपोनेंशियल विकास होता है।

नई खोज

इस शोध पत्र में, जैकब फॉक्स और ज़ैक हंटर ने अंततः सिद्ध किया कि एर्दोस सही थे।

वे दिखाते हैं कि तीन रंगों के लिए, एक पैटर्न बनाने के लिए मजबूर होने से पहले लाइन को अकल्पनीय रूप से लंबा होना चाहिए। विशेष रूप से, वे सिद्ध करते हैं कि यह संख्या $2^{k(\log^* k)/4}$ से बड़ी है।

इसे समझने के लिए, "इटरेटेड लॉगरिदम" ( $\log^* k$ ) की कल्पना करें। यह एक ऐसी संख्या है जो इतनी धीमी गति से बढ़ती है कि यह लगभग स्थिर (flat) लगती है। ब्रह्मांड में परमाणुओं की संख्या जितनी विशाल संख्या के लिए भी, $\log^* k$ केवल लगभग 5 होता है।

उपमा: यदि मानक घातीय वृद्धि (exponential growth) एक खरगोश की आबादी के हर दिन दोगुना होने की तरह है, तो यह नया परिणाम एक ऐसी खरगोश आबादी की तरह है जो दोगुना होती है, फिर दोगुना होने की गति दोगुनी हो जाती है, फिर उस गति की गति दोगुनी हो जाती है, और इसी तरह, लेकिन केवल तब जब आप एक ऐसी संख्या का इंतज़ार करते हैं जो शायद ही बदलती है। परिणाम एक ऐसी संख्या है जो कल्पना से परे है।

उन्होंने यह कैसे किया? (जादु적인 तरकीबें)

लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने एक "निर्माण" (एक विशिष्ट तरीका जिससे टाइलों को पेंट किया जाता है) बनाया जो पैटर्न से यथासंभव लंबे समय तक बचता है। उन्होंने कुछ चतुर गणितीय तरकीबों का उपयोग किया:

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

एक छोटे समूह से शुरू करें।
पैटर्न से बचने के लिए एक बड़ा समूह बनाने हेतु शफल और संयोजित करें।
इसे फिर से करें, ताकि एक और बड़ा समूह प्राप्त हो सके।
वे इसे लगभग $\log^* k$ बार कर सकते हैं।

क्योंकि वे इस प्रक्रिया को इतनी बार दोहरा सकते हैं, टाइलों की अंतिम संख्या जिसे वे बिना पैटर्न बनाए पेंट कर सकते हैं, अविश्वसनीय रूप से विशाल हो जाती है।

बोनस: एक पुराने पहेली को सुलझाना

तीन रंगों के लिए इसे सिद्ध करते हुए, उन्होंने एर्दोस और ग्राहम द्वारा पेश की गई एक संबंधित पहेली को भी हल किया जो "कैनोनिकल" (Canonical) वैन डेर वाल्डन संख्याओं के बारे में थी।

इस संस्करण में, आप केवल एक रंग के अनुक्रम की तलाश नहीं कर रहे हैं। आप एक ऐसा अनुक्रम देख रहे हैं जो या तो एक ही रंग का है या सभी अलग-अलग रंगों का है (जैसे लाल, नीला, हरा, लाल, नीला, हरा... नहीं, बस सभी अलग रंग)।

परिणाम: उन्होंने सिद्ध किया कि इस पैटर्न को मजबूर करने के लिए आवश्यक टाइलों की संख्या भी सुपर-विशाल है। यह $k$ की किसी भी सरल घात (power) से तेज़ बढ़ता है। यह दशकों पुराने प्रश्न को सुलझाता है कि क्या ये संख्याएँ इतनी तेज़ी से बढ़ती हैं कि उन्हें "सुपर-एक्सपोनेंशियल" माना जा सके।

सारांश

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

तकनीकी सारांश: तीन-रंगीन वैन डेर वाल्डन संख्याएँ सुपर-एक्सपोनेंशियल रूप से बढ़ती हैं

समस्या विवरण
यह शोध पत्र वैन डेर वाल्डन संख्याओं, जिन्हें $w(k; r)$ द्वारा दर्शाया जाता है, की वृद्धि दर को संबोधित करता है। यह संख्या उस न्यूनतम पूर्णांक $N$ को परिभाषित करती है कि प्रत्येक $r$ -रंगों (r-coloring) के लिए $\{1, 2, \dots, N\}$ के सेट में एक मोनोक्रोमैटिक (एक ही रंग वाली) अंकगणितीय प्रगति (arithmetic progression) का होना अनिवार्य है। हालांकि वैन डेर वाल्डन प्रमेय द्वारा इन संख्याओं का अस्तित्व सुनिश्चित है, लेकिन उनकी सटीक एसिम्प्टोटिक वृद्धि एक मौलिक खुला प्रश्न बना हुआ है।

ऐतिहासिक रूप से, $w(k; r)$ की वृद्धि गहन अटकलों का विषय रही है। स्थिर $r$ के लिए, एर्दोस (Erdős) ने अनुमान लगाया था कि $w(k; 2)$ सुपर-एक्सपोनेंशियल रूप से बढ़ता है (अर्थात $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$ )। इसके विपरीत, अन्य अनुमानों ने लीनियर एक्सपोनेंशियल वृद्धि का सुझाव दिया, विशेष रूप से $\lim_{k \to \infty} w(k; r)^{1/k} = r$ । इस कार्य से पूर्व, $w(k; r)$ के लिए ज्ञात सर्वोत्तम निचली सीमाएँ (lower bounds) मुख्य रूप से लोवाज़ लॉकल लेम्मा (Lovász Local Lemma) या विशिष्ट बीजगणितीय निर्माणों से प्राप्त की गई थीं, जो $w(k; r) \geq r^{k-1}/(4k)$ या, स्थिर $r \geq 5$ के लिए, $(3r/3)^{(1-o(1))k}$ के रूप में सीमाएँ प्रदान करती थीं। लेखक नोट करते हैं कि जबकि हंटर [20] के एक पिछले परिणाम ने $r \geq 5$ के लिए लीनियर एक्सपोनेंशियल अनुमान को गलत सिद्ध कर दिया था, $r=3$ के लिए मामला (और छोटे निश्चित $r$ के लिए सामान्य व्यवहार) अनसुलझा रहा।

कार्यप्रणाली (Methodology)
लेखक $w(k; r)$ के लिए निचली सीमाएँ स्थापित करने के लिए एक नवीन संभाव्य निर्माण (probabilistic construction) विकसित करते हैं। कार्यप्रणाली तीन प्राथमिक घटकों पर निर्भर करती है:

चक्रीय समूहों (Cyclic Groups) में सघन प्रगति-मुक्त सेट:
लेखक चक्रीय समूहों $\mathbb{Z}_N$ के बहुत सघन उपसमुच्चय (subsets) का निर्माण करते हैं जिनमें कोई $k$ -टर्म अंकगणितीय प्रगति (k-APs) नहीं होती है। वे एर्दोस-टुरान निर्माण (आधार $p$ में $p-1$ के बराबर अंक वाले पूर्णांकों के सेट) के विस्तार का उपयोग करते हैं, जिसे चक्रीय समूहों के लिए अनुकूलित किया गया है। महत्वपूर्ण रूप से, वे सिद्ध करते हैं कि "हिटिंग सेट्स" (लेम्मा 2.8) का अस्तित्व है जो विरल (density $\leq \epsilon$ ) हैं, फिर भी चक्रीय समूह में प्रत्येक $k$ -AP के तत्वों के एक स्थिर अंश (constant fraction) को प्रतिच्छेद (intersect) करते हैं। यह प्राइम्स के एक सेट के मॉड्युलो यादृच्छिक कॉंग्रुएंस क्लासेस (congruence classes) का चयन करके प्राप्त किया जाता है।
लोवाज़ लॉकल लेम्मा (LLL) के परिणाम:
लेखक यह प्रदर्शित करने के लिए लोवाज़ लोकल लेम्मा के सममित संस्करण (symmetric version) का उपयोग करते हैं कि ऐसे रंगीकरणों (colorings) का अस्तित्व है जहाँ कोई भी रंग वर्ग किसी भी $k$ -AP के "बड़े" अंश को नहीं रखता है। विशेष रूप से, कोरोलरी 3.3 यह स्थापित करता है कि उन समूहों के क्रम $N$ के लिए जिनमें छोटे अभाज्य गुणनखंड (prime factors) नहीं होते, एक ऐसा रंगों का उपसमुच्चय शीर्षों (vertices) को आवंटित किया जा सकता है जिससे कोई $k$ -AP मोनोक्रोमैटिक या लगभग मोनोक्रोमैटिक न हो।
यादृच्छिक शिफ्टेड प्रोडक्ट निर्माण (Random Shifted Product Constructions):
लेख-केंद्रित तकनीकी नवाचार एक परिष्कृत "यादृच्छिक शिफ्टेड प्रोडक्ट" निर्माण (लेम्मा 4.2 और 4.3) है। मानक उत्पाद रंगीकरणों के विपरीत, जो रंगों की संख्या को गुणा करते हैं, यह विधि लेखकों को रंगों की संख्या को स्थिर रखते हुए (या उन्हें नियंत्रित तरीके से बढ़ाते हुए) छोटे समूहों के रंगीकरणों को एक बड़े समूह में संयोजित करने की अनुमति देती है।

तंत्र (Mechanism): $H_1$ के एक रंगीकरण $c_1$ और $H_2$ के एक रंगीकरण $c_2$ को देखते हुए, यह निर्माण $H_1 \times H_2$ पर एक रंगीकरण को $H_2$ पर प्रोजेक्शन के फाइबर्स को स्वतंत्र रूप से शिफ्ट करके और बेस एलिमेंट $H_1$ के रंग के आधार पर रंगों को क्रमबद्ध (permute) करके परिभाषित करता है।
पुनरावृत्ति प्रक्रिया (Iterative Process): लेखक इस निर्माण को दोहराते हैं। प्रत्येक चरण में, वे एक समूह $Z_{n_{j-1}}$ के रंगीकरण को एक अभाज्य क्रम के चक्रीय समूह $Z_{q_j}$ के रंगीकरण के साथ संयोजित करते हैं। यह निर्माण समूह के आकार को $k$ के घातांक (exponential) के रूप में बढ़ाता है, जबकि "अच्छे" रंग वर्ग के घनत्व पैरामीटर में "डबल एक्सपोनेंशियल" हानि होती है। इन मापदंडों को सावधानीपूर्वक संतुलित करके, इस प्रक्रिया को लगभग $(\log^* k)/2$ बार दोहराया जा सकता है।

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

तीन रंगों के लिए सुपर-एक्सपोनेंशियल वृद्धि:
प्राथमिक परिणाम (थ्योरम 1) यह सिद्ध करता है कि पर्याप्त बड़े $k$ के लिए, तीन-रंगीन वैन डेर वाल्डन संख्या संतुष्ट करती है:
$w(k; 3) > 2^{k(\log^* k)/4}$
यह स्थापित करता है कि $w(k; 3)$ का विकास $k$ के किसी भी घातांकीय (exponential) फलन से तेज है, जिससे यह सिद्ध होता है कि $r \geq 3$ के लिए $\lim_{k \to \infty} w(k; r)^{1/k} = r$ का अनुमान गलत है।
कई रंगों के लिए निचली सीमाएँ:
थ्योरम 2 उस स्थिति के लिए निचली सीमा प्रदान करता है जहाँ रंगों की संख्या $r$ , $k$ के सापेक्ष बड़ी होती है (विशेष रूप से $r \geq (\log k)^{3/\epsilon}$ ):
$w(k; r) \geq r^{(1-\epsilon)k \log k}$
यह "मेनी कलर" (many color) शासन में पिछले अनुमानों में सुधार करता है।
एर्दोस-ग्राहम समस्या का समाधान:
लेखक कैनोनिकल वैन डेर वाल्डन संख्या $H(k)$ को संबोधित करते हैं, जो $[N]$ के प्रत्येक रंगीकरण के लिए न्यूनतम $N$ है जिसमें एक मोनोक्रोमैटिक या रेनबो (rainbow) $k$ -AP शामिल हो। एर्दोस और ग्राहम ने अनुमान लगाया था कि क्या $H(k)^{1/k}/k \to \infty$ होगा। $w(k, k-1)$ पर अपने बेहतर निचली सीमा का उपयोग करते हुए, लेखक सिद्ध करते हैं (थ्योरम 3) कि:
$H(k) \geq k^{(1-o(1))k \log k}$
यह पुष्टि करता है कि $H(k)$ सुपर-एक्सपोनेंशियल रूप से बढ़ता है, जो एर्दोस और ग्राहम द्वारा प्रस्तुत खुले प्रश्न को हल करता है।

महत्व
लेख का दावा है कि तीन या अधिक रंगों के लिए वैन डेर वाल्डन संख्याओं की वृद्धि सुपर-एक्सपोनेंशियल है, जो इन कॉम्बिनेटोरियल संख्याओं की समझ को मौलिक रूप से बदल देता है। इसका महत्व निम्नलिखित में निहित है:

लीनियर एक्सपोनेंशियल अनुमान को गलत सिद्ध करना: यह निश्चित रूप से दिखाता है कि $r \geq 3$ के लिए $w(k; r)$ का व्यवहार $r^k$ जैसा नहीं है।
कार्यप्रणाली में प्रगति: "यादृच्छिक शिफ्टेड प्रोडक्ट" निर्माण का परिचय यह अनुमति देता है कि निश्चित संख्या में रंगों को बनाए रखते हुए संभाव्य तर्कों को दोहराया जा सके, जो एक ऐसी तकनीक है जिसे लेखक $r \geq 5$ के लिए उपयोग किए गए पिछले संस्करणों की तुलना में अधिक कुशल बताते हैं।
कैनोनिकल रैमसे थ्योरी (Canonical Ramsey Theory): उनके परिणाम एर्दोस-ग्राहम समस्या का एक मजबूत समाधान प्रदान करते हैं, यह दिखाते हुए कि रेनबो प्रोग्रेशन की अनुमति देने के बाद भी, आवश्यक $N$ पहले स्थापित निचली सीमाओं की तुलना में बहुत बड़ा है।

लेखक नोट करते हैं कि हालांकि उनकी तकनीकें सामान्य हैं, लेकिन यहाँ विशिष्ट अनुप्रयोग इन निचली सीमाओं को स्थापित करने पर केंद्रित है। वे सुझाव देते हैं कि इन निर्माणों का उपयोग अन्य अंकगणितीय रैमसे संख्याओं के लिए नई सीमाएँ प्राप्त करने के लिए किया जा सकता है, जो एक विषय है जिसे वे एक साथी नोट (companion note) में तलाशने का इरादा रखते हैं। यह शोध पत्र यह दावा नहीं करता है कि सटीक वृद्धि दर या ऊपरी सीमाएं क्या हैं, बल्कि यह पहले की तुलना में काफी मजबूत निचली सीमा स्थापित करता है।

पुराना रहस्य

नई खोज

उन्होंने यह कैसे किया? (जादु적인 तरकीबें)

बोनस: एक पुराने पहेली को सुलझाना

सारांश

इसी तरह के और पेपर