Метод вычисления группы Галуа многочлена с рациональными коэффициентами тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Федеральное государственное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный университет'

На правах рукописи

Дуров Николай Валерьевич

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

специальность 01.01.06 — Математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2005 г.

Работа выполнена на кафедре высшей алгебры и теории чисел математико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель: доктор физико-математических наук,

профессор Востоков Сергей Владимирович

Официальные оппоненты: доктор физико-математических наук,

профессор, член-корреспондент РАН Паршин Алексей Николаевич

кандидат физико-математических наук, старший научный сотрудник Лурье Борис Вениаминович

Ведущая организация: Самарский государственный университет

Защита состоится « * ............. 200./г. в часов

на заседании диссертационного совета Д 212.232.29 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 191023, Санкт-Петербург, наб. р. Фонтанки, д. 27, комн. 311 (помещение ПОМИ РАН).

С диссертацией можно ознакомиться в научной библиотеке Санкт-Петербургского государственного университета по адресу: Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан » ........ 2005 г.

Ученый секретарь диссертационного совета Д 212.232.29 доктор физ.-мат. наук, профессор

В. М. Нежинский

Общая характеристика работы

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

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

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

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

ляющих извлекать полезную информацию виафяивмвйвмомрюсти полного опре-

деления группы Галуа.

Методы исследований. Для получения результатов применяется теория этальной фундаментальной группы, развитая в ЭвА 1, теорема плотности Чеботарева, как и в ее первоначальной форме, так и в эффективной форме, принадлежащей Лагариасу, Одлизко, Остерле и Серру, теория дзета- и ¿-функций Артина-Хассе-Вейля, теория классифицирующих топосов конечных и проконеч-ных групп, впервые появившаяся в БОА 4, теория А-колец Хирцебруха-Гротендика, теория представлений и характеров конечных групп, а также хорошо известная теория представлений симметрической группы, появившаяся еще в работах Фро-бениуса.

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

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

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

Апробация работы. Полученные результаты обсуждались на семинарах кафедры высшей алгебры и теории чисел математико-механического факультета СПбГУ (2003-2005), а также докладывались на международной конференции «Algebraic Geometry and Number Theory» (С.-Петербург, 2005).

Публикации. Основные результаты диссертации опубликованы в работах

[1-2].

Структура и объем работы. Диссертация объемом 179 страниц (основной текст — 156 страниц, приложение — 23 страницы) состоит из введения, пяти глав, разбитых на разделы, заключения, приложения и списка литературы, содержат щего 27 наименований.

Содержание диссертации

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

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

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

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

Изложим вкратце основную идею этого метода.

Пусть ^ € <0>[Т] — унитарный сепарабельный многочлен (не обязательно неприводимый) степени п с рациональными коэффициентами. Предположим, нас интересует группа Галуа этого многочлена, рассматриваемая как подгруппа группы подстановок корней, т.е. симметрической группы бп.

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

