авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 8 |
-- [ Страница 1 ] --

РОССИЙСКАЯ АКАДЕМИЯ НАУК

УРАЛЬСКОЕ ОТДЕЛЕНИЕ

ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

ПРОБЛЕМЫ

ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ

МАТЕМАТИКИ

Труды 35-й Региональной молодежной конференции,

26 - 30 января 2004 г.

ЕКАТЕРИНБУРГ

2004

РОССИЙСКАЯ АКАДЕМИЯ НАУК

УРАЛЬСКОЕ ОТДЕЛЕНИЕ

ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ

МАТЕМАТИКИ Труды 35-й Региональной молодежной конференции, 26 - 30 января 2004 г.

ЕКАТЕРИНБУРГ 2004 У Д К 517 ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕ МАТИКИ: Труды 35-й Региональной молодежной конференции.

Екатеринбург: УрО РАН, 2004. ISBN 5-7691-1490-8.

Настоящее издание включает материалы 35-й Региональной кон ференции молодых ученых, состоявшейся с 26 по 30 января 2004 года в г. Екатеринбурге.

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

Сборник представляет интерес для специалистов по указанным разделам математики.

Конференция проведена при финансовой поддержке РФФИ, грант №04–01–10024 и Президиума УрО РАН.

Ответственный редактор чл.-корр. РАН В.И. Бердышев Рецензенты:

акад. РАН И.И. Еремин, чл.-корр. РАН В.И. Бердышев, чл.-корр. РАН А.А. Махнев, д.ф.-м.н. А.И. Короткий, д.ф.-м.н. В.И. Максимов, д.ф.-м.н. В.Н. Ушаков, к.ф.-м.н. В.Л. Авербух, к.ф.-м.н. Е.Н. Акимова, к.ф.-м.н. М.Ю. Хачай Ответственные за выпуск:

Е.Н. Акимова, Н.А. Ваганова М.Ю. Филимонов ISBN 5-7691-1490-8.

ПРП-2004 13 (04) c П ПВ-2004 Институт математики и 8П6 (03) механики УрО РАН, 2004 г.

Алгебра и топология О КВАЗИРАСПОЗНАВАЕМОСТИ ПО МНОЖЕСТВУ ПОРЯДКОВ ЭЛЕМЕНТОВ ГРУПП F4 (q), q НЕЧЕТНО Алексеева О.А., Кондратьев А.С. e-mail: oksana@prima.susu.ac.ru, a.s.kondratiev@imm.uran.ru Пусть G конечная группа. Обозначим через (G) множество всех порядков элементов группы G. Множество (G) определяет граф простых чисел (граф Грюнберга-Кегеля) GK(G) группы G, в котором вершинами служат простые делители порядка группы G и две различные вершины p и q соединены ребром тогда и только тогда, когда G содержит элемент порядка pq. Обозначим число ком понент связности графа GK(G) через t(G), а множество его связных компонент через {i (G) | 1 i t(G)};



при этом для группы G четного порядка считаем, что 2 1 (G). Множество (G) частич но упорядочено относительно делимости и однозначно определяется подмножеством µ(G) своих максимальных элементов.

Общее строение конечных групп G с t(G) 2 дается теоремой Грюнберга-Кегеля (см. [1, теорема A]). Конечные простые неабелевы группы с несвязным графом Грюнберга-Кегеля описаны в [1, 2].

Результаты о конечных группах с несвязным графом Грюнберга Кегеля нашли большое применение в исследованиях распознаваемо сти конечных групп по множеству порядков элементов (см., напри мер, [3]). Конечная группа G называется распознаваемой (по (G)), если для конечной группы H равенство (H) = (G) влечет H G. = Выдвинута следующая Гипотеза В. Д. Мазурова. Конечные простые группы с несвяз ным графом Грюнберга-Кегеля, как правило, распознаваемы.

Первым этапом доказательства этой гипотезы, по-видимому, бу дет доказательство условия квазираспознаваемости, более слабого, чем распознаваемость. Конечная простая неабелева группа P назы вается квазираспознаваемой, если любая конечная группа G c (G) = (P ) имеет композиционный фактор, изоморфный P.

В [4, 5] авторы показали, что все конечные простые неабелевы группы P с t(P ) 3 квазираспознаваемы, за исключением случая, когда P изоморфна группе A6.

1

Работа выполнена при финансовой поддержке РФФИ (грант 04-01-00463) и РФФИ-БРФФИ (грант 04-01-81001).

4 Труды XXXV Молодежной школы-конференции В данной работе доказывается следующая теорема в направлении исследования квазираспознаваемости групп F4 (q), q нечетно (графы Грюнберга-Кегеля этих групп имеют точно две компоненты связно сти).

Теорема. Пусть G конечная группа с (G) = (F4 (q)), q нечет но. Тогда цоколь группы G/F (G) изоморфен либо F4 (q), либо Ap1 (r), где p делит r 1, либо 2 Ap1 (r), где p делит r + 1. Здесь p нечет ное простое число.

Наши обозначения и терминология в основном стандартны, их можно найти в [6–9]. Если n натуральное число и p простое число, то (n) обозначает множество всех простых делителей числа n. Для конечной группы G положим (G) = (|G|) и µi (G) = {n µ(G) | (n) i (G)}.

Приведем краткое доказательство теоремы. Мы часто использу ем следующие две предварительные леммы.

Лемма 1. [10, лемма 4]. Пусть P конечная простая группа с несвязным графом Грюнберга-Кегеля. Тогда (а) |µi (P )| = 1 для i 1, пусть ni = ni (P ) обозначает един ственный элемент из µi (P ) для i 1;

(б) P, 1 (P ), ni для 2 i t(P ) известны.

Лемма 2. [11, лемма 2.2]. Пусть p, q простые числа такие, что pa q b = 1 для некоторых натуральных чисел a, b. Тогда (pa, q b ) = (32, 23 ), (p, 2b ), (2a, q).

Пусть G конечная группа с (G) = (L), где L = F4 (q), q нечёт но. Ввиду теоремы Грюнберга-Кегеля, результата М. Р. Зиновьевой (Алеевой) [12] и леммы 1 Inn(P ) G = G/F (G) Aut(P ), где P конечная простая группа с t(P ) t(L), (F (G)) (G) 1 (G) и n2 (L) {ni (P ) | 2 i t(P )}. Далее рассматриваюся все возможно сти для P, описываемые в лемме 1. Мы рассмотрим только наиболее интересные случаи. Остальные случаи рассматриваются аналогично или непосредственными вычислениями.





1) Пусть P An. По лемме 1 ((n 3)!) (G) либо n = {p, p + 1, p + 2}, одно из n, n 2 не простое и q 4 q 2 + 1 = p, ли бо числа n = p, p 2 простые и q 4 q 2 + 1 {p, p 2}. Ясно, что 1 q 4 q 2 1 n 3 и q 4 q 2 1 нечётно. Поэтому в P существует Алгебра и топология элемент(цикл) порядка q 4 q 2 1. Следовательно, в G, а значит и в L, существует элемент x порядка q 4 q 2 1. Так как (| x |, q) = 1, то x полупростой элемент в L. Значит, x принадлежит некоторо му максимальному тору T группы L. Поэтому q 4 q 2 1 делит |T |.

Ввиду [9] число |T | принимает одно из следующих значений:

(q ± 1)4, (q 2 ± 1)(q ± 1)2, (q 2 ± 1)2, (q 3 ± 1)(q ± 1), q 4 ± 1, q 4 q 2 + 1.

Имеем (q 4 q 2 1, q 2 1) = (q 2 (q 2 1) 1, q 2 1) = 1, (q 4 q 2 1, q 2 + 1) = (q 4 (q 2 + 1), q 2 + 1) = 1, (q 4 q 2 1, q 4 q 2 +1) = ((q 4 q 2 +1)2, q 4 q 2 +1) = (2, q 4 q 2 +1) = 1.

Отсюда |x| делит q 2 ± q + 1 или q 4 + 1. В первом случае q 4 q 2 делит q 2 ± q + 1, что невозможно. Во втором случае q 4 q 2 1 = (q 4 q 2 1, q 4 + 1) = ((q 4 + 1) (q 2 + 2), q 4 + 1) = (q 2 + 2, q 4 + 1) = (q 2 + 2, q 2 (q 2 + 2) 2(q 2 + 2) + 5) = (q 2 + 2, 5), следовательно, q 4 q 2 1 = 5, откуда q 2 = 3;

противоречие.

2) Пусть P 3 D4 (r). По лемме 1 q 4 q 2 + 1 = r4 r2 + 1, откуда = легко видеть, что q = r. Имеем Aut(P ) = Inn(P ) F, где F циклическая группа полевых автоморфизмов группы P и q 3 = p|F | для некоторого нечётного простого числа p.

Предположим, что порядок группы G/Inn(P ) делится на простое число s 3. Тогда в G \ P существует элемент x порядка s и по [13] CP (x) 3 D4 (q0 ), где q = q0.

s = Тогда q0 + 1 делит q0 + 1 = q 6 + 1. Но (q0 q0 + 1, q 2 + 1) = 6 6s 4 2 2 2s 2 ((q0 +1)(q0 2)+3, q0 +1) = (3, q0 +1) = 1, так как 3 делит q0 (q0 1), 2 2 4 2 4 а (q0 (q0 1), q + 1) = 2. Поэтому q0 q0 + 1 делит q q + 1, а это противоречит тому, что s 1 (G).

Итак, G/P является {2, 3}-группой и, следовательно, 1 (G/P ) 1 (G) = (q(q 6 1)).

Поскольку (q 8 1, q(q 6 1)) = q 2 1, (q 2 +1, q 2 1) = (q 4 +1, q 2 1) = 2, то ((q 2 +1)(q 4 +1)/4) (q(q 6 1)) =. Отсюда ((q 2 +1)(q 4 +1)/4) 6 Труды XXXV Молодежной школы-конференции (F (G)). Так как подгруппа F (G) нильпотентна, то в ней найдется 2 элемент порядка s1 s2, где s1 ( q 2 ), s2 ( q 2 ). Значит, и в +1 + L найдётся полупростой элемент порядка s1 s2. Этот элемент содер жится в некотором максимальном торе T группы L, и значит, s1 s делит |T |. Но это противоречит всем возможностям для |T |.

3) Пусть P Cn (r), n = 2m 2. По лемме = rn + = q 4 q 2 + 1.

(2, r 1) Если (2, r 1) = 1, то rn + 1 = q 4 q 2 + 1, откуда rn = q 2 (q 2 1);

n противоречие. Поэтому (2, r 1) = 2 и r 2 = q 4 q 2 +1, т. е. rn 1 = + 2q (q 1). Положим r1 = r. Тогда (r1 1)(r1 + 1) = 2q 2 (q 2 1).

22 n/ Ясно, что (r1 1, r1 +1) = 2. Поэтому 2q 2 делит либо r1 1, либо r1 +1.

Отсюда r1 + = 2aq 2 для некоторого a N и {±1}. Если = 1, то 2aq 2 (2aq 2 + 2) = 2q 2 (q 2 1), откуда q 2 1 2a(aq 2 + 1) = q 2 1;

