🔢 mathematics

Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erd\H{o}s Problem #272)

यह शोध पत्र $3 \leq N \leq 12$ के लिए एर्दोश समस्या (Erdős Problem) #272 को यह सिद्ध करके हल करता है कि इस सीमा में साबो (Szabo) का निचला स्तर (lower bound) सटीक है, यह स्थापित करता है कि यह निचला स्तर एक सामान्य तत्व साझा करने वाले परिवारों के लिए अधिकतम है, और सामान्य अनुमान को केवल इस एकल शेष प्रश्न तक सीमित कर देता है कि क्या एक चरम परिवार (extremal family) में हमेशा एक सामान्य तत्व होना चाहिए।

मूल लेखक: Zhanfu Yang

प्रकाशित 2026-07-28

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

CC BY 4.0

मूल लेखक: Zhanfu Yang

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

कल्पना कीजिए कि आप 1 से $N$ तक कमरों वाले एक घर में एक विशाल पार्टी आयोजित कर रहे हैं। आप मेहमानों के समूहों को इन कमरों में रुकने के लिए आमंत्रित करना चाहते हैं, लेकिन आपके पास एक बहुत ही विशिष्ट, विचित्र नियम है कि कौन एक ही समूह में रह सकता है: यदि आप किन्हीं दो समूहों को लेते हैं और उनके पास जो लोग समान हैं उन्हें देखते हैं, तो वह साझा समूह लोगों की एक आदर्श, समान रूप से अंतराल वाली रेखा (evenly spaced line) बनानी चाहिए। गणित की भाषा में, इसे एक "अंकगणितीय प्रगति" (arithmetic progression) कहा जाता है। यह बिल्कुल वैसा ही है जैसे यदि समूह A में मेहमान {2, 5, 8} हैं और समूह B में {5, 8, 11} हैं, तो उनका ओवरलैप {5, 8} है, जो 3 के अंतराल वाली एक आदर्श रेखा है। लेकिन अगर ओवरलैप {5, 9} होता, तो वह एक टूटी हुई रेखा होती, और नियम टूट जाता।

बड़ा सवाल यह है जिसे गणितज्ञ दशकों से पूछ रहे हैं: बिना नियम तोड़े आप कितने अलग-अलग समूह आमंत्रित कर सकते हैं? यह इस बारे में है कि एक बॉक्स में कितने टुकड़ों को इस तरह फिट किया जा सकता है जहाँ हर टुकड़ा दूसरे के साथ एक विशिष्ट पैटर्न में पूरी तरह से फिट बैठता हो। यह केवल एक खेल नहीं है; यह कॉम्बिनेटरिक्स (combinatorics) की एक मौलिक समस्या है, जो गणित की वह शाखा है जो अध्ययन करती है कि चीजों को कैसे व्यवस्थित और गिना जा सकता है। इसे हल करने से हमें यह समझने में मदद मिलती है कि हम अव्यवस्था में कितनी संरचना थोप सकते हैं, इससे पहले कि वह ढह जाए।

लंबे समय तक, विशेषज्ञों को लगा कि वे उत्तर जानते हैं। उनका मानना था कि समूहों की अधिकतम संख्या लोगों के संभावित जोड़ों में से लगभग आधे के बराबर थी, साथ में थोड़ा सा अतिरिक्त। लेकिन फिर, शाबो (Szabó) नामक एक गणितज्ञ आए और उन्होंने कहा, "रुको, आप पुराने अनुमान से थोड़ा अधिक समूह वास्तव में समाहित कर सकते हैं!" उन्होंने एक चतुर निर्माण किया जिसने सिद्ध किया कि आप पुराने अनुमान से थोड़ा अधिक प्राप्त कर सकते हैं। हालाँकि, वह यह सिद्ध नहीं कर सके कि क्या यह पूर्ण सीमा थी या क्या छाया में कोई और भी अजीब व्यवस्था छिपी हुई थी। उन्होंने एक "कर्नेल प्रश्न" (kernel question) भी पूछा: क्या हमेशा एक विशिष्ट व्यक्ति होता है जो सर्वोत्तम संभव व्यवस्था में प्रत्येक समूह में शामिल होता है?