Итак, предположим, что р регулярно. Тогда редукция -Р^(Т) многочлена Р(Т) по модулю р является сепарабельным многочленом, и мы можем рассмотреть его разложение на неприводимые сомножители: -Рр = Сп • • • • С?г, где все Сг различны. Рассмотрим степени А* этих сомножителей. Можно предполагать, что А* > Аг > • • • > Аг > 0, так что мы получаем разбиение на слагаемые д(р) = А = (А!, Д2) •■•) натурального числа п (разбиение натурального числа п — это невозрастающая последовательность А = (Аг){>1 целых неотрицательных чисел, такая, что п = А<).

Возьмем теперь N различных регулярных простых чисел, вычислим для каждого из них разбиение А^ и положим т\ = тл(Аг) (число простых р, для которых А^ = А}. Что можно сказать о распределении шл и о частотах mь(N)/N при N оо?

Ответ на этот вопрос доставляется следующим вариантом теоремы плотности Чеботарева:

Теорема 1.1. Пусть Г С 6П - группа Галуа многочлена F(T) (для произвольно выбранной нумерации корней). Обозначим через С\ множество подстановок a € бп циклического типа А. Тогда плотность множества простых р, для которых AW = А, равна |Г П Сд|/|Г|, где \Х\ := card*.

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

Определение 1.2. Обозначим для каждой подгруппы Н С 6„ через рн : partn —> [0,1] функцию распределения, определенную формулой рн(Х) •= \Н П С\\/\Н\ (здесь partn — множество всех разбиений на слагаемые натурального числа тг). Мы будем называть такие функции также виртуальными подгруппами группы &п (в третьей главе приводится другое определение виртуальной подгруппы, эквивалентное данному).

Сопряженным подгруппам соответствует одна и та же виртуальная подгруппа 6„; может случиться, что виртуальной подгруппе соответствует более одного класса сопряженных подгрупп. Понятно, что исходя из теоремы плотности Чеботарева мы можем в принципе определить только виртуальную подгруппу рг, соответствующую искомой группе Галуа, поскольку рг(А) = limjv_»+00 m\(N)/N.

Поэтому мы ограничимся задачей нахождения виртуальной подгруппы, соответствующей группе Галуа. Впрочем, транзитивные подгруппы симметрической группы &„ при п < 7 однозначно с точностью до сопряжения определяются сответствующими виртуальными подгруппами. Даже если класс сопряженности подгрупп не определяется однозначно виртуальной подгруппой, из виртуальной подгруппы можно тем не менее извлечь очень много информации об искомой группе Галуа. Например, порядок, индекс, транзитивность и четность подгруппы симметрической группы всегда определяются соответствующей виртуальной подгруппой; в четвертой главе приводятся более подробный список'такого рода свойств, а также даются хорошие необходимые условия для того, чтобы подгруппа была разрешима или содержалась в другой подгруппе, в терминах соответствующих виртуальных подгрупп.

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

как можно меньшее, количество простых чисел ЛГ.

Для того, чтобы сделать его эффективным, предлагается сделать следующее:

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

2) Применять к получающимся данным о распределении циклических типов статистический анализ, позволяющий находить искомую виртуальную подгруппу, соответствующую группе Галуа, с заранее заданным «уровнем достоверности». Этот вопрос обсуждается в пятой главе. Там же обсуждается, каким образом в предположении истинности обобщенной гипотезы Римана оказывается возможным точное определение этой виртуальной подгруппы.

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

Во второй главе приводятся различные формулировки теоремы плотности Чеботарева и показывается, как из стандартной формулировки теоремы плотности Чеботарева для числовых полей выводится нужный для обоснования нашего метода ее вариант (см. формулировку теоремы 1.1 выше).

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

Для рассмотрения различных вариантов теоремы плотности Чеботарева, в особенности ее самого общего геометрического варианта, оказывается очень удоб-

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

Эта глава завершается обсуждением эффективной теоремы плотности Чеботарева, изначально доказанной Лагариасом и Одлизко и затем улучшенной Ос-терле и Серром.

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

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

Приведем здесь основные определения этой теории.