противоречие. Если = +1, то 2aq 2 (2aq 2 2) = 2q 2 (q 2 1), откуда q 2 1 2a(aq 2 1) = q 2 1;

противоречие.

4) Пусть P Cp (r), где p нечетное простое число и r = 2, 3.

= По лемме rp = q 4 q 2 + 1.

(2, r 1) Если r = 2, то 2p 1 = q 4 q 2 + 1, откуда 2p = q 4 q 2 + 2, 2(2p 1) = q 2 (q 2 1). Но q 2 1 = (q 1)(q + 1) делится на 4;

противоречие.

Итак, r = 3 и, следовательно, 3p = q 4 q 2 + 1, откуда 3(3p1 1) = 2q 2 (q 2 1).

p Ясно, что 3 делит q 2 1. Положим t = 3. Тогда q2 (t 1)(t + 1) = 2q 2, и мы так же, как в случае 3), приходим к противоречию.

5) Пусть P Ap1 (r), где p нечетное простое число, r степень = некоторого простого числа s и (p, r) = (3, 2), (3, 4). Тогда rp = q 4 q 2 + 1.

(r 1)(p, r 1) Алгебра и топология Пусть (p, r 1) = 1. Тогда rp = q 4 q 2 + 1, r rp1 + · · · + r + 1 = q 4 q 2 + 1, r(rp2 + · · · + 1) = q 2 (q 2 1). Если (r, q) = 1,то r = q 2 и, следовательно, q 2(p2) + · · · + q 2 + 1 = q 2 1.

Но левая часть этого равенства больше q 2 1;

противоречие.

Итак, (r, q) = 1, поэтому r делит q 2 1. Имеем rp1 1 = q 2 (q p 1) r. Положим r1 = r 2. Тогда (r1 1)(r1 + 1) = q 2 (q 2 1) r1. Так r r как (r1 1, r1 + 1) делит 2 и q нечётно, то q 2 делит либо r1 1, либо r1 + 1.

Если q 2 делит r1 1, то r1 1 = aq 2 для некоторого a N и, следовательно, r q 2 (q 2 1) aq 2 (aq 2 + 2) = q 2 (q 2 1) q 2 (q 2 1);

r противоречие.

Итак, q 2 делит r1 + 1, т. е. r1 + 1 = aq 2 для некоторого a N.

Отсюда r aq 2 (aq 2 2) = q 2 (q 2 1) q(q 2 1).

r Если a 2, то a(aq 2 2) 2(2q 2 2) = 4(q 2 1) q 2 1;

противоречие.

Поэтому a = 1 и, следовательно, r(q 2 2) = (q 2 1)(r 1), откуда получаем q 2 r = 1, r = r1, p = 3. По лемме 2 q = 3 и r = 8. Отсюда P L3 (8). Ввиду леммы 1 и [7] имеем (G/F (G)) = {2, 3, 7}, 1 (G) = = {2, 3, 5, 7, 41}. Отсюда {5, 41} (F (G)) и, следовательно, в F (G), а значит, и в L есть полупростой элемент порядка 205. Этот элемент содержится в некотором максимальном торе T группы L, откуда делит |T |. Но это противоречит всем возможностям для |T |.

Список литературы [1]. Williams J.S. Prime graph components of nite groups // J. Alge bra. 1981. V. 69, № 2. P. 487-513.

[2]. Кондратьев А.С. О компонентах графа простых чисел конеч ных простых групп // Матем. сб. 1989. Т. 180, № 6. C. 787-797.

8 Труды XXXV Молодежной школы-конференции [3]. Мазуров В.Д. Распознавание конечных простых групп S4 (q) по порядкам их элементов // Алгебра и логика. 2002. Т. 41, № 2.

С. 166-198.

[4]. Алексеева О. А., Кондратьев А. С. О распознаваемости группы E8 (q) по множеству порядков элементов // Укр. матем. ж., 2002.

Т. 54, № 7. С. 1003-1008.

[5]. Алексеева О.А., Кондратьев А.С. Квазираспознаваемость од ного класса конечных простых групп по множеству порядков элементов // Сиб. матем. ж. 2003. Т. 44, № 2. С. 241-255.

[6]. Aschbacher M. Finite group theory. Cambridge: Cambridge Univer sity Press, 1986.

[7]. Conway J. H., Curtis R., Norton S., Parker R. A., Wilson R. A.

Atlas of nite groups. Oxford: Clarendon Press, 1985.

[8]. Стейнберг Р. Лекции о группах Шевалле. - М.: Мир, 1976.

[9]. Семинар по алгебраическим группам. - М.: Мир, 1973.

[10]. Кондратьев А.С., Мазуров В.Д. Распознавание знакоперемен ных групп простой степени по порядкам их элементов // Сиб.

матем. ж. 2000. Т. 41, № 2. С. 359-369.

[11]. Tiep Pham Huu. p-Steinberg characters of nite simple groups // J. Algebra. 1997. V. 187, № 1. P. 304-319.

[12]. Алеева М.Р. О конечных простых группах с множеством поряд ков элементов как у группы Фробениуса или двойной группы Фробениуса // Матем. заметки. 2003. Т. 73, № 3. С. 323-339.

[13]. Kleidman P.B. The maximal subgroups of the Steinberg triality groups 3 D4 (q) and of their automorphism groups // J. Algebra.

1988. V. 115, № 1. P. 182-199.

Алгебра и топология О ПОЧТИ ХОРОШИХ ПАРАХ В РЕБЕРНО РЕГУЛЯРНЫХ ГРАФАХ Белоусов И.Н., Гурский Е.И., Дергач А.С., Махнев А.А. e-mail: makhnev@imm.uran.ru Мы рассматриваем неориентированные графы без петель и крат ных ребер. Если a, b – вершины графа, то через d(a, b) обозначается расстояние между a и b, а через i (a) – подграф графа, индуциро ванный множеством вершин, которые находятся на расстоянии i в от вершины a. Подграф 1 (a) называется окрестностью вершины a и обозначается [a]. Граф называется реберно регулярным графом с параметрами (v, k, ), если содержит v вершин, является регуляр ным степени k и каждое ребро из лежит в треугольниках. Для реберно регулярного графа через b1 обозначим k 1.

В лемме 1.4.2 из [1] доказано, что если неполный связный реберно регулярный граф с параметрами (v, k, ), в котором 2k/3 1, (эквивалентно k 3b1 ), то имеет диаметр 2, v 2k 2 и выполняется неравенство () kb1 (v k 1)(k + 1 2b1 ).

В работе [2] получен аналог этого результата для реберно регу лярных графов с k 3b1 2.

Пусть реберно регулярный граф с параметрами (v, k, ). То гда степень вершины в любом µ-подграфе из не больше k 2b1.

Поэтому для µ = k 2b1 + 1 и любых вершин u, w, находящихся на расстоянии 2, выполняется неравенство µ(u, w) µ. Пару вершин (u, w), находящихся на расстоянии 2, назовем (почти) хорошей, если µ(u, w) = µ (если µ(u, w) = µ + 1). Расположение хороших и по чти хороших пар в реберно регулярных графах изучалось в [3],[4]. В данной работе продолжено изучение расположения почти хороших пар в реберно регулярных графах с k 3b1 4.

Теорема 1. Пусть связный реберно регулярный граф с пара метрами (v, k, ) и b1 = k 1. Если u, w, z две вершины из 2 (u), µ(u, w) = µ(u, z) = k 2b1 +2 и подграф = [u][w][z] содер жит 1 вершин, то либо вершины w, z несмежны, k 3b1 4, 1 Работа выполнена при финансовой поддержке Российского фонда фунда ментальных исследований (грант 04-01-81001).

10 Труды XXXV Молодежной школы-конференции причем в случае k = 3b1 4 получим = 2;

либо вершины w, z смежны и выполняется одно из следующих утверждений:

(1) подграф является 2-кокликой и k 3b1 1;

(2) подграф является кликой, и если содержит вершину d, окрестность которой не лежит в u [w] [z] и k/ge3b1 3, то = {d, e} и (a) k = 3b1 2 вершина e несмежна с вершиной f из [u][w][z] и с вершиной g из [u] [z] [w], подграф [w] [z] [u] содержит 2k 5 вершин, b1 3 из которых смежны с d, а остальные b1 вершин смежны с e, вершины f, g смежны и [f ] [g] содержит [w] [z] [d] {e}, или (b) k = 3b1 3, и либо e несмежна с вершиной из [u] [w] [z] и с вершиной из [u] [z] [w], либо (с точностью до перестановки вершин w и z) e несмежна с вершиной из [u] [w] [z] и смежна с вершиной из [z] ([u] [w]), причем в последнем случае подграф [w] [z] [u] содержит 2k 6 вершин, по b1 3 из которых смежны с d и с e.

В [5] доказано, что связный реберно регулярный граф диаметра 2 с 2k/3 2 (равносильно с k 3b1 3) либо совпадает с графом P (2) на 20 вершинах или с локально шестиугольным графом на вершинах, либо содержит не более 2k + 5 вершин. В теореме 2 этот результат уточняется.

Теорема 2. Пусть связный реберно регулярный граф диа метра 2 с k 3b1 3. Тогда либо совпадает с графом P (2) на вершинах, либо является локально шестиугольным графом на или 19 вершинах, либо число v вершин графа не больше 2k + 4.

Ключевую роль в доказательстве теоремы 1 играет следующий результат.

Лемма 1. Пусть является реберно регулярным графом с па раметрами (v, k, ). Если содержит две несмежные вершины u, w с µ(u, w) = k 1, {u } = [w] u, {w } = [u] w, то выполняются следующие утверждения:

(1) [u ] [u] [w] = [w ] [u] [w];

(2) если k 2b1, то вершины u, w несмежны и µ(u, w ) = k 1.

Доказательство. Пусть вершина d из [u] [w] имеет степень в графе [u] [w]. Если d смежна с w, то = + 1 и вершина d смежна Алгебра и топология с u. Если же d несмежна с w, то = и вершина d несмежна с u.

Утверждение (1) доказано.

Пусть a [u ] (u w ). Если a несмежна с w, то [a] [w] = ([a] [u]) {u }, причем для d [a] [u] имеем |[d] (a u )| = |[d] (a w )|. Степень d в графе [a] [u] равна степени d в графе [a] [w]. Если k 2b1, то u смежна с некоторой вершиной d из [a] [u], противоречие. Итак, каждая вершина из [u ] (u w ) смежна с w. Отсюда µ(u, w ) = k 1 и вершины u, w несмжны.

Лемма доказана.

Список литературы [1]. Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs // Springer-Verlag. - Berlin Heidelberg New York, 1989.

[2]. Махнев А.А., Минакова И.М. Об одном классе реберно регуляр ных графов // Известия Гомельского госуниверситета, Вопросы алгебры, 2000, т. 3 (16), 145–154.

[3]. Махнев А.А., Веденев А.А., Кузнецов А.Н., Носов В.В. О хо роших парах в реберно регулярных графах // Дискрет. матем.

