On the largest sum-free subset of the lattice cube

यहाँ पीटर कीवश (Peter Keevash) और जेक लिम (Jeck Lim) के शोध पत्र "On the largest sum-free subset of the lattice cube" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र एक $d$-आयामी लैटिस क्यूब (lattice cube) के भीतर सबसे बड़े सम-मुक्त उपसमुच्चय (sum-free subset) के आनुपातिक घनत्व (asymptotic density) को निर्धारित करने की समस्या का समाधान करता है।

• परिभाषाएँ: एक एबेलियन समूह (abelian group) का उपसमुच्चय $S$ तब 'सम-मुक्त' कहलाता है यदि उसमें कोई $x, y, z \in S$ न हों जिससे $x + y = z$ हो। लेखक लैटिस क्यूब $[n+1]^d = \{0, 1, \dots, n\}^d$ के उपसमुच्चयों का अध्ययन करते हैं।
• उद्देश्य: सीमा $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$ का निर्धारण करना, जहाँ $S$ सबसे बड़ा सम-मुक्त उपसमुच्चय है।
• संदर्भ:
  • $d=1$ के लिए, यह ज्ञात है कि $c_1 = 1/2$ है।
  • $d=2$ के लिए, एल्शोल्ट्ज़ और रैकहैम (Elsholtz and Rackham) ने सिद्ध किया कि $c_2 = 3/5$ है।
  • $d=3, 4$ के लिए, लेप्सवेरिज़े और सन (Lepsveridze and Sun) ने हाल ही में इन मामलों को हल किया है।
  • परिकल्पना (The Conjecture): यह परिकल्पना की गई थी कि सभी $d$ के लिए, इष्टतम सेट एक हाइपरप्लेन द्वारा परिभाषित क्यूब का एक "स्लाइस" (slice) है। विशेष रूप से, सेट $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$, जहाँ $u$ स्लाइस के आयतन को अधिकतम करता है, अधिकतम घनत्व प्रदान करता है।
  • यदि $c^*_d$ निरंतर सीमा (continuous limit) $[0,1]^d$ में ऐसे स्लाइस का अधिकतम आयतन है, तो परिकल्पना कहती है कि $c_d = c^*_d$ है।

2. कार्यप्रणाली (Methodology)

यह प्रमाण लेप्सवेरिज़े और सन द्वारा स्थापित दृष्टिकोण का अनुसरण करता है, जिसमें रैखिक प्रोग्रामिंग द्वैतता (linear programming duality) और संभाव्यता युग्मन (probabilistic coupling/joint mixability) का संयोजन उपयोग किया गया है।

A. रैखिक प्रोग्रामिंग में न्यूनीकरण (Reduction to Linear Programming)

$|S|$ को सीमित करने की समस्या को एक रैखिक प्रोग्राम (LP) के रूप में पुनर्गठित किया गया है।

• प्राइमल समस्या (Primal Problem): $\sum |S(x)|$ को अधिकतम करना (जहाँ $S(x)$, सेट $S$ के फाइबर हैं) इस प्रतिबंध के अधीन कि किसी भी $x, y, z$ के लिए जहाँ $x+y=z$ हो, $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$।
• डुअल समस्या (Dual Problem): एक ऊपरी सीमा खोजने के लिए, डुअल LP के लिए एक व्यवहार्य समाधान (भार/weights) का निर्माण करना आवश्यक है। ऐसे भारों का अस्तित्व विशिष्ट संभाव्यता वितरणों को युग्मित (couple) करने की क्षमता पर निर्भर करता है।

B. जॉइंट मिक्सिबिलिटी (Joint Mixability)

मुख्य तकनीकी नवाचार एक जॉइंट मिक्सिबिलिटी (Joint Mixability) परिणाम का प्रमाण है।

