Subsequence Sums in Permutations

तकनीकी सारांश: क्रमचय में उपक्रम (Subsequence) योग

समस्या विवरण
यह शोध पत्र समुच्चय $\{1, 2, \dots, n\}$ के क्रमचयों (permutations) के भीतर विशिष्ट अंकगणितीय उपक्रमों (arithmetic subsequences) की उपस्थिति की जांच करता है। जबकि शास्त्रीय अंकगणितीय रामसे सिद्धांत (जैसे वैन डेर वार्डन का प्रमेय) पर्याप्त बड़े रंगीन समुच्चयों में मोनोक्रोमैटिक अंकगणितीय प्रगति (arithmetic progressions) की गारंटी देता है, एन्ट्रिंगर और जैक्सन (1973) ने प्रदर्शित किया कि क्रमचय मोनोटोन (monotone) 3-टर्म अंकगणितीय प्रगति (3-AP) से बच सकते हैं। लेखक पूछते हैं कि क्या अन्य अंकगणितीय गुण, विशेष रूप से "योगात्मक" (additive) उपक्रम, बड़े क्रमचयों में अपरिहार्य हैं।

धनात्मक पूर्णांकों के एक अनुक्रम $(a_1, a_2, \dots, a_k)$ को $\ell$-योगात्मक ( $\ell$-additive) कहा जाता है यदि इसके पदों का योग $\sum_{i=1}^k a_i = \ell a_1$ या $\sum_{i=1}^k a_i = \ell a_k$ हो। मुख्य ध्यान 2-योगात्मक उपक्रमों (जहाँ योग पहले या अंतिम पद का दोगुना होता है) और उनके मोनोटोन वेरिएंट पर है। शोध पत्र दो मुख्य प्रश्नों को संबोधित करता है:

1. एक निश्चित लंबाई $k \ge 3$ के लिए, क्या ऐसा $n$ मौजूद है कि $\{1, \dots, n\}$ का प्रत्येक क्रमचय एक $k$-लंबाई वाले 2-योगात्मक उपक्रम को समाहित करता है?
2. विशेष रूप से मोनोटोन अनुक्रमों तक सीमित होने पर, ऐसे उपक्रमों के अस्तित्व के लिए सटीक सीमाएँ (thresholds) और बाउंड्स क्या हैं?

कार्यप्रणाली (Methodology)
लेखक अंकगणितीय रामसे सिद्धांत की तकनीकों के साथ संयोजन में कॉम्बिनेटोरियल तर्क, केस विश्लेषण और अन्य विधियों का उपयोग करते हैं।

• कॉम्बिनेटोरियल निर्माण और विरोधाभास: अस्तित्व के लिए मुख्य प्रमाण (प्रमेय 1.1 और 1.3) क्रमचयों के विशिष्ट उपसमुच्चयों का निर्माण करने और विरोधाभास द्वारा प्रमाण (proof by contradiction) पर आधारित हैं। तत्वों की सापेक्ष स्थिति का विश्लेषण करके (एक क्रमचय $p$ में $s$ के बाईं ओर और दाईं ओर के तत्वों को $L_p(s)$ और $R_p(s)$ का उपयोग करके), लेखक प्रदर्शित करते हैं कि 2-योगात्मक उपक्रम से बचना क्रमचय के विन्यास (layout) में एक संरचनात्मक विरोधाभास पैदा करता है।
• बाउंडिंग तकनीक: ऐसे उपक्रमों के लिए सबसे छोटे $n$ (जिसे $f(k, 2)$ कहा जाता है) के लिए ऊपरी सीमा स्थापित करने हेतु, लेखक एक क्रमचय के पहले $2k-1$ तत्वों से प्राप्त "खतरनाक" (dangerous) योगों को परिभाषित करते हैं। वे एक सीमा $N_k$ निर्धारित करने के लिए इन योगों के लघुत्तम समापवर्त्य (LCM) का उपयोग करते हैं जिसके बाद 2-योगात्मक उपक्रम अनिवार्य हो जाता है।
• निम्नतम सीमाएँ (Lower Bounds) और प्रति-उदाहरण: निम्नतम सीमाओं को $n-1$ आकार के ऐसे क्रमचयों का स्पष्ट निर्माण करके स्थापित किया गया है जिनमें वांछित उपक्रमों का अभाव है।
• अनंतस्पर्शी विश्लेषण (Asymptotic Analysis): लेखक बड़े क्रमचयों में ऐसे उपक्रमों की संख्या पर निम्नतम सीमा प्राप्त करने के लिए प्राइम नंबर थ्योरम (रोसर के परिणामों के माध्यम से) का उपयोग करते हैं।
• रूपांतरण तर्क (Transformation Arguments): गुणन (products) और व्युत्क्रम योगों (inverse sums) में परिणामों का विस्तार करने के लिए, लेखक मानक रूपांतरणों का उपयोग करते हैं जो $\{1, \dots, n\}$ में योगात्मक गुणों को $\{2^1, \dots, 2^n\}$ में गुणात्मक गुणों में और $\{L_n/1, \dots, L_n/n\}$ में व्युत्क्रम-योगात्मक गुणों में मैप करते हैं (जहाँ $L_n$, $1$से$n$ का LCM है)।

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

