Количество групп порядка n

[Trotil]

Существует ли явная формула $f(n)$ - число групп порядка $n$ (с точностью до изоморфизма)

$f(1)=1$
$f(2)=1$
$f(3)=1$
$f(4)=2$
$f(5)=1$

Начиная с $n=6$ появляются неабелевы группы...

$f(6)=2$ (?)

[ИСН]

Не то что явной формулы нет, а, по-моему, довольно близко (первые тысячи) начинаются такие $n$, для которых мы даже и не знаем, сколько таких групп.

[Trotil]

Нашел у Слоэна такую последовательность.

Она носит замечательный номер: 000001
http://www.research.att.com/~njas/sequences/A000001

[Azog]

Ну абелевы группы понятное дело можно посчитать.. С неабелевыми группами проблема в том, что нет никакой разумной их классификации. Думаю, что например можно посчитать количество разрешимых групп или другие частные случаи.. Но в общем случае задача скорее всего неподъемная..

[Профессор Снэйп]

Azog писал(а):

С неабелевыми группами проблема в том, что нет никакой разумной их классификации.

Да вроде есть. Классификация всех конечных групп. Правда, сам я не спец, и в чём она заключается не знаю.

[Azog]

Мне об этом ничего не известно. Откуда у Вас такая информация? Дайте почитать =)

[Профессор Снэйп]

Azog писал(а):

Мне об этом ничего не известно. Откуда у Вас такая информация? Дайте почитать =)

От специалистов по теории групп слышал краем уха. Знал бы больше --- сказал бы что-нибудь более определённое.

[Brukvalub]

Например, об этом во введении к своему учебнику пишет Э.Б. Винберг.

[Руст]

Профессор Снэйп писал(а):

Да вроде есть. Классификация всех конечных групп. Правда, сам я не спец, и в чём она заключается не знаю.

Насколько я в курсе, проблема алгоритмический неразрешима, потому не существует классификации. Может вы путаете с классификацией всех конечных простых групп. Тут задача вроде решена. Но нет ни одного специалиста, который в курсе всех работ приведших к классификации (объём порядка 10 000 страниц). Группа специалистов собрались написать 10 томов по 1000 страниц с полной их классификацией. Выпустили несколько томов. Потом некоторые умерли, некоторые бросили это занятие. Так и осталось не написанным полный труд с классификацией всех конечных простых групп.
Даже группы порядка $p^n$ с простым p полностью не классифицированы. Я встречал не так давние труды о классификации для n=6 и n=7.

[Профессор Снэйп]

Вот классификация простых групп. Случай произвольной группы вроде бы сводится к случаю простой.

Добавлено спустя 2 минуты 53 секунды:

Руст писал(а):

Насколько я в курсе, проблема алгоритмический неразрешима, потому не существует классификации.

Ну да, я вероятно с простыми перепутал...

Неразрешима, насколько я знаю, проблема равенства слов в группах, заданных конечным списком порождающих и определяющих соотношений. В принципе, это может и не препятствовать классификации. Мало ли как она там может быть устроена?

[tolstopuz]

Профессор Снэйп писал(а):

Вот классификация простых групп. Случай произвольной группы вроде бы сводится к случаю простой.

Не то чтобы сводится, но в общем и целом эта задача вроде как решена, то есть существуют алгоритмы, дающие полный список групп данного порядка. Основная вычислительная проблема - выкинуть изоморфные дубликаты.

Вот статья:
http://www-public.tu-bs.de:8080/~hubesche/pr2000.ps

Добавлено спустя 1 минуту 41 секунду:

Руст писал(а):

Даже группы порядка $p^n$ с простым p полностью не классифицированы. Я встречал не так давние труды о классификации для n=6 и n=7.

Уже осилили для n=10. Их там почти 50 миллиардов штук.

[Профессор Снэйп]

tolstopuz писал(а):

Не то чтобы сводится, но в общем и целом эта задача вроде как решена, то есть существуют алгоритмы, дающие полный список групп данного порядка. Основная вычислительная проблема - выкинуть изоморфные дубликаты.

Существование алгоритма как раз ни о чём не говорит. Алгоритм может быть и полнопереборным

Или там какие-то эффективные в плане скорости алгоритмы есть?

[Azog]

Brukvalub писал(а):

Например, об этом во введении к своему учебнику пишет Э.Б. Винберг.

Не поленился - прочитал. Не нашел. Нельзя поподробнее..

Профессор Снэйп писал(а):

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

И как же?

Профессор Снэйп писал(а):

Неразрешима, насколько я знаю, проблема равенства слов в группах, заданных конечным списком порождающих и определяющих соотношений. В принципе, это может и не препятствовать классификации. Мало ли как она там может быть устроена?

Да, не разрешима.. Как я понимаю, отсюда можно вывести что неразрешима проблема изоморфности двух групп..

И вообще, что мы в данном случае понимаем под классификацией? Чем порядок группы не классификация =)

[tolstopuz]

Профессор Снэйп писал(а):

Или там какие-то эффективные в плане скорости алгоритмы есть?

Да, про это есть в разделе 3 статьи.

Azog писал(а):

И вообще, что мы в данном случае понимаем под классификацией? Чем порядок группы не классификация =)

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

Azog писал(а):

Как я понимаю, отсюда можно вывести что неразрешима проблема изоморфности двух групп..

Проблема изоморфизма конечных групп алгоритмически разрешима очевидным образом - перебором всех перестановок элементов и поклеточной сверкой получившихся таблиц умножения

[Профессор Снэйп]

Azog писал(а):

Профессор Снэйп писал(а):

Неразрешима, насколько я знаю, проблема равенства слов в группах, заданных конечным списком порождающих и определяющих соотношений. В принципе, это может и не препятствовать классификации. Мало ли как она там может быть устроена?

Да, не разрешима.. Как я понимаю, отсюда можно вывести что неразрешима проблема изоморфности двух групп..

Это всё для бесконечных групп. А для конечных всё не так.

Если конечная группа задаётся через конечную систему порождающих и произвольную (даже алгоритмически не распознаваемую) систему определяющих соотношений, то проблема равенства слов для этой группы разрешима. Впрочем, в этом случае систему определяющих соотношений можно всегда сделать разрешимой и даже конечной (просто задать таблицу умножения группы и всё )

Подумайте чуть-чуть и поймёте, что сказанное очевидно.

А что Вы понимаете под "проблемой изоморфизма групп". Дайте точные формулировки!!!

Добавлено спустя 4 минуты 7 секунд:

Azog писал(а):

Профессор Снэйп писал(а):

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

И как же?

Не знаю. Ляпнул, не подумав.

Azog писал(а):

И вообще, что мы в данном случае понимаем под классификацией? Чем порядок группы не классификация =)

Под "классификацией" скорее всего понимается классификация типов изоморфизма. Порядок группы тип изоморфизма не задаёт