2003, т. 15, 77–97.

[4]. Дрожевский А.В., Ищенко П.В., Махнев А.А., Паметов П.Ю.

О почти хороших парах вершин в реберно регулярных графах // Труды регион. молод. конф. "Проблемы теорет. и приклад.

матем.". - Екатеринбург 2003, 31–32.

[5]. Зарипов С.Р., Махнев А.А., Яблонко И.П. Реберно регулярные графы диаметра 2 с 2k/3 2 // Труды Украинского ма тем. конгресса, Киев 2001, секция 1: Алгебра и теория чисел, Институт математики НАН Украины. - Киев 2003, 46–61.

12 Труды XXXV Молодежной школы-конференции МИНИМАЛЬНЫЕ РЕГУЛЯРНЫЕ РАСШИРЕНИЯ ДВУХЭЛЕМЕНТНОЙ НУЛЕВОЙ ПОЛУГРУППЫ И ИХ ПРИМЕНЕНИЕ Булгакова А.А.

e-mail: anyahka@lipetsk.ru Цель работы найти минимальные регулярные расширения двух элементной нулевой полугруппы, показать их применение к постро ению алгебр внедуальных чисел расширений алгебры дуальных чисел, в которых каждое число если не обратимо, то обязательно обобщённо обратимо, и вывести формулы для соответствующих об ратных и обобщённо обратных элементов.

Рассмотрим двухэлементную нулевую полугруппу S0 = {0, } с операцией, где = 0. Полугруппа S0 не регулярна;

элемент регулярен, но элемент не регулярен: 0 0 0 = 0, 0 0 = 0, 0 = {0, }, = 0 =, 0 = 0 =.

Найдём минимальные регулярные расширения S0. Для этого рас смотрим множество M (S0 ), элементами которого являются матрицы всевозможных бинарных отношений на множестве S0 = {0, }:

0 0 0 0 0 0 1 M1 = M2 = M3 = M4 = 0 0 0 1 1 0 0 0 1 1 1 0 0 0 M5 = M6 = M7 = M8 = 0 0 0 0 1 1 0 1 0 1 0 0 1 1 M9 = M10 = M11 = M12 = 1 0 0 1 1 0 1 1 1 1 0 0 1 1 M13 = M14 = M15 = M16 = 0 1 1 1 1 1 1 M (S0 ) полугруппа с операцией умножения матриц, обычной во всём, кроме того, что 1 + 1 = 1. В этом можно убедиться, применив тест Лайта к элементам M2, M11, M12, составляющим порождающее множество M (S0 ) (см. [2]). Более того, M (S0 ) моноид с нейтраль ным элементом M10.

Все элементы моноида M (S0 ) регулярны, то есть имеют обобщён но обратные. Следовательно, и сам M (S0 ) регулярен.

Установим все соответствия 0 Mi и Mj. Очевидно, что нулю соответствует только M1. Соответствия Mj можно най ти, анализируя таблицу Кэли M (S0 ): если на главной диагонали на Алгебра и топология пересечении j-ой строки и j-ого столбца стоит M1, то Mj соответ ствует. Получаем, что M3 и M5. Введём следующие обозначения: M (S0 )3 = {M1, M3 }, M (S0 )5 = {M1, M5 }.

Для каждого вложения S0 M (S0 )3 M (S0 ) и S0 M (S0 ) M (S0 ) найдём все возможные минимальные регулярные расширения в рамках M (S0 ), которые обозначим M [(S0 )3 ]i и M [(S0 )5 ]i соответ ственно. Чтобы добиться регулярности M [(S0 )3 ]i (M [(S0 )5 ]i ), необ ходимо добавлять к M (S0 )3 (M (S0 )5 ) сначала обобщённо обратные к M3 (M5 ) и новые элементы, появляющиеся в таблице Кэли M [(S0 )3 ]i (M [(S0 )5 ]i ), а затем обобщённо обратные к уже добавленным элемен там, причём множества M [(S0 )3 ]i и M [(S0 )5 ]i должны быть замкну тыми. В итоге получили по четыре пятиэлементных минимальных регулярных расширения для M (S0 )3 и M (S0 )5, два из которых сов пали:

M [(S0 )3 ]1 = M [(S0 )5 ]1 = {M1, M2, M3, M4, M5 }, M [(S0 )3 ]2 = {M1, M3, M4, M6, M7 }, M [(S0 )3 ]3 = {M1, M2, M3, M8, M9 }, M [(S0 )3 ]4 = {M1, M3, M7, M9, M16 }, M [(S0 )5 ]2 = {M1, M2, M5, M6, M7 }, M [(S0 )5 ]3 = {M1, M4, M5, M8, M9 }, M [(S0 )5 ]4 = {M1, M5, M6, M8, M16 }.

Для каждой M [(S0 )3 ]i и M [(S0 )5 ]i (i = 1, 2, 3, 4) найдём мини мальные регулярные расширения R(S0 )j полугруппы S0, установив соответствия между их элементами:

1. R(S0 )1 = {0,,,, } M [(S0 )3,5 ]1 : M1 0, M3, M5, M2, M4 ;

2. R(S0 )2 = {0,,,, } M [(S0 )3 ]2 : M1 0, M3, M6, M4, M7 ;

M [(S0 )3 ]3 : M1 0, M3, M8, M9, M2 ;

M [(S0 )3 ]4 : M1 0, M3, M16, M9, M7 ;

M [(S0 )5 ]2 : M1 0, M5, M7, M2, M6 ;

M [(S0 )5 ]3 : M1 0, M5, M9, M8, M4 ;

M [(S0 )5 ]4 : M1 0, M5, M16, M8, M6.

Полугруппы R(S0 )1 и R(S0 )2 задаются таблицами Кэли:

14 Труды XXXV Молодежной школы-конференции R(S0 )1 0 0 0 = {0,,,, }, =, =, =, = R(S0 )2 0 0 0 = {0,,,, }, =, = {,,, }, = {, }, = {, } В итоге найдены два пятиэлементных минимальных регулярных расширения двухэлементной нулевой полугруппы, которые не изо морфны.

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

Дуальные числа это числа вида v = a + b, где a, b действи базисный элемент, 2 = 0. Кольцо V дуальных тельные числа, чисел наделено операциями сложения и умножения:

v1 + v2 = (a1 + b1 ) + (a2 + b2 ) = (a1 + a2 ) + (b1 + b2 ), v1 · v2 = (a1 + b1 )(a2 + b2 ) = a1 a2 + (a1 b2 + b1 a2 ).

Дуальные числа допускают представление матрицами вида a, (v) = detV = a2. При (v) = 0 дуальное число обра V= ba тимо, причём v 1 = ab. При (v) = 0, т. е. a = 0, дуальное число (v) b необратимо, а при b = 0 такое число и не обобщённо обратимо.

Построим кольца W(1) и W(2) внедуальных чисел, содержащие кольцо V в качестве подкольца и такие, что необратимые дуальные числа b (b = 0), не обобщённо обратимые в V, обобщённо обра тимы в W(1) и W(2). Внедуальные числа из W(1) это числа вида Алгебра и топология w(1) = a + b + c + d + e, где a, b, c, d, e действительные чис ла,,,, базисные элементы, перемножаемые в соответствии с таблицей Кэли R(S0 )1. Кольцо W(1) внедуальных чисел наделено операциями сложения и умножения:

(1) (1) w1 + w2 = (a1 + b1 + c1 + d1 + e1 ) + (a2 + b2 + c2 + d2 + e2 ) = (a1 + a2 ) + (b1 + b2 ) + (c1 + c2 ) + (d1 + d2 ) + (e1 + e2 ), (1) (1) w1 · w2 = (a1 + b1 + c1 + d1 + e1 )(a2 + b2 + c2 + d2 + e2 ) = a1 a2 + (a1 b2 + b1 a2 + b1 e2 + d1 b2 ) + (a1 c2 + c1 a2 + c1 d2 + e1 c2 ) + (a1 d2 + b1 c2 + d1 a2 + d1 d2 ) + (a1 e2 + c1 b2 + e1 a2 + e1 e2 ).

Внедуальные числа из W(1) допускают представление матрицами ви да a 0 0 0 b a+e 0 b c c (1) 0 a+d W = d c 0 a+d e 0 b 0 a+e (w(1) ) = detW(1) = a 2 (w(1) ), где = (w(1) ) = (a + d)(a + e) bc.

Обозначим µ = µ(w(1) ) = de bc. Тогда = a(a + d + e) + µ.

При (w(1) ) = 0 внедуальное число обратимо, причём [w(1) ]1 = 2 abac(µ+ad)(µ+ae). При (w(1) ) = 0 внедуальное число (w(1) ) необратимо, но обобщённо обратимо: при a = 0, = µ = 0 [w(1) ] = b c e d x µ µ (x µ ) (x µ );

при a = 0, = 0 [w(1) ] = µ a1 + y + b1 [ a2 cy (a + d)s (a + e)t] + s + t;

при a = = µ = [w(1) ] = x + y + b1 [1 (d + e)x cy ds et] + s + t, где x, y, s, t произвольные действительные числа.

Внедуальные числа из W(2) это числа вида w(2) = a + b + c + d + e, где a, b, c, d, e действительные числа,,,, базисные элементы, перемножаемые в соответствии с таблицей Кэли R(S0 )2.

Кольцо W(2) внедуальных чисел наделено операциями сложения и умножения:

(2) (2) w1 + w2 = (a1 + b1 + c1 + d1 + e1 ) + (a2 + b2 + c2 + d2 + e2 ) = (a1 + a2 ) + (b1 + b2 ) + (c1 + c2 ) + (d1 + d2 ) + (e1 + e2 ), (2) (2) w1 ·w2 = (a1 +b1 +c1 +d1 +e1 )(a2 +b2 +c2 +d2 +e2 ) = a1 a2 + 16 Труды XXXV Молодежной школы-конференции (a1 b2 + b1 a2 + b1 d2 + e1 b2 + e1 d2 ) + (a1 c2 + c1 a2 + c1 c2 + c1 e2 + d1 c2 ) + (a1 d2 + c1 b2 + c1 d2 + d1 a2 + d1 d2 ) + (a1 e2 + b1 c2 + e1 a2 + e1 c2 + e1 e2 ).

Внедуальные числа из W(2) допускают представление матрицами a 0 0 0 b a+e 0 b+e W(2) = c c 0 a+c+d d c 0 a+c+d e 0 b+e 0 a+e (w(2) ) = detW(2) = a 2 (w(2) ), где = (w(2) ) = (a + e)(a + c + d) c(b+e). Обозначим µ = µ(w(2) ) = debc. Тогда = a(a+c+d+e)+µ.

При (w(2) ) = 0 внедуальное число обратимо, причём [w(2) ]1 = 2 +(µab)ac(µ+ad)(µ+ae). При (w(2) ) = 0 внедуальное (w(2) ) число необратимо, но обобщённо обратимо: при a = 0, = µ = [w(2) ] = x+(x b+c+d+e ) µ (x c+e )(x c+d );

