द्वैध जालक

For duals of order-theoretic lattices, see Duality (order theory).

जाली (समूह) के सिद्धांत में, दोहरी जाली एक दोहरे वेक्टर स्थान के अनुरूप एक निर्माण है। कुछ मामलों में, एक जाली की दोहरी जाली की ज्यामिति ${\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\subseteq L^{*}}$ अभिन्न जालकों के लिए ${\textstyle 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}$एस वेक्टर.

q-ary जाली

उदाहरणों का एक महत्वपूर्ण वर्ग, विशेष रूप से जाली क्रिप्टोग्राफी में, क्यू-एरी लैटिस द्वारा दिया जाता है। एक मैट्रिक्स के लिए ${\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^{*})}}}$.

Theorem (Banaszczyk) — 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 के एक कारक के भीतर अनुमानित किया जा सकता है (जाली समस्या#GapSVP|${\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 —  Theorem (Poisson Summation) 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.