WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |   ...   | 38 |

Утверждение 2. Пусть сильно регулярный граф с параметрами (v, k,, µ), k = µ, = µ и с матрицей смежности A. Пусть также P матрица перестановки, отвечающая автоморфизму порядка 2 графа, сдвигающему только несмежные вершины. Тогда M = P A матрица смежности точного графа Деза с параметрами (v, k, max{, µ}, min{, µ}).

Заметим, что эта конструкция позволяет получать графы Деза с одинаковыми параметрами и одинаковыми наборами различных собственных значений, но в общем случае с различными их кратностями. Пусть k, r, s различные собственные значения матрицы смежности A сильно регулярного графа с кратностями 1, f, g соответственно. Тогда матрица смежности M графа Деза, полученного из с помощью утверждения 2, имеет собственные значения k, ±r, ±s 22 Тезисы 43-й молодежной школы-конференции с кратностями 1, f+, f-, g+, g- соответственно, причем f+ + f- = f, g+ + g- = g. Таким образом, построенные с помощью конструкции 2 графы Деза имеют не более 5 различных собственных значений.

Предложение 2. Если граф Деза, полученный из сильно регулярного графа с помощью утверждения 2, имеет точно 4 различных собственных значения, то автоморфизм P действует на V () без неподвижных точек и либо f- = f, g- = -fr/s, g+ = -k/s, либо g- = g, f- = -gs/r, f+ = -k/r.

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

Гипотеза 1. Графы Деза, построенные с помощью конструкции 2, имеют 5 различных собственных значений.

В работе также изучаются графы Деза с 4-мя различными собственными значениями, три из которых иррациональные числа.

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

Литература [1] Erickson M., Fernando S., Haemers W.H., Hardy D., Hemmeter J. Deza graphs: a generalization of strongly regular graphs // J.

Comb. Designs. 1999. Vol. 7. Pp. 359–405.

[2] Guo J., Wang K., Li F. Deza graphs based on symplectic spaces // Europ. J. of Comb. 2010. Vol. 31. Pp. 1969–1980.

[3] Haemers W.H., Kharaghani H., Meulenberg M.A. Divisible design graphs // J. Comb. Theory, A. Vol. 118, № 3. Pp. 978–992.

[4] Горяинов С.В., Шалагинов Л.В. О графах Деза на 14, 15 и вершинах // Сиб. электрон. матем. изв. 2011. № 8. С. 105–115.

Алгебра РЕШЕНИЕ КВАДРАТНЫХ УРАВНЕНИЙ В КОНЕЧНЫХ ПОЛЯХ ХАРАКТЕРИСТИКИ Глуско Кр.Л., Титов С.С.

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

Различают понятия абсолютного и относительного следа элемента поля.

В произвольном поле GF (q) формула будет выглядеть следу2 n-ющим образом: T r(z) = z + zp + zp +... + zp, где q = pn.

T r(z) GF (p) и может принимать значения 0, 1,..., p - 1.

Если поле GF (qm) является расширением поля GF (q), то речь уже идет о вычислении относительного следа элемента поля GF (qm).

Известно, что относительный след – единственная линейная операция, отображающая элементы поля F в элементы поля K, обладающая свойствами идемпотентности, коммутативности, ассоциативности и дистрибутивности [1].

Для решения уравнения x2 + x = z в полях GF (2n) при нечетном n используется так называемая формула полуследа:

n-1 n Sr(z) = x = z + z4 + z16 +... + z2, причём z2 = z.

Утверждение 1. Формула полуследа дает решение квадратного уравнение с нулевым следом в поле GF (2n), где n нечетное.

В книге [2] вычисление решения квадратного уравнения в полях GF (2n), где n четное, сводится к системе линейных уравнений.

Однако на основании исследований можно сформулировать следующее утверждение.

Утверждение 2. При четном n не существует многочлена вида, дающего решение квадратного уравнения z2 + z = a.

24 Тезисы 43-й молодежной школы-конференции В многочленах четных степеней появятся две степени подряд, поэтому при сложении z +z2 некоторые позиции сократятся и не дадут полной формулы, аналогичной для многочленов нечетной степени.

Можно ставить задачу поиска многочлена, корень которого является решением квадратного уравнения z2 + z в поле GF (2n), где n четное.

Для поиска решения уравнения больших степеней можно использовать идею расширения полей: зная формулу решения квадратного уравнения в полях GF (2n), где n нечетно, и зная формулу решения этого уравнения в полях GF (2k), мы сможем найти формулу решения в поле GF (2nk), k = 2, 4, 8, 16,... (см. рис. 1).