यह शोध पत्र, जो झांफू यांग (Zhanfu Yang) द्वारा लिखा गया है, इस पहेली को गहराई से सुलझाने के लिए है ताकि छोटे पार्टी आकारों के लिए सटीक उत्तर मिल सकें और यह सिद्ध किया जा सके कि क्या होता है जब हम एक विशिष्ट व्यक्ति को हर पार्टी में होने के लिए मजबूर करते हैं। लेखक ने केवल अनुमान नहीं लगाया; उन्होंने 12 कमरों तक की पार्टियों के लिए हर संभावित संयोजन की जांच करने के लिए शक्तिशाली कंप्यूटर प्रोग्रामों का उपयोग किया। परिणाम? इन छोटे आकारों के लिए, शाबो का चतुर निर्माण एकदम सही था। यह केवल एक अच्छा अनुमान नहीं था; यह पूर्ण अधिकतम था। शोध पत्र ने सटीक संख्याएँ पाईं: 12 कमरों वाली पार्टी के लिए, आप ठीक 69 समूह रख सकते हैं। यह संख्या अनुक्रम (4, 7, 12, 17, 23, 30, 39, 48, 58, 69) इतना नया है कि यह अभी तक प्रसिद्ध संख्या अनुक्रम डेटाबेस में दिखाई नहीं देता है।

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

लेखक ने उन समूहों के बारे में एक दिलचस्प संरचनात्मक नियम की भी खोज की जो पूर्ण रेखा पैटर्न का पालन नहीं करते (जिन्हें "टेढ़े" या crooked सदस्य कहा जाता है)। उन्होंने सिद्ध किया कि ऐसा कोई भी अजीब समूह लोगों के एक "बुरे जोड़े" (bad pair) को धारण करेगा—एक ऐसा जोड़ा जो रेखा नियम में फिट नहीं बैठता—जिसे पूरे पार्टी का कोई अन्य समूह साझा नहीं कर सकता। यह एक गुप्त हैंडशेक की तरह है जिसे केवल वह एक अजीब समूह जानता है। यह "निजी जोड़ा" (private pair) एक बाधा के रूप में कार्य करता है, जो इन अजीब समूहों को नियमों को तोड़े बिना बहुत अधिक जमा होने से रोकता है।

तो, अब हम कहाँ खड़े हैं? इस शोध पत्र ने छोटे नंबरों के लिए पहेली को हल कर दिया है और सिद्ध किया है कि यदि एक "साझा अतिथि" मौजूद है, तो उत्तर ज्ञात और सटीक है। एकमात्र चीज़ जो अभी भी हल होनी बाकी है, वह अंतिम, जिद्दी सवाल है: क्या रिकॉर्ड तोड़ने वाली पार्टी में हमेशा एक साझा अतिथि होता है? शोध पत्र सुझाव देता है कि यदि बिना किसी साझा अतिथि के रिकॉर्ड तोड़ने वाली पार्टी मौजूद है, तो उसे एक बहुत ही अजीब, अत्यधिक विशिष्ट संरचना होनी चाहिए जिसे लेखक ने पहले ही खारिज करना शुरू कर दिया है। हालांकि इस शोध पत्र ने हर संभव संख्या के लिए अंतिम रहस्य पर किताब बंद नहीं की है, लेकिन इसने एक अस्पष्ट अनुमान को एक सटीक मानचित्र में बदल दिया है, यह दिखाते हुए कि खजाना कहाँ छिपा है और यह सिद्ध करते हुए कि पुराना नक्शा गलत था। अब अंतिम उत्तर की यात्रा बहुत छोटी हो गई है, जिसका रास्ता लेखक के नए "निजी जोड़े" के नियम और पहले दर्जन मामलों के लिए पुष्ट सटीक मानों द्वारा स्पष्ट रूप से चिह्नित है।

तकनीकी सारांश: पूर्णांकों के परिवारों के लिए सटीक मान और सटीक ऊपरी सीमाएँ जिनका अंकगणितीय प्रगति (Arithmetic Progression) के साथ प्रतिच्छेदन होता है

समस्या विवरण
यह शोध पत्र अर्दोस समस्या (Erdős Problem) #272 को संबोधित करता है, जो फलन $t(N)$ को निर्धारित करने का प्रयास करती है। $t(N)$ को $\{1, \dots, N\}$ के $t$ अलग-अलग उपसमुच्चयों $A_1, \dots, A_t$ की अधिकतम संख्या के रूप में परिभाषित किया गया है, ताकि कि किन्हीं भी दो भिन्न समुच्चयों का प्रतिच्छेदन $A_i \cap A_j$ एक गैर-रिक्त अंकगणितीय प्रगति (AP) हो।

