द्वैध जालक

जालक (समूह) के सिद्धांत में, द्वैध जालक एक द्वैध सदिश स्थान के अनुरूप एक निर्माण है। कुछ स्तिथियों में, एक जालक की द्वैध जालक की ज्यामिति ${\textstyle L}$ की ज्यामिति का व्युत्क्रम ${\textstyle L}$ है, एक परिप्रेक्ष्य जो इसके कई उपयोगों को रेखांकित करता है।

द्वैध जालक में जालक सिद्धांत, सैद्धांतिक कंप्यूटर विज्ञान, कूटलेखन और गणित के अंदर व्यापक रूप से कई अनुप्रयोग हैं। उदाहरण के लिए, इसका उपयोग पॉइसन योग सूत्र के कथन में किया जाता है, स्थानांतरण प्रमेय एक जालक की ज्यामिति और उसके द्वैध के बीच संबंध प्रदान करते हैं, और कई जालक एल्गोरिदम द्वैध जालक का लाभ उठाते हैं।

भौतिकी/रसायन विज्ञान अनुप्रयोगों पर जोर देने वाले लेख के लिए, पारस्परिक जालक देखें। यह लेख द्वैध जालक की गणितीय धारणा पर केंद्रित है।

परिभाषा

मान लीजिये ${\textstyle L\subseteq \mathbb {R} ^{n}}$ एक जालक है। वह, ${\textstyle L=B\mathbb {Z} ^{n}}$ कुछ आव्यूह के लिए ${\textstyle B}$ है।

द्वैध जालक पर रैखिक रूप कार्यात्मक (गणित) का सम्मुच्चय है ${\textstyle L}$ जो प्रत्येक बिंदु पर पूर्णांक ${\textstyle L}$ मान लेता है:

$L^{*}=\{f\in ({\text{span}}(L))^{*}:\forall x\in L,f(x)\in \mathbb {Z} \}.$

अगर ${\textstyle (\mathbb {R} ^{n})^{*}}$ ${\textstyle \mathbb {R} ^{n}}$ से पहचाना जाता है तोडॉट उत्पाद का उपयोग करके हम ${\textstyle L^{*}=\{v\in {\text{span}}(L):\forall x\in L,v\cdot x\in \mathbb {Z} \}}$ लिख सकते हैं, ${\textstyle L}$ के रैखिक विस्तार में सदिश (गणित और भौतिकी) तक सीमित रहना महत्वपूर्ण है, अन्यथा परिणामी वस्तु एक जालक (समूह) नहीं है।

परिवेशी यूक्लिडियन स्थानों की इस पहचान के बाद भी, इस बात पर दबाव दिया जाना चाहिए कि एक जालक और उसके द्वैध मूल रूप से विभिन्न प्रकार की वस्तुएं हैं; एक में यूक्लिडियन स्थल में सदिश होते हैं, और दूसरे में उस स्थान पर रैखिक कार्यात्मकताओं का एक सम्मुच्चय होता है। इन पंक्तियों के साथ, कोई इस प्रकार अधिक अमूर्त परिभाषा भी दे सकता है:

$L^{*}=\{f:L\to \mathbb {Z} :{\text{f is a linear function}}\}={\text{Hom}}_{\text{Ab}}(L,\mathbb {Z} ).$

हालाँकि, हम ध्यान दें कि द्वैध को केवल कार्यों के एक अमूर्त एबेलियन समूह के रूप में नहीं माना जाता है, बल्कि यह एक प्राकृतिक आंतरिक उत्पाद: ${\textstyle f\cdot g=\sum _{i}f(e_{i})g(e_{i})}$ के साथ आता है, जहाँ ${\textstyle e_{i}}$ का एक अलंकारिकता आधार ${\textstyle {\text{span}}(L)}$ है (समान रूप से, कोई इसे सामान्य आधार ${\textstyle e_{i}}$ के ${\textstyle {\text{span}}(L)}$ पर घोषित कर सकता है, द्वैध सदिश ${\textstyle e_{i}^{*}}$, द्वारा परिभाषित ${\textstyle e_{i}^{*}(e_{j})=\delta _{ij}}$ एक प्रसामान्य लांबिक विश्लेषण आधार हैं।) जालक सिद्धांत में द्वंद्व के प्रमुख उपयोगों में से एक प्रारंभिक जालक की ज्यामिति का उसके द्वैध की ज्यामिति के साथ संबंध है, जिसके लिए हमें इस आंतरिक उत्पाद की आवश्यकता है। ऊपर दिए गए ठोस विवरण में, द्वैध पर आंतरिक उत्पाद सामान्यतः निहित है।

