💻 computer science

Witness-split + window-cardinality refinement for $r_3(N)$ : Architecture, empirical results, and a structural hard pocket

यह शोध पत्र $r_3(212)$ की ऊपरी सीमा की कठोर जांच करने के लिए विटनेस-स्प्लिटिंग (witness-splitting), विंडो-कार्डिनैलिटी प्रूनिंग (window-cardinality pruning) और हाइब्रिड SAT/MIP सॉल्वर को संयोजित करने वाले एक पुनरुत्पादक कम्प्यूटेशनल ढांचे को प्रस्तुत करता है, जो अधिकांश संभावित 44-सेट्स को सफलतापूर्वक समाप्त करते हुए दो प्रतिरोधी संरचनात्मक मामलों को अलग करता है जो व्यापक सत्यापन प्रयासों के बावजूद अप्रामाणित बने हुए हैं।

मूल लेखक: Mehmet Ergezer

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

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

CC BY 4.0

मूल लेखक: Mehmet Ergezer

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

कल्पना कीजिए कि आप एक सूटकेस (1 से 212 तक की संख्याएँ) को अधिक से अधिक वस्तुओं से भरने की कोशिश कर रहे हैं, लेकिन एक सख्त नियम के साथ: आप ऐसी तीन वस्तुएँ नहीं चुन सकते जो एक पूर्ण अंकगणितीय पैटर्न (arithmetic pattern) बनाती हों।

उदाहरण के लिए, यदि आप संख्या 2 चुनते हैं, तो आप 4 और 6 भी नहीं चुन सकते, क्योंकि $2, 4, 6$ एक ऐसा पैटर्न है जहाँ प्रत्येक संख्या पिछली संख्या से 2 अधिक है। इसे "3-टर्म अरिथमेटिक प्रोग्रेशन" कहा जाता है।

गणितज्ञ यह पता लगाने की कोशिश कर रहे हैं कि आप एक निश्चित आकार के सूटकेस में अधिकतम कितनी वस्तुएँ रख सकते हैं बिना नियम तोड़े। 211 के आकार वाले सूटकेस के लिए, उत्तर 43 ज्ञात है। बड़ा सवाल इस शोध पत्र के लिए यह है: क्या आप 212 के आकार के सूटकेस में 44 वस्तुएँ फिट कर सकते हैं?

लेखक, मेहमत एर्गजेज़र (Mehmet Ergezer) ने केवल अनुमान नहीं लगाया; उन्होंने यह साबित करने के लिए कि 44 असंभव है, एक विशाल डिजिटल फैक्ट्री बनाई। यहाँ इस शोध पत्र का विवरण दिया गया है, सरल उपमाओं का उपयोग करते हुए:

1. रणनीति: "विटनेस स्प्लिट" (Witness Split) फैक्ट्री

212 में से 44 संख्याओं के हर संभावित संयोजन की जाँच करना ऐसा ही है जैसे दुनिया के हर समुद्र तट पर रेत के एक विशिष्ट कण को खोजने की कोशिश करना। यह एक कंप्यूटर के लिए बहुत बड़ा है।

इसलिए, लेखक ने एक चतुर तरीका अपनाया:

विटनेस (Witness): उन्होंने पहले से ज्ञात "सुरक्षित" 43 संख्याओं की एक सूची से शुरुआत की जो पहले से ही काम करती है।
स्प्लिट (Split): उन्होंने उस सुरक्षित सूची से 24 सबसे "महत्वपूर्ण" संख्याएँ लीं और कंप्यूटर से उनके लिए हर संभावित "हाँ/नहीं" परिदृश्य की जाँच करने को कहा।
परिणाम: इसने डेटा के असंभव पहाड़ को 12.5 मिलियन छोटे, प्रबंधनीय ढेरों (जिन्हें "चंक्स" कहा जाता है) में तोड़ दिया। फिर कंप्यूटर ने एक-एक करके प्रत्येक ढेर को हल करने की कोशिश की।

2. उपकरण: "विंडो" और "रिफाइनमेंट" (Refinement)

कंप्यूटर को तेज़ बनाने के लिए, लेखक ने दो विशेष उपकरण जोड़े:

