चक्रीय समूहों का मौलिक प्रमेय एक चक्रीय समूह के भीतर चक्रीय उपसमूहों के अस्तित्व के बारे में गारंटी प्रदान करता है।

एक परिमित क्षेत्र (finite field) पर बहुपदों के Number Theoretic Transform (NTT) के संदर्भ में, और ZK-STARKs में FRI ऑपरेशन में भी, हमें ऐसे गुणात्मक उपसमूहों (multiplicative subgroups) की आवश्यकता होती है जिनकी कोटि (order - तत्वों की संख्या) दो की घात (power of two) हो। चक्रीय समूहों का मौलिक प्रमेय हमें जल्दी से यह निर्धारित करने में सक्षम बनाता है कि किसी विशेष परिमित क्षेत्र में उस कोटि का गुणात्मक उपसमूह है या नहीं।

हम प्रारंभिक रूप में निम्नलिखित को कवर करेंगे, फिर चक्रीय समूहों के मौलिक प्रमेय पर आएंगे:

1. उपसमूह (Subgroup) की परिभाषा
2. समूह या उपसमूह की कोटि (Order)
3. एक गुणात्मक समूह में एक अवयव (Element) की घातें (Powers)
4. चक्रीय उपसमूह, चक्रीय समूह, और उनके जनक (Generators)

1. उपसमूह की परिभाषा

दिए गए समूह $G$ के लिए, $G$ का एक उपसमुच्चय $H$, $G$ का एक उपसमूह (subgroup) होता है यदि $H$, $G$ में समूह संक्रिया (group operation) के संबंध में एक समूह बनाता है। दूसरे शब्दों में, यदि हम खुद को $H$ के अवयवों तक सीमित रखते हैं लेकिन $G$ की समूह संक्रिया का उपयोग करना जारी रखते हैं, तो एक समूह के सभी मानदंड अभी भी लागू होते हैं। सबसे महत्वपूर्ण बात यह है कि संक्रिया $H$ में संवृत (closed) होनी चाहिए, इसलिए जब भी हम $H$ के दो अवयवों पर संक्रिया लागू करते हैं, तो हमें $H$ का ही एक अन्य अवयव प्राप्त होना चाहिए।

उपसमूहों के उदाहरण

जोड़ (addition) के तहत पूर्णांकों का मॉड्यूलो 8 समुच्चय एक समूह $\mathbb{Z}_8 = (\{0, 1, 2, 3, 4, 5, 6, 7\}, +)$ बनाता है। $H_1=(\{0, 2, 4, 6\}, +)$ और $H_2=(\{0, 4\}, +)$ दोनों $\mathbb{Z}_8$ के उपसमूह हैं। दूसरी ओर, $H_3=(\{0, 2\}, +)$ नहीं है, क्योंकि $(2+2) \not \in H_3$

2. समूह या उपसमूह की कोटि

एक समूह $G$ की कोटि (order), जिसे $|G|$ द्वारा निरूपित किया जाता है, उसके अवयवों की संख्या है। यदि कोई समूह परिमित नहीं है, तो उसकी कोटि को अनंत कहा जाता है।

समूह और उपसमूह की कोटि का उदाहरण

ऊपर दिए गए उदाहरण के समूह $\mathbb{Z}_8$ पर विचार करें। $\mathbb{Z}_8$ की कोटि 8 है, जिसका अर्थ है $|\mathbb{Z}_8| = 8$ (चूंकि समूह में ठीक 8 अवयव हैं)। इसके अलावा, उपसमूह $H = (\{0, 2, 4, 6\}, +)$ की कोटि 4 है (अर्थात $|H| = 4$)।

3. एक गुणात्मक समूह में एक अवयव की घातें

यदि $g \in G$ है, तो अवयव $g$ की घातें, जिसे $\langle g\rangle$ द्वारा निरूपित किया जाता है, समुच्चय $\{g^i: i\in\mathbb{Z}\}$ बनाती हैं। उदाहरण के लिए, गुणा मॉड्यूलो 7 के तहत गैर-शून्य पूर्णांकों के समूह $G =\{1, 2, 3, 4, 5, 6\}$ पर विचार करें। $G$ में अवयव $3$ की घातें इस प्रकार हैं:

चूंकि:

$3^7$ के बारे में क्या?

