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

[Azog]

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

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

Пусть даны две группы G и H например. Найти алгоритм выясняющий изоморфны ли данные две группы. Возникает правда вопрос: как заданы данные группы. Известно (в Линдоне Шуппе кажется есть) что есть группы про которые нельзя эффективно установить их нетривиальность (напряг память и что-то такое вспомнилось, впрочем сейчас проверим =) ). Так что к сожалению проблема классификации неабелевых групп таким образом не возможно.

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

Azog писал(а):

Возникает правда вопрос: как заданы данные группы.

Ага. Мне вот тоже интересно: как же они заданы?

А то ведь задать можно по разному. Например, так: "Если континуум-гипотеза верна, то группа состоит из одного элемента, а если нет, то она равна $\mathbb{Z}_2$". С тем, что такое задание не позволяет установить тривиальность группы я, пожалуй, соглашусь

Правда, как из этого следует, что "проблема классификации невозможно", я не понимаю.

P. S. Вообще, как связаны неразрешимость проблемы изоморфизма (формальная постановка которой так и не была дана до сих пор) и классификация? Как вообще одно мешает другому?

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

[Azog]

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

З.Ы.Кстати, уважаемый топикастер а чего Вы хотели услышать в ответ на Ваш вопрос? А то мы тут уже много чего сказали)

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

Azog писал(а):

Ну в том о чем я говорю группы заданы порождающими и соотношениями.

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

[Azog]

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

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

Azog писал(а):

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

Да ради Бога, я же с этим согласился. Но при чём здесь классификация?

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

[Brukvalub]

Взято отсюда: http://www.abitura.com/mathematics/elementy_1.htm
"В 1970-е годы более сотни специалистов по теории групп образовали своеобразный консорциум, целью которого было представить полную классификацию простых конечных групп. Задача была поставлена крайне трудоемкая, и ее решение остается единственным примером использования «поточного метода» и «разделения труда» в чистой математике. Под общим руководством Даниэля Горенштейна проблема была разбита на «пакеты» задач, которые поручили различным группам математиков всего мира. Через десять лет интенсивной работы удалось составить полную классификацию всех простых конечных групп, состоящую из трех бесконечных счетных семейств и 26 так называемых спорадических групп с особыми свойствами. Существование спорадической группы с самым большим порядком, получившей прозвище «монстр», удалось доказать только при помощи компьютера. К счастью, кризис, разразившийся вокруг этой проблемы, можно обсуждать не вникая в детали классификации групп. Не обязательно даже вообще знать, что такое простая конечная группа.

В 1980-е годы случилось нечто не менее интересное, чем сама классификация групп. Сначала произошел внешне позитивный сдвиг: вроде бы удалось найти метод доказательства существования «монстра» без использования компьютера. Было решено объединить усилия различных групп математиков для проведения массированной проработки нащупанного доказательства, но вместо ожидаемого результата было выявлено множество пробелов в ранее принятых доказательствах. Б о льшую часть дыр удалось залатать, но одна оказалась настолько серьезной, что заявления о том, что получена полная классификация простых конечных групп, были в 1990 году признаны преждевременными. Со временем этот пробел был заполнен доказательством Ашбахера и Смита, и опять тогда казалось, что доказательство вполне корректно [3]. Интересно, что из двадцати томов этого окончательного доказательства до сих опубликованы лишь неполные пять, и это спустя четверть века после того, как теорема была «доказана»; подробнее см. [3], [27]. Михаэль Ашбахер, один из самых заинтересованных участников проекта, не исключает, что в один прекрасный день может быть открыта новая простая конечная группа. Если ее характеристики окажутся родственными характеристикам какой-либо из известных групп, это еще не страшно. Однако Ашбахер не исключает и возможности открытия принципиально новой простой конечной группы, и тогда всю работу по их классификации можно начинать заново; см. [4]. Отметим также, что и Жан-Пьер Серр весьма скептически относится к полноте и корректности имеющегося доказательства [24]. "

[Azog]

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

Профессор Снэйп
Даже если бы означенная классификация существовала, приведенные мною рассуждения показали бы ее неэффективности (когда вы будете пытаться использовать ее в конкретном случае - Вы никогда не будете уверены что сможете выяснить что за группа перед Вами) Так что толку с подобной классификации было бы немного. Теперь хотелось бы задать вопрос компетентным людям (из интереса) алгоритм по тому какая именно простая группа перед нами (по описанной классификации)?

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

Azog писал(а):

Даже если бы означенная классификация существовала, приведенные мною рассуждения показали бы ее неэффективности (когда вы будете пытаться использовать ее в конкретном случае - Вы никогда не будете уверены что сможете выяснить что за группа перед Вами)

Приведённые Вами рассуждения показали бы неэффективность классификации именно для этого способа задания. Ну и что?

Вот пример: классифицируем натуральные числа самими натуральными числами (то есть каждое натуральное число $n$ классифицируется самим числом $n$). Пусть $f$ --- произвольная невычислимая функция из $\mathbb{N}$ в $\mathbb{N}$. Тогда нет алгоритма, который бы для каждого $x \in \mathbb{N}$ классифицировал бы объект $f(x)$. О чём это свидетельствует? Да ни о чём!

[Azog]

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

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

Azog писал(а):

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

Ну есть как бы и более простой способ: через таблицу умножения элементов группы:)

[Azog]

Ага, жалко что нереальный

[ИСН]

Не нереальный, а длинный. Делов-то. А тот, можно подумать, короткий? Хе-хе.