Компьютерная алгебра в задачах

Министерство образования и науки Российской Федерации


Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский педагогический государственный университет»


И. А. Шилин






                КОМПЬЮТЕРНАЯ АЛГЕБРА
                В ЗАДАЧАХ




Учебное пособие

















МПГУ
Москва • 2018

УДК 512.6(076.1)
ББК 22.14-4
      Ш 578




Рецензенты:
А. В. Царев, доктор физико-математических наук (кафедра алгебры МПГУ);
А. А. Туганбаев, доктор физико-математических наук, профессор (кафедра высшей математики НИУ «МЭИ»)








      Шилин, Илья Анатольевич.
Ш578 Компьютерная алгебра в задачах : учебное пособие / И. А. Шилин.
      - Москва : МПГУ, 2018. - 56 с.


            ISBN 978-5-4263-0664-6


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

УДК 512.6(076.1)
ББК 22.14-4







ISBN 978-5-4263-0664-6

(О МПГУ, 2018
(О Шилин И. А., текст, 2018

Содержание


   ВВЕДЕНИЕ .................................... 4
   1. Вычисление образующих элементов мультипликативной группы поля вычетов и индексов по ним ... 7
   2. Вычисление коэффициентов унитарного комплексного многочлена по его корням, являющимися целыми гауссовыми числами ......................... 12
   3. Вычисление числа транзитивных отношений . 15
   4. Вложение конечной группы в группу преобразований этой группы .............................. 22
   5. Вычисление подгрупп и выделение нормальных делителей конечной группы .................. 30
   6. Вычисление централизаторов и нормализаторов подгрупп конечных неабелевых групп ....... 34
   7. Представление подстановки в виде композиции транспозиций ............................... 39
   8. Вычисление групп гомоморфизмов конечных групп . 43
   9. Вычисление групп автоморфизмов и внутренних автоморфизмов конечных групп ............... 47
   10. Решение линейного дифференциального уравнения второго порядка с постоянными коэффициентами . . 52


3

                ВВЕДЕНИЕ





   Компьютерная алгебра — это учебная дисциплина, призванная продемонстрировать и научить, как с помощью компьютеров можно решать математические задачи, относящиеся к общей алгебре. Под словом «решать» здесь следует понимать «решать точно», поскольку, например, задачу о вычислении корня полинома, принадлежащего заданному отрезку, на концах которого полином принимает значения разных знаков, относят к другой дисциплине — «Численным методам», где как раз достаточно найти приближенное решение с заданной точностью.
   Эта небольшая книга написана автором в том же духе, в каком написаны подавляющее число толстых книг по компьютерным наукам: отсутствует методически выверенное последовательное изложение от самых азов до сложных изысканностей и вместо этого читателю предлагается изучать дисциплину через разобранные в книге примеры, то есть, по сути, девизом книги является название некогда популярной телепередачи «Делай с нами, делай как мы, делай лучше нас».
   Почти все рассмотренные в книге задачи относятся к теории групп. В наше время существует немало вычислительных пакетов, с помощью которых можно найти точные решения теоретико-групповых задач. Наряду с обычными (Maple, Mathematica, MathCad, REDUCE, Derive, MATLAB) существуют специализированные вычислительные пакеты, целиком предназначенные именно для этой цели: свободно распространяемые GAP, Sage, FGB и коммерческие CAYLEY и Magma, созданные в Университете Сиднея¹. Однако в этой книге, возможно, наперекор духу времени, под решением задач с помощью компьютера подразумевается их решение с помощью программирования, а не использования уже готовых пакетов. Изучению возможностей пакетов компьютерной алгебры должен, по всей видимости, быть посвещен отдельный курс, итогом которого должно быть, например, знание команды NormalSubgroups в GAP, которая выводит на экран список всех нормальных делителей заданной группы. Пользуясь пакетом GAP, с помощью всего лишь одной командной строки

   gap> NormalSubgroups(SymmetriGroup(4));
удается вывести на экран все нормальные делители симметрической группы S4:

   [Group(()), Group([(1,4)(2, 3),(1,3)(2,4)]),

  ¹ Автору довелось побывать в Лаборатории компьютерной алгебры Университета Сиднея, которую возглавляет создатель CAYLEY и Magma Джон Кэннон.

4

   Group([(2,4,3),(1,4)(2, 3),(1,3)(2,4)]), Sym([1..4])],


то есть подгруппы {id}, K, A4 и S4, где K — так называемая подгруппа Клейна, состоящая из подстановок id, (1 2)(3 4), (1 3)(2 4) и (1 4)(2 3) и изоморфная группе Z₂² . Но такой способ использования компьютера непригоден для нашего курса, цель которого научить мыслить алгоритмически при решении алгебраических задач, переводить задачу с языка математики на язык программных кодов и результаты программы обратно на математический язык.

   При решении алгебраических задач с помощью программирования на первый план выступает задача реализации исследуемого математического объекта в программном коде. Подобный прием мы встречаем и в самой математике, например:
   а)    множество C реализуется как плоскость П = R2 посредством взаимно однозначного отображения z -—( (re z, im z);
   б)    расширенная комплексная плоскость C реализуется как сфера Римана S : Z2 + v² + Z2 = Z: совместив плоскость Z = 0 с П так, что ось Z = 0 совпадает с осью у = 0 и ось v = 0 — с осью x = 0, используем взаимно однозначное отображение


a + bi

।—м

           a            b        a² + b²
a² + Ь2 + 1, а² + Ь2 + 1, а² + Ь2 + 1

ж ।—м (0,0,1);


   в)    скалярное v • w и векторное v х w произведение векторов v = (x1 , x2 , x3 ) и w = (y1 , y2 , y3 ) реализуется как произведение чисто мнимых кватернионов h1 = x1i + x2j + x3k и h2 = y1i + y2j + y3k, а именно