इस प्रकार, $\langle 3\rangle = \{1, 2, 3, 4, 5, 6\}$। $i>6$ वाले प्रत्येक घात $3^i$ के लिए, परिणाम इस सूची में पहले से मौजूद अवयवों में से एक होगा।

अभ्यास: अवयव $4$ द्वारा उत्पन्न समुच्चय ज्ञात करें।

एक मनमाने अवयव की घातें एक उपसमूह बनाती हैं

मान लीजिए कि $g$, $G$ में एक मनमाना (arbitrary) अवयव है। अवयव $g$ की घातों का समुच्चय एक उपसमूह बनाता है। दूसरे शब्दों में,

$G$ का एक उपसमूह है।

प्रमाण. परिशिष्ट (appendix) देखें

4. चक्रीय उपसमूह, चक्रीय समूह, और उनके जनक

मान लीजिए कि $g$, $G$ में एक मनमाना अवयव है, तो उपसमूह $\langle g\rangle = \{g^i: i\in\mathbb{Z}\}$ को $g$ द्वारा उत्पन्न $G$ का चक्रीय उपसमूह (cyclic subgroup) कहा जाता है। उदाहरण के लिए, गुणा मॉड्यूलो 7 के तहत गैर-शून्य पूर्णांकों के समूह $G =\{1, 2, 3, 4, 5, 6\}$ पर विचार करें। अवयव $2$ द्वारा उत्पन्न चक्रीय उपसमूह है:

अभ्यास: अवयव $6$ द्वारा उत्पन्न उपसमूह ज्ञात करें।

चक्रीय समूह की परिभाषा

मान लीजिए कि $g$, $G$ में एक मनमाना अवयव है। यदि $G = \langle g\rangle$ है, तो हम कहते हैं कि $G$ एक चक्रीय समूह है और $g$, $G$ का एक जनक (generator) है। दूसरे शब्दों में, एक समूह चक्रीय होता है यदि उसमें कम से कम एक ऐसा अवयव हो जो समूह के सभी अवयवों को उत्पन्न करता हो।

चक्रीय समूह और जनकों का उदाहरण

गुणा मॉड्यूलो 7 के तहत गैर-शून्य पूर्णांकों के समूह $G =\{1, 2, 3, 4, 5, 6\}$ पर विचार करें। चूंकि $\langle 3 \rangle = G$, जैसा कि ऊपर दिखाया गया है, इसलिए $G$ एक चक्रीय समूह है और $3$, $G$ का एक जनक है।

ध्यान दें कि $\langle 2 \rangle = \{1, 2, 4\}\neq G$, जिसका अर्थ है कि अवयव $2$, $G$ का जनक नहीं है, बल्कि 2, $G$ का एक उपसमूह उत्पन्न करता है।

अभ्यास: निर्धारित करें कि क्या $5$, $G$ का जनक है

चक्रीय समूहों के जनक जरूरी नहीं कि अद्वितीय हों

चक्रीय समूहों में कम से कम एक जनक होता है, लेकिन जनक का अद्वितीय (unique) होना आवश्यक नहीं है। दूसरे शब्दों में, एक चक्रीय समूह में कई जनक हो सकते हैं, जिनमें से कोई भी पूरे समूह को उत्पन्न कर सकता है। यही बात चक्रीय उपसमूहों के लिए भी सच है।

जैसा कि आपने ऊपर दिए गए उदाहरण और अभ्यास में देखा, अवयव $3$ और $5$ दोनों समूह $G =\{1, 2, 3, 4, 5, 6\}$ के जनक हैं।

एक अन्य उदाहरण के लिए, गुणा मॉड्यूलो 5 के तहत गैर-शून्य पूर्णांकों के समूह पर विचार करें। अर्थात, $\{1, 2 ,3, 4\}$। अवयव $2$ और $3$ पूरे समूह को उत्पन्न करते हैं।

परिमित चक्रीय समूहों का मौलिक प्रमेय

परिमित चक्रीय समूहों का मौलिक प्रमेय तीन दावे करता है। मान लीजिए कि $G$ एक परिमित चक्रीय समूह है, और $H$, $G$ का एक उपसमूह है।

