🔢 mathematics

Bounds for Greedy $B_h$ -sets

यह शोध पत्र ग्रीडी $B_h$ -सेट के $k$ -वें तत्व के लिए नए गैर-तुच्छ निम्न और उच्च सीमाएँ स्थापित करता है, जो विशेष रूप से $k \ge 5$ के लिए सटीक स्पर्शोन्मुख अनुमान और सभी $k \ge 1$ के लिए एक सामान्य निम्न सीमा प्रदान करता है, साथ ही पाँचवें तत्व के सटीक स्पर्शोन्मुख व्यवहार के लिए एक अनुमान प्रस्तावित करता है।

मूल लेखक: Kevin O'Bryant

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

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

CC BY 4.0

मूल लेखक: Kevin O'Bryant

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

कल्पना कीजिए कि आप नंबर वाले ब्लॉकों से एक मीनार बना रहे हैं, लेकिन आपके पास एक बहुत ही सख्त नियम है: ब्लॉकों के दो अलग-अलग समूहों का योग समान नहीं होना चाहिए। यदि आप $h$ ब्लॉक चुनते हैं और उन्हें जोड़ते हैं, तो वह योग उस ब्लॉकों के विशिष्ट समूह के लिए अद्वितीय होना चाहिए। गणितज्ञ इन विशेष संग्रहों को $B_h$ -sets कहते हैं।

अब, कल्पना कीजिए कि आप इस नियम का पालन करने वाली सबसे छोटी संभव मीनार बनाना चाहते हैं। आप ब्लॉक 0 से शुरू करते हैं, फिर आप अगला सबसे छोटा नंबर देखते हैं जिसे आप नियम तोड़े बिना जोड़ सकते हैं। फिर आप उसके बाद का अगला सबसे छोटा नंबर देखते हैं, और इसी तरह आगे बढ़ते हैं। इसे ग्रीडी एल्गोरिदम (Greedy Algorithm) कहा जाता है। यह एक खेल की तरह है जहाँ आप हमेशा सबसे सस्ता, सबसे छोटा आइटम चुनते हैं जो आपके बजट को खराब नहीं करता है।

केविन ओ'ब्रायंट का शोध पत्र इसी बारे में है कि जैसे-जैसे मीनार ऊंची होती जाती है, ये "अगले" ब्लॉक कितने बड़े होते जाते हैं। विशेष रूप से, लेखक यह अनुमान लगाने की कोशिश कर रहा है कि 5वें, 6वें, 7वें और यहाँ तक कि उच्च ब्लॉकों का आकार क्या होगा, जो इस बात पर निर्भर करता है कि "कोई डुप्लिकेट योग नहीं" का नियम कितना सख्त है (जिसे $h$ द्वारा दर्शाया गया है)।

बड़ी खोज: 5वाँ ब्लॉक

लेखक की मुख्य उपलब्धि अंततः इस मीनार में 5वें ब्लॉक के आकार के लिए कुछ ठोस सीमाएँ तय करना है (जिसे $\gamma_5$ द्वारा दर्शाया गया है)।

इस शोध पत्र से पहले, हम जानते थे कि 5वाँ ब्लॉक 0 और एक बहुत बड़ी संख्या के बीच कहीं था, लेकिन हमारे पास इस पर कोई मजबूत पकड़ नहीं थी। यह पत्र दो चीजें सिद्ध करता है:

निचली सीमा (फर्श): 5वाँ ब्लॉक निश्चित रूप से $\frac{1}{8}h^4 + \frac{1}{2}h^3$ जितना बड़ा है। इसे एक ठोस फर्श की तरह समझें जिसके नीचे आप खुदाई नहीं कर सकते। चाहे आप कितनी भी कोशिश करें, 5वाँ ब्लॉक इससे छोटा नहीं होगा।
ऊपरी सीमा (छत): 5वाँ ब्लॉक लगभग $0.467214 \times h^4$ (प्लस कुछ छोटे पद) से छोटा है। यह एक ऐसी छत है जिसे ब्लॉक छू नहीं सकता।

तो, अब हम जानते हैं कि 5वाँ ब्लॉक इन दो संख्याओं के बीच एक विशिष्ट "अपार्टमेंट" में रहता है।

बड़ी तस्वीर: 6ठा ब्लॉक और उससे ऊपर

6ठे ब्लॉक और उसके बाद के सभी ब्लॉकों ( $k \ge 6$ ) के लिए, लेखक एक एकल सटीक सूत्र नहीं देता है। इसके बजाय, वे एक नुस्खा (recipe) प्रदान करते हैं जिससे यह गणना की जा सके कि ये ब्लॉक कितने बड़े हो सकते हैं।