गुण

हम द्वैध जालक के कुछ प्राथमिक गुणों को सूचीबद्ध करते हैं:

• अगर ${\textstyle B=[b_{1},\ldots ,b_{n}]}$ जालक के लिए आधार देने वाला एक आव्यूह ${\textstyle L}$ है, तब ${\textstyle z\in {\text{span}}(L)}$ ${\textstyle z\in L^{*}\iff b_{i}^{T}z\in \mathbb {Z} ,i=1,\ldots ,n\iff B^{T}z\in \mathbb {Z} ^{n}}$ को संतुष्ट करता है।
• अगर ${\textstyle B}$ जालक के लिए आधार देने वाला एक आव्यूह ${\textstyle L}$ है, तब ${\textstyle B(B^{T}B)^{-1}}$ द्वैध जालक के लिए एक आधार देता है। अगर ${\textstyle L}$ पूर्ण रैंक ${\textstyle B^{-T}}$ है तो द्वैध जालक के लिए एक आधार देता है: ${\textstyle z\in L^{*}\iff B^{T}z\in \mathbb {Z} ^{n}\iff z\in B^{-T}\mathbb {Z} ^{n}}$
• पिछला तथ्य तो यही दर्शाता है ${\textstyle (L^{*})^{*}=L}$। यह समानता एक सदिश स्थल की सामान्य पहचान के अंतर्गत उसके द्वैध के साथ, या उस व्यवस्थापन में होती है जहां आंतरिक उत्पाद की पहचान ${\textstyle \mathbb {R} ^{n}}$ इसके द्वैध के साथ की गई है।
• दो जालक ${\textstyle L,M}$ निर्धारित करें। तब ${\textstyle L\subseteq M}$ अगर और केवल अगर ${\textstyle L^{*}\supseteq M^{*}}$ होता है।
• किसी जालक का निर्धारक उसके द्वैध निर्धारक का व्युत्क्रम होता है: ${\textstyle {\text{det}}(L^{*})={\frac {1}{{\text{det}}(L)}}}$
• अगर ${\textstyle q}$ एक शून्येतर अदिश राशि है तो फिर, ${\textstyle (qL)^{*}={\frac {1}{q}}L^{*}}$.
• अगर ${\textstyle R}$ एक क्रमावर्तन आव्यूह है तो, ${\textstyle (RL)^{*}=RL^{*}}$.
• एक जालक ${\textstyle L}$ यदि ${\textstyle x\cdot y\in \mathbb {Z} }$ है तो वह सभी ${\textstyle x,y\in L}$ के लिए अभिन्न कहा जाता है। मान लीजिए कि जालक ${\textstyle L}$ पूर्ण रैंक है। यूक्लिडियन स्थल की इसके द्वैध के साथ पहचान के अंतर्गत, अभिन्न जालक ${\textstyle L}$ के लिए हमारे पास ${\textstyle L\subseteq L^{*}}$ है। उसे याद करें, यदि ${\textstyle L'\subseteq L}$ और ${\textstyle |L/L'|<\infty }$, तब ${\textstyle {\text{det}}(L')={\text{det}}(L)|L/L'|}$। इससे यह निष्कर्ष निकलता है कि एक अभिन्न जालक के लिए, ${\textstyle {\text{det}}(L)^{2}=|L^{*}/L|}$ है।
• एक पूर्णांकी जालक को एकमापांकी कहा जाता है यदि ${\textstyle L=L^{*}}$, जो, उपरोक्त के अनुसार, ${\textstyle {\text{det}}(L)=1}$ के बराबर है।

उदाहरण

ऊपर सूचीबद्ध गुणों का उपयोग करके, एक जालक के द्वैध की गणना हाथ या कंप्यूटर द्वारा कुशलतापूर्वक की जा सकती है। गणित और कंप्यूटर विज्ञान में महत्व रखने वाली कुछ जालक एक-दूसरे के लिए द्वैध हैं, और हम यहां कुछ को सूचीबद्ध करते हैं।

प्रारंभिक उदाहरण

• ${\textstyle \mathbb {Z} ^{n}}$ का द्वैत ${\textstyle \mathbb {Z} ^{n}}$ है।
• ${\textstyle 2\mathbb {Z} \oplus \mathbb {Z} }$ का द्वैत ${\textstyle {\frac {1}{2}}\mathbb {Z} \oplus \mathbb {Z} }$ है।
• मान लीजिये ${\textstyle L=\{x\in \mathbb {Z} ^{n}:\sum x_{i}=0\mod 2\}}$ पूर्णांक सदिशों की जालक बनें जिनके निर्देशांकों का योग सम हो। तब ${\textstyle L^{*}=\mathbb {Z} ^{n}+({\frac {1}{2}},\ldots ,{\frac {1}{2}})}$, यानी, द्वैध सभी के साथ पूर्णांक सदिश द्वारा उत्पन्न जालक ${\textstyle 1/2}$ s सदिश है।

क्यू-एरी जालक

उदाहरणों का एक महत्वपूर्ण वर्ग, विशेष रूप से जालक कूटलेखन में, क्यू-एरी जालक द्वारा दिया जाता है। एक आव्यूह ${\textstyle A\in \mathbb {F} _{q}^{m\times n}}$ के लिए हम परिभाषित करते हैं ${\textstyle \Delta _{q}(A)=\{x\in \mathbb {Z} ^{n}:x\mod q\in A^{T}\mathbb {F} _{q}^{m}\},\Delta _{q}^{\perp }(A)=\{x\in \mathbb {Z} ^{n}:Ax=0\mod q\}}$; इन्हें क्रमशः छवि और कर्नेल क्यू-एरी जालक ${\textstyle A}$ कहा जाता है। फिर, यूक्लिडियन स्थल को उसके द्वैध के साथ पहचानने के बाद, हमारे पास एक आव्यूह की छवि और कर्नेल क्यू-एरी जालक है ${\textstyle A}$ एक अदिश राशि तक द्वैध होते हैं। विशेष रूप से, ${\textstyle \Delta _{q}(A)^{*}={\frac {1}{q}}\Delta _{q}^{\perp }(A)}$ और ${\textstyle \Delta _{q}^{\perp }(A)^{*}={\frac {1}{q}}\Delta _{q}(A)}$। (प्रमाण एक अभ्यास के रूप में किया जा सकता है।)

स्थानांतरण प्रमेय

प्रत्येक ${\textstyle f\in L^{*}\setminus \{0\}}$ विभाजन ${\textstyle L}$ प्रत्येक पूर्णांक मान के अनुरूप स्तर सम्मुच्चय के अनुसार होता है। ${\textstyle f}$ के छोटे विकल्प उनके बीच अधिक दूरी वाले स्तर सम्मुच्चय तैयार करें; विशेष रूप से, परतों के बीच की दूरी ${\textstyle 1/||f||}$ है। इस तरह से तर्क करते हुए, कोई यह दिखा सकता है कि ${\textstyle L^{*}}$ में छोटे सदिश खोजने से गैर-अतिव्यापी क्षेत्रों के सबसे बड़े आकार पर एक निचली सीमा मिलती है, जिसे ${\textstyle L}$ बिंदुओं के आसपास रखा जा सकता है। सामान्यतः, एक जालक के गुणों को उसके द्वैध गुणों से संबंधित प्रमेयों को स्थानांतरण प्रमेय के रूप में जाना जाता है। इस खंड में हम जटिलता सिद्धांत के कुछ परिणामों के साथ उनमें से कुछ की व्याख्या करेंगे।

हमें कुछ शब्दावली याद आती है: एक जालक ${\textstyle L}$ के लिए , मान लीजिये ${\textstyle \lambda _{i}(L)}$ सबसे छोटी त्रिज्या वाली गेंद को निरूपित करते हैं जिसमें एक सम्मुच्चय ${\textstyle i}$ के रैखिक रूप से स्वतंत्र सदिश ${\textstyle L}$ होता है। उदाहरण के लिए, ${\textstyle \lambda _{1}(L)}$ के सबसे छोटे सदिश की लंबाई ${\textstyle L}$ है। मान लीजिए कि ${\textstyle \mu (L)={\text{max}}_{x\in \mathbb {R} ^{n}}d(x,L)}$, ${\textstyle L}$ की आवरण त्रिज्या को दर्शाता है।

इस चिन्हांकन में, इस खंड के परिचय में उल्लिखित निचली सीमा यह बताती है कि ${\textstyle \mu (L)\geq {\frac {1}{2\lambda _{1}(L^{*})}}}$ होता है।

प्रमेय (बनास्ज़्ज़िक) — For a lattice ${\textstyle L}$:

• $1\leq 2\lambda _{1}(L)\mu (L^{*})\leq n$

  $1\leq \lambda _{i}(L)\lambda _{n-i+1}(L^{*})\leq n$

इस दावे के लिए हमेशा एक कुशलतापूर्वक जांचने योग्य प्रमाण पत्र होता है कि एक जालक में एक छोटा गैर-शून्य सदिश होता है, अर्थात् सदिश ही होता है। बनास्ज़सीक के स्थानांतरण प्रमेय का एक महत्वपूर्ण परिणाम ${\textstyle \lambda _{1}(L)\geq {\frac {1}{\lambda _{n}(L^{*})}}}$ है, जिसका तात्पर्य यह सिद्ध करने के लिए है कि एक जालक में कोई छोटा सदिश नहीं है, कोई छोटे सदिश से युक्त द्वैध जालक के लिए एक आधार दिखा सकता है। इन विचारों का उपयोग करके कोई यह दिखा सकता है कि किसी जालक के सबसे छोटे सदिश को n के एक कारक ( ${\textstyle {\text{GAPSVP}}_{n}}$ समस्या) ${\textstyle {\text{NP}}\cap {\text{coNP}}}$ में अनुमानित किया जा सकता है।

अन्य स्थानांतरण प्रमेय:

• ${\textstyle \lambda _{1}(L)\lambda _{1}(L^{*})\leq n}$ का संबंध मिन्कोव्स्की के प्रमेय से अनुसरण करता है; वह, ${\textstyle \lambda _{1}(L)\leq {\sqrt {n}}({\text{det}}(L)^{1/n})}$, और ${\textstyle \lambda _{1}(L^{*})\leq {\sqrt {n}}({\text{det}}(L^{*})^{1/n})}$ है, जिसके बाद से ${\textstyle {\text{det}}(L)={\frac {1}{{\text{det}}(L^{*})}}}$ दावा अनुसरण करता है।

पॉइसन योग सूत्र

द्वैध जालक का उपयोग सामान्य पॉइसन योग सूत्र के कथन में किया जाता है।

Theorem —  प्रमेय (पॉइसन सारांश) Let ${\textstyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ be a well-behaved function, such as a Schwartz function, and let ${\textstyle {\hat {f}}}$ denote its Fourier transform. Let ${\textstyle L\subseteq \mathbb {R} ^{n}}$ be a full rank lattice. Then:

$\sum _{x\in L}f(x)={\frac {1}{\det(L)}}\sum _{y\in L^{*}}{\hat {f}}(y)$.

अग्रिम पठन

• Ebeling, Wolfgang (2013). "Lattices and Codes". Advanced Lectures in Mathematics. Wiesbaden: Springer Fachmedien Wiesbaden. doi:10.1007/978-3-658-00360-9. ISBN 978-3-658-00359-3. ISSN 0932-7134.