1. $H$ आवश्यक रूप से परिमित और चक्रीय है (जिसका अर्थ है कि $H$ में एक जनक है)।
2. $H$ की कोटि (इसमें मौजूद अवयवों की संख्या) $G$ की कोटि का एक गुणनखंड (factor) है। दूसरे शब्दों में, $H$ की कोटि $G$ की कोटि को विभाजित करती है। उदाहरण के लिए, मान लें कि $G$ की कोटि 6 है। हम स्वतः ही जान जाते हैं कि 5 की कोटि वाला उपसमूह मौजूद नहीं हो सकता, क्योंकि 5, 6 को विभाजित नहीं करता है।
3. यदि $q$, $G$ की कोटि है और $k$, $q$ को विभाजित करता है, तो $k$ आकार का एक उपसमूह अनिवार्य रूप से मौजूद होता है और अद्वितीय (unique) होता है। वास्तव में, हम इसके लिए तुरंत एक जनक पा सकते हैं: यदि $g$, $G$ का एक जनक है, तो $g^\frac{q}{k}$, आकार $k$ के एक उपसमूह के लिए एक जनक है। $k$ आकार का यह उपसमूह $\langle g^\frac{q}{k} \rangle$ के बराबर है। हम शीघ्र ही इसके उदाहरण दिखाएंगे।

Lagrange’s Theorem से संबंध

परिमित चक्रीय समूहों के मौलिक प्रमेय का कथन (2) किसी भी परिमित समूह $G$ के लिए मान्य है, भले ही $G$ चक्रीय न हो। इस सामान्य परिणाम को Lagrange’s Theorem के रूप में जाना जाता है।

संक्षेप के लिए, हम इसे चक्रीय समूहों का मौलिक प्रमेय कहेंगे, इस समझ के साथ कि हम परिमित समूहों से निपट रहे हैं।

चक्रीय समूहों के मौलिक प्रमेय के उपयोग के उदाहरण

आइए हम अपने चक्रीय समूह के रूप में गुणा मॉड्यूलो 7 के तहत $G = \{1,2,3,4,5,6\}$ का उपयोग करें। हम पहले ही दिखा चुके हैं कि $g = 3$ पूरे समूह को उत्पन्न करता है।

कोटि 1 का उपसमूह

चक्रीय समूहों के मौलिक प्रमेय का उपयोग करते हुए, हम जानते हैं कि $G$ में 1 की कोटि का एक उपसमूह है, क्योंकि 1, 6 को विभाजित करता है। अब आइए इस उपसमूह के लिए एक जनक खोजें। चूंकि $k = 1$ है, हमारे पास $3^{\frac{6}{1}} \equiv 1\pmod{7}$ है। तत्समक अवयव (identity element) $1$ स्पष्ट रूप से आकार एक के उपसमूह का जनक है।

कोटि 2 का उपसमूह

अब आइए 2 के आकार का उपसमूह खोजें। हम जानते हैं कि यह मौजूद है क्योंकि 2, 6 को विभाजित करता है। यहाँ, हमारे पास $g = 3$, $q = 6$, और $k = 2$ है। सूत्र में मान रखने पर, हमें $g^{\frac{q}{k}} = 3^{\frac{6}{2}} = 3^3 \equiv 6\mod{7}$ मिलता है। अवयव $6$, अवयवों $\{1, 6\}$ के साथ कोटि 2 का उपसमूह उत्पन्न करता है।

कोटि 3 का उपसमूह

चूंकि 3, 6 को विभाजित करता है, इसलिए 3 की कोटि का एक उपसमूह मौजूद है। इसके अलावा, अवयव $3^{\frac{q}{k}} = 3^{\frac{6}{3}} = 3^{2} \equiv 2\pmod{7}$ इस उपसमूह के लिए एक जनक है, $\langle 2\rangle = \{2^0, 2^1, 2^2\} =\{1, 2, 4\}.$

कोटि 4, 5 का उपसमूह

4 और 5 की कोटि के कोई उपसमूह नहीं हैं क्योंकि ये संख्याएँ 6 को विभाजित नहीं करती हैं।

कोटि 6 का उपसमूह

चूंकि 6, 6 को विभाजित करता है, इसलिए 6 की कोटि का एक उपसमूह मौजूद है। इसके अलावा, $3^{\frac{q}{k}} = 3^{\frac{6}{6}} = 3^{1} = 3$ इस उपसमूह का एक जनक है:

अभ्यास: गुणा मॉड्यूलो 11 के तहत अवयवों $G = \{1,2,3,4,5,6,7,8,9,10\}$ वाले समूह पर विचार करें।

1. इस समूह के लिए एक जनक खोजें।
2. समूह में कोटि 5 का एक उपसमूह है, क्योंकि 5, $G$ की कोटि को विभाजित करता है, जो कि 10 है। इस उपसमूह के लिए एक जनक खोजें और उस उपसमूह की गणना करें जिसे यह उत्पन्न करता है।

एक परिमित क्षेत्र में कोटि $k$ का गुणात्मक उपसमूह

हम एक परिमित क्षेत्र में विशिष्ट कोटि के गुणात्मक उपसमूह खोज सकते हैं। सबसे पहले, आइए परिमित क्षेत्रों (finite fields) की परिभाषा देखें:

परिभाषा के अनुसार, एक क्षेत्र $(\mathbb{F}, + , *)$ में दो एबेलियन (Abelian - बाइनरी ऑपरेटर क्रमविनिमेय होते हैं) समूह होते हैं:

1. योगात्मक समूह (Additive group): $(\mathbb{F}, +)$, जो एक परिमित क्षेत्र में एबेलियन और परिमित होता है।
2. गुणात्मक समूह (Multiplicative group): $(\mathbb{F^*}, *)$ (जहाँ $\mathbb{F}^* = \mathbb{F}\setminus\{0\}$), जो एक परिमित क्षेत्र में एबेलियन और परिमित भी होता है।

ध्यान दें कि $\mathbb{F}_q$, $q$ अवयवों वाले क्षेत्र को दर्शाता है, जबकि $\mathbb{F}^*_q$ ($\mathbb{F}_q$ का गुणात्मक समूह) में $q-1$ अवयव होते हैं।

निम्नलिखित प्रमेय में, हम देखते हैं कि प्रत्येक परिमित क्षेत्र में अनिवार्य रूप से कोटि $q - 1$ ($0$ को छोड़कर) का एक गुणात्मक उपसमूह होता है।

प्रमेय 1: गुणात्मक समूह $\mathbb{F}^*_q$, कोटि $q-1$ का चक्रीय है।

यदि $\mathbb{F}_q$, कोटि $q$ वाला एक परिमित क्षेत्र है, तो इसका गुणात्मक समूह $\mathbb{F}^*_q$, कोटि $q-1$ का चक्रीय है।

कि $\mathbb{F}^*_q$, $q-1$ कोटि का एक समूह बनाता है, यह सीधे परिमित क्षेत्र की परिभाषा से स्पष्ट होता है।

चूंकि गुणात्मक समूह की चक्रीयता (cyclicity) को साबित करना हमें इस लेख के दायरे से बाहर ले जाएगा, इसलिए हम इसे एक दिए गए तथ्य के रूप में लेंगे।

एक चक्रीय समूह का एक जनक होता है, इसलिए हम जानते हैं कि कुछ $g\in \mathbb{F}^*_q$ मौजूद हैं जैसे कि

एक परिमित क्षेत्र में प्रिमिटिव अवयव (जनक)

क्षेत्र सिद्धांत (field theory) में, परिमित क्षेत्र $\mathbb{F}_q$ का प्रिमिटिव अवयव (primitive element) क्षेत्र के गुणात्मक समूह का एक जनक होता है। प्रमेय 1 में अवयव $g$, $\mathbb{F}_q$ में एक प्रिमिटिव अवयव है।

नीचे दिया गया Python कोड $\mathbb{F}_7$ में प्रिमिटिव अवयवों (जनकों) की पहचान करने के लिए galois लाइब्रेरी का उपयोग करता है।

Copy
import galois

GF = galois.GF(7)

primitive_elements = GF.primitive_elements
print("Primitive elements:", primitive_elements)
# Primitive elements: [3 5]

# Alternatively, find a single primitive element
# suitable when there are a lot of primitive elements
primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

अभ्यास: क्षेत्र $\mathbb{F}_{11}$ के गुणात्मक समूह के सभी प्रिमिटिव अवयवों को खोजने के लिए Python का उपयोग करें।

उपप्रमेय 1: कोटि $k$ के उपसमूह के लिए परीक्षण — परिमित क्षेत्र में भाजकों के माध्यम से अस्तित्व