पत्र एक संख्या अनुक्रम $\alpha_k$ (जैसे $\alpha_6 = 0.382978$ , $\alpha_7 = 0.269877$ , आदि) पेश करता है। ये संख्याएँ एक सिकुड़ती हुई सीमा के रूप में कार्य करती हैं। लेखक सिद्ध करता है कि किसी भी ब्लॉक संख्या $k$ (जहाँ $k \ge 5$ ) के लिए, उस ब्लॉक का आकार कभी भी निम्नलिखित से अधिक नहीं होगा:
$\alpha_k \times h^{k-1}$
प्लस थोड़ा सा अतिरिक्त शोर (noise) जो $h$ के बहुत बड़े होने पर छोटा होता जाता है।

पत्र एक विशिष्ट सूत्र देता है कि यदि आप वर्तमान $\alpha$ जानते हैं तो अगला $\alpha$ नंबर कैसे प्राप्त करें, लेकिन यह पुनरावर्ती चरण (recursive step) विशेष रूप से 7वें ब्लॉक और उससे आगे के लिए काम करता है ( $\alpha_k$ से $\alpha_{k+1}$ की गणना करने के लिए $k \ge 7$ आवश्यक है)। 6ठे ब्लॉक के लिए, पत्र पिछले चरणों से प्राप्त एक विशिष्ट स्थिरांक मान प्रदान करता है। यह एक गणितीय असेंबली लाइन की तरह है: आप 6ठे ब्लॉक के लिए सीमा फीड करते हैं, और मशीन 7वें ब्लॉक की सीमा बाहर निकाल देती है, और इसी तरह आगे बढ़ती है।

जो यह पत्र नहीं कहता (और जिसे यह खारिज करता है)

यह जानना बहुत महत्वपूर्ण है कि यह पत्र क्या नहीं करता है, क्योंकि लेखक बहुत सावधान है:

यह पूरे पहेली को हल नहीं करता है। लेखक स्पष्ट रूप से बताता है कि जबकि उन्होंने 5वें ब्लॉक की सीमाएं ढूंढ ली हैं, उन्होंने अभी तक 5वें ब्लॉक का सटीक सूत्र नहीं खोजा है।
यह दावा नहीं करता कि 5वाँ ब्लॉक ठीक $\frac{1}{3}h^4$ है। लेखक एक कन्जेक्चर (पैटर्न के आधार पर अनुमान) करता है कि बड़े $h$ के लिए 5वाँ ब्लॉक वास्तव में $\frac{1}{3}h^4$ हो सकता है, लेकिन वे स्वीकार करते हैं कि यह केवल एक अनुमान है। उन्होंने इसे सिद्ध नहीं किया है।
यह नहीं कहता कि ब्लॉक सरल बहुपद (polynomials) हैं। लेखक संशय में है कि क्या सभी ब्लॉक हमेशा एक सरल, सुचारू बहुपद पैटर्न का पालन करते हैं। जबकि पहले कुछ ब्लॉक (0 से 4 तक) "क्वासी-पॉलीनोमियल" (ऐसे बहुपद जो $h$ को किसी संख्या से विभाजित करने पर शेषफल के आधार पर थोड़े बदलते हैं) के रूप में जाने जाते हैं, लेखक को संदेह है कि यह पैटर्न हर एक ब्लॉक के लिए हमेशा बना रहेगा।

"वर्जित" क्षेत्र (The Forbidden Zone)

पत्र अगले ब्लॉक के लिए एक "वर्जित क्षेत्र" के बारे में भी बताता है। यदि आपके पास ब्लॉकों की एक मीनार है, तो पूर्णांकों की एक सीमित संख्या है जिन्हें आप जोड़ने का प्रयास कर सकते हैं जो नियमों को तोड़ देंगे। पत्र सटीक रूप से गणना करता है कि कितने "बुरे" नंबर मौजूद हैं जिन्हें आप नहीं चुन सकते। यह पता चलता है कि किसी भी मौजूदा मीनार के लिए, केवल कुछ ही ऐसे "ट्रैप" नंबर हैं जो $B_h$ गुण को खराब कर देंगे, और वे सभी एक विशिष्ट सीमा के भीतर स्थित हैं।

6ठे ब्लॉक का रहस्य

