इकाई के मूलों की लांबिकता

Last updated on Apr 21, 2026

किसी primitive $k$ -th root of unity द्वारा उत्पन्न $k$ -th roots of unity की घातों (powers) का योग या तो शून्य होता है या $k$ होता है। हम इस गुण को orthogonality of roots of unity कहते हैं। हम अगले अध्याय में सीधे इस गुण का उपयोग करेंगे।

हम पहले उदाहरणों के माध्यम से इस गुण को स्पष्ट करते हैं, ताकि पाठक इससे परिचित हो जाएं। फिर हम इसे सामान्य रूप से सिद्ध करेंगे।

Roots of unity की घातों का योग

एक primitive $k$ -th root of unity $\omega$ द्वारा उत्पन्न $k$ -th roots of unity पर विचार करें:

[ 1, \omega, \omega^2, ..., \omega^{k-1} ]

यदि हम elements की इस सूची को लेते हैं और प्रत्येक element को $m$ घात (power) तक बढ़ाते हैं, तो हमें एक और सूची प्राप्त होती है:

[ 1^m, \omega^m, (\omega^2)^m, ..., (\omega^{k-1})^m]

इस अध्याय का लक्ष्य यह दिखाना है कि जब हम इस नई सूची के सभी elements का योग करते हैं तो क्या होता है। दूसरे शब्दों में, हम किसी भी $m$ के लिए नीचे दिए गए योग $s$ के मान की गणना करना चाहते हैं:

s = 1^m + \omega^m + (\omega^2)^m + ... + (\omega^{k-1})^m

$\mathbb{F}_{17}$ में $4$ th roots of unity पर विचार करें (हालांकि primitive $4$ th root of unity वाले किसी भी field में यह काम करेगा)। एक primitive root $\omega$ के लिए, ये roots हैं

[1, \omega^1, \omega^2, \omega^3],

या, इस स्थिति में $\omega^2 \equiv -1$ का उपयोग करते हुए, वे हैं

[ 1, \omega, -1, -\omega ]

आइए इन elements को किसी exponent $m$ तक बढ़ाते हैं, मान लें $m=3$ :

[ 1^3, \omega^3, (-1)^3, (-\omega)^3 ]

हम यह ध्यान देकर इनमें से कुछ elements को सरल बना सकते हैं कि $(-1)^3 = -1$ और $(-\omega)^3 = - \omega^3$ है।

इस प्रकार, उसी सूची को इस प्रकार लिखा जा सकता है

[ 1, \omega^3, -1, -\omega^3 ]

इन elements का योग शून्य है, क्योंकि

1 + \omega^3 + (-1) + (-\omega^3) = 0

एक अन्य उदाहरण के रूप में, आइए फिर से $\mathbb{F}_{17}$ में 4th roots of unity के साथ शुरू करते हैं, लेकिन अब प्रत्येक element को 8 की घात (power) तक बढ़ाते हैं।

इससे निम्नलिखित elements प्राप्त होते हैं:

[ 1^8, \omega^8, (-1)^8, (-\omega)^8 ]

चूँकि $8$ सम (even) है, इसलिए हमारे पास $(-1)^8 = 1$ और $(-\omega)^8 = \omega^8$ है।

साथ ही, याद रखें कि $4$ th roots of unity के लिए, $\omega^4=1$ होता है। इस प्रकार, $\omega^8 = (\omega^4)^2 = 1^2 = 1$ है।

इसलिए, हमारी सूची सरल होकर बनती है

[ 1^8=1, \omega^8=1, 1^8=1, \omega^8=1 ]

Elements का योग है

s=1 + 1+1+1=4

उपरोक्त उदाहरणों में, जब $m$ , $k$ $(k=4,m=3)$ का गुणज (multiple) नहीं है, तो योग शून्य होता है, लेकिन जब $m$ , $k$ ( $k=4,m=8$ ) का गुणज होता है, तो योग $k$ होता है। यह सामान्यतः सत्य है।

हम निम्नलिखित को दिखाएंगे और सिद्ध करेंगे:

यदि घात $m$ , $k$ का गुणज नहीं है, तो योग शून्य होता है।
अन्यथा, यदि $m$ , $k$ का गुणज है, तो योग $k$ होता है।

इस तथ्य को सामान्य रूप से सिद्ध करने से पहले, आइए एक और उदाहरण देखें।

$\mathbb{F}_{17}$ में 8th roots of unity

$\mathbb{F}_{17}$ में $8$ th roots of unity पर विचार करें। उन्हें इस प्रकार लिखा जा सकता है

[ 1, \omega, \omega^2, \omega^3, -1, -\omega, -\omega^2, - \omega^3 ],

