समूह तत्वों का एक सेट सेट कोसेट प्रतिनिधियों का एक सेट है?

Question

मुझे डर है कि प्रश्न थोड़ा तकनीकी है, लेकिन मुझे उम्मीद है कि कोई भी इसी तरह के विषय में ठोकर खा सकता है, या मुझे किसी प्रकार का सूचक दे ​​सकता है।

तो जी एक समूह (बीजीय संरचना के अर्थ में) है, और अगर जी , ..., जी _n जी के तत्व हैं, वहाँ एक एल्गोरिथ्म (या कुछ समर्पित कार्यक्रम में एक समारोह है , जीएपी की तरह) यह निर्धारित करने के लिए कि क्या जी का उपसमूह है कि वे तत्व उपसमूह के कोसेट्स के लिए प्रतिनिधियों का एक सेट बनाते हैं? (हम मान सकते हैं कि जी एक क्रमपरिवर्तन समूह है, और शायद पूर्ण सममित समूह भी है।)

(निश्चित रूप से टोड-कॉक्सेटर एल्गोरिदम जैसे दिए गए उपसमूहों के कोसेट्स को खोजने के लिए कई एल्गोरिदम हैं; यह एक तरह का है उलटा सवाल का।)

धन्यवाद, डेनियल

Answer 1

एकमात्र समाधान मैं के साथ आ सकते हैं अनुभवहीन है। असल में यदि आपके पास x1,...,xn तत्व हैं, तो आप जीएपी के LowIndexSubgroupsFpGroup का उपयोग इंडेक्स एन के साथ सभी उपसमूहों को गिनने के लिए करेंगे (इंडेक्स < एन वाले लोगों को छोड़कर)। फिर आप प्रत्येक ऐसे समूह से गुज़रेंगे, कोसेट उत्पन्न करेंगे, और जांच लें कि प्रत्येक कोसेट में तत्वों में से एक है।

यह सब मैं सोच सकता हूं। यदि आप बेहतर दृष्टिकोण के साथ आए तो मुझे बहुत दिलचस्पी होगी।

Answer 2

एक थोड़ा कम जानवर दृष्टिकोण सूचकांक n के सभी उपसमूहों की गणना करने में, के रूप में इल-भीम सुझाव हो सकता है, और उसके बाद प्रत्येक उपसमूह के लिए, प्रत्येक x _मैं * x _जे ^-1 अगर यह देखने के लिए जाँच उपसमूह में निहित है।

तत्वों x1, ..., xn एक उपसमूह के लिए प्रतिनिधि होगा तभी हर उत्पाद

एक्स _मैं * x _जे ^-1 जहां (i! = जे)

अगर

उपसमूह में नहीं है।

इस प्रकार का चेक सभी कोसेट उत्पन्न करने और कम्प्यूटेशनल रूप से तेज़ी से दोनों सरल लगता है।

Answer 3

क्या आप यह निर्धारित करने की कोशिश कर रहे यानी अगर वहाँ {छ , ..., जी _n} एच के cosets के transversal है जी के एक उपसमूह एच ऐसी है कि है है का एक सेट एच

पहले, Lagrange's प्रमेय द्वारा जी के विभाजन के प्रतिनिधियों, जी | = | जी: एच | * | जी |, जहां | जी: एच | = | जी |/| एच | जी के उपसमूह एच का सूचकांक है। यदि {जी , ..., जी _एन} वास्तव में एक ट्रांसवर्सेल है, तो | जी: एच | = | {जी , ..., जी _एन} |, इसलिए आपके एल्गोरिदम में पहला परीक्षण होना चाहिए कि क्या एन विभाजित है | जी |

इसके अलावा, जी _{के बाद से मैं} और जी _जे ही सही सह समुच्चय में केवल तभी ग्राम _मैं जी _जे^-1 एच में है, तो आप उपसमूहों सूचकांक n के साथ जांच को देखने के लिए कर सकते हैं अगर वे जी _i जी _जे^-1 से बचें। इसके अलावा, ध्यान दें कि (छ _मैं जी _जे^-1) (छ _जे जी _{कश्मीर}^-1) = ग्राम _मैं जी _{कश्मीर}^-1 है, तो आप चुन सकते हैं जी _i एस की कोई जोड़ी।

यदि एन की तुलना में छोटा है तो यह पर्याप्त होना चाहिए | जी |

एक और दृष्टिकोण एच तुच्छ समूह होने के साथ शुरू करते हैं और सेट एच ^* = {जी में घंटा की तत्वों को जोड़ने के लिए है: ज ^{कश्मीर} = छ _मैं जी _जे^-1, सभी के लिए, जे, के; i! = j} एच के जेनरेटर तक जब तक आप और नहीं जोड़ सकते (यानी जब तक यह अब एक उपसमूह नहीं है)। एच तब जी का अधिकतम उपसमूह है जैसे एच एच ^* का सबसेट है। यदि आप ऐसे सभी एच प्राप्त कर सकते हैं (और उन्हें पर्याप्त बड़ा हो) तो उस उपसमूह को आप उनमें से एक होना चाहिए।

यह दृष्टिकोण बड़े एन के लिए बेहतर काम करेगा।

किसी भी तरह से एक गैर-घातीय-समय दृष्टिकोण स्पष्ट नहीं है।

संपादित करें: मैं बस की चर्चा मिल गया है यह यहाँ बहुत विषय: http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Archives/Mathematics/2009_April_18#Is_a_given_set_of_group_elements_a_set_of_coset_representatives.3F