h1h2 = —v • w + (v х w) • h,

где под h подразумевается символический вектор (i, j, k);
   г)    группа G реализутся в некотором линейном пространстве L в виде подгруппы мультипликативной группы невырожденных линейных операторов этого пространства посредством гомоморфизма G —g GL(L), а для конечной группы G, стало быть, в виде подгруппы мультипликативной группы невырожденных матриц (над соответствующем полем Ф) посредством гомоморфизма G —м Mat(dim L, Ф). Такую реализацию называют представлением группы G. Например, группа Sₙ реализутся в виде подгруппы в Mat(n, Z2) посредством гомоморфизма T : о -—м т(о), где т(о) = б[1,о(1)] + ... + e[n,ₒ(n)] и под e[s,ₜ] понимается матрица (aij) над


5

полем Z2 , матричные элементы которой определены правилом


= 0₁,,

если s = i или t = j , если s = i и t = j ;


   д)   подмножество A непустого множества B реализуется как характеристическая функция (индикатор) xa : B —{ {0,1}, где

I

XA⁽x⁾ =

если x / A, если x G A

(обобщая эту реализацию, Заде определил в 1965 году нечеткое подмножество в B как отображение ф : B —[ [0; 1]).
   Если множество B конечно, а именно, B ={b1 , . . . , bₙ}, то, выписывая друг за другом значения характеристической функции xA , получаем двоичное число c1c₂ ... cn, где ci = XA(bi). Мы будем использовать этот прием, то есть реализовывать подмножества множества B в виде целых двоичных чисел от 0 (пустое подмножество) до 2ⁿ - 1 (само B), на протяжении всей книги. Аналогичную реализацию будем применять для отображений B —D D, где D состоит из m элементов: в кодах программ эти отображения будут заменяться целыми числами в m-ичной системе счисления, записанными с помощью n цифр (разрядов).
   К каждой из разобранных задач в качестве примера приведен программный код на языке PASCAL.

6

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





   Напомним, что факторкольцо кольца Z по идеалу nZ, состоящему из чисел, делящихся на п, состоит из элементов 0,1,... ,п, являющихся в кольце Z классами чисел с равными остатками, получающимися при делении на п. Это кольцо обозначается Zₙ и называется кольцом вычетов по модулю п. Элемент а обратим в том и только том случае, если НОД(а,п) = 1. Обратимые элементы образуют группу относительно умножения — ее называют мультипликативной группой кольца Zₙ . Будем обозначать ее Inv Zₙ . Понятно, что в случае простого п все не равные нулю элементы кольца обратимы и Zₙ является полем. Более того, можно доказать, что в случае простого п группа InvZn = {1,... ,n — 1} циклическая. Как известно, число образующих элементов циклической группы порядка k равно Ф(к), где Ф — функция Эйлера, поэтому число образующих элементов мультипликативной группы поля вычетов вычисляется по формуле Ф(Ф(п)) = Ф(п — 1).
   Пусть а — один из таких образующих элементов. Тогда группу Inv Zn можно представить в виде

Inv Zn = (a) = {a, a²,..., an-2, an-¹ = 1}.

Например, в циклической мультипликативной группе Inv Z₁7        =
{1,2,..., 16} поля Z17 элемент 3 является образующим, поскольку

31 = 3  35 = 5  39 = 14 013 = 12
                          3     
32 = 9  36 = 15 310 =8  314 = 2 
33 = 10 37 = 11 311 =7  315 = 6 
34 = 13 38 = 16 312 = 4 316 = 1 

   Напомним, что если элемент g циклической группы порядка k является образующим элементом, то элемент gs тоже является образующим элементом в том и только том случае, когда НОД($, k) = 1. Так, в приведенном примере числа 3, 5, 7, 9, 11, 13, 15 взаимно просты с 16 и, следовательно, элементы

33 = 10, 35 = 5, 37 = 11, 39 = 14,
3¹¹ = 7, 313 = 12, 315 = 6


7

группы Inv Z17, то есть элементы 5, 6, 7, 10, 11, 12, 14 тоже являются образующими элементами.
   Пусть a — образующий элемент группы InvZn (n — простое число). Индексом элемента b Е Inv Zn по основанию а называют такое наименьшее неотрицательное целое число s, что as = b. Обозначают индекс так: indab. Так, возвращаясь к рассмотренному примеру, имеем

ind31 = 0   ind35 =  5  ind3 9 = 2  ind313 = 4
ind3 2 = 14 ind36 =  15 ind310 = 3  ind314 = 9
ind3 3=1    ind3 7 = 11 ind311 = 7  ind315 = 6
ind3 4 = 12 ind3 8 = 10 ind312 = 13 ind316 = 8

   Отображение

Ind : Inv Zn —Z Zn-1, b ।—i inda b

является изоморфизмом мультипликативной группы Inv Zₙ в аддитивную группу Zₙ₋1, аналогом изоморфизма ln : R₊ -i R, b -i lnb мультипликативной группы положительных действительных чисел в аддитивную группу действительных чисел, и применяется для решения степенных и показательных уравнений над полем Zn.
   Компьютерная программа, которая спрашивает пользователя простое число n и выводит на экран образующие элементы группы Inv Zₙ и таблицу индексов по одному из образующих элементов, может быть составлена по следующей схеме:
   а)    производится отбор целых чисел i Е {1, . . . , n - 1}, взаимно простых с n — для этого используется включенная в программу функция gcd, вычисляющая наибольший общий делитель двух чисел;
   б)    если i — одно из отобранных чисел, то программа определяет его наименьшую степень s, такую, что остаток от деления is на n равен 1. Если s = n — 1, то i — образующий элемент. При этом остатки от деления чисел i¹, i², . . . , iⁿ⁻¹ на n записываются в массив. Программе достаточно найти всего один образующий элемент: пробегая целые числа s от 2 до n — 1, взаимно простые с n — 1, программа выводит на экран остатки от деления чисел is на n — эти числа суть все остальные образующие элементы;
   в)   используя массив, программа выводит на экран таблицу индексов.
   Соответствующий программный код может быть таким:

   program zn;
   var i,j,n : integer;
   inv,d : array[1..100] of integer;
   function gcd (x,y : integer) : integer;
   begin
   if x=0 then gcd:=y else gcd:=gcd(y mod x,x)

