Ранги симметрической и знакопеременной групп

[Sonic86]

Рангом группы называется минимальное число ее образующих.
Чему равны ранги симметрической и знакопеременной групп?
С одной стороны, в матэнциклопедии написано, что минимальной системой образующих для $S_n$ является $n-1$ транспозиций $(12),(23),...,(n-1 \ n)$, а значит $\operatorname{rk}S_n=n-1$. Кроме того, если $A_n=\langle b_1,...,b_k \rangle$, то поскольку $[S_n:A_n]=2$, то $S_n=\langle b_1,...,b_k, s \rangle$ для произвольного $s\not\in A_n$, а значит $\operatorname{rk}S_n\leqslant \operatorname{rk}A_n+1$, откуда $\operatorname{rk}A_n\geqslant n-2$.
С другой стороны, у меня получается, что $A_5=\langle (123),(345) \rangle$. Действительно, $A_n$ - группа четных подстановок, значит она порождается всевозможными тройками $(ijk)$ (подробнее: $A_n$ -порождается всевозможными произведениями пар четных транспозиций $(ij)(kl)$, но если 2 элемента транспозиций одинаковы, то имеем $(ij)(jk)=(ijk)$, а $(ij)(kl)=(ij)(jk)(jk)(kl)=(ijk)(jkl)$). Также, $(ikj)=(ijk)^2$ и элементы цикла можно циклически сдвигать. Значит $A_n=\langle (ijk): i<j<k\rangle$, в частности $A_5$ порождается $C_5^3=10$-ю тройными циклами.
Теперь вспоминаем, что если $\alpha_{\varphi}(\pi)=\varphi\pi\varphi^{-1}$ - автоморфизм и $\pi=(x_1...x_n)$, то $\alpha_{\varphi}(\pi)=(\varphi(x_1)...\varphi(x_n))$. И тогда $2$ цикла у нас изначально есть: $(123),(345)$, остается породить еще $8$:
$\alpha_{(123)}(345)=(145)$
$\alpha_{(132)}(345)=(245)$
$\alpha_{(345)}(123)=(124)$
$\alpha_{(354)}(123)=(125)$
$\alpha_{(124)}(123)=(243)$
$\alpha_{(125)}(123)=(253)$
$\alpha_{(245)}(345)=(352)$
$\alpha_{(354)}(145)=(134)$
Значит $A_5=\langle (123),(345) \rangle$ и значит $\operatorname{rk}S_5\leqslant 3$.
Где ошибка? И чему все-таки равны ранги $\operatorname{rk}S_n, \operatorname{rk}A_n$?

[AV_77]

Ранги вроде только для коммутативных групп имеют смысл. Там он хотя бы не зависит от системы образующих.
Ну а так и симметрическая и знакопеременная имеют системы из двух образующих.

[ИСН]

Зачем столько букв. Любая $S_n$ порождается парочкой $(12\dots n)$ и $(12)$.

-- Ср, 2013-05-01, 13:24 --

AV_77 в сообщении #718180 писал(а):

и симметрическая и знакопеременная имеют системы из двух образующих.

Да-да, вот я и говорю.

[Sonic86]

AV_77 в сообщении #718180 писал(а):

Ранги вроде только для коммутативных групп имеют смысл.

Вроде у свободных групп тоже ранги есть.

AV_77 в сообщении #718180 писал(а):

Ну а так и симметрическая и знакопеременная имеют системы из двух образующих.

ИСН в сообщении #718181 писал(а):

Зачем столько букв. Любая $S_n$ порождается парочкой $(12\dots n)$ и $(12)$.

Правда что-ли?? пойду проверю. (а букв было столько потому, что я думал, что я ошибся)
Спасибо!

[AV_77]

Для проверки удобнее для симметрической взять систему $(1,2)$ и $(2,3,\ldots,n)$, а для знакопеременной - типа $(1,2,3)$ и $(3,4,\ldots,n)$.

-- Ср май 01, 2013 13:35:17 --

Sonic86 в сообщении #718183 писал(а):

Вроде у свободных групп тоже ранги есть.

Да, для свободных групп ранг тоже смысл имеет. Но опять это связано с тем, что свободная группа полностью определяется указанием ее ранга, то есть ранг - это инвариант группы не зависящий от выбора системы образующих. А для симметрических групп... ну можно ввести, но смысла я не вижу.

[Sonic86]

ИСН в сообщении #718181 писал(а):

Любая $S_n$ порождается парочкой $(12\dots n)$ и $(12)$.

Точно!:
$S_n=\langle (12), (23),...,(n-1 \ n)\rangle$, но
$\alpha_{(12...n)}(12)=(23)$
$\alpha_{(12...n)}(23)=(34)$
... классно!

AV_77 в сообщении #718184 писал(а):

А для симметрических групп... ну можно ввести, но смысла я не вижу.

Я просто не думал, что все так просто. Полезно знать, что если взял достаточно простые элементы, но они порождают все или почти все. Недавно этот факт 2 раза подряд встретился, если бы я о нем знал, я бы меньше времени потратил на вычисления.
И вообще: если хватит 2-х образующих, то я могу простое представление $S_n$ выписать