जहाँ हमने उपयोग किया है कि एक primitive $8$ th root of unity $\omega$ के लिए $\omega^4 \equiv -1$ होता है।

यदि हम इस सूची के प्रत्येक element को एक ऐसी घात $m$ तक बढ़ाते हैं जो $8$ का गुणज नहीं है और सभी elements का योग करते हैं, तो परिणाम शून्य होता है। अन्यथा, यदि $m$ , $8$ का गुणज है, तो योग $8$ होता है।

नई सूची इस प्रकार दी गई है

[1^m, \omega^m, (\omega^{2})^m, (\omega^3)^m, (-1)^m, (-\omega)^m, (-\omega^{2})^m, (-\omega^3)^m ]

आइए संभावित मामलों की जाँच करें।

Case 1: $m$ , $8$ का गुणज नहीं है

आइए $m=2$ वाले मामले पर विचार करें। सूची है

[ 1^2, \omega^2, (\omega^2)^2, (\omega^3)^2, (-1)^2, (-\omega)^2,(-\omega^2)^2, (-\omega^3)^2 ]

इसे इस प्रकार लिखा जा सकता है

[1, \omega^2, \omega^4, \omega^6, 1, \omega^2, \omega^4, \omega^6 ]

इस तथ्य का उपयोग करते हुए कि $\omega^4 \equiv -1$ है, सूची बन जाती है

[1, \omega^2, -1, -\omega^2, 1, \omega^2, -1, -\omega^2 ]

इन elements को जोड़ने पर, हमें प्राप्त होता है

\begin{aligned} s &= 1 + \omega^2 + (-1) + (-\omega^2) + 1 + \omega^2 + (-1) + (-\omega^2) \\ &= (1 - 1) + (\omega^2 - \omega^2) + (1 - 1) + (\omega^2 - \omega^2) \\ &= 0 \end{aligned}

Exercise: दिखाएं कि $m=3$ और $m=4$ के लिए योग शून्य हो जाता है।

Case 2: $m$ , 8 का गुणज है

आइए उस मामले पर विचार करें जहाँ $m=16$ है। तब हमें नई सूची प्राप्त होती है

[1^{16}, \omega^{16}, (\omega^2)^{16}, (\omega^3)^{16}, (-1)^{16}, (-\omega)^{16}, (-\omega^2)^{16}, (-\omega^3)^{16} ],

या

[1, \omega^{16}, \omega^{32}, \omega^{48}, 1, \omega^{16}, \omega^{32}, \omega^{48} ]

हमारे पास यह भी है कि:

\begin{aligned} \omega^{16} &= (\omega^8)^2 \\ \omega^{32} &= (\omega^8)^4 \\ \omega^{48} &= (\omega^8)^6 \end{aligned}

चूँकि हम जानते हैं कि किसी भी primitive 8th root of unity के लिए $\omega^{8} \equiv 1$ होता है, सूची वास्तव में यह है

[1,1^2,1^4,1^6,1,1^2,1^4,1^6]

और सभी terms का योग $8$ है।

$k$ -th roots of unity की घातों का योग

अब आइए सामान्य रूप से सिद्ध करें जो हमने उदाहरणों के माध्यम से दिखाया है।

Theorem. एक primitive $k$ -th root of unity $\omega$ द्वारा उत्पन्न सभी $k$ -th roots of unity पर विचार करें। इन $k$ -th roots of unity की घातों का योग है:

शून्य यदि घात $k$ का गुणज नहीं है;
$k$ यदि घात $k$ का गुणज है।

नीचे, हम दोनों cases को अलग-अलग सिद्ध करेंगे।

Case (1): यह सिद्ध करना कि जब exponent $k$ का गुणज नहीं होता है तो योग शून्य होता है

$k$ -th roots of unity पर विचार करें, जिनमें से प्रत्येक को एक घात $m$ तक बढ़ाया गया है जो $k$ का गुणज नहीं है:

[ (\omega^0)^m, (\omega^1)^m, (\omega^2)^m, ..., (\omega^{k-1})^m ]

हम योग की गणना करना चाहते हैं

s = (\omega^0)^m + (\omega^1)^m + (\omega^2)^m + ... + (\omega^{k-1})^m

इस योग को इस प्रकार लिखा जा सकता है

s = \sum_{i=0}^{k-1} (\omega^{i})^m

हम इस तथ्य का उपयोग कर सकते हैं कि $(\omega^i)^m = (\omega^m)^i$ है, जिससे योग को फिर से इस प्रकार लिखा जा सकता है

s = \sum_{i=0}^{k-1} (\omega^{m})^i