8

    end;
    BEGIN
    writeln(); write(’Input n => ’);read(n);
    i:=2;
    repeat
          d[1]:=i; j:=1;
          repeat
              j:=j+1; d[j]:=(d[j-1]*i) mod n
          until d[j]=1;
          i:=i+1
    until j=n-1;
    writeln(); write(’Generators: ’);
    for i:=1 to n-2 do if gcd(i,n-1)=1
then if i>2 then write(’; ’,d[i]) else write(d[i]);
    write(’.’); writeln();
    for i:=1 to n-1 do
    begin j:=1;
        while d[j]<>i do j:=j+1;
        writeln(’ind(’,i,’)=’,j mod (n-1)) end
    END.




Упражнение 1. Составьте программу, которая спрашивает у пользователя п, коэффициенты а и b и выводит на экран решения линейного уравнения ax = b над кольцом Zn.

    Как известно, если a G InvZn, то уравнение ax = b имеет единственное решение x = a- 1b.
    При a / Inv Zn могут быть два случая:
    • Если d = НОД(а, п) является делителем числа b, то уравнение имеет d

x1 = с, x₂ = c + n, ..., xd = c + (d — 1)n,

      где n = d и с — единственное решение уравнения ax = b, a = d, b = d, над кольцом Zn;

    • Если b не делится на d, то уравнение ax = b не имеет решений.