एक उपयोगी उपप्रमेय (corollary) यह है कि हम $q-1$ के सभी भाजकों (divisors) को सूचीबद्ध करके जल्दी से जांच सकते हैं कि एक निश्चित आकार का उपसमूह मौजूद है या नहीं। उदाहरण के लिए, क्षेत्र $\mathbb{F}_{41}$ पर विचार करें, जिसमें 40 की कोटि वाला एक गुणात्मक समूह $\mathbb{F}_{41}^*$ है। हम जल्दी से जांच सकते हैं कि $\mathbb{F}_{41}^*$ में 8 के आकार का एक उपसमूह है क्योंकि 8, 40 को विभाजित करता है।

एक अन्य उदाहरण के रूप में, क्षेत्र $\mathbb{F}_{17}$ पर विचार करें, जिसके गुणात्मक समूह $\mathbb{F}_{17}^*$ की कोटि 16 है। चूंकि 8, 16 को विभाजित करता है, इसलिए $\mathbb{F}_{17}^*$ में 8 के आकार का एक उपसमूह है। इसी तरह, इसमें 4 के आकार का एक उपसमूह है, क्योंकि 4, 16 को विभाजित करता है, और जैसा कि आप अनुमान लगा सकते हैं, $\mathbb{F}_{17}$ में 2 के आकार का एक उपसमूह भी है।

किसी दिए गए आकार के गुणात्मक उपसमूह के लिए जनक खोजने के लिए, हम ऊपर दिए गए मौलिक प्रमेय के कथन (3) का उपयोग कर सकते हैं। $\mathbb{F}_{q}^*$ का आकार $q-1$ है, इसलिए यदि हमारे पास एक प्रिमिटिव अवयव $g$ है और हमें कोटि $k$ का एक गुणात्मक उपसमूह चाहिए, तो हम किसी भी प्रिमिटिव अवयव $g$ के लिए $g^\frac{q-1}{k}$ की गणना कर सकते हैं।

ऑल इन वन उदाहरण

परिमित क्षेत्र $\mathbb{F}_{17} =\{0, 1, 2, \dots, 16\}$ पर विचार करें। दिए गए $k$ के लिए, हम परिमित चक्रीय समूहों के मौलिक प्रमेय का उपयोग करके $\mathbb{F}_{17}$ में कोटि $k$ का एक गुणात्मक उपसमूह खोजना चाहते हैं।

चूंकि गुणात्मक उपसमूह $\mathbb{F}_{17}^*$ की कोटि $q-1=17-1=16$ है, हम चक्रीय समूहों के मौलिक प्रमेय के कथन (2) से जानते हैं कि इसमें कोटि 1, 2, 4, 8 और 16 के उपसमूह हैं, जिनमें से अंतिम समूह स्वयं है।

ये उपसमूह चक्रीय हैं, इसलिए प्रत्येक में कम से कम एक जनक है। प्रमेय के कथन (3) से, हम जानते हैं कि प्रत्येक उपसमूह के लिए एक जनक $g^\frac{q-1}{k}$ द्वारा दिया जाता है, जहाँ $g$ पूर्ण गुणात्मक समूह का एक जनक है और $k$ हमारे वांछित उपसमूह का आकार है।

इसलिए, उपसमूहों को उत्पन्न करने के लिए, पहला कदम $\mathbb{F}_{17}^*$ का एक जनक खोजना है, जो $\mathbb{F}_{17}$ का एक प्रिमिटिव अवयव है।

$\mathbb{F}^*_{17}$ का जनक

प्रमेय 1 से याद करें कि $\mathbb{F}^*_{17}$ एक चक्रीय समूह है। यह दिखाने के लिए कि $\mathbb{F}^*_{17}$ को अवयव $3$ द्वारा उत्पन्न किया जा सकता है, हम $3$ की सभी घातों की गणना इस प्रकार कर सकते हैं:

$3^{17}$ के बारे में क्या?

आप देख सकते हैं कि सभी $i \ge 17$ के लिए, अवयव $3^i$, $3^0, 3^1, 3^2, \dots, 3^{16}$ में से किसी एक के बराबर है। आप यह भी देख सकते हैं कि {1,2,…,16} में हर मान 3 की घातों की सूची में कहीं न कहीं दिखाई देता है। तब, $\langle 3 \rangle = \{1, 2, \dots, 16\} = \mathbb{F}^*_{17}$ है।