विंडो कार्ड (The Pruner): कल्पना कीजिए कि आप सूटकेस के एक छोटे से हिस्से को एक खिड़की से देख रहे हैं। हम पहले से ही गणित से जानते हैं कि 50 आकार की एक छोटी खिड़की में केवल 10 वस्तुएँ ही आ सकती हैं। कंप्यूटर इस नियम का उपयोग उस किसी भी ढेर को तुरंत बाहर करने के लिए करता है जो उस खिड़की में 11 वस्तुएँ रखने की कोशिश करता है। यह सबसे शक्तिशाली उपकरण था, जिसने कठिन ढेरों की संख्या को लगभग 30% कम कर दिया।
रिफाइनमेंट (The Deep Dive): यदि कोई ढेर 60 सेकंड में हल करने के लिए बहुत कठिन था, तो कंप्यूटर ने हार नहीं मानी। उसने उस विशिष्ट कठिन ढेर को लिया, उसमें और अधिक नियम जोड़े, और अधिक समय सीमा के साथ फिर से प्रयास किया। यह एक ताले से भरे बॉक्स को खोलने, एक विशिष्ट ताले को चुनने और बड़े चाबी के साथ फिर से प्रयास करने जैसा है।

3. परिणाम: "हार्ड पॉकेट" (The Hard Pocket)

एक सुपरकंप्यूटर क्लस्टर पर लाखों इन जाँचों को चलाने के बाद, यहाँ क्या हुआ:

शून्य सफलता: कंप्यूटर ने कभी भी 44 वस्तुओं को पैक करने का एक भी वैध तरीका नहीं पाया। हर बार जब इसने कोशिश की, तो इसने एक दीवार से टकराकर कहा, "असंभव।"
साक्ष्य: यह इस बात का मजबूत साक्ष्य है कि 44 असंभव है, लेकिन यह अभी भी एक औपचारिक प्रमाण नहीं है। क्यों? क्योंकि अभी भी कुछ जिद्दी ढेर बाकी हैं जिन्हें कंप्यूटर समय पर हल नहीं कर सका।

"हार्ड पॉकेट" (प्रतिरोधी चंक्स):
लाखों ढेरों में से, लेखक को 45 ढेरों का एक छोटा, जिद्दी समूह मिला जो अतिरिक्त समय और अलग उपकरणों के बाद भी हल होने से इनकार कर गया।

LP अटैक: उन्होंने एक अलग प्रकार के गणितीय सॉल्वर (जिसे HiGHS कहा जाता है) का उपयोग किया जो समस्या को एक चिकने वक्र (smooth curve) की तरह देखता है। यह 45 में से किसी भी ढेर को हल करने में विफल रहा।
CDCL अटैक: उन्होंने तीसरे प्रकार के सॉल्वर (जिसे CDCL कहा जाता है) का उपयोग किया जो एक जासूस की तरह काम करता है, अपनी गलतियों से सीखता है। यह सफल रहा! इसने 45 में से 18 ढेरों को हल कर दिया।
अंतिम 2: हालाँकि, 2 ढेर (जिन्हें T1c लेबल किया गया है) पूरी तरह से अनसुलझे रह गए। वे पहले सॉल्वर, दूसरे सॉल्वर और तीसरे सॉल्वर तीनों का विरोध कर गए। वे इस समस्या के "फाइनल बॉस" हैं।

4. निष्कर्ष: "यूनिट गैप" (The Unit Gap)

शोध पत्र यह निष्कर्ष निकालता है कि:

हमारे पास 43 संख्याओं की एक सत्यापित सूची है जो काम करती है।
हमारे पास इस बात के मजबूत प्रमाण हैं कि 44 असंभव है, क्योंकि कंप्यूटर ने लाखों बार कोशिश की और विफल रहा।
हालाँकि, उन 2 अंतिम जिद्दी ढेरों के कारण, हमारे पास अभी तक 100% गणितीय प्रमाण नहीं है। उत्तर लगभग निश्चित रूप से 43 है, लेकिन 43 और 44 के बीच का "गैप" तकनीकी रूप से अभी भी खुला है।

5. समुदाय को उपहार

केवल यह कहने के बजाय कि "मैं हार मानता हूँ," लेखक सारा डेटा जारी कर रहे हैं। वह उन 2 जिद्दी ढेरों को दुनिया के सामने एक चुनौती के रूप में रख रहे हैं।

वह सटीक कोड और डेटा प्रदान करते हैं ताकि अन्य गणितज्ञ केवल उन दो ढेरों को हल करने की कोशिश कर सकें।
उन्होंने इस समस्या को औपचारिक प्रमाण प्रणालियों (Lean) के लिए एक भाषा में भी अनुवादित किया है, जिससे कंप्यूटर वैज्ञानिक तर्क इंजन का उपयोग करके इसे सिद्ध करने का प्रयास कर सकें।