• परिभाषा: वितरण $\mu_1, \mu_2, \mu_3$ जॉइंटली मिक्सेबल (jointly mixable) हैं यदि $\mu_1, \mu_2, \mu_3$ के साथ एक युग्मन (coupling) $(X_1, X_2, X_3)$ मौजूद है जिससे $X_1 + X_2 + X_3 = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \mathbb{E}[X_3]$ लगभग निश्चित रूप से (almost surely) सत्य हो।
• मुख्य प्रमेय (Theorem 1.5): लेखक सिद्ध करते हैं कि किसी भी गैर-ऋणात्मक पूर्णांक $r, s, t$ के लिए, जहाँ $r+s+t = dn$है, डिस्क्रीट स्लाइस$L_d(r), L_d(s), L_d(t)$(जहाँ$L_d(k) = {x \in [n+1]^d : \sum x_i = k}$) पर यूनिफॉर्म वितरण जॉइंटली मिक्सेबल हैं।
• प्रमाण तकनीक:
  • $d$ पर इंडक्शन (Induction on $d$): आधार मामला $d=2$ अंतराल (intervals) और त्रिकोण असमानताओं (triangle inequalities) के ज्ञात परिणामों पर आधारित है।
  • इंडक्टिव स्टेप ($d \ge 3$): लेखक पहले निर्देशांकों (coordinates) के लिए एक युग्मन का निर्माण करते हैं, जिसमें फिक्स्ड-पॉइंट तर्क (Brouwer's Fixed Point Theorem या Perron-Frobenius) का उपयोग किया गया है। वे पहले निर्देशांकों के सपोर्ट पर संभाव्यता वितरणों के स्थान पर एक मानचित्र (map) को परिभाषित करते हैं और दिखाते हैं कि एक फिक्स्ड पॉइंट मौजूद है। यह फिक्स्ड पॉइंट यह सुनिश्चित करता है कि मार्जिनल्स (marginals) स्लाइस के आवश्यक यूनिफॉर्म वितरणों से मेल खाते हैं, जिससे शेष $d-1$ निर्देशांकों के लिए इंडक्शन परिकल्पना को लागू करना संभव हो जाता है।

C. वेट कंस्ट्रक्शन और स्लाइस अनुमान (Weight Construction and Slice Estimates)

डुअल LP में जॉइंट मिक्सिबिलिटी को लागू करने के लिए:

1. विभाजन (Partitioning): डोमेन $[n+1]^{d-1}$ को इष्टतम स्लाइस पैरामीटर $u^*_d$ के सापेक्ष निर्देशांकों के योग के आधार पर पाँच सेटों ($A, B, C, D, E$) में विभाजित किया गया है।
2. वेट फंक्शन (Weight Function): जॉइंट मिक्सिबिलिटी परिणाम का उपयोग करते हुए, लेखक इन सेटों के विशिष्ट ट्रिपल्स (triples) पर समर्थित एक वेट फंक्शन $w(x,y,z)$ का निर्माण करते हैं।
3. विश्लेषणात्मक अनुमान (Analytic Estimates): वे यूनिफॉर्म रैंडम वेरिएबल्स के योग (Irwin-Hall वितरण) के संभाव्यता घनत्व फलन के लॉग-कॉन्केविटी (log-concavity) गुणों का उपयोग करते हैं। वे स्लाइस वॉल्यूम के अनुपातों पर स्पष्ट सीमाएँ (लेम्मा 3.1) प्राप्त करते हैं ताकि निर्मित वेट्स डुअल बाधाओं को संतुष्ट कर सकें।
   • बड़े $d$ के लिए, वे लार्ज डेविएशन अनुमानों (large deviation estimates) का उपयोग करते हैं।
   • छोटे $d$ ($5 \le d < 200$) के लिए, वे इन असमानताओं को संख्यात्मक रूप से सत्यापित करते हैं।

3. मुख्य योगदान (Key Contributions)

1. सभी $d$ के लिए परिकल्पना का समाधान: यह शोध पत्र सिद्ध करता है कि सभी आयामों $d \ge 1$ के लिए $c_d = c^*_d$ है। यह पुष्टि करता कि इष्टतम सम-मुक्त उपसमुच्चय वास्तव में हाइपरप्लेन $\sum x_i \in [u^*_d n, 2u^*_d n)$ द्वारा परिभाषित स्लाइस है।
2. सामान्य जॉइंट मिक्सिबिलिटी प्रमेय: प्रमेय 1.5 का प्रमाण संभाव्यता सिद्धांत और कॉम्बिनेटरिक्स में एक महत्वपूर्ण योगदान है। यह स्थापित करता है कि एक हाइपरक्यूब के डिस्क्रीट स्लाइस के यूनिफॉर्म वितरण, जिनका योग एक स्थिर मान है, जॉइंटली मिक्सेबल हैं; यह एक ऐसा परिणाम है जो विशिष्ट निम्न आयामों के पिछले निष्कर्षों का सामान्यीकरण करता है।
3. लेप्सवेरिज़े-सन दृष्टिकोण का परिशोधन: लेखक $d=3,4$ के लिए उपयोग किए गए तरीके को अनिश्चित आयामों के लिए सामान्यीकृत करते हैं, और उच्च आयामों में युग्मन (couplings) के निर्माण की जटिलता को एक कठोर इंडक्टिव फिक्स्ड-पॉइंट तर्क के माध्यम से दूर करते हैं।

4. मुख्य परिणाम (Main Results)

• प्रमेय 1.1: किसी भी $d \ge 1$ और किसी सम-मुक्त उपसमुच्चय $S \subseteq [n+1]^d$ के लिए, आकार इस प्रकार सीमित है:
  $$|S| \le c^*_d n^d + O(n^{d-1})$$
  जहाँ $c^*_d$ स्लाइस $S_d(u) = \{x \in [0,1]^d : u \le \sum x_i < 2u\}$ का अधिकतम आयतन है।
• उपप्रमेय (Corollary): सीमित घनत्व (limiting density) सटीक रूप से इष्टतम स्लाइस का आयतन है, जो कैमरन, ग्रीन और अन्यों द्वारा प्रस्तुत स्वाभाविक परिकल्पना को हल करता है।

5. महत्व और विस्तार (Significance and Extensions)

• कॉम्बिनेटरियल नंबर थ्योरी: यह परिणाम उच्च-आयामी लैटिस में सम-मुक्त सेटों की संरचना के संबंध में एक लंबे समय से चले आ रहे खुले प्रश्न को हल करता है। यह पुष्टि करता है कि "स्लाइस" निर्माण सार्वभौमिक रूप से इष्टतम है, न कि केवल कम आयामों के लिए।
• संभाव्यता विधियाँ (Probabilistic Methods): यह शोध पत्र चरम कॉम्बिनेटरियल समस्याओं को हल करने में जॉइंट मिक्सिबिलिटी और कपलिंग तकनीकों की शक्ति का प्रदर्शन करता है। फिक्स्ड-पॉइंट थ्योरम के माध्यम से कपलिंग का इंडक्टिव निर्माण एक नवीन और सुदृढ़ तकनीक है।
• सामान्य उत्तल सेट (General Convex Sets): लेखक संक्षेप में चर्चा करते हैं कि क्या यह "स्लाइस" इष्टतमता सामान्य उत्तल सेटों (convex sets) के लिए भी लागू होती है। वे एक प्रति-उदाहरण (प्रपोजिशन 5.1) प्रदान करते हैं जो दर्शाता है कि पर्याप्त बड़े $d$ के लिए, ऐसे उत्तल सेट मौजूद हैं जहाँ सबसे बड़ा सम-मुक्त उपसमुच्चय एक लीनियर फंक्शनल द्वारा परिभाषित एकल स्लाइस नहीं है। यह हाइपरक्यूब की समरूपता (symmetry) को स्लाइस इष्टतमता के लिए महत्वपूर्ण बनाता है।
• खुली समस्या: यह शोध पत्र इस प्रश्न को खुला छोड़ देता है कि क्या आयाम $d=2$ में सभी परिबद्ध उत्तल सेटों (bounded convex sets) के लिए स्लाइस इष्टतमता लागू होती है।

संक्षेप में, यह शोध पत्र लैटिस क्यूब में सबसे बड़े सम-मुक्त उपसमुच्चय के आनुपातिक घनत्व का पूर्ण समाधान प्रदान करता है, जो पिछले आंशिक परिणामों को एकीकृत करता है और अनिश्चित आयामों को संभालने के लिए शक्तिशाली संभाव्यता उपकरणों को पेश करता है।