Matematické Fórum

7867088 · 07. 11. 2010 14:44

dobrý den,
toto téma striktně asi nepatří sem, patří spíše do algoritmizace ale tam by zapadlo, navíc je to spíše mat. orientovaný dotaz.
lámu si s hlavou nad složitostí naleznutí všech cyklikcých podgrup konečné grupy s násobením mod n. neexistuje nějaké pravidlo pro řády všech cyklických podgrup nějaké konečné grupy?
uvažoval jsem, že musí projít n čísel a postupně je mocnit dokud nedostane neutrální prvek. ptám se tedy, zda neexistuje rozumný předpoklad nejvyšší možné složitosti pro nalezení všech takových cyklických podgrup. nemuselo by to být exponenciální, ne?
můžete mi prosím poradit? nevím jak přesně určit nejvyšší řád a počet cyk. grup v nějaké grupě. moc by mi to pomohlo

Pavel Brožek · 07. 11. 2010 14:56

Nejvyšší řád bude řád celé grupy, pokud je grupa sama cyklická. Jinak řád podgrupy musí dělit řád grupy (Lagrangeova věta).

Vždyť stačí vzít každý prvek a mocnit ho (to je méně než n^2 násobení, pokud je v grupě n prvků) – to jsi i sám napsal. Určitě nemůže existovat žádná cyklická podgrupa, kterou bych takto nenašel. Tenhle postup má polynomiální složitost, ne?

7867088 · 07. 11. 2010 15:28

↑ BrozekP:já nevím jakou to má složitost, prot se ptám.. nevím jak si došel k tomu, že má méně než n^2 (?)
Tedy, vyložím karty. potřebuji vypočítat složitost (měla by být menší než u běžné faktorizace, řekl bych) u postupu, který jsem umístil v sekci Algoritmy a programování jako "pseudokód", já totiž nemohu pochopit jak se ty složitosti počítají.

Pavel Brožek · 07. 11. 2010 15:40

↑ 7867088:

Mám n prvků, každý budu mocnit maximálně n krát než se dostanu na neutrální prvek. Odtud nejhůře $n^2$ násobení. Dostanu tak n cyklických (ne nutně různých) podgrup. Teď se pokusím z toho dostat pouze ty různé podgrupy. Nejprve si všechny prvky v podgrupách seřadím (dejme tomu složitost nejhůře $n^2$ ). I kdybych měl porovnávat všechny grupy navzájem, zda jsou různé, tak to mám $\frac{n(n-1)}{2}$ porovnání. Při porovnání dvou podgrup porovnávám první prvek z jedné podgrupy s prvním s druhé podgrupy a tak dál (nejvýše $n$ operací). Zjistím tak, jestli jsou to stejné nebo různé podgrupy. Mám tak počet operací nejhůře $n^3$ (to je člen ze součinu $\frac{n(n-1)}{2}\cdot n$ ).

7867088 · 07. 11. 2010 21:03

↑ BrozekP:uvažuji nad tím svým algoritmem. je-li grupa G cyklická pak největší cyklická podgrupa je sama G. Co když není cyklická? je řád cyklických podgrup něčím určen? Když řád grupy G není prvočíslo ale číslo složené, jsou řády cyklických podgrup v multiplikativní konečné grupě G něčím určené?Mají tyto cyklické podgrupy vždy prvočíselný řád?

Pavel Brožek · 07. 11. 2010 22:57

↑ 7867088:

Jak jsem napsal, řád podgrup musí dělit řád grupy – to platí v konečných grupách obecně. (Neplatí však opak, tedy že pokud n dělí řád grupy, pak existuje podgrupa řádu n.) Pokud je řád grupy prvočíslo, pak je to jednoduché, všechny podgrupy jsou triviální. V případě, že je řád grupy složené číslo, nemusí mít cyklické podgrupy nutně prvočíselný řád. Představ si například direktní součin cyklické grupy řádu 4 s libovolnou netriviální grupou.

7867088 · 15. 12. 2010 14:42

znovu oživím téma, v rozkladu grupy na primární grupy jsou všechny bisoučinové činitele disjunktní, je to tak? Jsou všechny tyto činitele nutně abelovské? Řekl bych že ano, protože se jedná o cyklické grupy prvočíselného řádu a ty všechny musí být jednoduché, na druhou stranu žádné jiné jednoduché abelovské grupy než prvočíselného řádu a cyklické neexistují. mně není jasný váš postup, takto najdu akorát řády prvků? možná něco čtu špatně :-( Ale mocněním nezjistím, zda se jedná o cyklickou podgrupu. Možná se mýlím. Já potřebuji program, který mi najde veškeré cyklické a jednoduché podgrupy. Již jsem našel podivný text, nerozuměl jsem mu. Můžete prosím pomoct? Děkuji

Matematické Fórum

#1 07. 11. 2010 14:44

cyklické podgrupy konečné grupy

#2 07. 11. 2010 14:56

Re: cyklické podgrupy konečné grupy

#3 07. 11. 2010 15:28

Re: cyklické podgrupy konečné grupy

#4 07. 11. 2010 15:40

Re: cyklické podgrupy konečné grupy

#5 07. 11. 2010 21:03

Re: cyklické podgrupy konečné grupy

#6 07. 11. 2010 22:57

Re: cyklické podgrupy konečné grupy

#7 15. 12. 2010 14:42

Re: cyklické podgrupy konečné grupy

Zápatí