при a = 0, = c µ µ µ µ 0 [w(2) ] = a1 +c1 [ a2 (2a+b+2c+2d+e)y(a+c+e)t]+y+y+t;

при a = = µ = 0 [w(2) ] = x + y + 1(c+d+e)xcy(c+e)t + b+2c+2d+e 1(c+d+e)xcy(c+e)t + t, где x, y, t произвольные действитель b+2c+2d+e ные числа. Дуальные числа b, необратимые и не обобщённо обра тимые в V, обобщенно обратимы в W(1) и W(2), причём [(b)(1) ] = x + y + b1 + s + t, [(b)(2) ] = x + y + b1 + b1 + t, где x, y, s, t произвольные действительные числа.

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

Список литературы [1]. Биркгоф Г., Барти Т. Современная прикладная алгебра. - М.:

Мир, 1976. C. 281–293.

[2]. Клиффорд А.Х., Престон Г.Б. Алгебраическая теория полу групп. - М.: Мир, 1972. Т. 1. С. 23–24.

Алгебра и топология О РАСПОЗНАВАЕМОСТИ КОНЕЧНЫХ ПРОСТЫХ ОРТОГОНАЛЬНЫХ ГРУПП Васильев А.В., Гречкосеева М.А.

Спектром (G) конечной группы G называется множество по рядков ее элементов. Конечная группа G называется распознаваемой по ее спектру (кратко, распознаваемой), если для каждой конечной группы H такой, что (H) = (G), имеет место изоморфизм H G.

Поскольку любая конечная группа, обладающая нетривиальной раз решимой нормальной подгруппой, нераспознаваема (см. лемму 1 в [1]), то особый интерес представляет вопрос о распознаваемости про стых и почти простых групп (группа G называется почти простой, если S G Aut(S) для некоторой неабелевой простой группы S). Первые примеры распознаваемых конечных простых групп бы ли указаны Ши и Брандлом в середине 80-х годов прошлого века.

Они же в 1994 году доказали распознаваемость бесконечной серии простых линейных групп L2 (q), q = 9. К настоящему времени ре шен вопрос о распознаваемости (или нераспознаваемости) для всех групп, простые делители которых не превосходят 13 (см. [2]), до казана распознаваемость нескольких бесконечных серий конечных простых и почти простых групп. Список групп, для которых к на стоящему времени решен вопрос распознаваемости см. в [2]. Одна ко, все имеющиеся примеры распознаваемых групп, исключая знако переменные и симметрические группы подстановок, ограничены по размерности в следующем смысле. В силу классификационной тео ремы все конечные простые неабелевы группы кроме знакоперемен ных групп подстановок и 26 спорадических групп являются груп пами лиева типа. Лиев ранг любой конечной группы, для которой решен вопрос о ее распознаваемости, не превосходит 6 для скручен ных групп и 5 для нескрученных. В частности, размерность извест ных распознаваемых классических групп, то есть групп, имеющих 1 Работа выполнена при финансовой поддержке Российского фонда фундамен тальных исследований, проекты 02-01-00495 и 02-01-39005, Совета по грантам президента РФ и государственной поддержки ведущих научных школ, проект НШ-2069.2003.1, СО РАН, грант для коллективов молодых ученых, Постановле ние Президиума СО РАН N 404 от 06.12.2002, а также программы "Университеты России", проект УР.04.01.028.

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

А именно, серии ортогональных групп O2k +1 (2) и O2k +2 (2). Так как доказательство результата в основном опирается на лиев подход к описанию соответствующих групп, то в дальнейшем мы будем при держиваться лиевой нотации.

Теорема 1. Для каждого натурального числа m 2 группы C2m (2) и 2 D2m +1 (2) распознаваемы.

Замечание 1. Имеют место следующие изоморфизмы:

C2m (2k ) S2·2m (2k ) O2·2m +1 (2k ), 2 D2m +1 (q) O2·2m +2 (q).

Замечание 2. Распознаваемость группы 2 D5 (2) доказана в [3]. Не распознаваемость групп C2 (2) S4 (2) и 2 D3 (2) U4 (2) установлена соответственно в [4] и [5]. Группа же C4 (2) не является распознавае мой, так как ее спектр совпадает со спектром естественного расши рения группы 2 D4 (2) с помощью внешнего автоморфизма порядка 2. Последний факт несложно проверить, используя [6]. Таким обра зом, по модулю теоремы 1 вопрос о распознаваемости групп C2m (2) и 2 D2m +1 (2) полностью закрыт для любого натурального числа m.

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

Для ее формулировки мы воспользуемся удобным термином, пред ложенным недавно в [7]. Конечная простая неабелева группа G назы вается квазираспознаваемой, если каждая конечная группа H такая, что (H) = (G), имеет композиционный фактор, изоморфный G.

Теорема 2. Пусть m и k произвольные натуральные числа.

Группа G квазираспознаваема в каждом из следующих случаев:

а) G = 2 D2m (2k );

Алгебра и топология б) G = 2 D2m +1 (2) и m = 1;

в) G = C2m (2k ) и m 2.

Замечание 3. Тот факт, что группа 2 D3 (2) U4 (2) не является ква зираспознаваемой, следует из доказательства предложения 6 в [5].

То, что группы C2 (2k ) не являются квазираспознаваемыми, следует из предложения 1 в [2]. Группа C4 (2) не является квазираспозна ваемой в силу аргумента, приведенного в замечании 2 к теореме 1.

Вопрос о квазираспознаваемости групп C4 (2k ) при k 1 остается открытым. Наконец, поскольку распознаваемость групп 2 D2 (2k ) A1 (22k ) была установлена еще Брандлом и Ши, то при доказатель стве теоремы мы можем считать, что m 1.

Список литературы [1]. Мазуров В.Д., О множестве порядков элементов конечной груп пы, Алгебра и логика, 33, N 1, 1994, 81-89.

[2]. Мазуров В.Д., Распознавание конечных простых групп S4 (q) по порядкам их элементов, Алгебра и логика, 41, N 2, 2002, 166 198.

[3]. Shi W., Tang C.J., A characterization of some orthogonal groups, Prog. Nat. Sci, 7, N 2, 1997, 155-162.

[4]. Мазуров В.Д., Су М.Ч., Чао Х.П., Распознавание конечных про стых групп L3 (2m ) и U3 (2m ) по порядкам их элементов, Алгебра и логика, 39, N 5, 2000, 567-585.

[5]. Мазуров В.Д., Распознавание конечных простых групп по мно жеству порядков их элементов, Алгебра и логика, 37, N 6 1998, 651-666.

[6]. Conway J.H., Curtis R.T., Norton S.P., Parker R.A., Wilson R.A., Atlas of nite groups. - Oxford: Clarendon Press, 1985.

[7]. Алексеева О.А., Кондратьев А.С., Квазираспознаваемость од ного класса конечных простых групп по множеству порядков элементов, Сиб. матем. ж., 44, N 2, 2003, 241-255.

20 Труды XXXV Молодежной школы-конференции ВПОЛНЕ РЕГУЛЯРНЫЕ ГРАФЫ И БЛОК-СХЕМЫ Гаврилюк А.Л., Махнев А.А. e-mail: makhnev@imm.uran.ru Мы рассматриваем неориентированные графы без петель и крат ных ребер. Если a, b – вершины графа, то через d(a, b) обозначается расстояние между a и b, а через i (a) – подграф графа, индуциро ванный множеством вершин, которые находятся на расстоянии i в от вершины a. Подграф 1 (a) называется окрестностью вершины a и обозначается [a].

Граф называется вполне регулярным графом с параметрами (v, k,, µ), если содержит v вершин, является регулярным степени k, каждое ребро из лежит в треугольниках, и подграф [a] [b] содержит µ вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.

Если вершины u, w находятся на расстоянии i в, то через bi (u, w) (через ci (u, w)) обозначим число вершин в пересечении i+1 (u) (i1 (u)) с (w). Граф диаметра d называется дистанционно ре гулярным с массивом пересечений {b0, b1,..., bd1 ;

c1,..., cd }, если значения bi (u, w) и ci (u, w) не зависят от выбора вершин u, w на расстоянии i в.

Система инцидентности (X, B) с множеством точек X и множе ством блоков B называется t-(V, K, ) схемой, если |X| = V, каждый блок инцидентен ровно K точкам и любые t точек инцидентны ров но блокам. Любая 2-схема является (V, B, R, K, ) схемой, где B число блоков, каждая точка инцидентна R блокам, и имеют место равенства V R = BK, (V 1) = R(K 1).

Блок-схемы естественно возникают внутри сильно регулярных графов. Например, если для клики или коклики X графа дости гается равенство в границе Хоффмана (см. [1]), то пара (X, X) является 2-схемой. В монографии Камерона-Ван Линта [2], § 8 рас сматривается возможность, когда в сильно регулярном графе для некоторой вершины a пара ((a), 2 (a)) является 2-схемой, в кото рой точка и блок инцидентны, только если они смежны в. Важный класс примеров дают сильно регулярные графы без треугольников.

1 Работа выполнена при финансовой поддержке Российского фонда фунда ментальных исследований (грант 02-01-00772).

Алгебра и топология В данной работе исследуются вполне регулярные графы диа метра d, в которых для некоторой вершины a пара (d (a), d1 (a)) является 2-схемой. В таком графе d (a) является кликой, кокликой или сильно регулярным графом.

Теорема 1. Пусть вполне регулярный граф диаметра 3, име ющий параметры (v, k,, µ). Тогда следующие утверждения равно сильны:

(1) является дистанционно регулярным графом, в котором для каждой вершины a подграф 3 (a) является кликой, кокликой или сильно регулярным графом с параметрами (v, k,, µ ), где =µµ;

(2) для любой вершины a пара (3 (a), 2 (a)) является 2-схемой.

В работе рассмотрены также вполне регулярные графы диаметра 3, в которых для некоторой вершины a пара (3 (a), 2 (a)) является 2-схемой и подграф 3 (a) граф Зейделя (сильно регулярный граф с собственным значением 2). Хорошо известно, что граф Зейделя это полный многодольный граф Kr2, nn решетка, треугольный граф T (m), граф Петерсена, Клебша, Шрикханде, Шлефли или один из трех графов Чанга.

Теорема 2. Пусть вполне регулярный граф диаметра 3. Ес ли для некоторой вершины a пара (3 (a), 2 (a)) является 2-схемой и = 3 (a) граф Зейделя, то выполняется одно из следующих утверждений:

(1) граф Петерсена и схема (, 2 (a)) имеет параметры (10, 30, 12, 4, 4);

(2) является n n решеткой и либо схема (, 2 (a)) имеет параметры (n2, 4n2, 2(n + 1), (n + 1)/2, 1), где n нечетно, либо для n 50 верно одно из утверждений:

(i) n = 3, схема (, 2 (a)) имеет параметры (9, 24, 8, 3, 2), (ii) n = 4, схема (, 2 (a)) имеет параметры (16, 360, 90, 4, 18), (iii) n = 6, схема (, 2 (a)) имеет параметры (36, 225, 50, 8, 10), 22 Труды XXXV Молодежной школы-конференции (iv) n = 10, схема (, 2 (a)) имеет параметры (100, 825, 132, 16, 20), (v) n = 21, схема (, 2 (a)) имеет параметры (441, 2940, 80, 12, 2);

