Характеристики периодичности преобразования

Преобразованию g конечного множества X и любому элементу х е X соответствуют последовательность преобразований g_> = {g*} и последовательность g_>(x) = (g*(x)} над X, где g°(x) =x_yi = 0, 1,… В силу конечности множества X в обеих последовательностях имеются повторения, при этом если i-й и j-й члены любой из этих последовательностей совпадают, i < j, то совпадают их (i + г)-й и (/ + г)-й члены, г — 1,2, …. Следовательно, обе эти последовательности являются периодическими.

Периодом (предпериодом) элемента х относительно преобразования g называется период (предпериод) последовательности g_>(x) (их длины обозначим t_xg и v_xg соответственно или кратко t_x и v_r, если преобразование g фиксировано).

Утверждение 8.2. Для любогоgе П (Х) и любогохе X выполнено t_{x R} +.

+ v"*< Ixl.

Последовательность g^(x) чисто периодическая вершина х циклическая в F (g), и t_x есть длина цикла, которому принадлежит вершина х.

Если вершина х графа F (g) ациклическая, то v* есть длина подхода из вершины х к циклу С в графе Y (g) и t_x есть длина цикла С.

Л Если вершина х циклическая, то период последовательности g_>(pc) состоит из всех вершин цикла, содержащего вершину х.

Если вершина х ациклическая, то предпериод последовательности g_>(x) состоит из всех ациклических вершин подхода из вершины х к циклу С графа r (g), а период последовательности g_>(x) состоит из всех вершин цикла С. Пусть длины указанного подхода и цикла равны соответственно 1_Х и /. Тогда в g_>(x) имеются совпадения на расстоянии / начиная с номера 1_Х. Следовательно, но утверждению 8.1а v_v = 1_Х и t_x делит /. Вместе с тем t_x не меньше /, так как элементы цикла различны и совпадений в g^(x) на расстоянии меньшем / не имеется.

Для любого g е П (Х) период и предпериод элемента х суть две непересекающиеся бесповторные выборки из множества X размера 1_Х и / соответственно. Отсюда t_{x g} + v_xя< |х|. ?

Периодом (предпериодом) преобразования g называется период (предпериод) последовательности g^, их длины обозначим их t_g и v_g.

Утверждение 8.3. Для g е П (Х) величины t_g и v_g суть циклическая глубина и период элемента g моноида П (Х), при этом t= HOK (/j, 1_т)_у где /i, l_m — все различные длины циклов графа T (g). Если g — подстановка, то v^= 0, в противном случае v_g равна наибольшей из длин всех подходов к циклам графа T (g).

Ч Равенства = depg, t_g = perg вытекают из определений циклической глубины и периода элемента g полугруппы, с одной стороны, и из определений длин предпериода и периода последовательности g_^, с другой.

Период последовательности g'_> совпадает с максимальной подгруппой циклической полугруппы (g) (с циклической группой (g), если g — подстановка). Совпадение преобразований равносильно совпадению их таблиц, поэтому g = gJ при i, j е N g (x) = g^J(^x) для любого х е X. Следовательно,.

t_g и v_g равны соответственно длинам периода и предпериода сопряжения множества последовательностей {g_>0r)^{: х Е г}Д^е v_r и t_x определены утверждением 8.2. Тогда по теореме 8.2а t_g= HOK (^_v: х е X) = НОК (/_1? …, l_m)y v^= шах^ х е X}. ?

Для преобразований g «-множества X и для х е X верны абсолютные оценки: x< п 1 g Нижние оценки достижимы для тождественной подстановки. Верхняя оценка t_x достижима для цикла длины «, верхняя оценка t_g достигается лишь при п < 2.

Определим длину периода и цикловую структуру преобразования g множества V₃ регистра правого сдвига с одной обратной связью f (x_{, х₂, х₃) = х_х 0 х₂ Ф х₃.

Из следствия теоремы 7.5 имеем, что g — подстановка. Построим независимые циклы графа Г(g). При построении очередного цикла выбираем в качестве начальной вершину х, нс использованную при построении предыдущих циклов, и вычисляем элементы последовательности g_>(x) до тех нор, пока впервые не выполнится равенство g^l(x) = х, означающее, что элемент х принадлежит циклу длины /. В данном примере вычисления дают результаты:

• 1) g (0, 0, 0) = (0, 0, 0), значит t_{(0 0 0}>= 1;
• 2) Ж0, 0, 1) = (1, 0, 0), Ж1, 0, 0) = (1, 1, 0), Ж1, 1, 0) = (0, 1, 1), Ж0, 1, 1) = (0, 0, 1),

значит ?_{(0 0} i) = ?(i_t о, о>⁼ *(1, i, o>⁼ %), i, i) ⁼ 4;

• 3) g (0, 1,0) = (1,0, l), g (l, 0, 1) = (0, 1,0), значит t^_{0 t 0)} = ?_{(1 0 1}} = 2;
• 4) Ж1, 1″ 1) = (1. t 1)" значит t_(l, _1}= 1.

Тогда цикловая структура преобразования g имеет вид (П²1, 210, 410); период преобразования g равен НОК (1, 2, 4) = 4. О.