1. 2-योगात्मक उपक्रमों का अस्तित्व (प्रमेय 1.1):
   किसी भी निश्चित $k \ge 3$ के लिए, यदि $n$ पर्याप्त रूप से बड़ा है, तो $\{1, \dots, n\}$ का प्रत्येक क्रमचय एक $k$-लंबाई वाले 2-योगात्मक उपक्रम को समाहित करता है।

   • सीमाएँ: शोध पत्र ऐसे $n$ के लिए सबसे छोटे $f(k, 2)$ के लिए बहुपद सीमाएँ (polynomial bounds) प्रदान करता है।
     • निम्नतम सीमा: $f(k, 2) \ge (k-1)(3k-4)/2$.
     • ऊपरी सीमा: $f(k, 2) \le 9(k-2)(k^2-k)^2/4$.
   • $k=3$ के लिए सटीक मान: लेखक सिद्ध करते हैं कि $f(3, 2) = 5$। $\{1, \dots, 5\}$ का प्रत्येक क्रमचय 3-लंबाई वाले 2-योगात्मक उपक्रम को समाहित करता है, जबकि $n=4$ के लिए एक प्रति-उदाहरण मौजूद है।

2. मोनोटोन 2-योगात्मक उपक्रम (प्रमेय 1.3):
   शोध पत्र अधिक सख्त शर्त को संबोधित करता है जहाँ उपक्रम को अनिवार्य रूप से मोनोटोन होना चाहिए।

   • परिणाम: यदि $n \ge 18$, तो $\{1, \dots, n\}$ का प्रत्येक क्रमचय 3-लंबाई वाले एक मोनोटोन 2-योगात्मक उपक्रम को समाहित करता है।
   • तीक्ष्णता (Sharpness): 18 का मान इष्टतम है; $\{1, \dots, 17\}$ का एक विशिष्ट क्रमचय निर्मित किया गया है जो ऐसे उपक्रमों से बचता है।
   • खुला प्रश्न: यह अज्ञात है कि क्या यह $k \ge 4$ की लंबाई वाले मोनोटोन 2-योगात्मक उपक्रमों के लिए भी लागू होता है।

3. सामान्य $\ell$-योगात्मक उपक्रम:

   • यदि $k = \ell$, तो पहचान क्रमचय (identity permutation) $(1, 2, \dots, n)$ में $k$ लंबाई का कोई $\ell$-योगात्मक उपक्रम नहीं होता है।
   • शोध पत्र दो विशिष्ट मिश्रित मामलों को हल करता है:
     • $f(4, 3) = 8$ (8 तत्वों का प्रत्येक क्रमचय 4-लंबाई वाले 3-योगात्मक उपक्रम को रखता है)।
     • $f(3, 4) = 13$ (13 तत्वों का प्रत्येक क्रमचय 3-लंबाई वाले 4-योगात्मक उपक्रम को रखता है)।
   • $k \neq \ell$ के साथ सामान्य मामला जहाँ $k, \ell \ge 4$ है, एक खुला प्रश्न बना हुआ है।