(3) треугольный граф T (n) и для n 50 верно одно из утвер ждений:

(i) n = 9, схема (, 2 (a)) имеет параметры (36, 84, 14, 6, 2), (ii) n = 11, схема (, 2 (a)) имеет параметры (55, 264, 48, 10, 8), (iii) n = 14 и схема (, 2 (a)) имеет параметры либо (91, 195, 15, 7, 1), либо (91, 546, 60, 10, 6), (iv) n = 15 и схема (, 2 (a)) имеет параметры либо (105, 910, 104, 12, 11), либо (105, 520, 104, 21, 20), (v) n = 17, схема (, 2 (a)) имеет параметры (136, 8568, 378, 6, 14), (vi) n = 20, схема (, 2 (a)) имеет параметры (190, 513, 135, 50, 35), (vii) n = 25, схема (, 2 (a)) имеет параметры (300, 4600, 414, 27, 36), (viii) n = 35, схема (, 2 (a)) имеет параметры (595, 22440, 1056, 28, 48).

Если граф из заключения теоремы 2 является дистанционно ре гулярным, то не может быть графом Петерсена или 33 решеткой.

Интересным представляется вопрос о существовании графа, в кото ром третья окрестность каждой вершины является 6 6 решеткой.

Этот гипотетический граф имеет массив пересечений {60, 45, 8;

1, 12, 50}, спектр {601, 1445, 0207, 1069 }, и граф 2 сильно регулярен с параметрами (322, 225, 160, 150).

Список литературы [1]. Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs // Springer-Verlag. - Berlin Heidelberg New York. 1989.

[2]. Cameron P.J., van Lint J. Graphs, Codes and Desidns. London Math. Soc. Lecture Notes №43. - Cambridge: Cambridge Univ.

Press. 1980.

Алгебра и топология ЦЕПИ ДНК И ПРОБЛЕМА РАСПОЗНАВАНИЯ ТРИВИАЛЬНОГО УЗЛА Давыдов О.М., Перевалов Д.С. e-mail: davydov@csu.ac.ru, denis.perevalov@mail.ru Биологическая постановка задачи.

В настоящее время главным объектом изучения биологии явля ется ДНК – молекула дезоксирибонуклеиновой кислоты, составляю щая основу наследственности всех живых организмов. Эта молеку ла представляет собой спираль, состоящую из двух комплементар ных антипараллельных полинуклеиновых нитей. Полинуклеотидная нить состоит из блоков-нуклеотидов мономеров нуклеиновых кис лот с пиримидиновым основанием: цитозин (C), тимин (T );

или пу риновым основанием: аденин (A), гуанин (G). Две цепи-нити удер живаются вместе и скручиваются в спираль, благодаря водородным связям между азотистыми основаниями этих цепей.

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

В то же время некоторые важные биологические процессы связа ны с геометрическими свойствами расположения ДНК в простран стве, и потому такие свойства требуют изучения, выходящего за рам ки комбинаторного анализа букв. Одно такое свойство – заузлен ность ДНК. Оказывается, что от топологического типа узла, кото рый соответствует данной молекуле, зависят ее физические свойства 1 Работа поддержана грантом РФФИ 02–01–01013. Авторы выражают благо дарность Руслану и Михаилу Шматковым (ИМ СО РАН), Марии Куликовой (ЮУрГУ), Денису Ильютко (МГУ) и Сергею Валентиновичу Ленскому (УрГУ) за предоставленные материалы и ценные замечания в ходе работы над статьей, а также Светлане Татур (УрГУ) за подготовку иллюстрации ДНК.

24 Труды XXXV Молодежной школы-конференции Рис. 1: ДНК – скорость движения в геле и функциональные – взаимодействие с ферментами.

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

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

Отметим, что данные методы можно применять в двух направ лениях:

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

2. для автоматического анализа заузленности ДНК при числен ном моделировании расположения молекулы в пространстве.

Задача распознавания тривиального узла. У проблемы рас познавания тривиального узла давняя и богатая событиями история.

Первый такой алгоритм был предложен У. Хакеном в 1961 году. Ал горитм Хакена был универсальным (распознавал любой тривиаль ный узел), но практически нереализуемым, причем не столько из-за своей сложности, сколько из-за трудностей в его программистской реализации. Впоследствии, на основе идеологии Хакена, строились различные алгоритмы, универсальные и частичные, позволяющие распознавать и развязывать тривиальный узел.

Узлы и их эквивалентность.

Узел это образ окружности при некотором гомеоморфизме пространства S 3. Напомним, что изображаются узлы в виде про екций на плоскость;

проекция будет иметь самопересечения: разные точки узла будут проектироваться в одну. Проекция называется пра вильной, если:

1) в одну точку плоскости проектируется не более двух точек узла;

2) проекция касательной к веревочке в любой точке представляет собой прямую (а не вырождается в точку!);

3) множество перекрестков точек проекции, в которые проек тируется две различных точки узла – конечно и проекции касатель ных в соответствующих данному перекрестку двух точках узла не совпадают.

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

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

Классическая теорема Райдемайстера гласит: два узла эквива лентны тогда и только тогда, когда от одного к другому можно пе ±1 ±1 ± рейти последовательностью преобразований R1, R2 R3.

Рис. 2: Преобразования R1, R2, R Проблема распознавания тривиального узла заключается в отве те на вопрос: эквивалентен ли данный узел стандартному вложению окружности в R3 (например x2 + y 2 = 1, z = 0)?

Метод Дынникова.

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

Пусть P1, P2, P3 - три полуплоскости в евклидовом пространстве R3, границы которых совпадают: P1 = P2 = P3 = l. Обозначим их объединение P1 P2 P3 через Y. На прямой l выберем ориента цию.

Трехстраничной диаграммой зацепления назовeм замкнутую ло маную линию L Y, удовлетворяющую следующим двум условиям:

1)трансверсальность к прямой l: пересечение L l конечно, L l = A1... Am, и два ребра ломаной L, примыкающие к вер шине Ak, лежат в различных полуплоскостях Pi для любого k m;

2)монотонность: ограничение ортогональной проекции R l R на каждую из связных компонент пересечения L Pi является монотонной функцией для любого i=1,2,3.

Теорема 1. (Дынников [13]) Любое зацепление можно предста вить трехстраничной диаграммой.

Рассмотрим множество A, состоящее из следующих двенадцати Алгебра и топология векторов:

0 0 0 a1 = 1, b1 = 1, c1 = 1, d1 = 1, 1 1 1 1 1 1 a2 = 0, b2 = 0, c2 = 0, d2 = 0, 1 1 1 1 1 1 a3 = 1, b3 = 1, c3 = 1, d3 = 1.

0 0 0 Пусть дана некоторая неориентированная трехстраничная диаграм ма L. Обозначим, как и раньше, вершины из L l через A1,..., Am, занумеровав их в порядке следования на линии переплета l. Каж дой вершине Ak сопоставим ее тип - вектор xk A, определенный по следующему правилу: i-я координата вектора xk для i {1, 2, 3} равна 1, если Ak - левый конец некоторого ребра, лежащего в полуплоскости Pi, -1, если A - правый конец некоторого ребра, k xi = k лежащего в полуплоскости Pi, 0, если Ak - не является концом ребра, лежащего в Pi.

Трехстраничной диаграмме L сопоставляем следующее слово в алфавите A:

wL = x1... xm.

Доказано, что такое слово задает зацепление, если для всех i = p n xi = 0 и для любого 1 p n xi 1, 2, 3 k k i=1 i= Например, трехстраничной диаграмме зацепления Уайтхеда, со ответствует слово:

a1 a2 d1 a3 d2 d1 d3 d2 d2 d1 d3 c2 c2 c 28 Труды XXXV Молодежной школы-конференции Рис. 3: Диаграмма задается словом a1 a2 d1 a3 d2 d1 d3 d2 d2 d1 d3 c2 c2 c Слова в данном алфавите образует моноид с достаточно длин ным списком соотношений. Проблема распознавания тривиального узла таким образом сводится к проблеме распознавания тривиаль ного слова, для чего Дынниковым построено несколько эффективно работающих частичных алгоритмов.

Метод Матвеева. Алгоритм был построен Матвеевым в книге [16] на основе метода Хакена и теории нормальных поверхностей.

Вообще говоря, проблему можно свести к распознаванию почти про стого спайна дополнения к узлу в трехмерной сфере (спайны шара и сферы совпадают по определению: спайном замкнутого многообра зия M называется спайн многобразия M \ B 3, где B 3 трехмерный шар).

Список литературы [1]. Pickering W. R. Advanced Biology Oxford University Press, 1996.

128 p.

[2]. Setubal J., Meidanis J. Introduction to Molecular Computational Biology. PWS Publ. Comp., 1997.

[3]. Waterman M.S. Introduction to Computational Biology Chapman and Heil, 1995.

[4]. Sumners W. Lifting the Curtain: Using Topology to Probe the Hid den Action of Enzymes //Notices of the AMS, 42(5), 1995. P. 528– 537.

Алгебра и топология [5]. Sogo J.M., Stasiak A., Martinez-Roblez M.L., Krimer P.B., Her nandez P., Schwartzman J.B. Formation of Knots in Partially Repli cated DNA Molecules //J. Mol. Biol., 286, 1999. P. 637–643.

[6]. Wang J. C. DNA Topoisomerases: Why So Many? //J. Biol. Chem., 266, 1991. P. 6659–6672.

[7]. Vologodskii A.V., Crisow N.J., Laurie B., Pieranski P., Katritch V., Dubochet J., Stasiak A. Segmentation and electrophoretic Migration of DNA Knots and Catenanes // J. Mol. Biol., 278, 1998. P. 1–3.

[8]. Stasiak A., Katritch V., Bendar J., Muchoud D., Dubochet J. Elec trophorethic Mobility of DNA Knots //Nature, 384, 1996. 122 p.

[9]. Katritch V., Bendar J., Muchoud D., Sharein R. G. Dubochet J., Stasiak A. Geometry and Physics of Knots //Nature, 384, 1996. P.

142–145.

[10]. Laurie B., Katritch V., Sogo J., Kollen T., Dubochet J., Stasiak A.

Geometry and Physics of Catenanes Applied to the Study of DNA Replication //Biophys. J., 74, 1998. P. 2815–2828.

[11]. Katritch V., Olson W., Pieranski P., Dubochet J., Stasiak A. Prop erties of Ideal Composite Knots //Nature, 388, 1997. P. 148–151.

[12]. Pieranski P., Przybyl S., Stasiak A. Tight Open Knots //Eur. Phys.

J., E6, 2002. P. 123–128.

[13]. Дынников И. А. Трехстраничное представление зацеплений.

УМН, т. 53, вып. 5., 1998. C. 237–238.

[14]. Дынников И. А. Трехстраничный подход в теории узлов. Ко дирование и локальные движения, Функ. анализ и его приложе ния, т.33, вып. 4. C. 25–37.