ऐतिहासिक रूप से, साइमोनोविट्स और सोस (Simonovits and Sós) ने स्थापित किया था कि $t(N) = O(N^2)$ है और उन्होंने यह अनुमान लगाया था कि अधिकतम मान एक निश्चित तत्व को समाहित करने वाले आकार $\le 3$ के सभी उपसमुच्चयों द्वारा प्राप्त किया जाता है, जिससे $\binom{N}{2} + 1$ की सीमा प्राप्त होती है। साबो (Szabó) ने बाद में इस सटीकता अनुमान को गलत सिद्ध किया और एक ऐसा परिवार निर्मित किया जिससे $t(N) \ge \binom{N}{2} + 1 + \lfloor (N-1)/4 \rfloor$ प्राप्त होता है। साबो ने आगे यह भी स्थापित किया कि $t(N) = N^2/2 + O(N^{5/3}(\log N)^3)$ का विषम व्यवहार (asymptotic behavior) होता है और उन्होंने दो महत्वपूर्ण प्रश्न उठाए: (i) क्या $t(N) = \binom{N}{2} + O(N)$ है, और (ii) "कर्नेल प्रश्न" (kernel question), जो यह पूछता है कि क्या प्रत्येक चरम परिवार (extremal family) - जो अधिकतम आकार प्राप्त करता है - में एक सामान्य तत्व होता है जो इसके सभी समुच्चयों में साझा किया जाता है।

कार्यप्रणाली
लेखक व्यापक कम्प्यूटेशनल सत्यापन, संरचनात्मक संयोजन विज्ञान (structural combinatorics), और विश्लेषणात्मक बाउंडिंग तकनीकों को मिलाने वाला एक हाइब्रिड दृष्टिकोण अपनाते हैं:

सटीक गणना (Exact Computation): छोटे $N$ $N$ ( $N \le 12$ $N \leq 12$ ) के लिए, समस्या को एक ग्राफ में अधिकतम क्लिक (maximum clique) खोजने के रूप में मॉडल किया गया है जहाँ शीर्ष $[N]$ $[N]$ के गैर-रिक्त उपसमुच्चय हैं और किनारे (edges) उन समुच्चयों को जोड़ते हैं जिनका गैर-रिक्त AP प्रतिच्छेदन होता है।
- $N \le 10$ के लिए, एक बिट-समानांतर (bit-parallel) ब्रांच-एंड-बाउंड सॉल्वर का उपयोग किया गया जिसमें ग्रीडी कलरिंग बाउंड्स का उपयोग किया गया था।
- $N=11$ और $12$ के लिए, एक निर्णय खोज (decision search) का उपयोग किया गया जिसमें रूट डिकंपोजिशन, डिजेनेरेसी ऑर्डरिंग, कोर पीलिंग और एक कठोर "स्टार प्रूनिंग" (star pruning) चरण का उपयोग किया गया था ताकि बड़े परिवारों के अस्तित्व को सिद्ध किया जा सके।
संरचनात्मक अपघटन (Structural Decomposition): सामान्य ऊपरी सीमा के लिए प्रमाण एक "स्टार्ड" (starred) परिवार (एक ऐसा परिवार जिसमें एक सामान्य तत्व $m$ होता है) को आकार $\le 2$ , आकार $3 $, और आकार$ \ge 4$ के उपसमुच्चयों में विभाजित करने पर आधारित है।
डिफेक्ट-वन काउंटिंग इनइक्वालिटी (Defect-One Counting Inequality): एक केंद्रीय तकनीकी उपकरण "स्टेयरकेस रीजन" (शून्य युक्त पूर्णांक अंतरालों के परिवार) के लिए एक काउंटिंग इनइक्वालिटी है। लेखक सिद्ध करते हैं कि किसी भी ऐसे परिवार के लिए, सदस्यों की संख्या "बैड पेयर्स" (जोड़े $\{u,v\}$ कि $\{0,u,v\}$ एक AP नहीं है) की संख्या द्वारा सीमित होती है जिन्हें वे कवर करते हैं, साथ ही एक छोटा डिफेक्ट टर्म भी होता है। इसे 500 तक के मापदंडों के लिए एक सटीक डायनेमिक प्रोग्राम और बड़े मापदंडों के लिए पॉजिटिव-डेफिनेट क्वाड्रेटिक फॉर्म्स का उपयोग करके एक विषम तर्क के माध्यम से सत्यापित किया गया है।
प्राइवेट-पेयर थ्योरम (Private-Pair Theorem): एक संरचनात्मक प्रमेय स्थापित किया गया है जो यह दर्शाता है कि प्रत्येक "क्रूक्ड" (crooked) सदस्य (एक सेट जिसका आकार $\ge 4$ है और जो AP नहीं है) में एक "प्राइवेट बैड पेयर" होता है—अर्थात तत्वों का एक ऐसा जोड़ा जो परिवार के किसी अन्य सदस्य में शामिल नहीं है। यह गैर-AP सदस्यों के बीच "किल्स" (bad pairs) को साझा करने से रोकता है, जिससे एक सटीक काउंटिंग बाउंड प्राप्त होता है।

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