Определение 3.1. Для любой конечной группы О обозначим через В© категорию С-множеств (т.е. множеств с левым действием группы 67), а через Ь<? — полную подкатегорию Вс, образованную конечными С-множествами. Будем называть Во классифицирующим топосом группы (7. Для любого гомоморфизма групп / : О —► Н обозначим через /* функтор, сопоставляющий каждому Н-множеству X соответствующее (7-множество /*Х, полученное из X сужением скаляров вдоль /. Обозначим через /* и /] левый (соотв. правый) сопряженный функтор к /*.

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

Оказывается, что функторы /« и /| всегда существуют и допускают явное описание; значительная часть этого раздела посвящена изучению свойств этих

функторов. Особое внимание уделяется случаям, когда / — вложение или сюръ-ективный гомоморфизм групп.

Рассматриваются также категории абелевых групп В^ в классифицирующих топосах, т.е. категории С?-абелевых групп. Для них можно определить функторы и аналогичные определенным выше; при этом функторы и /*,оЬ «совпадают» с функторами /» и /*, однако вообще говоря, нет.

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

В третьем разделе напоминаются основные понятия теории А-колец. Напомним, что пред-Х-кольцом называется коммутативное кольцо К, на котором определены дополнительные унарные операции («операции вычисления п-ой внешней степени») Ап : К К (п = 0,1,2,...), такие, что А°(х) = 1, А*(х) = х и Ап(х + у) = \*(х)\1(у) для всех х,у € К и п > 0. Обозначим через

С?(К) множество формальных степенных рядов из со свободным членом, равным единице, рассматриваемое как абелева группа относительно умножения; тогда вместо задания операций А" на кольце К, удовлетворяющих приведенным выше условиям, можно задавать гомоморфизм абелевых групп Аг : К —► &(К),

определенный равенством А<(а;) = А"(х)£" = 1 + х£ + А2(х)£2 ----. Конечно

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

Гомоморфизм пред-А-колец / : К —► К' называется А-гомоморфизмом, если /(Ап(х)) = А"(/(х)) для любого х € К и п > 0, иначе говоря, если \к> 0 / = (здесь &(}): &{К) С?(К') — отображение, применяющее / к каждому из коэффициентов степенного ряда; тем самым Сг является функтором из категории коммутативных колец в категорию абелевых групп). Для любого К на абелевой группе С1*(К) можно единственным образом определить умножение о и А-операции А", превращающие (?{К) в пред-А-кольцо, потребовав, чтобы эти операции были функториальными (т.е. перестановочными со всеми £*(/)), и чтобы {1 + ХЬ) о {1+У«} = 1 + ХП в У]), Аи,ад{1 + ХО = {1 + {1+ХЬ}и

-11в Си{С,{К[Х])). Определенные таким образом операции задаются некоторыми универсальными многочленами с целыми коэффициентами.

Наконец, пред-Л-кольцо К называется Х-кольцом, если гомоморфизм абеле> вых групп А4 : К —» С?(К) является А-гомоморфизмом. Практически все возникающие естественным образом пред-А-кольца (например, С?(К)) в действитель-4 ности являются А-кольцами.

Этот раздел завершается описанием некоторых дополнительных операций на пред-А-кольцах. Упомянем симметрические операции в" : К —► К (п > 0), определенные равенствами 5г(х) = Х^п>о зп{х)^п и з^х) • = 1, а также

операции Адамса Ф* : К —► К, определенные при к > 1 (в том случае, если К содержит поле рациональным чисел 12) равенством

(1) |(М*))/ш = £(-1)*-^ ч*)**-1 •

Операции Адамса всегда аддитивны: 9к{х + у) = Ф*(х) + 9к(у). Более того, пред-А-кольцо К является А-кольцом тогда и только тогда, когда

(2) Ф*(1) = 1; 9к{ху) = Ф*(®)Ф*(у); 9* о 9* = 9*" .

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

В четвертом разделе третьей главы изучаются кольца характеров конечных и проконечных групп и устанавливается их связь с группами Гротендика категорий конечномерных представлений групп. Для любой проконечной группы С? мы рассматриваем группу Гротендика К'(С?, С) категории непрерывных конечномерных комплексных представлений группы <3; непрерывность в данном случае означает, что представление р : С? —► Аи^У) пропускается через конечную дискретную факторгруппу группы б. Оказывается, что, как и в случае конечной группы С, К'((3, С) есть свободная абелева группа, порожденная классами изо* морфности неприводимых конечномерных непрерывных комплексных представлений С; этот факт доказывается редукцией к конечной группе С? и последующим переходом к пределу относительно проективной системы конечных дискретных факторгрупп б. Помимо этого, мы рассматриваем кольцо Сеп((3, С) непрерывных центральных комплекснозначных функций на С (непрерывность здесь снова

означает, что мы рассматриваем только те центральные функции, которые пропускаются через конечную дискретную факторгруппу группы G).

Каждому C-G-модулю V (т.е. каждому представлению р : G —* Aut(V)) мы сопоставляем его характер — центральную функцию xv € Cen(G, С), определенную равенством Xv(g) = Trp(g) для любого g € G. Сопоставление V xv аддитивно и потому определяет гомоморфизм абелевых групп хв : К'(G, С) —> Cen(G, С), отображающий clV в xg-

Отметим, что K'(G, С) является коммутативным кольцом с единицей относительно умножения, определенного тензорным произведением представлений: (cl У) • (clW) := cl (У ® W)] единицей в этом кольце является класс одномерного C-G-модуля с тривиальным действием G. Кроме того, на K'(G, С) имеется естественная структура пред-А-кольца, определенная с помощью операции взятия внешней степени представления: A" (cl У) = с1Л"У. Кольцо Cen(G,C) также обладает естественной структурой А-кольца, которую проще всего описать с помощью соответствующих операций Адамса: (Ф*(/))(д) := /(<?*) для любых feCea(G,C),ffeGHk>l.

Оказывается, что отображение хв • K'(G, С) —► Cen(G, С) является инъек-тивным А-гомоморфизмом пред-А-колец (мы доказываем для проконечных групп G этот известный факт с помощью редукции к случаю проциклической группы G = Z, в котором он проверяется непосредственно), откуда, ввиду того, что Cen(G, С) очевидным образом является А-кольцом (см. (2)), немедленно следует, что K'(G, С) также является А-кольцом. Кроме того, это позволяет отождествить K'(G, С) с его образом относительно xg — подкольцом X(G) С Cen(G, С), которое называется кольцом (виртуальных) характеров группы G; элементы этого кольца называются виртуальными характерами группы G.

Пятый раздел посвящен изучению конечных (дискретных) G-множеств и виртуальных подгрупп проконечной группы G. Любому конечному G-множеству X мы сопоставляем следующие объекты: 1) C-G-модуль на котором G действует, переставляя базисные элементы; 2) [X] := с1С^ 6 K'(G, С) — класс этого C-G-модуля в группе Гротендика; 3) Хх '•= Xcw € X(G) С Cen(G, С) — соответствующий характер. Понятно, что Хх{9) = card{:r € X : gx = х}, так что значениями хх являются целые числа в диапазоне от 0 до card X. Упомянем некоторые свойства характеров хх'- ясно, что Хх{е) ~ := cardX. XxuY ~ Xx+XY,

ХххУ = Хх • XV, также верно, что |ЛУ<3| - (хх, Хо) = (1/|<3|) ■ Т,деаХх(д), где Хо — главный характер <3: Хо{д) = 1 для всех д € Для произвольной группы (3 могут существовать неизоморфные конечные (7-множества X и У, такие, что Хх = Ху; мы доказываем, что для случая проциклической группы <3 = 2 такого не может быть.

Далее, для любой конечной группы (3 и любой ее подгруппы Я мы определяем соответствующую виртуальную подгруппу хя := Хв/н £ Х((7) как характер, соответствующий (левому) <3-множеству (3/Я. Легко видеть, что для любого класса сопряженных элементов См С <3 мы имеем Хн{Сц) = (С : Я) • |#ПСМ|/|СМ|, и, в частности, Хя(е) = ((3 : Я). Поэтому задание хя эквивалентно заданию порядка |Я| группы Я и набора чисел \Н П Сц|. Отсюда следует, что хя и соответствующая функция распределения \Н П См|/|Я| полностью определяют друг друга, что оправдывает терминологию первой главы, где виртуальная подгруппа определялась как соответствующая функция распределения.

Пусть (См)м6м — классы сопряженности элементов (3, С/10 = {е}, и пусть (Ха)а6Л — неприводимые характеры (3; мы предполагаем, что О С Л и что хо ~ главный характер (3. Любая виртуальная подгруппа хя полностью определяется набором целых чисел х\ > 0, таких, что хя ~ Еа3^ ' Ха> а также набором значений — целых чисел Хя(С^) > 0; мы полагаем у^ := Хя(См) • |СР|/((3 : Я) = |Я П См| € 2. Эти два набора легко выражаются друг через друга с помощью таблицы характеров группы (3. Кроме того, они удовлетворяют ряду естественных ограничений: например, а;0 = 1, Ущ> = 1, Еа^а = (<3 : Я), = |Я| и т.д. Мы (несколько непоследовательно) называем виртуальной подгруппой любой набор целых чисел (жд), (ум), удовлетворяющих этим условиям, хотя он может и не соответствовать никакой реальной подгруппе Я С О.

Шестой раздел посвящен определению и доказательству основных свойств , т-операций и т-критерия, играющих ключевую роль в диссертации. Для любого конечного ^-множества X и любого целого п > О мы рассматриваем «симметрическую степень» апХ — множество неупорядоченных наборов, составленных из п элементов X, с естественным действием (3. Мы определяем тпХ С апХ как С-подмножество, состоящее из тех наборов, все компоненты которых попарно различны; можно сказать, что тпХ — это множество (*) п-элементных подмножеств в X. Ясно, что С«"*> = ^(С^), откуда х*пх = «п(ху), где в правой части зп

— это п-ая симметрическая операция на А-кольце Х((7) С Сеп(С, С); это означает, что х*"Х легко вычисляется, исходя из хх, поскольку симметрические операции выражаются через операции Адамса, которые задаются на Х(С?) формулой - /(9к)- После этого мы доказываем ключевую комбинаторную лемму: Лемма 3.6.1. Для любого конечного в-множества X и любого п > 0 существует канонический изоморфизм в-множеств зпХ = х тп~2кХ.

Отсюда немедленно следует, что, если определить т-операции тп на А-кольце Х(С?) с помощью равенств ц(х) = 53„>0 тп(х)Ьп и ъ(х) = зг(х)/з^(х) = А_42(ж)/А_!(х), то Хт*х = тп(хх)-

После этого мы формулируем т-критерий:

Предложение 3.6.2. («т-критерий»). Для того, чтобы х € Сеп((7, С) имел вид хх для некоторого конечного (^-множества X, необходимо выполнение следующих условий: 1) коэффициенты разложения х относительно базиса, составленного из неприводимых характеров, являются целыми неотрицательными; 2) значения х(э) также целые неотрицательные; 3) эти два условия выполнены и для всех тпх, п > 0; 4) тпх = тЛ~пх для всех 0 < п < й := х(е)-

Отметим, что виртуальные подгруппы хн — Хв/Н также должны удовлетворять этим условиям; это дает эффективный способ отсечения виртуальных подгрупп, не соответствующих никакой настоящей подгруппе.

Далее в этом разделе приводится необходимое условие для того, чтобы подгруппа и С <7 содержалась в некоторой подгруппе, сопряженной с У с С?, в терминах хи и XV'> это условие также основано на т-критерии.

Четвертая глава посвящена задаче эффективного перечисления виртуальных подгрупп симметрической группы ©„. В первом разделе мы напоминаем основные свойства представлений симметрических групп; отметим, что в этом случае и классы сопряженных элементов С^ С 6„, и неприводимые характеры ха естественным образом параметризуются множеством разбиений Л = М :== раг^. Следующие два раздела описывают три метода, позволяющие построить полный список виртуальных подгрупп 6П (возможно, содержащий лишние элементы, т.е. несущественные виртуальные подгруппы), исходя из уже построенных списков для &к, к < п; затем можно избавиться от большей части несущественных виртуальных подгрупп с помощью т-критерия. Метод (а) основан на том, что любая подгруппа Н С &п-1 является также подгруппой &п> что может быть записано

в терминах виртуальных подгрупп; метод (с) состоит в том, что если Н\ С и Яг С 6„2, то Hi х Яг — подгруппа 6ni+7l2; наконец, метод (Ь) вычисляет все остальные виртуальные подгруппы Я С вп, исходя из рассмотрения всевозмож-, ных разложений <5п/Н в сумму 6„_1-орбит. Четвертый раздел подводит итог изучению виртуальных подгрупп перечислением тех свойств подгрупп, которые ^ могут быть установлены исходя из соответствующих виртуальных подгрупп; при этом приводятся ссылки на соответствующие места диссертации.

Пятая глава посвящена подробностям эффективной реализации предлагаемого метода вычисления группы Галуа. В первых трех разделах изучается задача нахождения набора А^ степеней неприводимых сомножителей многочлена Fp £ FpfT]. Основная идея этих методов заключается в рассмотрении конечномерной Fp-алгебры А := WP[T\/(FP(T)) и ее эндоморфизма Фробениуса РгоЬ^, матрица которого Ф может быть эффективно вычислена. Затем первый метод рассматривает последовательность рангов гапк(Ф* — Е), а второй — последовательность следов Тг Ф*; оказывается, что первые несколько членов любой из этих двух последовательностей полностью определяют разбиение А^.

В четвертом разделе предлагается и обсуждается метод статистического анаг лиза результатов, получаемых при применении предлагаемого метода подсчета циклических типов. Основная идея здесь — сравнение с близкой статистической задачей. Предположим, мы хотим определить значение неизвестной величины 77, принимающей значения в заранее известном конечном множестве Я (в нашем случае Н — список виртуальных подгрупп ©„, а г) — искомая группа Галуа, точнее, соответствующая виртуальная подгруппа). Для этого мы проводим серию экспериментов fb&j ■ • •, в каждом из которых мы измеряем значение некоторой случайной величины распределение которой зависит от 77; мы предполагаем, что £ принимает значения из некоторого конечного множества Е (в нашем случае S = part„, а эксперимент состоит в выборе простого р и вычислении раз-

I)

биения = А^ € partn). Мы предполагаем известными условные вероятности Р(£ = х\г] = h) (в нашем случае они задаются функциями разбиения). После этого задача определения 77 с любой заранее фиксированной вероятностью ошибки е легко решается с помощью формулы Байеса, если предполагать & независимыми; возможен и более тонкий анализ в предположении малости корреляций между Затем обсуждается, что правомочность замены исходной задачи этой стати-

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

В заключении подводится общий итог и перечисляются результаты, выносимые на защиту. В приложении приводятся примеры вычисления группы Галуа с помощью программы, реализующей предложенный метод, и примеры решения некоторых задач теории Галуа (например, определение включения, равенства или линейной разделенности полей разложений многочленов). Показывается, каким образом предложенный метод может использоваться в задачах обратной теории Галуа на (известном) примере многочлена с группой Галуа, равной группе Матье Мц. Кроме того, в приложении приводятся таблицы виртуальных подгрупп симметрических групп &„ при п < 6, вычисленные при помощи методов четвертой главы. На примере этих виртуальных подгрупп демонстрируются возможности т-критерия для определения свойств виртуальных подгрупп.

Работы автора по теме диссертации

[1] Дуров Н.В., Вычисление группы Галуа, многочлена с рациональными коэффициентами I, Зап. яаучн. семин. ПОМИ 319 (2004), 117-198.

[2] Дуров Н.В., Вычисление группы Галуа многочлена с рациональными коэффициентами Л, Зап. научн. семин. ПОМИ 321 (2005), 90-135.

4

t

ж

? I

»24 0 57

РНБ Русский фонд

2006-4 26171

Содержание.

Введение.

Глава 1. Обзор методов вычисления группы Галуа

1.1. Классический метод абсолютной резольвенты.

1.2. Метод относительных резольвент.

1.3. Метод линейных резольвент.

1.4. Метод подсчета циклических типов.

Глава 2. Теорема плотности Чеботарева.

2.1. Этальная фундаментальная группа.

2.2. Теорема плотности Чеботарева

2.3. Обоснование метода.

Глава 3. Подгруппы, G-множества и линейные представления групп.

3.1. Категория G-множеств.

3.2. Категория G-множеств: проконечный случай

3.3. А-кольца.

3.4. Кольцо характеров проконечной группы.

3.5. Виртуальные подгруппы.

3.6. т-операции и т-критерий.

Глава 4. Виртуальные подгруппы симметрической группы

4.1. Характеры симметрической группы

4.2. Поиск виртуальных подгрупп в &п: методы (а) и (с).

4.3. Поиск виртуальных подгрупп в &п\ метод (Ь).

4.4. Свойства виртуальных подгрупп

Глава 5. Эффективная реализация метода.

5.1. Нахождение разбиения А^: общие замечания.

5.2. Метод, основанный на вычислении рангов.

Ф 5.3. Метод, основанный на вычислении следов.

5.4. Статистический анализ результатов.

Задача вычисления группы Галуа конкретного многочлена с рациональными коэффициентами как подгруппы группы подстановок корней многочлена рассматривалась Жорданом еще в 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 (в полученном списке оказалось 11800 виртуальных подгрупп, из них 7213 соответствуют п — 11); при этом для вычисления таблиц при п < 10 потребовалось всего лишь семь минут работы. Поскольку эти таблицы требуется вычислить лишь однажды, нам представляется, что с помощью предлагаемых методов можно вычислить за приемлемое время эти таблицы для п < 12; для больших значений п, по всей видимости, потребуется дальнейшее развитие этих методов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

1. Джеймс Г., Теория представлений симметрических групп, «Мир», М., 1982.

2. Касселс Дж., Фрёлих А., Алгебраическая теория чисел, «Мир», М., 1969.

3. Бурбаки Н., Алгебра. Гл. X. Гомологическая алгебра, «Наука», М., 1987.4. ван дер Варден Б.Л., Алгебра, 2-е изд., «Наука», М., 1979.

4. Дуров Н.В., Вычисление группы Галуа многочлена с рациональными коэффициентами I, Зап. научн. семин. ПОМИ 319 (2004), 117-198.

5. Дуров Н.В., Вычисление группы Галуа многочлена с рациональными коэффициентами II, Зап. научн. семин. ПОМИ 321 (2005), 90-135.

6. Серр Ж.-П., Дзета-функции и L-функции, УМН 20 (1965), 19-26.

7. Серр Ж.-П., Линейные представления конечных групп, «Мир», М., 1970.

8. Serre J.P., Quelques applications du th6oreme de densite de Chebotarev, Publ. Math. IHES, 54 (1981), 123-201.

9. Dieudonne J., Grothendieck A., Elements de Geom€trie Algebrique I: Le language des schemas, Publ. Math. IHES, 4 (1960).

10. Dieudonne J., Grothendieck A., Elements de GeomStrie Algebrique IV: Etude locale des sch6mas et des morphismes de schemas, Publ. Math. IHES, 20 (1964), 24 (1965), 28 (1966), 32 (1967).

11. Grothendieck A. et al., Revetements etales et Groupe Fondamental, Lecture Notes in Math., 224, Springer-Verlag, Heidelberg, 1971.

12. Artin M., Grothendieck A., Verdier J. L. et al., ThSorie des Topos et Cohomologie Etale des Sch6mas, Lecture Notes in Math., 269, 270, 305, Springer-Verlag, Heidelberg, 1972-1973.

13. Berthelot P., Illusie L. et al., ThSorie des Intersections et ThSordme de Riemann-Roch, Lecture Notes in Math., 225, Springer-Verlag, Heidelberg, 1971.

14. Lagarias J.C., Odlyzko A.M., Effective versions of the Chebotarev density theorem // Frolich A. (ed.), Algebraic Number Fields (L-functions and Galois properties), pp. 409-464, Academic Press, 1977.

15. OEsterle J., Versions effectives du theoreme de Chebotarev sous l'hypothese de Riemann g6n6ralis6e, Asterisque, 61 (1979), 165-167.

16. Tschebotareff N., Die Bestimmung der Dichtigkeit einer Menge von Primzahlen, welche zu einer gegebenen Substitutionklasse gehdren, Math. Ann. 95 (1926), 191-228.

17. Jordan С., ТгаИё des substitutions et des 4quations algebriques, Gauthier-Villars, 1870.

18. Hulpke A., Techniques for the Computation of Galois Groups // Algorithmic algebra and number theory (Heidelberg, 1997), pp. 65-77, Springer-Verlag, Berlin, 1999

19. Stauduhar R.P., The determination of Galois groups, Math. Сотр. 27 (1973), 981-996.

20. McKay J., Soicher L.H., Computing Galois groups over the rationale, J. Number Theory 20 (1985), 273-281.

21. Yokoyama K., A modular method for computing the Galois group of polynomials, J. Pure Appl. Algebra 117-118 (1997), 617-636.

22. Geissler К., Kliiners J., Galois group computation for rational polynomials, J. Symb. Сотр. 30 (2000), no. 6, 653-674.

23. Butler G., McKay J., The transitive groups of degree up to eleven, Comm. Alg. 11 (1983), no. 8, 863-911.

24. Conway J., Hulpke A., McKay J., On transitive permutation groups, LMS J. Comput. Math., 1 (1998), 1-8.

25. Darmon H., Ford D., Computational verification of Мц and Mu as Galois groups over Q, Comm. Algebra 17 (1989), 2941-2943.

26. Matzat B.H., Konstruktive Galoistheorie, Lecture Notes in Math., 1284, Springer-Verlag, Heidelberg, 1987.