[VladimirKr]

(Оффтоп)

Цитата:

...Я просто не думал, что все так просто. Полезно знать, что если взял достаточно простые элементы, но они порождают все или почти все...

Две случайно равновероятно выбранные подстановки порождают симметрическую группу с вероятностью 3/4 при $n\rightarrow\infty$ (Теорема Софи Пикар. Цитирую по памяти...)

[Sonic86]

VladimirKr в сообщении #718442 писал(а):

Две случайно равновероятно выбранные подстановки порождают симметрическую группу с вероятностью 3/4 при $n\rightarrow\infty$ (Теорема Софи Пикар. Цитирую по памяти...)

Это очень интересно!
А с какой предельной вероятностью 2 случайно выбранные подстановки, имеющие общий переставляемый элемент, порождают всю симметрическую группу?
Можно попробовать посчитать вероятность того, что 2 случайные перестановки не имеют общих переставляемых элементов...

[AV_77]

Такими задачами столько народу занималось, результатов очень много. Начните, например, с работ Сачкова В.Н.

[apriv]

Sonic86 в сообщении #718447 писал(а):

Это очень интересно!
А с какой предельной вероятностью 2 случайно выбранные подстановки, имеющие общий переставляемый элемент, порождают всю симметрическую группу?

Я думаю, что ровно с той же, что им мешает?

[Sonic86]

AV_77 в сообщении #718472 писал(а):

Такими задачами столько народу занималось, результатов очень много. Начните, например, с работ Сачкова В.Н.

Нагуглил Сачкова, спасибо! Попробую прочесть.

apriv в сообщении #718534 писал(а):

Sonic86 писал(а):

Это очень интересно!
А с какой предельной вероятностью 2 случайно выбранные подстановки, имеющие общий переставляемый элемент, порождают всю симметрическую группу?

Я думаю, что ровно с той же, что им мешает?

А как Вы это посчитали?
На всякий случай уточню вопрос: пусть для любой перестановки $\sigma$ $\mathrm{NFix}(\sigma)=\{j:\sigma(j)\neq j\}$. Какова вероятность $\mathrm{NFix}(\sigma)\cap\mathrm{NFix}(\pi)=\varnothing$?
Смысл вопроса в том, что я хочу исключить из рассмотрения тривиальный случай: ясно, что если $\mathrm{NFix}(\sigma)\cap\mathrm{NFix}(\pi)=\varnothing$, то $\langle \sigma,\pi\rangle=\langle \sigma\rangle\times \langle\pi\rangle\not\cong S_n$. По идее, надо было еще добавить условие $\mathrm{NFix}(\sigma)\cup\mathrm{NFix}(\pi)=\{1,2,...,n\}$, поскольку в противном случае$\langle \sigma,\pi\rangle\leqslant S(\mathrm{NFix}(\sigma)\cup\mathrm{NFix}(\pi))<S_n$.

Я попытался вычислить вероятность первого условия, получилось вот что:
$A=\mathrm{NFix}(\sigma), B=\mathrm{NFix}(\pi)$
$P(A\cap B=\varnothing)=\sum\limits_{k=0}^n\sum\limits_{s=0}^nP(A\cap B=\varnothing||A|=k,|B|=s)P(|A|=k)P(|B|=s)$
$P(|A|=0)$ - число беспорядков, считается через формулу включений-исключений: $P(|A|=0)=n!\sum\limits_{j=0}^n\frac{(-1)^j}{j!}$. Точно так же считается $P(|A|=k)$:
$P(|A|=k)=\frac{n!}{k!}\sum\limits_{j=0}^{n-k}\frac{(-1)^j}{j!}$. Нетрудно видеть, что $P(A\cap B=\varnothing||A|=k,|B|=s)=\frac{C^s_{n-k}}{C_n^s}=[s+k\leqslant n]\frac{(n-k)!(n-s)!}{n!(n-k-s)!}$.
И тогда

$$P(A\cap B=\varnothing)=\frac{1}{n!}\sum\limits_{k=0}^n\sum\limits_{s=0}^n\frac{(n-k)!(n-s)!}{(n-k-s)!k!s!}[k+s\leqslant n]\sum\limits_{j=0}^{n-k}\frac{(-1)^j}{j!}\sum\limits_{i=0}^{n-s}\frac{(-1)^i}{i!}.$$

И как это считать я не представляю совсем. Я выбрал неправильный путь?

upd: Хотя, наверное, эта вероятность просто стремится к нулю. И тогда все понятно.

[apriv]

Sonic86 в сообщении #719870 писал(а):

А как Вы это посчитали?

Две случайные перестановки с вероятностью 1 порождают либо $S_n$, либо $A_n$. Если они обе четные — получается $A_n$, если нет — получается $S_n$. Поэтому в первоначальной задаче ответ $3/4$, и всякие дополнительные условия про общий элемент не имеют значения.

[Sonic86]

apriv в сообщении #719902 писал(а):

и всякие дополнительные условия про общий элемент не имеют значения.

еще бы уметь доказать, почему они не имеют значения.

[AV_77]

Вот это посмотрите http://www.mathnet.ru/links/61d9352c96e ... /tdm45.pdf