लेखक $h$ के विभिन्न मानों के लिए 6ठे ब्लॉक ( $\gamma_6$ ) के लिए एक कंप्यूटर द्वारा गणना की गई संख्याओं की तालिका शामिल करता है। हालाँकि, इन संख्याओं को देखते हुए, लेखक स्वीकार करता है: "अभी तक कोई सूत्र नहीं सुझाया गया है।"
यह संख्याओं के एक अनुक्रम को देखने और यह कहने जैसा है कि, "हम जानते हैं कि वे क्या हैं, लेकिन हमें यह पता नहीं है कि उन्हें उत्पन्न करने वाला नियम क्या है।" लेखक $\gamma_6$ के पहले 33 मानों को सूचीबद्ध करता है और नोट करता है कि अभी तक किसी ने उनके लिए कोई पैटर्न नहीं खोजा है।

खुले प्रश्न

पत्र उन रहस्यों को सूचीबद्ध करके समाप्त होता जो अभी भी अनसुलझे हैं:

क्या हम सिद्ध कर सकते हैं कि 5वाँ ब्लॉक ठीक $\frac{1}{3}h^4$ है?
क्या हम 6ठे, 7वें और उच्च ब्लॉकों के लिए सूत्र पा सकते हैं?
क्या ये ब्लॉक गणितीय अर्थ में समान रूप से वितरित हैं, या वे अजीब तरह से क्लस्टर (cluster) होते हैं? (लेखक नोट करता है कि 2रे ब्लॉक के लिए, वे इस तरह से क्लस्टर होते हैं जो यादृच्छिक (random) नहीं है)।
क्या कोई विशिष्ट संख्या (जैसे 33) है जो मीनार के दो ब्लॉकों के बीच का अंतर कभी नहीं हो सकती? (लेखक नोट करता है कि 2रे ब्लॉक के लिए, 1 से 87 तक की प्रत्येक संख्या अंतर के रूप में दिखाई देती है सिवाय 33 के, जो एक अजीब संयोग है)।

संक्षेप में, यह पत्र 5वें ब्लॉक के चारों ओर एक मजबूत घेरा बनाता है और इसके ऊपर के सभी ब्लॉकों के लिए एक सिकुड़ती हुई सीढ़ी प्रदान करता है, लेकिन मीनार का सटीक आकार और उच्च ब्लॉकों के गुप्त सूत्र अभी भी एक रहस्य बने हुए हैं जो अगले खोजकर्ता की प्रतीक्षा कर रहे हैं।

तकनीकी सारांश: ग्रीडी $B_h$ -सेट्स के लिए बाउंड्स (Bounds)

समस्या विवरण
यह शोध पत्र $B_h$ -सेट्स के निर्माण में प्रयुक्त होने वाले ग्रीडी एल्गोरिदम (greedy algorithm) के स्पर्शोन्मुखी व्यवहार (asymptotic behavior) की जांच करता है। एक गैर-ऋणात्मक पूर्णांकों के सेट $A$ को $B_h$ -सेट तब कहा जाता है जब समीकरण $a_1 + \dots + a_h = b_1 + \dots + b_h$ (जहाँ $a_i, b_i \in A$ ) के प्रत्येक समाधान के लिए यह निहित हो कि मल्टीसेट्स (multisets) $\{a_1, \dots, a_h\}$ और $\{b_1, \dots, b_h\}$ समान हैं। अध्ययन का मुख्य विषय 'ग्रीडी $B_h$ -सेट', जिसे $G(h) = \{\gamma_0, \gamma_1, \gamma_2, \dots\}$ के रूप में दर्शाया गया है, का निर्माण है। इसका निर्माण लेक्सिकोग्राफिक रूप से $\gamma_0 = 0, \gamma_1 = 1$ निर्धारित करके किया जाता है, और $\gamma_{k+1}$ को वह सबसे छोटा पूर्णांक माना जाता है जिससे $\{\gamma_0, \dots, \gamma_{k+1}\}$ एक $B_h$ -सेट बना रहे।

मुख्य समस्या $k$ के निश्चित मान के लिए $h$ के फलन के रूप में $\gamma_k(h)$ की विकास दर (growth rate) निर्धारित करना है। जबकि $k \le 4$ के लिए सटीक सूत्र ज्ञात हैं, $k \ge 5$ के लिए व्यवहार कम्प्यूटेशनल गणनाओं (computational enumeration) के अलावा काफी हद तक अनछुआ रहा है। यह शोध पत्र $\gamma_k(h)$ के लिए, विशेष रूप से $\gamma_5(h)$ के लिए, और $k \ge 5$ के लिए सामान्य बाउंड्स के लिए गैर-तुच्छ (nontrivial) ऊपरी और निचली सीमाएं (upper and lower bounds) स्थापित करने का प्रयास करता है।

कार्यप्रणाली (Methodology)
लेखक कॉम्बिनेटरियल विश्लेषण, रिकर्सिव बाउंडिंग (recursive bounding), और विस्तृत केस एन्यूमरेशन (case enumeration) के संयोजन का उपयोग करता है:

कॉम्बिनेटरियल बाउंड्स: शोध पत्र इस अवलोकन का उपयोग करता है कि $k+1$ आकार के एक सेट के अलग-अलग $h$ -फोल्ड योगों की संख्या $\binom{k+h}{k}$ होती है। चूंकि ये योग अंतराल $[h\gamma_0, h\gamma_k]$ के भीतर होने चाहिए, इसलिए यह $\gamma_k(h)$ पर एक आधारभूत निचली सीमा (baseline lower bound) प्रदान करता है।
"मेक्स" (Mex) लक्षण वर्णन: एक प्रमुख लेम्मा यह स्थापित करता है कि $\gamma_{k+1} = \text{mex}(F^{(k)})$ , जहाँ $F^{(k)}$ उन सभी पूर्णांकों का सेट है जिन्हें विशिष्ट बाधाओं के तहत $\frac{1}{r}\sum_{i=1}^k \gamma_i(m_i - m'_i)$ के रूप में दर्शाया जा सकता है। यह लक्षण वर्णन लेखक को एक निश्चित थ्रेशोल्ड से ऊपर $F^{(k)}$ में "वर्जित" (forbidden) मानों की गणना करके $\gamma_{k+1}$ को बाउंड करने की अनुमति देता है।
निचली सीमा निर्माण ( $\gamma_5$ ): $\gamma_5(h)$ के लिए निचली सीमा सिद्ध करने के लिए, लेखक पूर्णांक वेक्टर्स $\Delta$ के एक विशिष्ट सेट को परिभाषित करता है जो पहले चार तत्वों के लिए वैध गुणांक संयोजनों (coefficient combinations) का प्रतिनिधित्व करते हैं। इन वेक्टर्स को एक विशिष्ट "ओडोमीटर" शैली के क्रम (lexicographical ordering) के आधार पर व्यवस्थित करके और $\langle \gamma_1, \gamma_2, \gamma_3, \gamma_4 \rangle$ के साथ डॉट प्रोडक्ट के तहत उनके इमेज का विश्लेषण करके, लेखक यह प्रदर्शित करता है कि उनके इमेज एक निरंतर अंतराल (contiguous interval) बनाते हैं। यह सुनिश्चित करता है कि "मेक्स" (पहला लापता पूर्णांक) इन इमेजेस के एक विशिष्ट उपसमुच्चय के अधिकतम मान से कम से कम अधिक होगा।
ऊपरी सीमा निर्माण ( $\gamma_k$ ): ऊपरी सीमा के लिए, लेखक एक इंडक्टिव दृष्टिकोण का उपयोग करता है। यह मानते हुए कि $\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$ , लेखक $\beta_k h^k$ के थ्रेशोल्ड से ऊपर $F^{(k)}$ के आकार का अनुमान लगाता है। सबसे बड़े तत्व $\gamma_k$ की बहुलता (multiplicities) के आधार पर $F^{(k)}$ को वर्गीकृत करके और "स्टार्स-एंड-बार्स" (stars-and-bars) कॉम्बिनेटरियल काउंटिंग लागू करके, लेखक $\alpha_k$ के गुणांकों के लिए एक रिकरेंस रिलेशन प्राप्त करता है। $\alpha_k$ का अनुक्रम गैर-बढ़ता (non-increasing) है और शून्य की ओर अभिसरित (converging) होता है।

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

$\gamma_5(h)$ के लिए निचली सीमा: शोध पत्र ग्रीडी $B_h$ -सेट के पांचवें तत्व के लिए एक गैर-तुच्छ निचली सीमा स्थापित करता है:
$\gamma_5(h) \ge \frac{1}{8}h^4 + \frac{1}{2}h^3$
यह परिणाम पहले चार तत्वों द्वारा उत्पन्न वर्जित योगों के कठोर विश्लेषण के माध्यम से प्राप्त किया गया है।
$\gamma_k(h)$ के लिए ऊपरी सीमाएं ( $k \ge 5$ ): शोध पत्र $k \ge 5$ के लिए $\gamma_k(h)$ के लिए पहली गैर-तुच्छ ऊपरी सीमाएं प्रदान करता है। विशेष रूप से, यह सिद्ध करता है कि:
$\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$
जहाँ $\alpha_k$ के स्थिरांक (constants) पुनरावर्ती रूप से (recursively) परिभाषित हैं। शोध पत्र स्पष्ट रूप से गणना करता है:
- $\alpha_5 \approx 0.467214$
- $\alpha_6 \approx 0.382978$
- $\alpha_7 \approx 0.269877$
- $k \ge 7$ के लिए, $\alpha_{k+1} = \frac{1}{2} \alpha_k + \frac{1}{2^k k!} \sum_{j=0}^{k-1} \binom{k-1}{j} \binom{k}{j} 2^j$ .
  $\alpha_k$ का अनुक्रम तेजी से घटता हुआ दिखाया गया है, जो यह दर्शाता है कि $\gamma_k(h)$ पहले के अप्रमाणित अनुमानों की तुलना में धीमी गति से बढ़ता है।
$\gamma_5(h)$ पर अनुमान (Conjecture): $h \le 47$ के लिए कम्प्यूटेशनल डेटा के आधार पर, लेखक एक सटीक स्पर्शोन्मुखी सूत्र का अनुमान लगाता है:
$\gamma_5(h) = \frac{1}{3}h^4 + O(h^3)$
यह सुझाव देता है कि $1/8$ की निचली सीमा सटीक नहीं है, और वास्तविक अग्रणी गुणांक (leading coefficient) संभवतः $1/3$ है।
सामान्य निचली सीमा: शोध पत्र सामान्य निचली सीमा $\gamma_k(h) \ge \frac{1}{k!}h^{k-1} + O(h^{k-2})$ को दोहराता है और उसे संदर्भ देता है, यह पुष्टि करता है कि ग्रीडी एल्गोरिदम निश्चित $k$ के लिए सही विकास दर (order of growth) वाले सेट बनाता है।

महत्व और दावे
लेखक इस कार्य के महत्व को तीन मुख्य क्षेत्रों में फ्रेम करता है:

सौंदर्यपरक और सैद्धांतिक आवश्यकता: $B_h$ -सेट्स कॉम्बिनेटरियल नंबर थ्योरी में मौलिक वस्तुएं हैं। लेखक तर्क देता है कि ग्रीडी एल्गोरिदम के आउटपुट को समझना $B_h$ -सेट्स के लिए एक स्वाभाविक समस्या है, जो तत्काल अनुप्रयोगों से स्वतंत्र है।
ग्रीडी विश्लेषण की व्यवहार्यता: शोध पत्र गैर-ग्रीडी निर्माणों (जैसे सिंगर का निर्माण जो परिमित क्षेत्रों (finite fields) का उपयोग करता है) के विश्लेषण की तुलना में ग्रीडी एल्गोरिदम के विश्लेषण की कठिनाई को दर्शाता है। जबकि परिमित क्षेत्रों का उपयोग करके 11 तत्वों वाला $B_{100}$ -सेट बनाना (जैसे $\mathbb{F}_{101}^{11}$ में काम करना) कम्प्यूटेशनल रूप से असंभव है, ग्रीडी $B_{100}$ -सेट के 10वें तत्व के लिए एक सूत्र खोजना "कठिन लेकिन संभव" बताया गया है। यह कार्य $k \ge 5$ के लिए ऐसे विश्लेषण को कठोर बनाने की दिशा में पहला कदम है।
ग्रीडी एल्गोरिदम को समझना: मुख्य प्रेरणा $B_2$ -सेट्स (सिडन सेट्स/Sidon sets) के लिए ग्रीडी एल्गोरिदम को बेहतर ढंग से समझना है, जिनके भौतिक वास्तविक दुनिया के अनुप्रयोग हैं (जैसे गोलोम्ब रूलर्स, फ्रीक्वेंसी एलोकेशन)। चूंकि ग्रीडी एल्गोरिदम एडिटिव समस्याओं के लिए एक मानक ह्यूरिस्टिक है, इसलिए $B_h$ -सेट्स के लिए बाउंड्स स्थापित करना एडिटिव नंबर थ्योरी में ग्रीडी रणनीतियों की व्यापक समझ में योगदान देता है।

शोध पत्र खुले प्रश्नों (open problems) की सूची के साथ समाप्त होता है, जिसमें $\gamma_k$ के क्वासी-पॉलीनोमियल (quasi-polynomial) सूत्रों को सिद्ध करना, कॉंग्रुएंस क्लासेस (congruence classes) में तत्वों का एकसमान वितरण, और उस $s$ का इन्फिमम (infimum) शामिल है जिसके लिए ग्रीडी $B_h$ -सेट्स के रेसिप्रोकल पावर्स का योग अभिसरित (converge) होता है। लेखक विनम्रतापूर्वक नोट करता है कि हालांकि बाउंड्स गैर-तुच्छ हैं, वे सटीक (tight) नहीं भी हो सकते हैं, और $k \ge 5$ के लिए सटीक गुणांक अभी भी अनुमानित (conjectural) हैं।