वह सबसे बड़ी राशि जो चुकाई नहीं जा सकती, अब एक कसी हुई सीमा में

एक ऐसे कैश काउंटर की कल्पना कीजिए जो केवल कुछ तरह के सिक्के लेता है, जिनकी आपूर्ति असीमित है, और जो कभी छुट्टा वापस नहीं करता। कुछ राशियाँ ठीक-ठीक चुकाई जा सकती हैं; कुछ कभी नहीं। गणितज्ञ इन सिक्का-मूल्यों को जनक (generators) कहते हैं, और एक भ्रामक रूप से सरल प्रश्न पूछते हैं: वह सबसे बड़ी राशि कौन-सी है जो चुकाई नहीं जा सकती?

वे राशियाँ जो कभी नहीं चुकाई जा सकतीं

ऐसी पूर्ण संख्याएँ a₁ < a₂ < … < aₙ लीजिए जिनमें कोई ऐसा गुणनखंड न हो जो सभी में साझा हो। इन संख्याओं को जोड़कर, हर एक को जितनी बार चाहें लेकर, जो योग मिलता है उसे “निरूपणीय” कहते हैं। केवल सीमित संख्या में ही पूर्ण संख्याएँ निरूपणीय नहीं होतीं; उनमें सबसे बड़ी है फ्रोबेनियस संख्या, F। (अगर कोई एक मूल्य 1 हो, तो हर राशि चुकाई जा सकती है और F को −1 माना जाता है।)

एक छोटा उदाहरण: 3, 4 और 6 के सिक्कों से आप 3, 4, 6, 7, 8 और उसके बाद की हर राशि चुका सकते हैं, लेकिन 1, 2 या 5 कभी नहीं। इसलिए F = 5। ध्यान दें कि 3 और 6 में एक साझा गुणनखंड है; मायने यह रखता है कि कोई भी गुणनखंड तीनों में साझा नहीं है।

दो सिक्कों के लिए एक सटीक उत्तर है, सिल्वेस्टर का सूत्र: F(a₁, a₂) = a₁a₂ − a₁ − a₂। तीन या अधिक के लिए काम F को सीमा में बाँधने का है: यह साबित करना कि वह सिक्कों से गणना किए गए किसी मान से अधिक नहीं हो सकता।

2 का एक ज़िद्दी गुणक

पॉल एर्डोश (Paul Erdős) और रोनाल्ड ग्राहम (Ronald Graham) ने तीन या अधिक जनकों के लिए साबित किया:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

यहाँ aₙ सबसे बड़ा मूल्य है, aₙ₋₁ दूसरा सबसे बड़ा, n मूल्यों की संख्या, और ⌊ ⌋ का अर्थ है नीचे की ओर पूर्णांकन। सिल्वेस्टर के सूत्र की तरह, इसमें भी दो सबसे बड़े सिक्के शामिल हैं।

उन्होंने सबसे बुरी स्थिति का भी अनुमान लगाया, यानी F का वह सबसे बड़ा संभव मान जब सभी n मूल्य अधिकतम t हों। उनके अनुमानों के बीच का अंतर, मोटे तौर पर 2 का गुणक, एक अनुमान (कंजेक्चर) तक ले गया, जो एर्डोश समस्या #433 (Erdős Problem #433) के रूप में दर्ज है। जैक्स डिक्समियर (Jacques Dixmier) ने इसे हल किया, और हर समूह पर लागू होने वाली एक सरल सीमा भी साबित की: F ≤ aₙ²/(n − 1)। 2 का गुणक चला गया, लेकिन दूसरा सबसे बड़ा सिक्का भी।

दोनों सबसे बड़े सिक्कों को बनाए रखना

झेजियांग विश्वविद्यालय के कंप्यूटर विज्ञान एवं प्रौद्योगिकी कॉलेज के लिन चेन (Lin Chen), तिंगवेई हू (Tingwei Hu), यूचेन माओ (Yuchen Mao) और गुओचुआन झांग (Guochuan Zhang) दोनों चाहते थे: 2 का गुणक न हो, और दूसरा सबसे बड़ा सिक्का बना रहे। उनका उत्तर, जो दो या अधिक मूल्यों के किसी भी समूह के लिए मान्य है:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

यहाँ ⌈ ⌉ का अर्थ है ऊपर की ओर पूर्णांकन। एर्डोश और ग्राहम की तुलना में 2 का गुणक ग़ायब हो गया है, इस क़ीमत पर कि अब n के बजाय n − 1 से भाग दिया जाता है और ऊपर की ओर पूर्णांकन होता है। डिक्समियर की तुलना में, जब दूसरा सबसे बड़ा सिक्का सबसे बड़े के मुक़ाबले छोटा हो, तो नई सीमा काफ़ी छोटी हो सकती है।

3, 4, 6 वाले उदाहरण पर एर्डोश और ग्राहम की सीमा 10 देती है, डिक्समियर की 18, और नई सीमा 4 × 3 − 6 − 1 = 5, ठीक वास्तविक मान। इसमें कोई आश्चर्य नहीं: यह समूह नीचे बताए गए चरम उदाहरणों के परिवार का हिस्सा है, जिन्हें ठीक सीमा तक पहुँचने के लिए ही बनाया गया है; शोधपत्र सामान्य समूहों पर कोई तुलना नहीं देता।

राशियों को शेषफल के अनुसार छाँटना