यह जनक Python कोड में galois.primitive_elements के साथ पाया जा सकता है।

Copy
import galois

GF = galois.GF(17)

primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

$\mathbb{F}^*_{17}$ में कोटि $k$ का उपसमूह खोजना

मान लीजिए कि हम यह निर्धारित करना चाहते हैं कि परिमित क्षेत्र $\mathbb{F}_q = \mathbb{F}_{17}$ में कोटि $k=4$ का गुणात्मक उपसमूह मौजूद है या नहीं। ध्यान दें कि $\mathbb{F}_q$ के गुणात्मक समूह का आकार $q-1$ होता है। $\mathbb{F}_{17}$ के लिए, गुणात्मक समूह $\mathbb{F}_{17}^*$ में $q-1 = 17-1 = 16$ अवयव हैं।

परिमित चक्रीय समूहों के मौलिक प्रमेय से याद करें कि चूंकि $k$, $q-1$ को विभाजित करता है (स्पष्ट रूप से, $4$, 16 को विभाजित करता है), तो $g^{\frac{q-1}{k}}$ एक जनक है और $\langle g^{\frac{q-1}{k}}\rangle$ आकार 4 का एक उपसमूह है।

इस प्रकार, 13, $\mathbb{F}^*_{17}$ में 4 के आकार के उपसमूह के लिए एक जनक है और

स्पष्ट रूप से, $\{1, 13, 16, 4\}$ उपसमूह है।

अभ्यास: $2$ और $8$ कोटि के गुणात्मक उपसमूहों की गणना करें।

सारांश

• लक्ष्य क्षेत्र $\mathbb{F}_q$ में $k$ आकार के गुणात्मक उपसमूहों को खोजना है।
• यदि $G = \langle g\rangle = \{g^i: i\in\mathbb{Z}\}$ है, तो $G$ एक चक्रीय समूह है, और $g$, $G$ का एक जनक है।
• यदि $\mathbb{F}_q$, कोटि $q$ का एक परिमित क्षेत्र है, तो $(\mathbb{F}^*_q, .)$ कोटि $q-1$ का एक चक्रीय समूह है।
• चक्रीय समूहों का मौलिक प्रमेय बताता है कि परिमित क्षेत्र $\mathbb{F}_q$ में $k$ आकार का एक उपसमूह होता है यदि और केवल यदि $k$, $q-1$ को विभाजित करता है। इसके अलावा, इस उपसमूह का एक जनक $g^{\frac{q-1}{k}}$ है, जहाँ $g$ गुणात्मक समूह $\mathbb{F}^*_q$ का एक जनक है।

परिशिष्ट

हम $\langle g \rangle$ को $G$ का उपसमूह होने के लिए आवश्यक तीन शर्तों की जांच करेंगे।

तत्समक (Identity): चूंकि $1 = g^0$, इसलिए $1 \in \langle g \rangle$ है।

संवृत (Closure): मान लीजिए कि $a, b \in \langle g \rangle$ है। तब हम जानते हैं कि कुछ $n, m$ के लिए $a = g^n$ और $b = g^m$ है। समूह संक्रिया को लागू करने पर यह प्राप्त होता है

चूंकि $n+m\in\mathbb{Z}$, इसलिए $ab\in \langle g \rangle$ है।

प्रतिलोम (Inverse): मान लीजिए कि $a\in \langle g \rangle$ है। तब कुछ $m$ के लिए $a = g^m$ है,

चूंकि $-m\in\mathbb{Z}$, इसलिए $a^{-1} \in \langle g \rangle$ है।

अभ्यास

$\mathbb{F}_{31}$ के गुणात्मक उपसमूहों की सभी कोटियाँ क्या हैं और प्रत्येक उपसमूह के लिए एक जनक क्या है?

$\mathbb{F}_{5}$ के गुणात्मक उपसमूहों की सभी कोटियाँ क्या हैं और प्रत्येक उपसमूह के लिए एक जनक क्या है?

$\mathbb{F}_{51}$ के गुणात्मक उपसमूहों की सभी कोटियाँ क्या हैं और प्रत्येक उपसमूह के लिए एक जनक क्या है?