Замечание. Поскольку порядок элемента конечной группы является делителем порядка группы, то число |Inv Zn| = Ф(п) делится на порядок s элемента a. Тогда Ф(п) = ks и, следовательно, a?⁽ⁿ) = (as) = 1k = 1. Отсюда aa®⁽n)-1 = 1, то есть

a-1 =      .                              (1)

При решении уравнения ax = b вручную при больших п гораздо проще использовать формулу (1), однако компьютерная программа совершит гораздо меньше операций, если найдет элемент a-1 методом перебора.

9

Упражнение 2. Составьте программу, которая спрашивает у пользователя п, коэффициенты а и b и выводит на экран решения линейного уравнения ax = b над кольцом Zn, найденное с помощью цепных дробей.


    Разделим n на a с остатком:
n = aq₀ + r1, 0 < r1 < |a|.

Если r1 = 0, разделим a на r1 с остатком:

a = riqi + Г2, 0 < Г2 < ri.

Если r2 = 0, разделим r1 на r2 с остатком:

ri = r2q2 + r3, 0 < гз < r2

Последовательность rᵢ , r₂ , r₃ , . . . строго убывает и ограничена снизу числом ноль, поэтому, продолжая процесс деления с остатком далее, получим на некотором шаге равный нулю остаток и запись


        n1
_ = qo ⁺ -■
        a1
q¹⁺-1—
            q2 +---------j              q3 + ... +qₘ

которую называют представлением числа n Для цепной дроби используется компактная

в виде цепной (или непрерывной) дроби. запись [qₒ; qᵢ , q₂, . . . , qₘ]. Цепные дроби

                        §o :=[qo], Si := [qo; qₓ],

§2 := [qo; qi^],---,

§m-i := [qo; qi, . . . , qm-i], §m := [qo; qi, q2, . . . , qm]


называют подходящими к дроби [qo; qi, q2, . . . , qₙ]. Обозначим числитель и знаменатель подходящей дроби §i соответственно Pi и Qi . Если a и n взаимно просты, то единственным решением уравнения ax = b является класс целых чисел, содержащий число (-1)mPm-ib.



Упражнение 3. Составьте программу, которая спрашивает у пользователя простое число п, коэффициенты a, k, c и b и выводит на экран решения показательного уравнения akx+c = b над полем Zn.

   Пусть z — образующий элемент группы Inv Zn. Тогда
indz akx+c = indz b, (kx + c)indz a = indz b, (k indz a)x + (c indz a) = indz b,
то есть задача свелась к решению линейного уравнения над кольцом Zₙ₋ᵢ.


10

Упражнение 4. Составьте программу, которая спрашивает у пользователя простое число п, коэффициенты а и b и показатель степени k и выводит на экран решения степенного уравнения axk = b над полем Zn.

   Если Inv Zn = (z), то


indz (axk) = indz b, indz a + k indz x = indz b, k indzx = indz b — indza,

то есть задача свелась к решению линейного уравнения над кольцом Zₙ₋1 .


11