[15]. Dynnikov I. A. A new way to represent links. One-dimensional formalism and untangling technology. Acta Appl. Math. V. 69. 2001.

P. 243–283.

[16]. Matveev S. V. Algorithmic topology and classication of 3 manifolds. Springer - Verlag. 2003. 450 p.

30 Труды XXXV Молодежной школы-конференции ОБ АВТОМОРФИЗМАХ ГРАФОВ С ПАРАМЕТРАМИ (115, 18, 1, 3) Кабанов В.В., Ткачева И.М. e-mail: vvk@imm.uran.ru Мы рассматриваем неориентированные графы без петель и крат ных ребер. Если a, b – вершины графа, то через d(a, b) обозначается расстояние между a и b в графе, а через i (a) – подграф графа, порожденный множеством вершин, которые находятся на рассто янии i в от вершины a. Подграф 1 (a) называется окрестностью вершины a и обозначается через [a]. Через a обозначается подграф на [a] {a}.

Граф называется регулярным графом степени k, если [a] содер жит точно k вершин для любой вершины a из. Граф называется реберно регулярным графом с параметрами (v, k, ), если содер жит v вершин, является регулярным степени k, и каждое ребро из лежит точно в треугольниках. Граф называется вполне регу лярным графом с параметрами (v, k,, µ), если реберно регуля рен с соответствующими параметрами и подграф [a] [b] содержит µ вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Граф называется силь ным с параметрами (, µ), если каждое ребро из лежит точно в треугольниках и подграф [a] [b] содержит µ вершин для любых несмежных a, b. Число вершин в [a] [b] обозначим через (a, b) (че рез µ(a, b)), если d(a, b) = 1 (если d(a, b) = 2), а соответствующий подграф назовем -подграфом (µ-подграфом).

Подграфы неподвижных точек автоморфизмов сильно регуляр ного графа с малыми значениями параметров и µ имеют жестко заданное строение. Так подграф множества неподвижных точек ав томорфизма графа Мура сам является графом Мура или звездой (см. лемму 1 [1]).

Основным результатом работы является следующая теорема:

Теорема. Пусть является сильно регулярным графом с пара метрами (115, 18, 1, 3), G = Aut(). Если p элемент нечетного 1 Работа выполнена при финансовой поддержке Российского фонда фунда ментальных исследований (грант 02-01-00772).

Алгебра и топология простого порядка из G, = Fix(p), то выполняется одно из утвер ждений:

(1) |p| = 3, каждая связная компонента графа является одно вершинным графом и || 13 или является вполне регулярным графом с = 1, µ = 3;

(2) |p| = 5 или 23, является пустым графом.

Доказательство теоремы опирается на метод Дональда Хигме на работы с автоморфизмами сильно регулярного графа, предло женный в третьей главе монографии Камерона [2]. сильно ре гулярный граф, имеющий параметры (115, 18, 1, 3), G = Aut(), P иQ матрицы собственных значений соответствующей 2-схемы, 1 характер представления на подпространстве размерности G 1 1 1 1 1 45. Тогда P = 18 3 5, Q = 69 23/2 23/8, и 96 4 4 45 25/2 15/ 2 (g) = 1/8(30 (g) 1 (g) + 15) для любого g G.

Список литературы [1]. Махнев А.А., Падучих Д.В. Об автоморфизмах графа Ашбахе ра // Алгебра и логика 2001, T. 40, № 2, C. 125–134.

[2]. Cameron P. Permutation Groups, London Math. Soc. Student Texts 45. - Cambridge: Cambridge Univ. Press, 1999.

[3]. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: Springer-Verlag, 1989.

[4]. Willbrink H.A., Brouwer A.E. A (57, 14, 1) strongly regular graph does not exist// Proc. Kon. Nederl. Akad. Ser. A, 1983. Vol. 45, N 1. P. 117–121.

32 Труды XXXV Молодежной школы-конференции ГРАФЫ БЕЗ 3-ЛАП С ОГРАНИЧЕНИЯМИ НА ПОРЯДКИ µ-ПОДГРАФОВ Кабанов В.В., Сабирзянова Е.Ш.

e-mail: vvk@imm.uran.ru Мы рассматриваем только конечные неориентированные графы без петель и кратных ребер. Пусть граф с множеством вершин V () и множеством ребер E(). Будем писать x y и говорить, что вершины x и y смежны, в том случае, когда {x, y} ребро из E(). Далее всюду, если не оговорено противное, подграф из будет означать порожденный подграф графа, то есть подграф, в кото ром вершины смежны тогда и только тогда, когда они смежны в.

Если a вершина графа, то через [a] будем обозначать окрест ность вершины a, то есть множество вершин графа, смежных с a, а через a объединение [a] {a}, которое назовем замкнутой окрестностью. Для двух несмежных вершин a, b графа, положим M (a, b) = a b. Подграф, порожденный множеством M (a, b) бу дем называть µ-подграфом вершин a и b, если они находятся на расстоянии два в.

Полный граф с числом вершин n будем обозначать Kn, тогда вполне несвязный граф с n вершинами это его дополнение. Пол ный многодольный граф с долями, состоящими из m1, m2,..., mk обозначим через Km1,m2,...,mk. Под 3-лапой будем понимать граф K1,3. Путь на n вершинах обозначается через Pn. Для двух вер шин x и y графа обозначим через d(x, y) расстояние между ними в. Реберный граф L() графа это граф на ребрах графа, причем два ребра смежны в нем в том и только в том случае, когда они имеют одну общую вершину. Реберный граф полного двудоль ного графа с долями из m и n вершин называется m n-решеткой.

Реберный граф полного графа Kn называется треугольным графом T (n). Треугольные графы T (n) при n 3 и mn-решетчатые графы не содержат 3-лап и любая пара несмежных вершин в этих графах лежит в порожденном 4-цикле. Более того, число вершин в любом µ-подграфе равно 4 для треугольного графа и 2 для решетчатого.

Это свойство послужило основанием для данной работы.

Рассмотрим следующие условия, налагаемые на граф :

(i) не содержит 3-лап;

Алгебра и топология (ii) для любых двух вершин a, b лежащих в порожденном 4-цикле в число вершин в M (a, b) равно µ;

(iii) для любых двух вершин a, b находящихся в на расстоянии 2 друг от друга и не лежащих в порожденном 4-цикле в число вершин в M (a, b) равно и µ.

Графы, удовлетворяющие условиям (i) (iii) были классифици рованы в работе [1] В.В. Кабановым и А.А. Махневым при условии, что = µ. При этом оказалось, что если граф содержит пару вер шин, лежащих в порожденном 4-цикле, то любая пара несмежных вершин в этом графе содержится в порожденном 4-цикле. В.В. Ка банов высказал гипотезу о том, что это свойство выполняется и для графов, удовлетворяющих условиям (i) (iii) без предположения о равенстве = µ. Работа посвящена доказательству этой гипотезы.

Список литературы [1]. Кабанов В.В., Махнев А.А. Графы без 3-лап с равномощными µ-подграфами // Изв. Урал. гос. ун-та. 1998. №10. (Математика и механика. Вып.1.) С. 44–68.

34 Труды XXXV Молодежной школы-конференции О ПОЛУГРУППЕ ИНТЕРВАЛЬНЫХ ОКРУГЛЕНИЙ Крюкова А.Л.

e-mail: krukova@vologda.ru Интервальным округлением (I-округлением) [1] называется отоб ражение множества IR всех ограниченных замкнутых интервалов вещественной прямой в себя, удовлетворяющее аксиомам:

O1 : (A IR) (A (A)), O2 : (A, B IR) (A B (A) (B)), O3 : 2 =.

Произведение понимается как композиция отображений и, то есть их последовательное выполнение.

Множество всех интервальных округлений обозначим. Приме рами I-округлений являются отображения (k, l), действующие по правилу (k, l) (A) = [a ;

b+ ], где A = [a, b], a – результат обычного k l k (числового) округления a по недостатку до k-го (десятичного) раз ряда, а b+ – результат округления b до l-го разряда по избытку (k, l l – любые целые числа). Такие округления называются регулярными (r-округлениями).

Множество всех r-округлений, дополненное тождественным отоб ражением и отображениями (k, ) и (, l) :

(k, ) (A) = [a ;

b], (, l) (A) = [a;

b+ ], k l обозначим (Z). В множестве содержится также отображения, ма ло похожие на округления, понимаемые в интуитивном смысле. При мером может служить отображение M = [ max(| a |, | b |);

max(| a |, | b |)].

Обширность множества вызывает желание ограничить его, вы бросив из него подобного рода “патологические” отображения, и све сти (или приблизить) действие произвольного I-округления к дей ствию регулярных округлений. Приведем необходимые для дальней шего определения и факты.

В статье [1] доказаны следующие предложения:

Алгебра и топология Предложение 1. Если оба произведения и I-округлений и являются I-округлениями, то и коммутируют: =.

Предложение 2. Если I-округления и коммутируют, то оба произведения и являются I-округлениями.

Обозначим через множество всех коммутирующих друг с дру гом I-округлений, содержащее все r-округления. В силу предложе ний 1 и 2 алгебра, · является полугруппой. Округление M в ней не содержится, так как оно не коммутирует с регулярными округле ниями. Таким образом, введение на некотором подмножестве множе ства алгебраической структуры позволяет исключить из дальней ших рассмотрений, по крайней мере, некоторые I-округления “пато логического” типа.

В множестве всех I-округлений следующим определением вво дится отношение порядка:

1 2 (A IR) (2 (A) 1 (A)). (1) В [1] показано, что модель, является полной верхней по лурешеткой, иными словами в ней любое семейство A I-округлений имеет наименьшую верхнюю границу A. Подмодель, явля ется подрешеткой полурешетки,.

Так как алгебра, · – коммутативная полугруппа идемпотен тов, то в ней можно ввести так называемое отношение естественного порядка, полагая 1 2 1 2 = 1, (2) превращающее ее в упорядоченную полугруппу. Для упорядоченной полугруппы, · определения (1) и (2) эквивалентны. Заметим еще, что эта полугруппа является решеткой, в которой 1 2 = 1 2.

В множестве важную роль играют регулярные округления. Ал гебра (Z), · является в полугруппе, · подполугруппой, кроме того модель (Z), является подрешеткой в решетке,. В ра боте [1] доказаны следующие предложения:

36 Труды XXXV Молодежной школы-конференции Предложение 3. Если I-округление не является r-округлением, то существует покрывающее его r-округление, то есть такое r округление, что и внутри отрезка [;

] не содержится r-округлений.

Предложение 4. Если I-округление не является r-округлением и имеет нижнюю границу, принадлежащую подрешетке (Z), то су ществует покрываемое им r-округление, то есть такое r-округле ние, что и внутри отрезка [, ] не содержится r-округле ний. При этом является наименьшей верхней границей множе ства всех нижних границ, I-округления, содержащихся в подре шетке (Z).

