close

Вход

Забыли?

вход по аккаунту

?

Исследование наследственных признаков в конечных группах.

код для вставкиСкачать
УДК 519.7
В.М. Фомичёв
ИССЛЕДОВАНИЕ НАСЛЕДСТВЕННЫХ ПРИЗНАКОВ
В КОНЕЧНЫХ ГРУППАХ
Предложен общий подход к дифференциации элементов конечной группы 〈S〉, порождённой системой образующих S, по
принадлежности подмножеству H группы 〈S〉. Для наследственного подмножества H группы 〈S〉 определение множества
(S((H сведено к определению элементов множества H во всех максимальных циклических подгруппах группы (S(, что может быть существенно более простым при вычислениях в некоторых группах. Исследована сложность порождения хотя бы
одного элемента множества H, определённая как кратчайшая из длин слов в алфавите S, представляющих элементы множества H. Данный подход позволяет, в частности, существенно сузить область поиска линейной подгруппы в группе подстановок векторного пространства над конечным полем.
1. Основные понятия и исследовательские
задачи изучения признаков
2. Оценки показателей групповых
признаков
Пусть Φ − конечная группа, 〈S〉 – группа, порожденная системой образующих S = {s1, s2, …, sp}, где
S ⊆ Φ и p = ⎪S⎪>0; G = 〈S〉. Обозначим через L(g, S)
длину элемента g группы 〈S〉 в системе образующих
S, [1].
Определение 1. Для непустого подмножества Q
множества Φ его показателем в системе образующих
S (обозначается pokS Q) назовём наименьшую из длин
всех элементов множества Q в системе образующих S,
т.е.
pokS Q = min L(g,S).
Определение 4. Если G ∩ H<G, то H-признак в
группе G назовём групповым признаком.
Теорема 1. Если группа G имеет групповой Hпризнак, то
Пусть Q ⊆ G и H – подмножество элементов группы Φ, обладающих определённым набором свойств
(признаком).
Определение 2. Будем говорить, что множество Q
имеет H-признак или во множестве Q имеется Hпризнак, если Q ∩ H≠∅, при этом H-признак тривиален (нетривиален), если Q ∩ H – одноэлементное
множество (содержит более одного элемента). Множество Q не имеет H-признака или во множестве Q
имеется пустой H-признак, если Q ∩ H = ∅.
Определение 3. Если множество Q имеет H-признак, то показателем H-признака множества Q в системе образующих S назовём pokS(Q ∩ H). В случае
Q = G используем запись pokSH.
В связи с этими определениями сформулируем несколько важных задач криптологии, связанных с исследованием строения группы G и её подмножеств.
Для заданной группы G и множества H описание
множества G ∩ H, определение доли элементов множества G ∩ H в группе G и её подгруппах. Особый
интерес представляет случай, когда H – подмножество r-го слоя группы G, r = 2,3,…
Для заданных множеств S и H определение (или
оценка) H-показателя группы G в системе образующих S. Если H-признак в группе 〈S〉 тривиален, т.е.
G ∩ H = {g}, то эта задача сводится к задаче определения или оценки величины L(g, S).
Для заданной группы G и множества H исследование зависимости величины pokS(G ∩ H) от выбора
системы S образующих элементов.
Многие из указанных задач допускают более глубокую вероятностную формулировку, если задать вероятностную меру на множестве образующих S.
pokg(〈g〉 ∩ H) = ⎪〈g〉:(〈g〉 ∩ H)⎪.
g∈Q
294
pokS(G ∩ H) ≤ ⎪G:(G ∩ H)⎪,
где ⎪G:(G ∩ H)⎪ – индекс подгруппы G ∩ H в группе
G.
Верхняя оценка теоремы 1 достигается для циклических групп.
Теорема 2. Если циклическая группа 〈g〉 имеет
групповой H-признак, то
Нижние оценки величин pokS(G ∩ H) существенно
зависят от свойств множеств S, G и H и могут достигать малых значений.
Например, если S ∩ H ≠ ∅, то pokS H = 1. Если
S ∩ H = ∅, множество G ∩ H содержит единицу группы Φ и система S содержит инволюции или взаимно
обратные элементы, то pokS H = 2.
3. Свойства наследственных признаков
в группе
Рассмотрим квазипорядок на группе G: g′ ≤ g для
g′, g∈G тогда и только тогда, когда 〈g′〉<〈g〉.
Определение 5. Подмножество Q группы G называется наследственным, если для любого g∈Q из
g′ ≤ g следует g′∈Q.
Пусть G ∩ H ≠ ∅, тогда H-признак в группе G назовём наследственным, если G ∩ H – наследственное
подмножество группы G.
Множество всех наследственных подмножеств
группы G образует дистрибутивную решётку, и всякое наследственное подмножество Q группы G имеет
единственное несократимое представление в виде
объединения всех максимальных циклических подгрупп множества Q [2, гл. II, §1, следствие 13]:
Q = ∪ 〈 g〉 .
g ∈BQ
Систему BQ элементов группы G, порождающих
максимальные циклические группы множества Q, назовём с-базисом множества Q, а порядок системы BQ
назовём с-шириной множества Q (обозначается hc(Q)).
В силу этого представления изучение наследственного H-признака в группе G можно свести к изучению H-признака в максимальных циклических подгруппах группы G. Сложность такого подхода характеризуется с-шириной группы G.
Для нетривиального наследственного множества Q
справедливы (достижимые) оценки:
1 ≤ hc(Q) ≤ ⎪Q⎪–1.
Верхняя оценка достигается для прямого произведения групп порядка 2.
Описание множества 〈g〉 ∩ H равносильно описанию подмножества тех чисел t∈{1,…,n}, для которых
gt∈H. Заметим, что gt∈H для t∈{1,…,n} тогда и только тогда, когда gd∈H, где d = gcd(t,n), так как
〈gt〉 = 〈gd〉. Следовательно, достаточно описать все делители числа n со свойством gt∈H. Множество делителей t1,…,tr числа n таких, что система
{gt: t ∈ {t1,…, tr}} образует с-базис множества 〈g〉 ∩ H,
обозначим Π(H,g). Следовательно,
〈g〉 ∩ H = ∪ 〈 g t 〉 .
t∈Π ( H , g )
Пусть N – множество натуральных чисел, M ⊆ N,
D(n) – решётка делителей числа n.
Через prm M (dom M) обозначим подмножество
всех минимальных (максимальных) элементов множества M по отношению делимости. Множество
prm M (и dom M) образует антицепь в частично упорядоченном множестве M по отношению делимости.
Теорема 3. Пусть группа 〈g〉 имеет наследственный H-признак, тогда
Π(H, g) = prm {t∈D(n): gt ∈ H}.
Следствия.
1) pokg H = min Π(H, g).
2) Наследственный H-признак в группе 〈g〉 является групповым признаком тогда и только тогда, когда
⎪Π(H, g)⎪ = 1.
3) Наследственный H-признак в группе 〈g〉 является тривиальным признаком тогда и только тогда, когда множество Π(H, g) состоит из единственного числа, равного n.
4) Если группа G имеет наследственный H-признак, то pokS H не превышает наименьшего из чисел
множества Π(H,s1) ∪…∪ Π(H, sp).
4. Взаимосвязь наследственных признаков
и монотонных функций на группах
Пусть Y – множество с частичным порядком и
⎪Y⎪ > 1, F(G,Y) – класс функций, определённых на
группе G и принимающих значения во множестве Y и
F0(G,Y) – его подкласс, состоящий из всех функций f
со свойством: если 〈g〉 = 〈g′〉 для g, g′∈G, то
f (g) = f (g′).
Определение 6. Функция f из F0(G,Y) называется
монотонной (антимонотонной), если из отношения
g′ ≤ g′′ для g′, g′′ ∈ G следует, что f (g′) ≤ f (g′′)
(f (g′) ≥ f (g′′)). Антимонотонной на группе G является,
например, функция f (g) = ord g. Функция ϕ(g) =
= (ord g)–1 является монотонной.
Множество всех элементов g группы G, удовлетворяющих при y ∈ Y условию f (g) ≥ y ( f (g) ≤ y), обозначим G( fy) (G( f y)).
Теорема 4. Если функция f из F0(G,Y) монотонна
(антимонотонна), то при любом y∈Y множество G( f y)
(множество G( fy)) является наследственным и группа
G имеет наследственный G( f y)-признак (G( fy)-признак).
Если группа G имеет наследственный H-признак,
то существует монотонная (антимонотонная) функция
f из F0(G,Y), такая, что G ∩ H = G( fy) (G ∩ H = G( f y))
при некотором y ∈ Y.
Ограничение функции f из F(G,Y) на циклическую
группу 〈g〉 порядка n назовём g-подфункцией функции
f и обозначим fg(t), где fg(t) = f (gt), t ∈{1,…, n}.
Следствие. Наследственный G( f ≤ y)-признак
(G( f ≥ y)-признак) тривиален в группе G тогда и только тогда, когда fg(n) ≤ y и fg(t) > y ( fg(n) ≥ y и fg(t) < y)
для любого элемента g с-базиса группы G и любого
коатома t решётки D(n).
Эта теорема используется для исследования наследственных признаков в группах подстановок с помощью функций, определённых на группе подстановок и характеризующих структуру подстановки или
её таблицу.
5. Изучение наследственных признаков
в группах подстановок
5.1. Пусть Φ(X) – группа всех подстановок множества X, G < Φ(Х), g∈Φ(X), ord g = n и L(g) = {l1,…, lm}
– множество всех длин циклов подстановки g. Для делителя τ числа n через mpn(τ) обозначим наименьший
делитель τ′ числа n такой, что НОК(τ,τ′) = n.
Определение 7. Подстановку g назовём d-доминантной, если ⎪dom L(g)⎪ = d, в частности, унидоминантной, если ⎪dom L(g)⎪ = 1.
Пусть U(X) (кратко U) – множество всех унидоминантных подстановок из Φ(X). Рассмотрим ⎪dom L(g)⎪
как функцию, определённую на группе Φ(X).
Теорема 5. Функция ⎪dom L(g)⎪ монотонна,
вследствие этого всякая группа G подстановок множества X имеет наследственный U-признак. Если
⎪dom L(g)⎪>1, то
Π(U,g) = prm{mpn(l1),…,mpn(ld)},
pokgU = min{mpn(l1),…,mpn(ld)},
hc(〈g〉 ∩ U)≤⎪domL(g)⎪.
Следствие. Нетривиальная группа подстановок G
имеет нетривиальный наследственный U(X)-признак.
Если G = 〈S〉, где S = {s1,…,sp}, то
pokS U ≤ min{u1′,…,up′},
где uj′ – наименьшее из чисел множества Π(U,sj),
j = 1,…, p.
5.2. Пусть I(g) – подмножество всех элементов
множества X, неподвижных относительно подстановки g, где Х – аддитивная группа; σ(Z) = ∑ x , где
x∈Z
295
Z ⊆ Х; Х1,…, Хk суть блоки разбиения множества Х на
циклы подстановки g. Обозначим:
σ( g ) = {σ(Х1),…,σ(Хk)},
Φ( σ ⊆I) = {g∈Φ(Х): σ( g ) ⊆I(g)}.
Подстановку g назовём σ -стабильной, если
〈g〉 ⊆ Φ( σ ⊆ I). Множество всех σ -стабильных подстановок из Φ(X) обозначим Σ(X).
Теорема 6. Подстановка g является σ -стабильной
тогда и только тогда, когда gt ∈ Φ( σ ⊆ I) при любом
t ∈ D(n). Σ(X)-признак в группе G является наследственным признаком и
6. Использование наследственных признаков
для определения линейной подгруппы в группе
подстановок векторного пространства
Пусть Р r – векторное пространство размерности r
над конечным полем Р порядка q; G – группа подстановок пространства Р r; GL(r,q) – полная линейная
группа преобразований пространства Р r.
Теорема 7. Группа G имеет групповой GL(r, q)признак и
G ∩ GL(r,q) ⊆ Gθ ∩ U(Р r) ∩ Σ(Р r),
где θ – нулевой вектор пространства Р r; Gθ – стабилизатор элемента θ в группе G.
Π(Σ(X), g) = prm{t ∈ D(n): 〈gt〉 ⊆ Φ( σ ⊆I)}.
ЛИТЕРАТУРА
1. Глухов М.М. О числовых параметрах, связанных с заданием конечных групп системами образующих элементов // Труды по дискретной
математике. Т. 1. М.: ТВП, 1997. С. 43 – 66.
2. Гретцер Г. Общая теория решёток. М.: Мир, 1982. 454 с.
Статья представлена кафедрой защиты информации и криптографии факультета прикладной информатики и кибернетики Томского государственного университета, поступила в научную редакцию «Информатика» 16 мая 2005 г.
296
Документ
Категория
Без категории
Просмотров
5
Размер файла
371 Кб
Теги
конечный, признаков, группа, наследственная, исследование
1/--страниц
Пожаловаться на содержимое документа