छोटे $N$ के लिए सटीक मान: यह शोध पत्र $N = 3, \dots, 12$ के लिए $t(N)$ को सटीक रूप से निर्धारित करता है। मान $4, 7, 12, 17, 23, 30, 39, 48, 58, 69$ हैं। इस पूरी श्रेणी में, साबो का निचला मान (lower bound) सटीक है। यह अनुक्रम वर्तमान में OEIS में उपलब्ध नहीं है।
परिष्कृत अनुमान (Sharpened Conjecture): कम्प्यूटेशनल साक्ष्य के आधार पर, लेखक अनुमान लगाते हैं कि सभी $N \ge 1$ के लिए:
$t(N) = \binom{N}{2} + 1 + \left\lfloor \frac{N-1}{4} \right\rfloor$
यह साबो के विषम प्रश्न को एक सटीक सूत्र में परिष्कृत करता है।
स्टार्ड परिवारों के लिए सटीक ऊपरी सीमा: मुख्य सैद्धांतिक परिणाम (थ्योरम 1.4) यह सिद्ध करता है कि किसी भी स्टार्ड परिवार (जहाँ सभी सेट एक सामान्य तत्व साझा करते हैं) के लिए, आकार साबो के निचले मान द्वारा सीमित है। यह $N \ge 5$ $N \geq 5$ के लिए ज्ञात किसी भी प्रकार के इस तरह के पहले सटीक ऊपरी सीमा का प्रमाण है।
- यह प्रमाण गैर-AP सदस्यों को संभालने के लिए "डिफेक्ट-वन" काउंटिंग इनइक्वालिटी और "प्राइवेट-पेयर थ्योरम" को जोड़ता है।
कर्नेल प्रश्न में न्यूनीकरण (Reduction to the Kernel Question): लेखक प्रदर्शित करते हैं कि यदि साबो का कर्नेल अनुमान सत्य है (अर्थात, प्रत्येक चरम परिवार स्टार्ड है), तो परिष्कृत अनुमान (कि सूत्र सभी $N$ के लिए लागू होता है) तुरंत सिद्ध हो जाता है। इस प्रकार, $t(N)$ को सटीक रूप से निर्धारित करने की समस्या को यह सिद्ध करने में बदल दिया गया है कि चरम परिवारों में एक सामान्य तत्व होना चाहिए।
प्रति-उदाहरणों पर संरचनात्मक प्रतिबंध: शोध पत्र एक काल्पनिक गैर-स्टार्ड चरम परिवार (कर्नेल अनुमान के विरुद्ध एक प्रति-उदाहरण) की संरचना का विश्लेषण करता है। यह सिद्ध करता है कि यदि ऐसा परिवार मौजूद है, तो इसके ट्रिपल्स (triples) एक सामान्य तत्व साझा करते हैं, और इस तत्व से बचने वाले कोई भी सदस्य छोटे अंतर वाली लंबी अंकगणितीय प्रगति होते हैं। लेखक तर्क देते हैं कि ऐसी कॉन्फ़िगरेशन "स्व-सीमित" (self-limiting) हैं और अनुमानित सीमा तक पहुँचने की संभावना कम है, हालांकि एक पूर्ण प्रमाण अभी भी शेष है।

महत्व
यह शोध पत्र दावा करता है कि यह $N \ge 5$ (विशेष रूप से $N \le 12$ ) के लिए $t(N)$ का पहला सटीक निर्धारण प्रदान करता है और प्रतिबंधित वर्ग के लिए पहला सटीक ऊपरी सीमा स्थापित करता है। यह सिद्ध करके कि निचला मान सभी स्टार्ड परिवारों के लिए सटीक है, यह कार्य अर्दोस समस्या #272 को पूरी तरह से हल करने के लिए एकमात्र शेष बाधा के रूप में "कर्नेल प्रॉपर्टी" को अलग करता है। लेखक नोट करते हैं कि उनके परिणाम पुष्टि करते हैं कि साबो का निर्माण साझा तत्व वाले परिवारों के वर्ग के भीतर इष्टतम है, और वे एक संभावित गैर-स्टार्ड प्रति-उदाहरण के स्वरूप पर पहला कठोर संरचनात्मक प्रतिबंध प्रदान करते हैं। यह कार्य नई कॉम्बिनेटरियल तकनीकों, विशेष रूप से "डिफेक्ट-वन काउंटिंग इनइक्वालिटी" और "प्राइवेट-पेयर थ्योरम" को भी पेश करता है, जो अन्य प्रतिच्छेदन समस्याओं पर भी लागू हो सकती हैं।

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