संक्षेप में: लेखक ने एक विशाल डिजिटल मशीन बनाई जिसने पैटर्न के बिना संख्याओं को पैक करने का रिकॉर्ड तोड़ने की कोशिश की। मशीन रिकॉर्ड तोड़ने का तरीका खोजने में विफल रही, लेकिन वह दो छोटे, अविश्वसनीय रूप से कठिन पहेलियों पर अटक गई। शोध पत्र कहता है, "हमें 99.9% यकीन है कि उत्तर 43 है, लेकिन इसे सिद्ध करने के लिए यहाँ वे दो अंतिम पहेलियाँ हैं जिन्हें आपको हल करना होगा।"

तकनीकी सारांश: $r_3(212)$ के लिए विटनेस-स्प्लिट + विंडो-कार्डिनैलिटी रिफाइनमेंट

समस्या विवरण
यह शोध पत्र $r_3(N)$ के सटीक गणना पर केंद्रित है, जिसे $[1, N]$ के एक ऐसे उपसमुच्चय (subset) के अधिकतम आकार के रूप में परिभाषित किया गया है जिसमें कोई गैर-तुच्छ तीन-पदों वाली अंकगणितीय प्रगति (3-AP) न हो। जबकि इसकी अनंत व्यवहार (asymptotic behavior) अच्छी तरह से अध्ययन किया गया है (जैसे, रोथ का प्रमेय, केली-मेका), यहाँ ध्यान $N=212$ की परिमित सीमा (finite frontier) पर है। OEIS A003002 के आधार पर, $r_3(211) = 43$ है। लेखक इस निर्णय समस्या की जांच कर रहे हैं: क्या $[1, 212]$ में एक 44-तत्वों वाला 3-AP-मुक्त उपसमुच्चय मौजूद है?
लेखकों ने एक 43-तत्वों वाले विटनेस (witness) को स्वतंत्र रूप से सत्यापित किया है, जिससे $r_3(212) \ge 43$ स्थापित होता है। ऊपरी-सीमा (upper-bound) का प्रश्न यह है कि क्या $r_3(212) \le 43$ है। किसी भी काल्पनिक 44-सेट के लिए एक आवश्यक शर्त यह है कि उसमें दोनों अंत बिंदु, 1 और 212 शामिल होने चाहिए; अन्यथा, वह $[1, 211]$ में एक 44-सेट में परिवर्तित हो जाएगा, जो ज्ञात मान का खंडन करता है। अतः, समस्या एक 44-सेट (जिसमें $\{1, 212\}$ शामिल हो) की असंभवता को सिद्ध करने तक सीमित हो जाती है।

कार्यप्रणाली और आर्किटेक्चर
लेखक एक 44-सेट खोजने के लिए पांच घटकों को संयोजित करने वाला एक पुनरुत्पादक (reproducible) कम्प्यूटेशनल ढांचा प्रस्तावित करते हैं:

