Метод вычисления группы Галуа многочлена с рациональными коэффициентами

Задача вычисления группы Галуа конкретного многочлена с рациональными коэффициентами как подгруппы группы подстановок корней многочлена рассматривалась Жорданом еще в XIX веке. Предложенный тогда метод «абсолютной резольвенты» решал эту задачу в принципе и позволял доказывать определенные теоретические результаты о группах Галуа многочленов, однако был совершенно непригоден для практического использования. Затем в течение долгого времени эта проблема не привлекала внимания исследователей.

Ситуация изменилась в 70-х годах XX века, когда появление и широкое распространение электронных вычислительных машин сделало возможным практическую реализацию алгоритмов вычисления группы Галуа. Эти алгоритмы используются как и по отдельности (например, для изучения подпо-лей данного простого расширения поля рациональных чисел, для вычисления зависимостей между корнями одного или нескольких неприводимых многочленов, для построения многочленов, обладающих заданной группой Галуа, что представляет собой теоретический интерес в связи с обратной задачей теории Галуа), так и в составе других алгоритмов (например, в системах компьютерной алгебры для упрощения выражений с радикалами и алгебраическими числами или функциями, а также для нахождения решений уравнений в радикалах, что исторически послужило одной из основных причин для создания теории Галуа).

Поскольку классический метод абсолютной резольвенты был совершенно непригоден для практического использования, даже на компьютерах, рядом авторов были предложены новые алгоритмы нахождения группы Галуа. Первым из этих методов был метод относительных резольвент, предложенный в 1973 году в работе [20]- практически все последующие предложенные и реализованные алгоритмы представляют собой либо модификации метода относительных резольвент, либо сочетают его с другими методами — чаще всего с методом линейных резольвент, предложенным в работе [21] уже в 80-х годах. В отличие от метода относительных резольвент, метод линейных резольвент дает только частичную информацию об искомой группе Галуаоднако он более эффективен, и полученная в результате его применения информация позволяет существенно ускорить последующее применение метода относительных резольвент в той или иной его модификации.

Многие авторы отмечают возможность применения теоремы плотности Чеботарева [17] (см., напр., [21] или обзор [19]). Тем не менее обычно обсуждение не выходит за рамки упоминания о том, что теорема плотности Чеботарева обычно позволяет быстро определить, что группа Галуа данного многочлена является симметрической или знакопеременной, и что практическое применение теоремы плотности Чеботарева для получения дальнейшей информации о группе Галуа, к сожалению, крайне неэффективно.

Целью данной диссертации является построение и обоснование некоторого эффективного метода вычисления группы Галуа многочлена с рациональными коэффициентами, основанного на теореме плотности Чеботарева. Такой метод естественным образом носит вероятностный характерв связи с этим будет изучено, каким образом можно добиться того, чтобы вероятность ошибки была меньше любого наперед заданного числа. Впрочем, в предположении истинности обобщенной гипотезы Римана наш метод удается сделать в определенном смысле точным (см. 5.4).

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

Кроме того, мы не хотим ограничиваться рассмотрением неприводимых многочленов (что соответствует рассмотрению только тех групп Галуа, которые являются транзитивными подгруппами симметрической группы (5П), как это делалось до сих пор: несмотря на то, что метод относительных резольвент формально годится для произвольных (сепарабельных) многочленов степени п, как это было отмечено еще в работе [20], его применение для приводимых многочленов требует предварительного знания решетки подгрупп симметрической группы &-п и, как следствие, вычисления большого количества относительных резольвент. В связи с этим существующие реализации ограничиваются случаем неприводимого многочлена (т.е. транзитивных групп подстановок), поскольку классификация транзитивных подгрупп симметрической группы &-п хорошо известна для п < 31.

Хочется подчеркнуть, что задача нахождения группы Галуа приводимого многочлена F представляет самостоятельный интерес и вовсе не сводится, как можно было бы предположить, исключительно к изучению групп Галуа неприводимых сомножителей многочлена F.

Расммотрим следующий пример. Предположим, что F — F1F2 является произведением различных неприводимых многочленов F и F^, и G, G2, G — группы Галуа мночленов Fi, F2 и F соответственно, а К и К2 — поля разложений многочленов F и F2 над полем рациональных чисел Q (рассматриваемые как подполя в Q). Тогда, как несложно видеть, порядок G равен произведению порядков G и G2 в том и только том случае, когда поля К и К2 линейно разделены над Q (и тогда G = G х G2). С другой стороны, порядок G равен порядку Gi в том и только том случае, если К2 содержится в поле К} и знание G как группы подстановок корней позволяет определить гомоморфизм группы Галуа G в группу G2, определенный ограничением на подполе К. Кроме того, отсюда видно, что К = К2 в том и только том случае, если порядки групп G, G и G2 равны.

