Полиномы Холла бернсайдовых групп периода 3

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

ЛИТЕРАТУРА
1. Семенов А. Д., Артамонов Д. В., БрюхачевА.В. Идентификация систем управления. Учеб. пособие. Пенза: Изд-во Пенз. ун-та, 2003. 211с.
2. Материалы компании AlterTrader Research [Электронный ресурс]. http: //www. altertrader. com/ - 21. 04. 2015.
3. Загоруйко Н. Г., Кутненко О. А. Методы распознавания, основанные на алгоритме AdDel // Сиб. журн. индустр. матем. 2004. Т. 7. № 1. С. 39−47.
4. Воронцов К. В. Методы обучения ранжированию (Learning to rank). Курс лекций. [Электронный ресурс]. 2013. http: //www. machinelearning. ru/wiki/images/8/89/ Voron-ML-Ranking-slides. pdf
5. Кожушко О. А., Тарков М. С. Использование иерархической временной памяти для идентификации системы ранжирования документов // Проблемы информатики. 2015. № 1(26). С. 47−54.
УДК 519. 688 DOI 10. 17 223/2226308X/8/57
ПОЛИНОМЫ ХОЛЛА БЕРНСАЙДОВЫХ ГРУПП ПЕРИОДА 31
А. А. Кузнецов, К. В. Сафонов
Пусть Bk = (к, 3) — бернсайдова к-порождённая группа периода 3. В работе вычислены полиномы Холла для Bk при к ^ 4.
Ключевые слова: периодическая группа, собирательный процесс, полиномы Холла.
Пусть Bk = (k, 3) -бернсайдова k-порождённая группа периода 3. Ф. Леви и ван дер Варден доказали [1], что |Bk| = 3к+(2)+(з) и ступень нильпотентности Bk не превышает 3.
Для каждой Bk несложно получить рс-представление (power commutator presentation) используя систему компьютерной алгебры GAP или MAGMA.
Пусть а1 … аП& quot- и а1 … аП& quot- -два произвольных элемента в группе Bk, записанные в коммутаторном виде. Тогда их произведение равно
nx1 rtx& quot-. Г1У1 ПУп — nz1 nz& quot-
а-[.. ап а-[.. а^ - а i … а^.
Основой для нахождения степеней zi является собирательный процесс [2, 3], который реализован в указанных системах компьютерной алгебры. Кроме того, существует альтернативный способ для вычисления произведений элементов группы, предложенный Ф. Холлом [4]. Холл показал, что zi представляют собой полиномиальные функции (в нашем случае над полем Z3), зависящие от переменных x1,…, xi, yi,…, yi, которые принято сейчас называть полиномами Холла. Согласно [4],
Zi = Xi + yi + Pi (xi,.., Xi-i, yi,…, yi-i).
Необходимость применения полиномов Холла возникает при решении задач, требующих многократного умножения элементов группы. Исследование структуры графа Кэли некоторой группы является одной из таких задач. Вычислительные эксперименты на ЭВМ в группах периода пять и семь [5, 6] выявили, что метод полиномов Холла
1 Работа выполнена при поддержке Министерства образования и науки РФ (проект Б 112/14) и
гранта Президента Р Ф (проект МД-3952. 2015. 9).
148
Прикладная дискретная математика. Приложение
имеет преимущество перед традиционным собирательным процессом. Следует также отметить, что данный метод легко программно реализуем, в том числе на многопроцессорных вычислительных системах.
В настоящей работе вычислены ранее неизвестные полиномы Холла для групп B& amp- при k ^ 4. Для k & gt- 4 полиномы вычисляются аналогично, однако их вывод занимает значительно больше места. Заметим, что, вычислив полиномы для некоторого k, нетрудно получить полиномы Холла для меньших значений k.
Получим в GAP рс-представление группы B4.
Коммутаторы веса 1:
ai, $ 2, аз, Я4 — образующие группы.
Коммутаторы веса 2: a5 = [a2,ai], = [a3,ai], а7 = [а3,а2], = [а4, ai], а9 = [а4,а2], аю = [а4, а3].
Коммутаторы веса 3:
aii = [а5,аз] = [а2,а1,аз], ai2 = [05,04] = [а2,ai, a4], a13 = [а6,а4] = [a3,ai, a4], ai4 = [а7,а4] = [а3,а2,а4].
Список определяющих соотношений R для базисных коммутаторов (тривиальные соотношения вида а3 = 1 и [aj, а^] = 1 для краткости не приводятся):
[а2, ai] = a5, [a3, ai] = a6, [a3, a2] = a7, [a4, ai] = a8, [a4, a2] = a9, [a4, a3] = aio, [a5,a3]= aii, [a5,a4] = ai2, [a6,a2] = aii, [a6,a4] = ai3, [a7,ai]= aii, [a7,a4] = ai4, [a8, 02] = a2, [a8,03] = a23, [ag, ai] = ai2, [09,03]= [aio, ai]= ai3, [aio, 02]= ai4.
Таким образом, B4 = (, 02, 03, 04, 05, 06, 07,08, 09, 0i0, 0ii, 0i2, 0i3, 0i4 | R).
Каждый элемент группы выражается единственным образом в виде нормального коммутаторного слова:
Уд Е B4 (д = 0×2 axз aXБ ax6 0×7 0×8 ax9 00°, 0х}1^, 0×13,), X* G Z3.
Основным результатом настоящей работы является
Теорема 1. Пусть … и al/1 … aY44 -два произвольных элемента в группе B4, записанные в коммутаторном виде. Тогда их произведение равно … х
i4
формулами:
х 0У1… ai44 = a//1… a//44, где z Е Z3 -полиномы Холла, задаваемые следующими
zi = xi + yi,
Z2 = X2 + У2, Z3 = X3 + У3, z4 = X4 + y4, Z5 = X5 + У5 + X2yi, Z6 = X6 + ye + X3yi, Z7 = X7 + y7 + X3y2, Z8 = X8 + y8 + X4yi, Z9 = X9 + y9 + X4y2,
Zi0 = Xio + yio + X4y3,
Zii = Xii + yii + Х5Уз + 2хвУ2 + Xzyi + X2X3 yi + X2 yiy3 + 2хзУ1У2, Z12 = X12 + У12 + Х5У4 + 2X8 У2 + Х9У1 + X2X4 yi + X2 У1У4 + 2Х4У1У2, Z13 = Xi3 + yi3 + Xioyi + Х6У4 + 2X8 Уз + Х3Х4У! + X3yiy4 + 2Х4У^з, Zi4 = Xi4 + yi4 + ХюУ2 + Х7У4 + 2Х9У3 + Х3Х4У2 + Х3У2У4 + 2Х4У2У3.
ЛИТЕРАТУРА
1. Levi F. and van der Waerden B. Uber eine besondere Klasse von Gruppen // Abh. Math. Sem. Univ. Hamburg. 1933. No. 9. S. 154−158.
2. Sims C. Computation with Finitely Presented Groups. Cambridge: Cambridge University Press, 1994. 628 p.
3. HoltD., EickB., and O'-Brien E. Handbook of computational group theory. Boca Raton: Chapman & amp- Hall/CRC Press, 2005. 514 p.
4. Hall P. Nilpotent groups, Notes of lectures given at the Canadian Mathematical Congress 1957 Summer Seminar, in The collected works of Philip Hall. Oxford: Clarendon Press, 1988. P. 415−462.
5. Кузнецов А. А., Кузнецова А. С. Быстрое умножение элементов в конечных двупорождён-ных группах периода пять // Прикладная дискретная математика. 2013. № 1. C. 110−116.
6. Кузнецов А. А. Сафонов К. В. Hall'-s polynomials of finite two-generator groups of exponent seven // Журнал СФУ. Сер. математика и физика. 2014. № 2. C. 186−190.
УДК 512. 54. 05+519. 712.4 DOI 10. 17 223/2226308X/8/58
О СЛОЖНОСТИ ЗАДАЧИ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В ИНТЕРВАЛЕ В ГРУППЕ С ЭФФЕКТИВНЫМ ИНВЕРТИРОВАНИЕМ
М. В. Николаев
Задача дискретного логарифмирования в интервале заключается в поиске для заданной конечной группы G (с аддитивной записью операции), заданных P, Q? G, N & lt- |G| - 1 такого значения n, что Q = nP, 0 ^ n ^ N. Одним из наиболее эффективных методов решения данной задачи является алгоритм Годри — Шо-ста. В 2010 г. С. Гэлбрейт и К. Рупраи представили усовершенствованную версию алгоритма для групп с эффективным инвертированием. Оценка средней трудоёмкости решения задачи составила (1,36 + o (1))/N групповых операций в G при N ^ т. е. В настоящей работе приводится новая модификация алгоритма Годри — Шоста для решения задачи дискретного логарифмирования в интервале в группе с эффективным инвертированием и получена оценка средней трудоёмкости, составляющая (1 + e) JnN/2 групповых операций в G.
Ключевые слова: задача дискретного логарифмирования в интервале, алгоритм Годри — Шоста.
Приведём постановки задач.
Определение 1. Задача дискретного логарифмирования.
Дано: группа G = (P), Q? G.
Найти: n? {0,…, |G| - 1}, такое, что Q = nP.
Определение 2. Задача дискретного логарифмирования в интервале. Дано: группа G = (P), Q? G, N? N, 2|N, N & lt- |G| - 1, Q = nP для некоторого (неизвестного) n? { - N/2,…, N/2}. Найти: n.

ПоказатьСвернуть
Заполнить форму текущей работой