डिसाइज-फॉर्म CP-SAT मॉडल: समस्या को $i \in [1, 212]$ के लिए बूलियन वेरिएबल्स $x_i$ का उपयोग करके एनकोड किया गया है। बाधाओं (constraints) में शामिल हैं:
- 3-AP असमानताएं: सभी ट्रिपल $(a, b, c)$ जो एक AP बनाते हैं, उनके लिए $x_a + x_b + x_c \le 2$ ।
- कार्डिनैलिटी समानता: $\sum x_i = 44$ (प्रोपोगेशन के लिए असमानता की तुलना में अधिक सटीक)।
- एंडपॉइंट फोर्सिंग: $x_1 = x_{212} = 1$ ।
- सिमेट्री ब्रेकिंग: रिफ्लेक्शन सिमेट्री को समाप्त करने के लिए लेक्सिकोग्राफिकल ऑर्डरिंग।
विटनेस-स्प्लिटिंग (Witness-Splitting): सर्च स्पेस को प्रबंधित करने के लिए, लेखक एक सत्यापित 43-तत्वों वाले विटनेस $A_{43}$ का उपयोग करते हैं। वे $A_{43}$ के तत्वों को उनके AP-इंसीडेंस डिग्री (incidence degree) द्वारा रैंक करते हैं और शीर्ष 24 तत्वों का चयन करते हैं। इन 24 वेरिएबल्स के मानों को फिक्स करके सर्च स्पेस को $2^{24}$ "चंक्स" (chunks) में विभाजित किया जाता है। कई चंक्स तुरंत हटा दिए जाते (pruned) यदि फिक्स्ड प्रीफिक्स एक 3-AP को मजबूर करता है।
विंडो-कार्डिनैलिटी प्रूनिंग (Window-Cardinality Pruning): एक महत्वपूर्ण हस्तक्षेप OEIS A003002 से प्राप्त वैध असमानताओं को जोड़ना है। किसी भी विंडो $[a, a+L-1]$ के लिए, वेरिएबल्स का योग $r_3(L)$ द्वारा सीमित होता है। $N=212$ के साथ, यह 22,154 असमानताएं जोड़ता है, जो कच्चे 3-AP बाधाओं की तुलना में मॉडल को काफी मजबूत बनाता है।
रिकर्सिव रिफाइनमेंट (Recursive Refinement): वे चंक्स जो ब्रॉड लेयर (डेप्थ 24) पर UNKNOWN लौटते हैं, उन्हें अगले उच्चतम-डिग्री वाले विटनेस वेरिएबल्स (डेप्थ 40, 48, 56, 64) के साथ प्रीफिक्स बढ़ाकर और लंबे टाइम कैप के साथ पुनः हल करके रिफाइन किया जाता है।
सॉल्वर विविधता और इंजीनियरिंग: यह अभियान UMass Unity क्लस्टर पर चलने वाले एक SLURM-आधारित पाइपलाइन का उपयोग करता है। इसमें निम्नलिखित शामिल हैं:
- CP-SAT (OR-Tools): ब्रॉड पास और रिकर्सिव रिफाइनमेंट के लिए।
- HiGHS (MIP): एक LP-रिलैक्सेशन-आधारित सॉल्वर जिसका उपयोग सबसे कठिन "UNKNOWN" चंक्स पर हमला करने के लिए किया जाता है।
- CDCL/SAT (CaDiCaL): उन चंक्स पर पुनः हमला करने के लिए जो LP विधियों के प्रति प्रतिरोधी हैं, जो असंतोषजनकता (unsatisfiability) के लिए स्वतंत्र रूप से सत्यापित DRAT प्रमाण उत्पन्न करते हैं।

अनुभवजन्य परिणाम (Empirical Results)
अभियान ने डेप्थ-24 स्वीप और विभिन्न रिफाइनमेंट स्तरों के माध्यम से लाखों उप-समस्याओं को प्रोसेस किया।

शून्य व्यवहार्य समाधान (Zero Feasible Solutions): परीक्षण किए गए सभी उप-समस्याओं (ब्रॉड पास, रिफाइनमेंट, HiGHS, और CDCL) में, शून्य व्यवहार्य 44-सेट्स पाए गए। यह $r_3(212) = 43$ के अनुमान को मजबूत अनुभवजन्य समर्थन प्रदान करता है, हालांकि यह एक औपचारिक प्रमाण नहीं है।
विंडो-कार्डिनैलिटी का प्रभाव: विंडो-कार्डिनैलिटी असमानताओं को सक्षम करने से ब्रॉड पास में UNKNOWN दर में लगभग 28 प्रतिशत अंक की कमी आई (उदाहरण के लिए, नियंत्रित बैचों में ~30% से ~1.65% तक), जो इसे सबसे प्रभावी प्रूनिंग लेयर बनाता है।
स्ट्रक्चरल हार्ड पॉकेट (The Structural Hard Pocket):
- 100,000-चंक विस्तार बैच से, 6,071 चंक्स ने UNKNOWN लौटाया।
- इन चंक्स के एक रैंडम सैंपल के 300-सेकंड के रीकैप ने 45 प्रतिरोधी चंक्स छोड़े (Tier T1)।
- HiGHS हमला: एक घंटे का HiGHS रन 0/45 को बंद करता है। एक 8-घंटे के ऑडिट ने 25/45 को बंद किया, जिससे 20 चंक्स (Tier T1b) बचे, जिनका डुअल बाउंड 0.0 पर स्थिर था, जो दर्शाता है कि LP रिलैक्सेशन ने असंतोषजनकता का कोई प्रमाण प्रदान नहीं किया।
- CDCL हमला: T1b के 20 चंक्स पर एक शुद्ध CDCL/SAT हमले ने 18/20 को बंद किया, और स्वतंत्र रूप से सत्यापित DRAT प्रमाण उत्पन्न किए।
- अवशिष्ट (The Residual - T1c): दो चंक्स (ID 40959 और 48895) 12-घंटे के शुद्ध CDCL रन और 4-घंटे के विंडो वाले CDCL डायग्नोस्टिक्स के बाद भी UNKNOWN बने रहे। ये दो चंक्स CP-SAT, HiGHS (LP-MIP), और CDCL प्रतिमानों को भी विफल कर देते हैं।

