Сохор Ирина Леонидовна

КОНЕЧНЫЕ ГРУППЫ В КОМПЬЮТЕРНОЙ МАТЕМАТИКЕ

УО "Гомельский государственный университет имени Ф. Скорины"

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

Система компьютерной математики может быть определена как совокупность теоретических, алгоритмических, аппаратных и программных средств, предназначенных для эффективного решения различных видов математических задач. Подобные системы уже давно стали неотъемлемым компонентом научных исследований. Среди известных систем компьютерной математики условно можно выделить семь основных классов [1]:

−       системы для численных расчетов,

−       табличные процессоры,

−       матричные системы,

−       системы для статистических расчетов,

−       системы для специальных расчетов,

−       системы для аналитических расчетов,

−       универсальные системы.

При этом типовая структура современных систем компьютерной математики включает в себя:

−       ядро системы, включающее в себя описание встроенных функций и процедур системы;

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

−       библиотеки различных процедур и функций, а также дополнительные пакеты расширения системы

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

GAP (Groups, Algorithms, Programming − Группы, Алгоритмы, Программирование) − свободно распространяемая на условиях универсальной общественной лицензии GPL (General Public License) открытая, кроссплатформенная система компьютерной математики для вычислительной дискретной алгебры. Последняя версия системы − GAP 4.8.2 (20 февраля 2016) [2].

Система GAP поставляется вместе с исходными текстами, которые написаны на двух языках:

−       ядро системы написано на языке С,

−       библиотека функций − на специальном паскалеподобном языке (язык GAP), который в отличие от Pascal является языком объектно-ориентированным программирования.

Важной особенностью системы GAP является ее расширяемость. Функционал системы может быть расширен как с помощью внешних специализированных пакетов и библиотек, так и посредством самостоятельного описания недостающих компонент на языке GAP. Интересным является тот факт [3], что разработчики программ для данной системы могут оформить свои разработки в виде пакета для GAP и представить их на рассмотрение в Совет GAP. После прохождения процедуры рецензирования и одобрения советом GAP такой пакет включается в приложение к дистрибутиву GAP и распространяется вместе с ним. Процедура рецензирования позволяет приравнивать принятые Советом GAP пакеты к научной публикации, и ссылаться на них наравне с другими источниками.

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

В текущей версии GAP с помощью стандартных функций могут быть заданы следующие группы:

−       некоторые основные виды групп, например, симметрические группы;

−       классические матричные группы;

−       транзитивные группы подстановок степени, не превышающей 30;

−       группы малых порядков (все группы порядка не более 2000, за исключением групп порядка 1024);

−       конечные совершенные группы порядка не более 106 (за исключением 11 порядков);

−       примитивные группы подстановок степеней меньше чем 1000 (для степеней меньше чем 256 − все такие группы);

−       неприводимые разрешимые подгруппы группы GL(n, p) для n>1 и p^n<256;

−       неприводимые максимальные конечные группы целочисленных матриц размерности не более 31.

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

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

Выделим функции для генерации основных видов групп:

−       TrivalGroup([filter]) создает тривиальную группу в категории filter.

−       CyclicGroup([filt,] n) строит циклическую группу порядка n в категории filt.

−       AbelianGroup([filt,] ints) строит абелeву группу в категории filt, имеющую тип изоморфизма Сints[1]*Сints[2]*…*Cints[n]. Ints должно являться списком натуральных чисел. Порождающие элементы возвращаемой группы соответствуют элементам списка ints.

−       ElementaryAbelianGroup([filt,] n) возвращает элементарную абeлeву группу порядка n в категории filt.

 −      DihedralGroup([filt,] n) возвращает группу диэдра порядка n в категории filt (по умолчанию IsPcGroup).

−       ExtraspecialGroup([filt,] order, exp) возвращает экстраспециальную группу в категории filt, которая зависит от параметра exp и имеет порядок order=p^(2n+1), где р – простое число, а n – натуральное.

−       AlternatingGroup([filt,] deg) и AlternatingGroup([filt,] dom) возвращают знакопеременную группу степени deg в категории filt. Во втором варианте возвращается знакопеременная группа, действующая на множестве dom, которое должно состоять из натуральных чисел.