Рис. 1: схема расширения полей Решение квадратного уравнения при четном n = 2m можно выразить следующим образом:

z GF (2n) z = x + y, x, y GF (2m) 2n-1 2n-T r(z) = z + z2 + z4 +... + z2 = (z + z4 + z16 + z2 + (z2+ 2n-1 n-+z8 +... + z2 ) = (x + x2 +... + x2 ) + (y + y4 + y16 +... + n-1 n +y2 ) + 2(y2 + y8 + y32 +... + y2 ).

z2 + z + z1 = (x2 + 2y2) + (x + y) + (x1 + y1), где 2 = + 1.



(x2 + x + y2) + (y2 + y) = x1 + y1.

Отсюда следует:

T r(y1) = 0, T r(x1 + y2) = 0.

Алгебра При n нечетном T r(Sr(a)) = 0, если T r(a) = 0.

Одно из решений при условии, если T r(x1) = 0:

4 16 2n-y = Sr(y1) = y1 + y1 + y1 +... + y1.

2 8 32 2n-2 n 2 y2 = [Sr(y1)]2 = y1 + y1 + y1 +... + y1 + y2 = y1 + y1 + y1+ 32 2n-+y1 +... + y1.

Сложив эти выражения, получим: y + y2 = y1 = T r(y1) + y1 = T r(y1) = 0.

Если T r(x1) = 1, то T r(x1 + y2) = T r(x1) + T r(y2) = T r(x1) + T r(y) = T r(x1), что противоречит начальным утверждениям.

Поэтому условия таковы: T r(x1) = T r(y1) = 0, а формула – такова:

y = Sr(y1) + T r(x1);

2 x = Sr(x1 + y2) = Sr(x1) + Sr(y1) = Sr(x1) + T r(x1) + Sr(y1).

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

На основании проведенных исследований можно сказать, что надо выбирать базис GF (2s), s = 2k через симметричный, или самовозвратный многочлен. Это связано с тем, что нормальный базис при последовательном возведении в степень создает цикл, что упрощает расчеты.

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

Литература [1] Лидл Р., Нидеррайтер Г. Конечные поля: в 2-х тт. Т. 1. Пер. с англ. – М.: Мир, 1988. С. 71–72.

[2] Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: алгебраические и алгоритмические основы. – М.: КомКнига, 2006. С. 49–50, 60–62.

26 Тезисы 43-й молодежной школы-конференции О ГРАФАХ ДЕЗА, ПОЛУЧАЕМЫХ ИЗ ЦИКЛИЧЕСКИХ ГРУПП Горяинов С.В., Шалагинов Л.В.Мы рассматриваем конечные неориентированные графы без петель и кратных ребер.

Определение 1. Графом Деза с параметрами (v, k, b, a), где b a, называется граф на v вершинах, степень каждой вершины которого равна k, и любые две вершины которого имеют a или b общих соседей.

Определение 2. Пусть G1 и G2 графы. Композицией G1[G2] графов G1 и G2 называется граф с множеством вершин V (G1) V (G2) такой, что вершины (u1, u2) и (v1, v2) смежны тогда и только тогда, когда либо u1 смежна с v1, либо u1 = v1 и u2 смежна с v2, см.

[2].

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

Пусть группа и D. Определим D-1 как множество {d-1 :

d D} и определим DD-1 как мультимножество {dd -1 : d, d D} (в DD-1 могут быть повторяющиеся элементы). Для подмножеств A и B множества элементов и целых чисел a и b будем писать DD-1 = aA+bB, если в DD-1 содержится a копий каждого элемента из A и b копий каждого элемента из B.

Теорема 1. [1] Пусть D – подмножество элементов группы такое, что (i) || = v и |D| = k;

(ii) единица группы не содержится в D;

Работа выполнена при финансовой поддержке гранта Президента РФ для молодых ученых (проект МК-938.2011.1), программы УрО РАН для молодых ученых и фонда поддержки молодых ученых ЧелГУ.

Алгебра (iii) D-1 = D;

(iv) DD-1 = aA + bB + ke, где A, B и {e} разбиение.

Пусть G граф, множество вершин которого все элементы группы, и вершины u и v которого смежны тогда и только тогда, когда v-1u D. Тогда G граф Деза с параметрами (v, k, b, a).

Теорема 2. [1] Если G1 сильно регулярный граф с параметрами (n, k,, µ) и G2 граф Деза с параметрами (n, k, b, a), то G1[G2] регулярный граф степени (k + kn ) на nn вершинах. Этот граф является графом Деза тогда и только тогда, когда |{a + kn, b + kn, µn, n + 2k }| 2.

Приведем пример: если G1 = Kx (полный граф на x вершинах) и G2 = yK2 (y копий K2), тогда граф G1[G2] является графом Деза с параметрами (2xy, 1 + 2y(x - 1), 2y(x - 1), 2 + 2y(x - 2)).

Теорема 3. [1] Пусть G граф Деза с параметрами (n, k, b, a).

Тогда k = b в том и только том случае, если G изоморфен G1[G2], где G1 (n1, k1, 1) и G2 = Kn для некоторых n1, n2, k1, 1. При этом его параметры равны n = n1n2, k = b = k1n2, a = 1n2.

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

Лемма 1. Пусть G = Kx[yK2] граф Деза. Тогда в группе C2xy найдется множество D, удовлетворяющее условию теоремы 1 такое, что полученный граф Деза изоморфен G.

В таблице 1 приведены все графы Деза, получаемые с использованием теоремы 1 из циклических групп Cn при n 56, для каждого графа найдено множество D и построена его матрица смежности. Не указаны сильно регулярные графы (они хорошо известны), графы с k = b (они описываются теоремой 3), все возможные композиции Kx[yK2] и произведения Kn K4, а также простые случаи: объединения циклов, полных графов, полных двудольных графов, полные двудольные графы с удаленным паросочетанием и т.п.

28 Тезисы 43-й молодежной школы-конференции Таблица 1: параметры графов, получаемых из циклических групп Параметры Описание (19,6,2,1) локально циклический изоморфен M(19) [3] (20,13,9,8) (21,12,7,6) (26,13,12,6) P aley(13)[K2] [4] (28,19,15,12) (34,17,16,8) P aley(13)[K2] [4] (37,18,9,8) имеет те же параметры, что и P aley(37) (37,24,16,15) (41,20,10,9) имеет те же параметры, что и P aley(41) (53,26,13,12) имеет те же параметры, что и P aley(53) Литература [1] Erickson M., Fernando S., Haemers W.H., Hardy D., Hemmeter J.





Deza graphs: a generalization of strongly regular graphs// J. Comb.

Designs. 1999. Vol. 7. Pp. 359-405.

[2] Harary F. Graph theory. Reading: Addison-Wesley, 1969. Pp. 36-37.

[3] Зарипов С.Р., Махнев А.А., Яблонко И.П. О сильно регулярных графах без треугольников / в сб. Алгебра и линейная оптимизация, тр. Междунар. семинара, посвящ. 90-летию со дня рождения С.Н. Черникова. C. 117-121. Екатеринбург: ИММ УрО РАН, 2002.

[4] Ермакова Г.М., Кабанов В.В. Графы Деза, которые являются кликовыми расширениями сильно регулярных графов / в сб.

Проблемы теорет. и прикл. математики, тр. 37-й Регион. молодёж. конф. С. 27-29. Екатеринбург: ИММ УрО РАН, 2006.

Алгебра ДЛИНА ОДНОПОРОЖДЕННОЙ КРАТНО -РАССЛОЕННОЙ ФОРМАЦИИ T -ГРУПП Демина Е.Н.

Аддитивная группа G c нулевым элементом 0 называется мультиоператорной T -группой с системой мультиоператоров T (или, коротко, T -группой), если в G задана еще некоторая система nарных алгебраических операций T при некоторых n, удовлетворяющих условию n > 0, причем для всех t T выполняется условие t(0,..., 0) = 0, где слева элемент 0 стоит n раз, если операция t nарна [1, гл. VI, c. 356]. Используемые обозначения и определения можно найти в работах [1–5]. Пусть C – класс всех T -групп с конечными композиционными рядами. Все рассматриваемые T -группы принадлежат классу C. Пусть I – класс всех простых C-групп, – непустой подкласс класса I, = I\ и K(G) – класс всех простых C-групп, изоморфных композиционным факторам C-группы G. Если K(G), то G называется -группой. Обозначим через C класс всех -групп, принадлежащих C, и положим O(G) = GC.

Функция f: { } {формации T -групп} называется F функцией; функция : I {непустые формации Фиттинга T групп} называется F R-функцией. Формация F (f, ) = (G C :

G/O(G) f( ) и G/G(A) f(A) для всех A K(G)) называется -расслоенной формацией T -групп с -спутником f и направлением ( – r-направление, если CA (A) = (A) для любого A I, 0(A) = CA для любого A I). Обозначим через Fn множество всех n-кратно -расслоенных C-формаций с направлением.

Пусть Fn(G, ) – Fn -формация, порожденная C-группой G. Через LF (F) обозначается решетка всех Fn -подформаций в F Fn, n где n N0 и – произвольное направление.

Для любых двух формаций F1 и F2 полагают F1 F2 = F1 F2, F1 F2 = form(F1 F2). Всякое множество формаций, замкнутое относительно операций и, является решеткой [2].

Лемма 1. [4, теорема 4] Решетка Fn является полной и модулярной для любого n N0 и любого направления, 0.

Используя свойства полноты и модулярности решетки, Ски30 Тезисы 43-й молодежной школы-конференции ба А.Н. ввел понятие длины формации. Сформулируем его для мультиоператорных T -групп.

Определение 1. Пусть – полная модулярная решетка формаций мультиоператорных T -групп, 0 – нуль решетки. Будем говорить, что -формация F = 0 имеет -длину n, и обозначать l(F) = n, если существует такая совокупность -формаций F0, F1,..., Fn, что F0 = 0, Fn = F и Fi-1 – максимальная -подформация -формации Fi, i = 1,..., n.

Пусть {Fi|i I} – набор C-формаций таких, что FiFj = (0), i, j I, i = j. Нетрудно показать, что F = iIFi = {Ai + Ai +... + 1 +Ai |Ai Fi, ij I, j = 1, 2,..., n, n N}, где Ai + Ai +... + Ai n j j 1 2 n – внешняя прямая сумма C-групп Ai, j = 1, 2,..., n, является Cj формацией.

Теорема. Пусть F = F1F2...Ft, где Fi – непустая C-формация из Fn с r-направлением таким, что (A) CA CA для любого A I, и lF (Fi) = ni < для любого i = 1, 2,..., t. Тогда lF (F) = n n = n1 + n2 +... + nt + 1 - t.

Для формулировки следствий из теоремы приведем некоторые вспомогательные результаты.

Определение 2. [1] Элемент B решетки C-формаций с нулем (0) называется атомом, если B = (0) и (0) H B, где H, влечет, что H = (0) или H = B.

Лемма 2. [5, лемма 6] Если F = Fn(G, ), где n N0 и 0, то решетка LF (F) содержит лишь конечное число атомов.

n Определение 3. [1] Ограниченную решетку C-формаций будем называть решеткой с дополнениями, если для любой непустой Cформации B существует C-формация H такая, что B H = = (0) и B H = F, где F – максимальный элемент решетки.

Определение 4. [1] Решетка называется булевой, если она дистрибутивна и является решеткой с дополнениями.

Лемма 3. [5, теорема 2] Пусть F Fn, где – r-направление такое, что (A) CA CA для любого A I. Тогда следующие условия равносильны:

Алгебра (1) решетка LF (F) булева;

n (2) F = iIFi, где {Fi|i I} – набор всех атомов решетки LF (F);

n (3) в F дополняем каждый элемент решетки LF (F).

n Следствие 1. Пусть F = Fn(G, ), где G – C-группа и – rнаправление такое, что (A) CA CA для любого A I. Если ре шетка LF (F) булева, то lF (F) = t + 1, где t – число атомов n n решетки LF (F).

n Следствие 2. Пусть F = Fn(G, ), где G – C-группа и – rнаправление такое, что (A) CA CA для любого A I. Если в F дополняем каждый элемент решетки LF (F), то lF (F) = t + 1, n n где t – число атомов решетки LF (F).

n Литература [1] Скорняков Л.А. Общая алгебра. Т. 2. М.: Наука, 1991.

[2] Шеметков Л.А., Скиба А.Н. Формации алгебраических систем.

М.: Наука, 1989.

[3] Скиба А.Н. Алгебра формаций. Минск: Беларуская навука, 1997.

[4] Ведерников В.А., Демина Е.Н. -расслоенные формации мультиоператорных T -групп // Сибирский математический журнал.

2010. T. 51, № 5. C. 990–1009.

[5] Демина Е.Н. Булевы решетки кратно -расслоенных формаций мультиоператорных T -групп / в сб. Теория групп и ее приложения, труды восьмой Межд. школы-конф., посв. 75-летию В.А. Белоногова. С. 86–93. Нальчик: Каб.-Балк. ун-т, 2010.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 38 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.