उपरोक्त सूत्र एक geometric series है, अर्थात, एक ही element की क्रमिक घातों (successive powers) का योग:

s = (\omega^m)^0 + (\omega^m)^1 + (\omega^m)^2 + ... + (\omega^m)^{k-1}

इस रूप की एक geometric series संतुष्ट करती है

s = (\omega^m)^0 + (\omega^m)^1 + (\omega^m)^2 + ... + (\omega^m)^{k-1} = \frac{(\omega^m)^k - 1}{\omega^m -1}

यह सिद्ध करने के लिए कि उपरोक्त भिन्न (fraction) शून्य के बराबर है, हमें पहले यह दिखाना होगा कि हर (denominator) गैर-शून्य (non-zero) है और फिर यह कि अंश (numerator) शून्य के बराबर है।

यह तथ्य कि $m$ , $k$ का गुणज नहीं है, यहाँ महत्वपूर्ण है। एक primitive $k$ -th root of unity की परिभाषा को याद करें: यह एक ऐसा element $\omega$ है जिसके लिए $\omega^k \equiv 1$ होता है, लेकिन किसी भी $0 \leq r <k$ के लिए $\omega^r \neq 1$ होता है।

इस प्रकार, primitive $k$ -th roots of unity $\omega$ के लिए, केवल $\omega^k$ की घातें ही $1$ के बराबर होती हैं, जैसे $(\omega^k)^0, (\omega^k)^1, (\omega^k)^2$ , इत्यादि।

चूँकि $m$ , $k$ का गुणज नहीं है, इसलिए $\omega^m$ किसी भी पूर्णांक $n$ के लिए $\omega^{nk}$ के रूप का नहीं है, और इसलिए $\omega^m \neq 1$ है। इस प्रकार, उपरोक्त भिन्न का हर $\omega^m-1$ गैर-शून्य है।

आइए अब अंश $(\omega^m)^k - 1$ पर विचार करें। इसे $(\omega^k)^m - 1$ के रूप में लिखा जा सकता है।

चूँकि $\omega$ एक primitive $k$ -th root of unity है, हमारे पास $\omega^k = 1$ है, और अंश बन जाता है

\begin{align*} (\omega^k)^m -1 &=(1)^m-1 \\ &= 1 - 1 \\ &= 0 \end{align*}

चूँकि अंश शून्य है और हर गैर-शून्य है, इसलिए पूरा योग शून्य है।

अगले भाग में, हम उस मामले का अध्ययन करेंगे जहाँ exponent $m$ , $k$ का गुणज है।

Case (2): प्रत्येक element को एक ऐसे exponent से बढ़ाना जो $k$ का गुणज हो

इस भाग में, हम दिखाएंगे कि $k$ -th roots of unity का योग, जिसे एक घात $m$ तक बढ़ाया गया है जो $k$ का गुणज है, शून्य नहीं है, बल्कि $k$ है।

$k$ -th roots of unity पर विचार करें

[ \omega^0, \omega^1, \omega^2, ..., \omega^{k-1} ]

आइए इस सूची के प्रत्येक element को किसी घात $m$ तक बढ़ाते हैं:

[ (\omega^0)^m, (\omega^1)^m, (\omega^2)^m, ..., (\omega^{k-1})^m ]

चूँकि $(a^b)^c = (a^c)^b$ है, हम उपरोक्त प्रत्येक term को इस प्रकार पुनर्व्यवस्थित (rearrange) कर सकते हैं:

[ (\omega^m)^0, (\omega^m)^1, (\omega^m)^2, ..., (\omega^m)^{k-1} ]

अब उस मामले पर विचार करें जिसमें $m$ , $k$ का गुणज है, अर्थात किसी $n$ के लिए $m=kn$ है। इस प्रकार, हमारी सूची को इस रूप में लिखा जा सकता है

[ (\omega^{nk})^0, (\omega^{nk})^1, (\omega^{nk})^2, ..., (\omega^{nk})^{k-1} ]

चूँकि $\omega^{nk} = (\omega^k)^n$ है, हमें यह सूची प्राप्त होती है

[ (\omega^{k})^{0n}, (\omega^{k})^{1n}, (\omega^{k})^{2n},..., (\omega^{k})^{(k-1)n}]

$\omega^k \equiv 1$ का उपयोग करते हुए, सूची में संख्या 1 किसी घात तक बढ़ाई गई है:

[ (1)^{0n}, (1)^{1n}, (1)^{2n},..., (1)^{(k-1)n}]

या सीधे शब्दों में

[1,1,1,...,1]

चूँकि सूची में $k$ elements हैं, इसलिए योग है

\underbrace{1 + 1 + 1 + \dots + 1}_{k \text{ times}} = k