4. उपक्रमों की गणना:
   लेखक $n$ आकार के किसी भी क्रमचय में $k$ लंबाई वाले $\ell$-योगात्मक उपक्रमों की न्यूनतम संख्या पर सीमाएँ प्रदान करते हैं:

   • ऊपरी सीमा: $O(n^{k-1})$।
   • निम्नतम सीमा: $\Omega(n / \log n)$ (यह मानते हुए कि $f(k, \ell)$ मौजूद है), जो अभाज्य संख्या वितरण तर्कों का उपयोग करके प्राप्त की गई है।
   • 3-लंबाई वाले मोनोटोन 2-योगात्मक उपक्रमों के लिए विशिष्ट सीमाएँ $n/[18(\log n - \log 18 + 2)] - 6 \le G(3, 2, n) \le \frac{1}{18}n^2 + \frac{7}{6}n$ दी गई हैं।

5. गुणों और व्युत्क्रम योगों में विस्तार:
   अंकगणितीय रामसे सिद्धांत रूपांतरणों का उपयोग करते हुए, शोध पत्र निम्नलिखित के लिए योगात्मक परिणामों का विस्तार करता है:

   • गुणात्मक (Multiplicative): प्रत्येक बड़े पर्याप्त क्रमचय में एक ऐसा उपक्रम होता है जहाँ गुणनफल पहले या अंतिम पद का वर्ग होता है (2-गुणात्मक)।
   • व्युत्क्रम-योगात्मक (Inverse-Additive): प्रत्येक बड़े पर्याप्त क्रमचय में एक ऐसा उपक्रम होता है जहाँ व्युत्क्रमों का योग पहले या अंतिम पद के व्युत्क्रम का दोगुना होता है।
   • शोध पत्र नोट करता है कि 3-लंबाई वाले मोनोटोन 2-गुणात्मक उपक्रमों के लिए, सीमा अधिकतम 32 है (और ठीक 32 है, क्योंकि $n=31$ के लिए एक प्रति-उदाहरण मौजूद है)।

महत्व और दावे
शोध पत्र दावा करता है कि यह विशेष रूप से क्रमचयों के लिए पहले शूर-राडो-टाइप (Schur-Rado-type) परिणामों को स्थापित करता है, यह प्रदर्शित करते हुए कि जबकि क्रमचय मोनोटोन अंकगणितीय प्रगति (3-AP) से बच सकते हैं, वे मनमाने लंबाई के 2-योगात्मक उपक्रमों से नहीं बच सकते। यह कार्य इन संरचनाओं के अस्तित्व के लिए पहले बहुपद सीमाएँ प्रदान करता है और छोटे मामलों ($k=3$) के लिए सटीक सीमाएँ निर्धारित करता है।

लेखक अपने योगदान को आगे के अध्ययन के लिए एक आधार के रूप में विनम्रतापूर्वक प्रस्तुत करते हैं। वे इस बात पर प्रकाश डालते कि $k \neq \ell$ का सामान्य मामला अभी भी खुला है और $k > 3$ की लंबाई वाले मोनोटोन 2-योगात्मक उपक्रमों का व्यवहार अज्ञात है। यह शोध पत्र इन निष्कर्षों को क्रमचय संरचना और अंकगणितीय गुणों के बीच परस्पर क्रिया को समझने की दिशा में एक कदम के रूप में स्थापित करता है, जो भारित (weighted) उपक्रम योगों और गुणात्मक एवं व्युत्क्रम-योगात्मक वेरिएंट के लिए सीमाओं के परिशोधन में भविष्य की दिशाओं का सुझाव देता है।