−       SymmetricGroup([filt,] deg) и SymmetricGroup([filt,] dom) возвращают симметрическую группу степени deg в категории filt. Во втором варианте возвращается симметрическая группа, действующая на множестве dom, которое должно состоять из натуральных чисел.

−       MathieuGroup([filt,] degree) конструирует группу Матье степени degree (которая может принимать значения [9, 10, 11, 12, 21, 22, 23, 24]), в категории filt.

−       SuzukiGroup([filt,] q) и Sz( [filt,] q) конструируют группу, изоморфную группе Сузуки Sz(q) над полем из q элементов (где q>=8 и является нечетной степенью 2) в категории filt.

Следующие функции возвращают классические матричные группы:

−       GeneralLinearGroup([filt,] d, q ) / GL([filt,] d, q) возвращают группу, изоморфную полной линейной группе GL(d, q) матриц порядка d над полем из q элементов в категории filt.

−       GeneralLinearGroup(d, Integers) / GL(d, Integers) строят группу целочисленных обратимых матриц порядка d.

−       GeneralLinearGroup( d, Integers mod m ) / GL( d, Integers mod m ) строят полную линейную группу степени d над кольцом классов вычетов Z/mZ.

−       SpecialLinearGroup([filt,] d, q ) / SL([filt,] d, q) строят группу изоморфную специальной линейной группе SL( d, q ), состоящей из матриц порядка d над полем из q элементов, определитель которых является единицей этого поля, в категории filt (по умолчанию  IsMatrixGroup).

−       SpecialLinearGroup(d, Integers) / SL(d, Integers) возвращают группу целочисленных матриц порядка d с определителем 1.

−       SpecialLinearGroup(d, Integers mod m ) / SL(d, Integers mod m ) строят группу матриц порядка d над кольцом Z/mZ с определителем 1 (mod m).

Библиотека групп малых порядко (SmallGroup) в содержит все конечные группы, порядок которых не превышает 2000, за исключением групп порядка 1024. Каждая группа из библиотеки имеет свой номер, обозначающий ее тип изоморфизма. Этот номер имеет вид [n, m], где n − порядок группы, m − ее номер в каталоге групп порядка n. По данному идентификатору группа может быть вызвана из библиотеки с помощью функции SmallGroup, например [4]:

gap> S:=SmallGroup(16,8);

<pc group of size 16 with 4 generators>

Более того, для многих групп возможно определение их типа изоморфизма посредством функции IdGroup. Так, например, группа диэдра порядка 8 может быть получена как группа с номером 3 из библиотеки групп порядка 8:

gap> D:=DihedralGroup(8);

<pc group of size 8 with 3 generators>

gap> IdGroup(D);

[ 8, 3 ]

Для отбора групп из библиотеки используется также функция AllSmallGroups. Первый обязательный аргумент данной функции является − Size, второй – порядок требуемых групп, затем могут следовать другие пары аргументов, при этом в каждой паре первый аргумент − функция для отбора групп, второй − ее требуемое значение для указанной функции отбора. В следующем примере отобраны все неабелевы группы порядка 64, причем результат выполнения последней команды Length указывает на то, что таких групп 256:

gap> l:=AllSmallGroups(Size,64, IsAbelian, false);;

gap> Length(last);

256

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

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

1. Дьяконов, В.П. Компьютерная математика / В.П. Дьяконов // Русский переплет [Электронный ресурс]. – 2016. – Режим доступа: http://www.pereplet.ru. – Дата доступа: 25.02.2016.

2. GAP // GAP − Groups, Algorithms, Programming − a System for Computational Discrete Algebra [Электронный ресурс]. – 2016. – Режим доступа: http://www.gap-system.org. – Дата доступа: 25.02.2016.

3. Коновалов, А.Б. Cистема компьютерной алгебры GAP 4.7 / А.Б. Коновалов // Brief GAP Guidebook in Russian [Электронный ресурс]. – 2015. – Режим доступа: http://www.gap-system.org/ukrgap/gapbook/chap0.html. – Дата доступа: 25.02.2016.

4. Библиотека групп системы GAP // Изучаем алгебру и теорию чисел с системой компьютерной алгебры GAP [Электронный ресурс]. – 2016. – Режим доступа: http://www.gap-system.org/ukrgap/Examples/Groups.htm. – Дата доступа: 25.02.2016.