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

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

Итак, для генерации последовательностей больших периодов биективные дифференцируемые по модулю pn функции могут быть использованы как сопрягающие для транзитивных функций. Представляют интерес также статистические свойства таких последовательностей. Поэтому группа дифференцируемых по модулю pn функций заслуживает внимания. Однако пока не описано представление, позволяющее эффективно вычислять данные функции, их реальное использование не практично. Поэтому в дальнейшем стоит задача поиска эффективного представления для функций из класса дифференцируемых по модулю pn функций или из его подклассов. Предполагается, что данное представление можно получить для этих функций по модулю 2n, используя элементарные операции, такие, как AND, XOR, RIGHT_SHIFT.

ЛИТЕРАТУРА

1. Ивачев A. C. Исследование класса дифференцируемых функций в кольцах классов вычетов по примарному модулю // Прикладная дискретная математика. Приложение. 2014. №7. С. 19-22.

УДК 512.543.72 DOI 10.17223/2226308X/8/11

ОБРАЩЕНИЕ ДИФФЕРЕНЦИРУЕМЫХ ПЕРЕСТАНОВОК

НАД ГРУППОЙ

А. В. Карпов

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

Ключевые слова: перестановка, полином над группой, дифференцируемая функция.

Пусть задана группа G с нормальным рядом G = H0 > Hi > ... > Hn = e. Через Ф обозначим множество функций, отображающих G в себя, которые действуют на факторах Hk/Hk+i (k Е {0,... ,n — 1}) как эндоморфизмы.

Определение 1. Функция f : G ^ G называется дифференцируемой в точке a Е G относительно нормального ряда G = H0 > Hi > ... > Hn = e, если существует функция Е Ф, такая, что для любого члена нормального ряда Hk и любого элемента h Е Hk выполняется равенство

f (a + h) = f (a) + ^fa(h) (mod Hk+i).

Функция называется дифференцируемой, если она дифференцируема в каждой точке группы G. Функция называется производной функции f в точке a.

В качестве примеров дифференцируемых функций можно привести следующие: полиномиальные функции над примарным кольцом вычетов Zpn, где в качестве G выступает (Zpn, +), Hk = pkZpn, = f'(a) и ^f,a(h) = h*f'(a); полиномиальные вектор-функции, т. е. системы из m полиномов от m переменных с коэффициентами из Zpn, где G = (Z^n, +), совпадает с матрицей частных производных, вычисленных в точке a;

Дискретные функции

31

к

Л £i

полиномы над разрешимой группой вида u(x) = g\x£lg2x£2 ... gkx£l с фиа{К) = hi=1 в случае центрального ряда.

Следующая теорема обобщает критерий биективности из [1] на случай дифференцируемой функции.

Теорема 1. Пусть u : G ^ G — дифференцируемая относительно нормального ряда G = H0 > Hi > ... > Hn = e функция. Тогда u биективна на G, если и только если выполняются следующие два условия:

1) u биективна по модулю Hi;

2) для всех x Е G производная фи,х является автоморфизмом на всех факторах ряда.

Естественно называть дифференцируемую биективную функцию дифференцируемой перестановкой. Будем говорить, что v — обратная (по модулю Hk) к u дифференцируемая перестановка, если для всех x Е G выполняется

v(u(x)) = x (v(u(x)) = x (mod Hk)).

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

2n

вательности модулей p, p2,... ,pn в случае примарного кольца, что даёт возможность применять схожие с [2] методы обращения перестановок. Основная идея заключается в сведении задачи обращения над всей группой к обращению над «маленькой» фактор-группой с последующим подъёмом решения. Это удаётся сделать, если группа G разрешима и известно промежуточное решение по модулю некоторой подгруппы из нормального ряда.

Теорема 2. Пусть u — перестановка элементов разрешимой группы G, дифференцируемая относительно нормального ряда G = H0 > Hi > ... > Hn = e, vk — обратная перестановка к u по модулю Hk. Тогда обратной к u по модулю Hk+i является перестановка

(

u,vk

где ф"^(х) —обратный к фиж^х) автоморфизм в Aut(Hk/Hk+i). Если дополнительно 'Ф'U,vk(х) и ф-юк,х —взаимно обратные автоморфизмы фактора Hk/Hk+i, то

vk+i

Vk+l (х) = Vk(х) - Vk(п(ук(х))) + Vk(ж).

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

Теорема 3. Пусть п и V — взаимно обратные по модулю Нк дифференцируемые перестановки и для всех х Е С дифференцируемая функция по удовлетворяет следующим условиям:

1) по (х) Е Нк-1;

2) фпо ,х : Нк-1 ^ Нк.

Тогда обратной к п*(х) = п(х) + п0(х) по модулю Нк является перестановка v*(x) = = v(x) - фv,x(nо(v(x))).

В качестве примера рассмотрим С = Т3^7) с разрешимым рядом С = Т3^7) > > ЦТ3^7) > ЦТ|^7) > ЦТ|^7) = е, где ЦТ3^7) — подгруппа, состоящая из унитре-угольных матриц с (г — 1) нулевыми диагоналями над главной.

'2 4 3\ /12 5\ /1 6

Введём функцию u(x) =

0 ,0

x

0 ,0

x

0 0

4N

x. Сначала обра-

тим u(x) в первом факторе T3(Z7)/UT4(Z7) ~ Z;  Z;  Z^:

400 v1(x)= 10 5 0 I x, v1 .0 0 6,

3 6 2 0 2 5

004

'3 0 4

0 2 6

.0 0 4,

362

0 2 5 1 ( mod U7s(Z7)). 004

Так как производная фи х — тождественный автоморфизм, по теореме 2 получаем

V2

\-l

V2 u

362 025 004

vn u

36 02 00

362 025 004

6

5 4

362

0 2 5 1 (mod UT32(Z7)),

,0 0 4V 362 0 2 5 004

Умножим справа u(x) на добавку uo(x), удовлетворяющую условиям 1 и 2 теоремы 3:

0 6N

u0(x) = x-1 I 0 1 0 | x, u*(x) = u(x)u0(x). .0 0 1,

Построенная ранее v3(x) не обращает u*(x):

v3 u

362 025 004

'3 6 5 0 2 5 0 0 4

Построим обратную к u*(x) функцию:

v;(x) = V3(x)(^vs,x(uo(v3(x)))) 1 = V3(x)(uo(v3(x))) 1,

3 6 2 3 6 2

0 2 5 III = I 0 2 5 0 0 4 0 0 4

* I *

v u

Таким образом, задача обращения дифференцируемой перестановки над разрешимой группой сводится к обращению над фактор-группой с последующим подъёмом решения. Если известна обратная перестановка по модулю Hk, то можно строить другие пары взаимно обратных перестановок по модулю Hk, используя теорему 3.

ЛИТЕРАТУРА

1. Anashin V. S. Noncommutative algebraic dynamics: ergodic theory for profinite groups // Proc. Steklov Institute of Math. 2009. V.265. P. 30-58.

2. Карпов А. В. Перестановочные многочлены над примарными кольцами // Прикладная дискретная математика. 2013. №4(22). C. 16-21.