Обратимся далее к упорядоченной полугруппе, ·. Обозначим через множество всех I-округлений из, обладающих нижними границами в ее подполугруппе (Z). Легко видеть, что – подпо лугруппа полугруппы. Действительно, если 1, 2 и (k, l), (r, s) – их нижние границы в (Z),то есть (k, l) 1, (r, s) 2, то (k, l) · (r, s) 1 · 2, то есть 1 2.

Определение. Назовем наибольшей нижней регулярной границей (н.н. р.г.) I-округления \(Z) r-округление (k, l) такое, что (k, l) и внутри отрезка [(k, l) ;

] нет r-округлений. Наибольшей нижней регулярной границей r-округления (u, v) будем считать его самого.

Согласно предположению 4, у любого I-округления суще ствует н.н.р.г., легко видеть, что она единственная. Действительно, для регулярного округления это утверждение справедливо три виальным образом. Пусть (Z) и (k, l), (r, s) – две его н.н.р.г., / тогда (k, l), (r,s). Следовательно, (k, l) (r, s). Таким образом, (k, l) (k, l) (r, s), (r, s) (k, l) (r, s), откуда следует (k, l) (r, s) = (k, l) = (r, s).

Наибольшую нижнюю регулярную границу округления будем обозначать r.

Теорема 1. ( · )r = r · r Действительно, так как r, r, то r · r ·. Если при этом r · r = ·, то – r-округление. Тогда ()r =, откуда следует ( · )r = r · r.


Алгебра и топология Пусть теперь r · r ·. Допустим, что существует r-округле ние такое, что r · r ·. Так как, то. Значит, – нижняя граница I-округления в решетке (Z), а так как r – наименьшая верхняя граница множества всех его регулярных ниж них границ, то r. По аналогичной причине r. Перемножая эти неравенства, получим r · r, что противоречит допущению r · r. Таким образом, внутри отрезка [r · r ;

] не содержится r-округлений и, значит, ( · )r = r · r.

Рассмотрим отображение f полугруппы в полугруппу (Z), по лагая f () = r. Оно сюръективно: прообразом регулярного округ ления служит оно само, и, согласно теореме 1, является гомомор физмом. Применением теоремы о гомоморфизмах для полугрупп, получается Теорема 2. Факторполугруппа Ker f изоморфна (Z).

Заметим, что ядром гомоморфизма f является конгруэнция, определяемая условием 1 2 (f ( 1 ) = f ( 2 )), иными словами, 1 2 1 r = 2 r.

Теорема 3. – связка полугрупп.

Действительно, факторполугруппа = (Z) есть полугруппа идемпотентов. Кроме того, классы конгруэнции являются полу группами: если r = (k, l), (r, s) некоторые классы, то их произве дение тоже класс конгруэнции – r = (k, l) · (r, s).

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

Список литературы [1]. Каминский Т.Э. К теории интервальных округлений //в сб.

"Исследования по математическому анализу и методике препо давания математики". - Вологда, 2000. С. 23–36.

[2]. Kulisch U. An axiomatic Approach to Rounded Computations //Numer. Math. 1971. № 18. C. 1–17.

38 Труды XXXV Молодежной школы-конференции О ГРУППАХ ПОРОЖДЕННЫХ КЛАССОМ СОПРЯЖЕННЫХ ЭЛЕМЕНТОВ ПОРЯДКА Максименко А.А.

М.Ашбахер и М.Холл в [1] исследовали конечные группы, порож денные классом сопряженных элементов порядка 3, любые два из ко торых либо коммутативны либо порождают SL2 (3) или A4. Также подобные группы исследовал Штельмахер в [2], с той лишь раз ницей, что у него элементы порядка 3 могут порождать также и A5. В [1] получен следующий результат: Пусть G конечная груп па, порожденная классом D подгрупп порядка 3, таким, что лю бая пара некоммутирующих подгрупп A, B из D порождает под группу, изоморфную SL2 (3) или A4. Предположим, что G не содер жит нетривиальных разрешимых нормальных подгрупп. Тогда G изоморфна Spn, Un или P GUn и D однозначно определенный класс подгрупп.

В данной работе исследуется подобный класс групп, но без пред положения конечности группы G.

Теорема. Пусть G группа, порожденная классом сопряжен ности D подгрупп порядка 3, таким, что любая пара подгрупп A и B из D порождает подгруппу, изоморфную SL2 (3) или A4. То гда либо G U3 (3), либо G расширение 2–группы посредством = группы порядка 3, при этом группа G локально–конечна.

Список литературы [1]. Aschbacher M., Hall M. Group Generated by a Class of Elements of Order 3 //J. Algebra 24, 1973. p.591–612.

[2]. Stellmacher B. Einfache Gruppen, die von einer Konjugiertenklasse von Elementen der Ordnung drei erzeugt werden //J. Algebra 30, 1974, p.320–355.

Алгебра и топология АНАЛОГ ТЕОРЕМЫ БЭРА-СУЗУКИ ДЛЯ БЕСКОНЕЧНЫХ ГРУПП Мамонтов А.С. Бэр показал [4, Теорема III 6.14], что если группа G конечна и порождается энгелевыми элементами, то G нильпотентна. Важным следствием этого результата является следующее утверждение:

(*)Пусть x p-элемент конечной группы G, тогда x Op (G) в том и только в том случае, если xg, xh p-группа для всех g, h G (здесь Op (G) максимальная нормальная p-подгруппа группы G) В [5] Сузуки получил другое доказательство (*) и использовал этот результат при исследовании некоторых свойств инволюций в конечных группах (в связи с этим утверждение (*) известно как теорема Бэра-Сузуки). Позднее более короткое и доступное дока зательство (*) получили Альперин и Лайонс [1], а сама эта теорема применялась в теории конечных разрешимых групп [3] и при класси фикации конечных простых групп [6]. Важным практическим след ствием теоремы Бэра-Сузуки является утверждение о том, что в про стой группе G любая инволюция обращает некоторый нееденичный элемент нечетного порядка [1].

По теореме Бернсайда-Виландта конечная группа нильпотентна тогда и только тогда, когда она является прямым произведением сво их силовских подгрупп [7, теорема 17.1.4]. В связи с этим теорему Бэра-Сузуки можно переформулировать таким образом: Пусть C класс сопряженности конечной группы G. Если любые два элемен та из C порождают нильпотентную группу, то и C порождает нильпотентную группу.

Настоящая работа посвящена некоторому обобщению этой "модер низированной" теоремы Бэра-Сузуки.

Теорема 1. Пусть G группа, в которой нет бесконечно воз растающих цепочек нильпотентных подгрупп. Пусть x G и для 1 Работа выполнена при финансовой поддержке Российского фонда фундамен тальных исследований, проект N 02-01-00495 и Министерства образования РФ, грант N E00-1.0-77. В полном виде статья выйдет в Сибирском Математическом Журнале.

40 Труды XXXV Молодежной школы-конференции любого g G подгруппа x, xg нильпотентна, тогда xG нильпо тентна.

Отметим, что если отказаться от требования того, чтобы в группе не было бесконечно возрастающих цепей нильпотентных подгрупп, то нельзя даже рассчитывать на то, что соответствующая группа xG будет локально нильпотентна. В качестве соответствующего примера можно рассмотреть группу Голода с тремя порождающи ми [7, пример 18.3.2].

Доказательство теоремы 1 опирается на следующий результат Теорема 2. Пусть G группа, N нильпотентная нормаль ная подгруппа в G, x1,..., xn элементы группы G, порождающие нильпотентную подгруппу K и G = N, x1,..., xn. Группа G ниль потентна тогда и только тогда, когда для любого i = 1,..., n под группа N, xi нильпотентна.

Список литературы [1]. Alperin J., Lyons R. On conjugacy classes of p-elements // J. Al gebra 19, 1971, P. 536-537.

[2]. Aschbacher M. Finite Group Theory. 2nd edition. - Cambridge Uni versity Press, 2000.

[3]. Doerk K., Hawkes T. Finite Soluble Groups. - Berlin: de Gruyter, 1992.

[4]. Huppert B. Endliche Gruppen I. - Springer-Verlag, 1979.

[5]. Suzuki M. Finite groups in which the centralizer of any element of order 2 is 2-closed // Ann. of Math 82, 1968. P. 191-212.

[6]. Горенстейн Д. Конечные простые группы. Введение в их клас сификацию, - М.: Мир, 1985.

[7]. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп, 3-е изд. - М.: Наука, Физматлит, 1982.

[8]. Хухро Е.И., Нильпотентные группы и их автоморфизмы. - Ново сибирск, 1993.

Алгебра и топология ТОЧНО-НЕ-АБЕЛЕВЫ ТОПОЛОГИЧЕСКИЕ ГРУППЫ Мухин Ю.Н., Стрижов П.Б. С начала развития абстрактной теории групп и по сей день мно гочисленные исследования вдохновлялись идеей выделения достой ного (и доступного) для изучения класса групп путем наложения ограничений на те или иные семейства подгрупп. Достаточно упомя нуть основополагающие работы Дедекинда о гамильтоновых груп пах, Миллера и Морено – о минимальных неабелевых, О. Ю. Шмид та – о минимальных ненильпотентных. После решения в 50-е годы прошлого века 5 проблемы Гильберта открылась возможность раз работки подобной проблематики на материале уже не дискретных, а локально-компактных топологических групп, где тоже было полу чено много интересных результатов. В 1956 г. известный алгебраист Б. Нейман [1] предложил в какой-то мере двойственный подход – наложение ограничений на собственные факторгруппы, первым из которых была коммутативность. Ясно, что успеха в исследовании такого рода можно ожидать лишь для групп, обладающих замет ным количеством факторгрупп. Так, работы по этой тематике для дискретных групп были выполнены (см. [2], [3], [5]) в предположе нии разрешимости изучаемой группы. Цель нашей работы – изучить локально-компактные группы, все собственные факторгруппы кото рых абелевы, но вместо разрешимости мы предлагаем топологиче ское ограничение: компактность группы по модулю связной компо ненты единицы.

Пусть некоторое групповое свойство. Топологическую группу G назовем точно-не--группой (короче: j-группой), если для лю бой собственной замкнутой нормальной подгруппы N факторгруппа G/N обладает свойством, а сама G им не обладает. Если в качестве принять абелевость, то возникает класс jA-групп.

Всюду далее будем использовать следующие обозначения:

G – локально-компактная группа с компактной факторгруппой G/G0, где G0 – связная компонента единицы e группы G;

g1,..., gn – подгруппа, топологически порожденная элементами g1,..., gn ;

G – замыкание коммутанта группы G;

[A, B] – замыкание 1 Работа поддержана грантом РФФИ № 04-01-00463.

42 Труды XXXV Молодежной школы-конференции взаимного коммутанта групп A и B;

G = A B – топологическое по лупрямое произведение замкнутых подгрупп A и B, где A нормальна в G и отображение (a, b) ab, где a A и b B– гомеоморфизм пространства A B на G;

Aut(G) – группа всех непрерывных авто морфизмов группы G;

Int(G) – группа всех непрерывных внутрен них автоморфизмов группы G;

t t cos sin et 2 2 t R ;

H+ = SO2 = tR ;