प्रमुख योगदान
लेखक स्पष्ट रूप से अपने योगदान को $r_3(212)$ के नए सटीक मान के बजाय मेथोडोलॉजिकल (पद्धतिगत) रूप में फ्रेम करते हैं। विशिष्ट योगदान हैं:

आर्किटेक्चर: सटीक ऊपरी-सीमा खोजों के लिए विटनेस-स्प्लिटिंग, विंडो-कार्डिनैलिटी प्रूनिंग और रिकर्सिव रिफाइनमेंट को संयोजित करने वाला एक पुनरुत्पादक ढांचा।
अनुभवजन्य विवरण: $N=212, K=44$ अभियान का विस्तृत विश्लेषण, जिसमें सॉल्वर ट्रेड-ऑफ और सर्च स्पेस की गैर-एकरूपता (जैसे, विशिष्ट पिन असाइनमेंट वाले "मिडल-आउट" चंक्स काफी कठिन हैं) शामिल है।
हार्ड पॉकेट का लक्षण वर्णन: एक संरचनात्मक बाधा (T1c) की पहचान जो उदार समय सीमाओं के तहत भी CP-SAT, HiGHS और CDCL प्रतिमानों में अपरिवर्तित रहती है।
बेंचमार्क रिलीज: चरणों में जारी किए गए इंस्टेंस:
- T1a: 25 चंक्स जिन्हें HiGHS द्वारा बंद किया गया।
- T1b \ T1c: DRAT प्रमाणों के साथ CDCL द्वारा बंद किए गए 18 चंक्स।
- T1c: अंतिम 2 प्रतिरोधी चंक्स, जिन्हें सबसे तीक्ष्ण ओपन प्रॉब्लम के रूप में प्रस्तुत किया गया है।
- T2/T3: 6,071 ब्रॉड UNKNOWNs और भविष्य के प्रयासों के लिए पूर्ण 12.5M चंक जनरेटर।
औपचारिकीकरण (Formalization): औपचारिक प्रमाण-खोज प्रणालियों के लिए T1c लक्ष्यों का एक Lean 4 एनकोडिंग।

महत्व और दावे
लेखक विनम्रतापूर्वक दावा करते हैं कि हालांकि अभियान $r_3(212) = 43$ के अनुमान का पुरजोर समर्थन करता है, लेकिन अनसुलझे T1c अवशिष्ट के कारण यह एक औपचारिक प्रमाण नहीं है। महत्व विशिष्ट कम्प्यूटेशनल बाधा को अलग करने में निहित है:

प्रमाणित सीमाओं के बीच का अंतर ठीक एक है ( $43 \le r_3(212) \le 44$ )।
LP-आधारित विधियों (HiGHS) की विफलता और CDCL की आंशिक सफलता यह सुझाव देती है कि कठिनाई केवल प्रोपेगेशन आर्टिफैक्ट नहीं है, बल्कि एक संरचनात्मक गुण है जहाँ LP रिलैक्सेशन गैप टाइट है और पूर्णांक असंतोषजनकता प्रमाण (integer infeasibility certificate) कॉम्बिनेटोरियली विसरित (diffuse) है।
यह शोध प्रस्ताव करता है कि अंतराल को बंद करने के लिए या तो मजबूत एडिटिव-कॉम्बिनेटोरियल सीमाओं (जैसे, फूरियर-एनालिटिक या मल्टी-विंडो पार्टीशन बाउंड्स) या कस्टम ब्रांच-एंड-बाउंड सिस्टम की आवश्यकता है जो उन विशिष्ट सिमेट्रीज़ का लाभ उठा सकें जिन्हें सामान्य-उद्देश्य वाले सॉल्वर कैप्चर नहीं कर पाते हैं।

यह कार्य एक बेंचमार्क के रूप में कार्य करता है, जो विशिष्ट, सत्यापित इंस्टेंस (T1c) प्रदान करता है जो इस वर्ग की समस्याओं के लिए सामान्य-उद्देश्य वाले कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन सॉल्वरों की वर्तमान सीमा का प्रतिनिधित्व करते हैं।