प्रमाण एर्डोश और ग्राहम के रास्ते पर चलता है। हर राशि को सबसे बड़े सिक्के aₙ से भाग देने पर बचे शेषफल के अनुसार छाँटिए। जैसे ही छोटे सिक्कों का कोई योग किसी दिए गए शेषफल तक पहुँचता है, उसमें aₙ की प्रतियाँ जोड़कर उसी शेषफल वाली हर बड़ी राशि तक पहुँचा जा सकता है। काम यह दिखाना है कि हर शेषफल तक कम लागत में पहुँचा जा सकता है।

मुख्य औज़ार क्नेसर का प्रमेय (Kneser’s theorem) है, जो बताता है कि योगों का एक समुच्चय कम से कम कितना बड़ा होना चाहिए। एर्डोश और ग्राहम ने इसका उपयोग यह दिखाने के लिए किया कि लगभग aₙ/n सिक्कों के योग आधे से अधिक शेषफलों को ढक लेते हैं, और फिर सिक्कों की संख्या दोगुनी करके सबको ढक लिया। इन योगों का हर सिक्का अधिकतम aₙ₋₁ मूल्य का है, इसलिए सिक्कों की संख्या दोगुनी करने से लागत भी दोगुनी हो जाती है: यहीं से 2 का गुणक आता है।

नया प्रमाण ⌈aₙ/(n − 1)⌉ सिक्कों के योगों का उपयोग करता है। जब ये योग कुछ शेषफलों से चूक जाते हैं, तो क्नेसर का प्रमेय कहता है कि छूटे हुए शेषफल यूँ ही बेतरतीब बिखरे नहीं होते: वे नियमित अंतरालों पर फैले शेषफलों के पूरे-पूरे परिवार बनाते हैं। जितने अधिक परिवार छूटते हैं, छोटे सिक्कों को उतना ही अधिक हर उस परिवार में ठसना पड़ता है जिस तक पहुँचा गया है, इसलिए ऐसे हर परिवार में कुछ छोटे सिक्के होते हैं, और छूटे परिवारों तक पहुँचने के लिए ज़रूरी थोड़े-से अतिरिक्त सिक्के सस्ते पड़ते हैं। कुल लागत कभी भी ⌈aₙ/(n − 1)⌉ × aₙ₋₁ से अधिक नहीं होती।

यह पहला चरण सीमा को उसके अंतिम “− 1” के बिना देता है। आख़िरी इकाई एक अलग तर्क से आती है, जो शेर्क (Scherk) और केम्परमैन (Kemperman) के एक प्रमेय पर आधारित है, जो उन योगों के बारे में है जिन्हें केवल एक ही तरीक़े से बनाया जा सकता है: यह दिखाता है कि सीमा पर खड़ी राशि aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ स्वयं भी हमेशा चुकाई जा सकती है। आभार-खंड के अनुसार, लेखकों ने पहले कमज़ोर सीमा साबित की; फिर GPT-6 ने वह तर्क खोजने में मदद की जो इसे एक से घटाता है, और इस प्रमाण में भी सहायता की कि सीमा को और नीचे नहीं लाया जा सकता, तथा अंग्रेज़ी के संपादन में भी। लेखक कहते हैं कि अंतिम पांडुलिपि की ज़िम्मेदारी वे स्वयं लेते हैं।

वे उदाहरण जो ठीक सीमा को छूते हैं

इस सीमा को और नीचे नहीं लाया जा सकता: हर n ≥ 3 के लिए लेखक ऐसे अनगिनत समूह बनाते हैं जिनमें F ठीक इसके बराबर होता है। कोई भी q ≥ 2 लीजिए और मूल्य q, 2q, …, (n − 1)q, साथ में (n − 2)q + 1। एक को छोड़कर सभी q के गुणज हैं, इसलिए वे ऐसी कोई राशि नहीं चुकाते जो अकेला q न चुका सके। यह समूह दो सिक्कों, q और (n − 2)q + 1, की तरह व्यवहार करता है, और सिल्वेस्टर का सूत्र ऐसा F देता है जो नई सीमा से ठीक मेल खाता है। n = 3 और q = 3 के साथ यह नुस्ख़ा ठीक ऊपर वाला 3, 4, 6 का उदाहरण देता है।

कम सिक्के, नीची छत

इस सीमा को घनत्व के रूप में भी पढ़ा जा सकता है। यह i सबसे छोटे मूल्यों और सबसे बड़े मूल्य से बने किसी भी घटाए हुए समूह पर लागू होती है, बशर्ते उनमें अब भी कोई साझा गुणनखंड न हो। सिक्के हटाने से चुकाना केवल कठिन ही हो सकता है, इसलिए घटाए हुए समूह के लिए साबित की गई छत पूरे समूह पर भी लागू होती है। परिणाम को मोटे तौर पर aᵢ/i नियंत्रित करता है, जो इस बात का व्युत्क्रम है कि पहले i मूल्य 1 से aᵢ तक की संख्याओं को कितनी सघनता से भरते हैं: सबसे सघन समूह जीतता है। लेखक विशेष रूप से बताते हैं कि जब भी बाक़ी सिक्कों में कोई ऐसा गुणनखंड न हो जो सभी में साझा हो, तो दूसरे सबसे बड़े सिक्के को सीधे किनारे रखा जा सकता है।

शोधपत्र पूरी तरह सैद्धांतिक रहता है: यह कोई संख्या नहीं देता कि सामान्य सिक्का-समूहों पर नई सीमा कितनी छोटी है, और इसकी सटीकता (sharpness) केवल तीन या अधिक सिक्का-मूल्यों के लिए साबित की गई है।