t t 0 et sin cos 2 R – аддитивная группа действительных чисел;

Cpn – циклическая группа порядка pn ;

тот факт, что группы A и B топологически изо морфны будем обозначать A B.

Отметим некоторые свойства jA-группы G.

1 Пересечение любого семейства замкнутых нормальных под групп jA-группы G нетривиально.

В частности, пересечение любого семейства собственных характе ристических подгрупп нормальной замкнутой подгруппы jA-группы G нетривиально.

Всюду в дальнейшем M есть пересечение всех собственных за мкнутых нормальных подгрупп группы G.

2 В jA-группе G выполняется M = G.

3 Если G jA-группа и G/G0 компактна, то G лиева.

4 Если G jA-группа и G/G0 компактна, то G конечна, либо G нетривиальна и G/G0 конечна.

Основным нашим результатом являются следующие две теоремы (теорема 1 в разрешимом случае может быть получена из результа тов М. Ньюмана [2] и [3];

однако, для конечных групп доказательство упрощается):

Теорема 1. Для того чтобы конечная группа G была jA-группой, необходимо и достаточно, чтобы она являлась группой типа 1, или 3.

Теорема 2. Для того чтобы ненульмерная локально-компактная группа G с компактной факторгруппой G/G0 была jA-группой, необ ходимо и достаточно, чтобы она являлась группой типа 4, 5, 6.

Алгебра и топология pm = 2, 1. Пусть Kp,m = (Z A) B, где A, B Cp, Z приm = Z Cpm, [Z, B] = e, [A, B] = m Zp приm m+1 m ap bp = e, ba = a1+p b;

Lp,m = a, b, где = e, a4 = e, b2 = a2, ba = a1 b.

N2,1 = a, b, где a) Зафиксируем m 1 и простое p так, чтобы pm = 2.

Группа G получается путем последовательного центрального склеи вания конечного набора групп, каждая из которых изоморфна либо Kp,m, либо Lp,m. Склеивание происходит по циклической группе по рядка pm, изоморфной центру Kp,m и Lp,m.

b) Группа G получается путем последовательного центрального склеивания конечного набора групп, каждая из которых изоморфна либо L2,1, либо N2,1. Склеивание происходит по циклической группе порядка 2, изоморфной центру L2,1 и N2,1.

2. G = A B, где A Cm, B абелева p -группа действующая на p A точно и неприводимо, pm = 2.

3. G является подгруппой группы Aut(H),содержащей Int(H) и действующей на H точно, где H = S n, S - простая конечная неабеле ва группа;

причем в H нет собственных G-инвариантных подгрупп и G/Int(H) абелева.

4. G = A B, где A R, B действует на A точно либо как груп па аффинных преобразований прямой, либо как группа аффинных преобразований прямой первого рода.

5. G = A B, где A R a) B0 = e, B/B0 конечна, B действует на A точно как подгруп па из SO2 H+, проекция которой на SO2 содержит не менее трех элементов.

b) B действует на A точно как конечная группа вращений, поря док B больше 4 и не равен 6.

6. G является замкнутой подгруппой группы Aut(H), содержа щей Int(H) и действующей на H точно, где H = S n, S - простая 44 Труды XXXV Молодежной школы-конференции связная неабелева группа Ли;

причем в H нет собственных замкну тых G-инвариантных подгрупп и G/Int(H) конечная абелева группа.

В процессе доказательства теоремы 2 используются следующие полученные нами результаты:

Теорема 3. Если группа вращений двумерного векторного про странства V над R содержит элемент, который поворачивает V на угол =, где n 5 и n = 6, то в V нет собственных замкну n тых A - инвариантных подгрупп.

Теорема 4. Пусть группа A, где A0 = e, действует на двумерном векторном пространстве V над R, причем действие A не исчерпы вается гомотетиями и A0 действует на V нетривиально. Тогда в V нет собственных замкнутых A-инвариантных подгрупп.

Теорема 5. Если абелева группа A действует на n-мерном вектор ном пространстве V над R как группа линейных преобразований, то в V найдется либо одномерное, либо двумерное A-инвариантное подпространство.

Теорема 6. Если компактная абелева группа A действует на дву мерном векторном пространстве V над R неприводимо как группа линейных преобразований, то она действует как группа вращений.

Теорема 7. Пусть A – абелева группа действующая на двумер ном векторном пространстве V над R точно и неприводимо и A/A компактна. Тогда A действует на V как подгруппа из SO2 H+ про екция которой на SO2 содержит не менее трех элементов, если базис в V выбран надлежащим образом.

Следующий результат является обобщением леммы Робинсона [4].

Теорема 8. Пусть A и N такие замкнутые нормальные подгруп пы локально-компактной -компактной группы G, что A N, [A, N ] не тривиальна, N = e. Предположим также, что каж дая замкнутая подгруппа из N/A нормальна в G/A, причем A абе лева подгруппа не содержащая собственных G-инвариантных за мкнутых подгрупп. Тогда A отщепляется в G.

Алгебра и топология Список литературы [1]. Neumann B.H. Ascending derived series //Compositio Math. 13, 1956. p. 47–64.

[2]. Newman M.F. On a class of metabelian groups //Proc. London Math. Soc., 3, 10, 1960. p. 354–364.

[3]. Newman M.F. On a class of nilpotent groups //Proc. London Math.

Soc. 3, 10, 1960. p. 365–375.

[4]. Robinson D. J. S. Groups whose homomorphic images have a tran sitive normality relation //Trans. of the Amer. Math. Soc., 176, 1973. p. 181–213.

[5]. Rosati L. A. Sui gruppi a factoriali abeliani. //Mathematiche (Cata nia), 13, 1958. p. 138–147.

46 Труды XXXV Молодежной школы-конференции ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПОЛИНОМИАЛЬНОГО КОДИРОВАНИЯ Титов С.С., Демкина О.Е., Ициксон М.А., Моклокова Л.М., Торгашова А.В., Яковлева Е.В.

Помехоустойчивое кодирование, применяемое также для шифро вания с открытым ключом и электронной цифровой подписи [1, 2], ставит задачу автоматического построения многочленов над конеч ными полями с нужными свойствами. Одной из таких задач явля ется поиск многочленов f (x) данной степени n, определяющих та кую длину кода m, что кодовое расстояние dmin гарантированно не меньше заданного. Для генерации примитивных многочленов дан ной степени в предыдущих работах [3, 4] были получены формулы перехода от многочленов с корнем x к многочленам с корнем xt, в том числе – явные рекуррентные формулы для малых t = 3, 5, 7, 9, что можно применить для построения оптимальных кодов, увели чивая dmin за счет уменьшения длины передаваемого кода m. Это можно сделать, построив логарифм L Зеха-Якоби [6, 5]. Полученные формулы для нахождения m при, например, dmin 4 и dmin через L(k) позволяют находить длину кода по начальному отрезку таблицы степеней многочлена f (x) без перебора всех информацион ных многочленов [4], т.е. нахождение величины m – максимальной длины кода (m, m n), построенного при помощи полиномиального кодирования посредством многочлена f (x), удовлетворяющего усло вию dmin = d для заданного d. Данная задача может решаться как простым перебором всей таблицы степеней многочлена f (x) [8], так и другим способом, а именно: для данного примитивного многочлена f (x) степени n над полем Z2 из логарифма Зеха-Якоби f (x) в виде подстановки или в виде разложения на циклы по первым строкам таблицы степеней многочлена определить m из условия dmin 4 ра венством m = min(L(k)) 1, где 1 k m. Длина кода m может быть разной для разных f (x) одной степени. Так, если f (x) – трех член, то dmin не может быть больше трех ни для какого m. Вообще dmin не может быть больше веса Хэмминга ||f (x)|| многочлена f (x).

Для перебора всех примитивных многочленов степени n и их ло гарифмов Зеха-Якоби достаточно взять один примитивный много член f (x), построить для него логарифм Зеха-Якоби, а затем при Алгебра и топология менить следующее простое соотношение. Пусть для данного прими тивного многочлена f (x) степени n над полем Z2 известен его ло гарифм Lf Зеха-Якоби целиком, то есть вычислен Lf (k) для всех k {0, 1,..., 2n 2}. Если g(x) – примитивный многочлен степени n такой, что его корень y есть некоторая степень корня x0 многочлена f (x), скажем, y = xt, t N, то для всех k 0, 1,..., 2n 2 имеет место сравнение Lf (tk) tLg (k)( mod 2n 1) т.е.

Lg (k) t1 Lf (tk)( mod 2n 1) (k : k {0, 1,..., 2n 2}) Следовательно, если L(k) (M + L(N M ))( mod 2n 1) для всех троек чисел (K, M, N ) таких, что K M N, и m L(k) для всех 1 k m, то полиномиальный (m, m n)-код, построенный при помощи многочлена f (x), удовлетворяет условию dmin 5. Ана логичные условия можно выписать для больших dmin. Однако для применения данного метода на практике также необходимо прово дить полный перебор, сравнимый по объему с полным перебором при взломе кода.

Проведя подобные проверки, выяснили, например, что для при митивных многочленов 11 степени для получения dmin = 5 необ ходимо, чтобы m было меньше двадцати трёх. В то же время для некоторых непримитивных многочленов 11 степени обнаружили, что dmin 5. Для больших n применение примитивных многочленов в задачах построения оптимальных кодов, как правило, неэффектив но. Действительно, рассматривая логарифм Зеха-Якоби, получаем, что при m = 2n 1 для примитивного многочлена имеем всего лишь в точности dmin = 3. А для построения БЧХ-кодов используются многочлены, которые не являются неприводимыми. Например, при m = 255 для значения dmin = 19 вместо ожидаемой n = 80 = deg f (x) получаем n = 76, то есть увеличивается число информационных бит за счет экономии избыточных на 4 бита. Получаем длину ко да m n = 179 = k, то есть код (255,179) вместо (255,183). Работа для оптимизации БЧХ проделана для целой серии чисел m. На осно ве этих работ можно дать рекомендации по технической реализации оптимальных кодеров и декодеров [3].

Использование примитивных многочленов оправданно при шиф ровании гаммированием для построения гаммы шифра максималь ного периода [13, 10]. Однако в помехоустойчивом кодировании и 48 Труды XXXV Молодежной школы-конференции применении кодовых конструкций при шифровании с открытым ключом они не всегда обладают оптимальными характеристиками.

Рассмотрим этот тезис подробнее для малых m и n в данной ра боте. Полиномиальное кодирование с исправлением одной ошибки равносильно задаче построения многочлена порядка p, большего ли бо равного длине m передаваемого кода [9]. Рассмотрим коды, ис правляющие многократные ошибки, при данном p.

Утверждение 1. Пусть во множестве X корней многочлена f (x) есть геометрическая прогрессия длины l. Тогда нет такого кодового многочлена b(x), что b(x) 0( mod f (x)) и среди его коэффициен тов менее (l + 1)–го отличны от нуля, т.е. dmin l + 1.

Утверждение очевидно: доказывается аналогично тому, как для БЧХ-кодов с использованием определителя Вандермонда.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 8 |
 

Похожие работы:





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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