दोनों गुणों का संयोजन

दोनों गुणों को व्यक्त करने का एक सुंदर (elegant) और सुविधाजनक तरीका निम्नलिखित है:

\sum_{i=0}^{k-1} (\omega^{i})^{m}=\begin{cases}k, & \text{if } m \text{ is a multiple of } k,\\[6pt]0, & \text{otherwise}.\end{cases}

यहाँ summation पहले term $\omega^0$ से लेकर अंतिम term $\omega^{k-1}$ तक है।

$k$ -th roots of unity की दो सूचियों का inner product

इस भाग में, हम ऊपर प्राप्त अपने संबंध (relation) को एक ऐसे रूप में फिर से लिखेंगे जो अगले अध्यायों में उपयोग के लिए अधिक उपयुक्त है।

अधिक सटीक रूप से, हम इसे इस प्रकार लिखेंगे

\sum_{i=0}^{k-1} (\omega^{i})^{r-s}=\begin{cases}k, & \text{if } r\equiv s \pmod{k},\\[6pt]0, & \text{otherwise}.\end{cases}

सबसे पहले, आइए दिखाएं कि ये दोनों रूप समान हैं, और फिर दूसरे रूप को प्रेरित (motivate) करें।

दोनों रूप समतुल्य (equivalent) हैं

यदि $r$ , $s$ mod $k$ के congruent है (दूसरा रूप), तो किसी पूर्णांक $n$ के लिए $r-s = nk$ होगा।

इस प्रकार, हम यह कह रहे हैं कि $r-s$ , जिसे पहले रूप में $m$ के रूप में लिखा गया है, $k$ का गुणज है। यह $m$ को $k$ का गुणज बताने के समान ही है।

दूसरे रूप में $r$ और $s$ का उपयोग करने का कारण यह है कि हम दो vectors के inner product पर विचार करेंगे, जिनमें से प्रत्येक roots of unity की घातों से बना है।

Roots of unity के दो vectors का inner product

आइए $k$ -th roots of unity के दो vectors पर विचार करें। पहला vector, $A$ , घात $r$ तक बढ़ाया गया है और इसका रूप है

A =[ (\omega^0)^r, \omega^r, (\omega^2)^r, ..., (\omega^{k-1})^r ]

दूसरा vector, $B$ , ऋणात्मक (negative) exponent $-s$ तक बढ़ाया गया है और इसका रूप है

B = [ (\omega^0)^{-s}, \omega^{-s}, (\omega^2)^{-s}, ..., (\omega^{k-1})^{-s} ]

नोट: primitive $k$ -th root of unity को ऋणात्मक घात (negative power) तक बढ़ाना कोई समस्या नहीं है। हम $\omega^{-s} = (\omega^{-1})^s$ लिख सकते हैं, जहाँ $\omega^{-1}$ , $\omega$ का multiplicative inverse है।

चूँकि $\omega^{k} = 1$ है, दोनों पक्षों को $\omega^{-1}$ से गुणा करने पर $\omega^{-1} = \omega^{k-1}$ प्राप्त होता है। दोनों पक्षों को घात $s$ तक बढ़ाने पर, हमें $\omega^{-s} = \omega^{(k-1)s}$ प्राप्त होता है।

Vectors $A$ और $B$ का inner product है

A \cdot B = (\omega^0)^r \cdot (\omega^0)^{-s} + \omega^r \cdot \omega^{-s} + ... + (\omega^{k-1})^r (\omega^{k-1})^{-s}

समान रूप से (Equivalently), इसे इस प्रकार लिखा जा सकता है

A \cdot B = (\omega^0)^{r-s} + \omega^{r-s} + ... + (\omega^{k-1})^{r-s}

एक संक्षिप्त (compact) नोटेशन में, $A$ और $B$ का inner product इस प्रकार लिखा जा सकता है

A \cdot B = \sum_{i=0}^{k-1} (\omega^{i})^{r-s}

इसलिए, यह सूत्र

\sum_{i=0}^{k-1} (\omega^{i})^{r-s}=\begin{cases}k, & \text{if } r\equiv s \pmod{k},\\[6pt]0, & \text{otherwise}.\end{cases}

को इस प्रकार समझा जा सकता है: दो vectors का inner product, जिनकी entries $k$ -th roots of unity की घातें हैं, या तो $k$ होता है या शून्य, जो इस बात पर निर्भर करता है कि exponents $r$ और $s$ modulo $k$ के congruent हैं या नहीं। हम अगले अध्यायों में इस तथ्य का उपयोग करेंगे।

यह लेख हमारी ZK Book में Number Theoretic Transform पर आधारित एक श्रृंखला का हिस्सा है।