Обращение дифференцируемых перестановок над группой | ПДМ. Приложение. 2015. № 8.

Обращение дифференцируемых перестановок над группой

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

The inverse of differentiable permutations over groups.pdf Пусть задана группа G с нормальным рядом G = H0 > H1 > ... > Hn = e. Через Ф обозначим множество функций, отображающих G в себя, которые действуют на факторах /Hfc+1 (k е {0,... , n - 1}) как эндоморфизмы. Определение 1. Функция f : G - G называется дифференцируемой в точке а е G относительно нормального ряда G = H0 > H1 > ... > Hn = e, если существует функция -0/,а е Ф, такая, что для любого члена нормального ряда Яд и любого элемента h е Яд выполняется равенство f(а + h) = f(а) + fa(h) (mod H.+1). Функция называется дифференцируемой, если она дифференцируема в каждой точке группы G. Функция -0/,а называется производной функции f в точке а. В качестве примеров дифференцируемых функций можно привести следующие: полиномиальные функции над примарным кольцом вычетов Zpn, где в качестве G выступает (Zpn, +), = pkZpn, -0/,a = f'^) и -0/,a(h) = h*f'^); полиномиальные вектор-функции, т. е. системы из m полиномов от m переменных с коэффициентами из Zpn, где G = (Z^n, +), совпадает с матрицей частных производных, вычисленных в точке а; k Л £i полиномы над разрешимой группой вида u(x) = gix£1 g2x£2 ... x£l с ^«(h) = hi=1 в случае центрального ряда. Следующая теорема обобщает критерий биективности из [1] на случай дифференцируемой функции. Теорема 1. Пусть u : G ^ G - дифференцируемая относительно нормального ряда G = H0 > Hi > ... > Hn = e функция. Тогда u биективна на G, если и только если выполняются следующие два условия: 1) u биективна по модулю H1; 2) для всех x е G производная является автоморфизмом на всех факторах ряда. Естественно называть дифференцируемую биективную функцию дифференцируемой перестановкой. Будем говорить, что v - обратная (по модулю Hk) к u дифференцируемая перестановка, если для всех x е G выполняется v(u(x)) = x (v(u(x)) = x (mod Hk)). В работе решается задача нахождения обратной дифференцируемой перестановки к заданной. Нормальный ряд в группе G задаёт структуру, аналогичную последо- 2n вательности модулей p, p2,... ,p' в случае примарного кольца, что даёт возможность применять схожие с [2] методы обращения перестановок. Основная идея заключается в сведении задачи обращения над всей группой к обращению над «маленькой» фактор-группой с последующим подъёмом решения. Это удаётся сделать, если группа G разрешима и известно промежуточное решение по модулю некоторой подгруппы из нормального ряда. Теорема 2. Пусть u - перестановка элементов разрешимой группы G, дифференцируемая относительно нормального ряда G = H0 > Hi > ... > Hn = e, - обратная перестановка к u по модулю H. Тогда обратной к u по модулю Hfc+i является перестановка ( где (x) -обратный к "0«,vk(x) автоморфизм в Aut(Hk/Hfc+i). Если дополнительно "0«,vk(ic) и -взаимно обратные автоморфизмы фактора H/Hfc+i, то vfc+i (x) = vfc(x) - vfc(u(vfc(x))) + vfc(x). Возможно также обращение дифференцируемой перестановки, если известно обращение другой дифференцируемой перестановки, отличающейся от заданной на определённую добавку. Теорема 3. Пусть u и v - взаимно обратные по модулю H дифференцируемые перестановки и для всех x е G дифференцируемая функция u0 удовлетворяет следующим условиям: 1) uo (x) е Hfc-i; : Hfc-i ^ Hfc. Тогда обратной к u*(x) = u(x) + u0(x) по модулю Hk является перестановка v*(x) = = v(x) - ^v,x(uo(v(x))). vfc+i(x) = vfc(x) - (x)(-x + u(vfc(x))^ В качестве примера рассмотрим G = T3(Z7) с разрешимым рядом G = T3(Z7) > > UT3(Z7) > UT32(Z7) > UT33(Z7) = e, где UT3(Z7) - подгруппа, состоящая из унитре-угольных матриц с (i - 1) нулевыми диагоналями над главной. '2 4 А /12 5\ /1 6 4 1 Введём функцию u(x) = x. Сначала обра 0 0 0 0 0 0 x x тим u(x) в первом факторе T3(Z7)/UT4(Z7) ~ Z? 0 Z? 0 Z7: 400 v1(x)= 10 5 0 | x, v1 006 '3 0 4 0 2 6 .0 0 4, 3 6 2 025 004 362 0 2 5 1 ( mod UT3(Z7)). 004 Так как производная - тождественный автоморфизм, по теореме 2 получаем 1 V2(x) = V1(x)(x u(v1(x))) , V3 = V2(x)(x u(v2 (x))) 362 0 2 5 1 (mod UT32(Z7)), 0 4и 362 0 2 5 004 V2 u vn u 362 025 004 36 02 00 362 025 004 6 5 4 Умножим справа u(x) на добавку u0(x), удовлетворяющую условиям 1 и 2 теоремы 3: 106 u0(x) = x-1 | 0 1 0 | x, u*(x) = u(x)u0(x). .0 0 1, Построенная ранее v3(x) не обращает u*(x): v3 u '3 6 5 0 2 5 0 0 4 362 025 004 Построим обратную к u*(x) функцию: v*(x) = V3(x)(^vs,x(u0(v3(x)))) 1 = v3(x)(u0(v3(x))) 1, 3 6 2 3 6 2 0 2 5 ||| = | 0 2 5 0 0 4 0 0 4 Таким образом, задача обращения дифференцируемой перестановки над разрешимой группой сводится к обращению над фактор-группой с последующим подъёмом решения. Если известна обратная перестановка по модулю Яд, то можно строить другие пары взаимно обратных перестановок по модулю Яд, используя теорему 3.

Ключевые слова

differentiable function, polynomial over group, permutation, дифференцируемая функция, полином над группой, перестановка

Авторы

ФИООрганизацияДополнительноE-mail
Карпов Артем ВалерьевичНациональный исследовательский Томский государственный университетаспирант кафедры защиты информации и криптографииkarpov@isc.tsu.ru
Всего: 1

Ссылки

Anashin V. S. Noncommutative algebraic dynamics: ergodic theory for profinite groups // Proc. Steklov Institute of Math. 2009. V.265. P. 30-58.
Карпов А. В. Перестановочные многочлены над примарными кольцами // Прикладная дискретная математика. 2013. №4(22). C. 16-21.
 Обращение дифференцируемых перестановок над группой | ПДМ. Приложение. 2015. № 8.

Обращение дифференцируемых перестановок над группой | ПДМ. Приложение. 2015. № 8.