Приведенный выше пример показывает, что даже знание порядков групп Галуа приводимых многочленов дает много интересной информации о полях разложения многочленов. Отметим, что развиваемый в настоящей диссертации метод позволяет определять как минимум порядок группы Галуа многочленов степени <11 (даже если он оказывается не в состоянии полностью определить искомую группу Галуа) и в то же время очень эффективен, и потому он пригоден для практического решения задач, подобных описанным выше.

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

Оказывается, что для того, чтобы сделать эффективным метод, основанный на теореме плотности Чеботарева, необходимо заранее построить список всех виртуальных подгрупп симметрической группы &-п. В связи с этим существенная часть диссертации посвящена изложению и обоснованию эффективных методов перечисления виртуальных подгрупп симметрической группы. Эти методы были реализованы автором на компьютере, что в результате позволило построить списки всех виртуальных подгрупп <Вп при п < 11, для чего понадобилось 55 часов работы компьютера Pentium-IV (в полученном списке оказалось 11 800 виртуальных подгрупп, из них 7213 соответствуют п — 11) — при этом для вычисления таблиц при п < 10 потребовалось всего лишь семь минут работы. Поскольку эти таблицы требуется вычислить лишь однажды, нам представляется, что с помощью предлагаемых методов можно вычислить за приемлемое время эти таблицы для п < 12- для больших значений п, по всей видимости, потребуется дальнейшее развитие этих методов.

Итак, предлагаемая диссертация содержит:

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

2) Методы эффективного построения таблиц виртуальных подгрупп симметрической подгруппы. Для этого на кольце виртуальных характеров симметрической группы в дополнение к стандартным операциям мы вводим новые «т-операции» и вводим т-критерий, обычно позволяющий быстро отсекать «несущественные» виртуальные подгруппы, т. е. наборы данных, которые не соответствуют никакой «настоящей» подгруппе.

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

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

Кроме того, в приложении приведены таблицы виртуальных подгрупп для п < 6 и примеры вычисления групп Галуа.

В связи с вышеизложенным диссертация построена следующим образом.

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

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

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

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

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

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

Приложение содержит примеры вычисления группы Галуа, а также таблицы виртуальных подгрупп &-п при п < 6, вычисленные методами, изложенными в основном тексте.

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

Основные результаты, излагаемые в настоящей диссертации, опубликованы автором в работах [5] и [6].

Заключение

.

Подведем общий итог.

На основе теоремы плотности Чеботарева возможно построение эффективного метода вычисления группы Галуа многочлена с рациональными коэффициентами как подгруппы (точнее, соответствующей «виртуальной подгруппы») симметрической группы ©-п.

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

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

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

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

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

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

Предложенный метод позволяет вычислять количество (но не длины) орбит относительно действия группы Галуа многочлена F (T) на различных ©-&bdquo—множествах, например, на упорядоченных или неупорядоченных наборах, составленных из г различных корней многочлена F (T). Поскольку это представляет собой большую часть информации, обычно извлекаемой из метода линейных резольвент, а наш метод предоставляет и много другой информации о группе Галуа, представляется целесообразным его использование вместо метода линейных резольвент как и для получения частичной информации о группе Галуа, так и перед применением алгоритмов полного определения группы Галуа, основанных на методе относительных резольвент, для сокращения необходимого объема вычислений.