Свойства еильно зависимых n-арных полугрупп | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/10

Свойства еильно зависимых n-арных полугрупп

Приводится обзор результатов о свойствах сильно зависимых n-арных полугрупп, обобщающих известные результаты о строении и свойствах n-арных групп. Класс сильно зависимых функций является расширением класса n-арных квазигрупп. Рассмотрены варианты обобщения понятия существенной зависимости функции от переменной. Поясняется, что класс сильно зависимых функций, с одной стороны, наследует многие важные свойства квазигрупп с точки зрения применения операции бесповторной суперпозиции. С другой стороны, в некоторых случаях он является очень широким и в него попадают почти все функции. Приведены аналоги теорем Поста и Глускина - Хоссу, содержащие общее описание строения сильно зависимых n-арных полугрупп. Описано строение групп автотопий таких операций.

Properties of strong dependance n-ary semigroups.pdf 1. Варианты определения понятия зависимости функции от переменной Для двоичных функций важную роль играет понятие существенной зависимости функции от переменной. При переходе к функциям k-значной логики понятие зависимости может быть определено различными способами. Рассмотрим четыре варианта такого определения. Пусть X - непустое конечное множество. Рассмотрим следующие классы функций вида f : Xn ^ X при n ^ 2. Класс Фо состоит из всех функций, существенно зависящих от всех своих переменных, т. е. Vi, 1 ^ i ^ n, 3ai,..., ai-i, ai+i,...,an G X 3x, y G X, такие, что f (ai,... ,ai-i,x,ai+i,..., a„) = f (ai,..., aj-i, y, ат,... , a„). (1) Класс Ф1 состоит из всех сюрьективных функций f, таких, что Vi Vx,y G X 3ai,..., ai-1, ai+1,... , an G X, такие, что выполнено неравенство (1). Этот класс был введён в [1] при изучении свойств операций, удовлетворяющих тождествам (i, j ^ассоциативности для пар {i, j}, содержащихся в некотором множестве M. Как показано в [1], для функций из этого класса выполнение тождеств ассоциативности для множества M равносильно выполнению тождества ассоциативности только для некоторой одной пары. Класс Ф2 состоит из сильно зависимых функций, т. е. Vi 3a1,... , ai-1, ai+1,... , anGX, такие, что унарная функция f (a1,... , ai-1, Xi, ai+1... , an) является подстановкой по переменной Xj. Для конечных множеств X этот класс функций замкнут относительно операции бесповторной суперпозиции, т. е. бесповторная суперпозиция таких функций является сильно зависимой в том и только в том случае, когда каждая из функций, участвующих в суперпозиции, также является сильно зависимой [2]. Класс Ф3 состоит из n-квазигрупп на множестве X, т. е. Vi Va1,..., ai-1, ai+1,..., an G G X унарная функция f (a1,... , ai-1, Xj, ai+1,... , an) является подстановкой по переменной Xi. Изучению свойств n-квазигрупп уделялось наибольшее внимание в связи с их многочисленными применениями в области комбинаторики, теории кодирования, планировании эксперимента и т.д. (см., например, [3]). Этот класс также замкнут относительно операции бесповторной суперпозиции. В общем случае имеют место включения Ф3 С Ф2 С Ф1 С Ф0, причём при k = 2 Ф0 = Ф1 = Ф2 и при каждом n ^ 1 класс Ф0 содержит только две функции, а при k > 2 все включения оказываются строгими. Приведём оценки мощностей этих классов. Для классов Ф0 и Ф1 из определения вытекают неравенства kfcn - nkfc"-1 ^ |Ф0| ^ kfcn - kfcn-1, kkn - nk(fc-1)fcn-1 ^ |Ф1| ^ kkn - k(fc-1)fcn-1. Значит, 1 > |Ф01/kkn ^ |Ф11/kkn - 1 при n ^ 2, k ^ 2 и max{n, k} - то, так как всегда nkk" 1 n nk(k-1)kn 1 n kkn = k(k-1)kn-1 ^ kkn = kkn-1 - Для класса Ф2 имеем kkn - n(kk - k!)kn-1 ^ |Ф2| ^ kkn - (kk - k!)kn-1. Поэтому при n - то и фиксированном k почти все функции k-значной логики являются сильно зависимыми, а при k - то в общем случае имеет место Утверждение 1 [4, 5]. Пусть е > 0 и k - то. При n > k/ln k + 1/2 + е почти все функций k-значной логики от n переменных являются сильно зависимыми. Если n < k/ln k + 1/2 - е, то почти все функции k-значной логики от n переменных не являются сильно зависимыми. Так как классы Ф0 и Ф1 не замкнуты относительно операции бесповторной суперпозиции, то при изучении полугрупповых операций, удовлетворяющих тождествам ассоциативности, имеет смысл рассматривать только сильно зависимые функции. 2. Строение еильно зависимых n-арных полугрупп Напомним, что моноидом называется бинарная полугруппа с единицей. Подмоноид моноида G = (X, о) -это подмножество H моноида G, которое замкнуто относительно операции о. Единица моноида H должна совпадать с единицей моноида G. При n =2 каждая бинарная полугруппа (X, *) с сильно зависимой операцией * является моноидом. В частности, ассоциативная квазигруппа является группой. Этот факт вытекает из следующих утверждений, доказанных в [6, с. 57]: 1) Если для бинарной операции * найдутся элементы a,b Е X, такие, что трансляции La = (aXx) и Rb = (жХь) являются подстановками, то операция * главно-изотопна операции с единицей, причём изотопия имеет вид (R-1, L-1, iU). 2) Если бинарная операция с единицей о изотопна ассоциативной операции *, то операция о изоморфна операции *, при этом изоморфизм имеет вид ^ = L-1 R-1 (теорема A. A. Алберта). Пусть n ^ 3. Непустое конечное множество X с заданной на нём n-арной операцией f называется n-арной полугруппой (n-полугруппой), если при всех i, j, 1 ^ i < j ^ n, выполняются тождества {i, j}-ассоциативности f (xi, . . . , f . . . , 1) , £г+га> . . . , x2n-1) = f (x1, . . . , xj -1, f (xj, . . . , xj+ra-1), . . . , x2n-1) , Xi,... , xn Е X. Если при этом n-полугруппа является n-квазигруппой, то она называется n- группой. Строение произвольной n-арной групповой операции впервые описано Э. Постом в [7] в терминах так называемой обёртывающей группы. Оказывается, что в случае сильно зависимых n-арных полугрупп можно получить аналогичное описание. В данном случае вместо группы используется моноид. Определение 1. Назовём моноид G = (X, о) обёртывающим для n-арной полугруппы (X, f) c сильно зависимой операцией f, если X С X, множество X порождает моноид G, а n-арная операция f связана с бинарной операцией в моноиде G равенством f (x1, ж2,..., xn) = ж1 о ж2 о ... о xn, x1,x2,...,xn G X. (2) Теорема 1 (аналог теоремы Э. Поста [8]). Пусть n ^ 3. Для конечной n-арной полугруппы (X, f) с сильно зависимой операцией f найдётся обёртывающий моноид G = (X, о), такой, что при некотором обратимом элементе a G X множеству X0 = = X о a-1 соответствует: подмоноид H = (X0, о), удовлетворяющий условиям G = (X), a о Xo о a-1 = Xo и |X| | |Xo|(n - 1). Если элемент g обратим, то |H*g| = |H| и при 0 ^ i < j ^ t - 1, где t - минимальное натуральное число с условием g* G H, выполняются равенства |H о gj | = |H о gj | и (Hоgj) П (Hоgj) = 0. Если G = (H, g), то для моноида G справедливо равенство |G| = = |H| • t. Поэтому в этом случае можно говорить, что моноид G допускает разложение на смежные классы по подмоноиду H. Таким образом, теорема Поста утверждает, что операция исходной n-арной полугруппы (X, f) по сути совпадает с ограничением операции x1 о x2 о ... о xn на смежный класс X = X0 о a обёртывающего моноида G = (X, о). Другой способ описания строения n-арной групповой операции получен в работах Л. М. Глускина [9] и М. Хоссу [10]. Аналог их результата для случая сильно зависимых функций имеет следующий вид: Теорема 2 (аналог теоремы Глускина - Хоссу [5]). Если f - ассоциативная сильно зависимая n-арная операция на конечном множестве X, то для некоторого моноида (X, *), обратимого элемента a и автоморфизма в этого моноида, таких, что en-1(x) = a * x * a-1, e(a) = a, справедливо тождество f (xi,... ,xn) = xi * e(x2) * e2(xs) * ... * en-1(xn) * a, (3) xi G X, i = 1 , . . . , n. В работе [11] обсуждается взаимосвязь теорем Поста и Глускина - Хоссу и утверждается, что они, по-сути, являются различными формами одного и того же результата. В данном случае это также справедливо и легко устанавливается при переходе от записи функции f с использованием операции о в обёртывающем моноиде к записи функции f с использованием операции * на самом смежном классе X = X0 о a. Если исходить из теоремы 1, то обозначим через < внутренний автоморфизм обертывающего моноида

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

n-арные полугруппы, сильно зависимые функции, группа ав-тотопий, n-ary semigroup, strongly dependent function, autotopy group

Авторы

ФИООрганизацияДополнительноE-mail
Черемушкин Александр ВасильевичФГУП «НИИ «Квант»доктор физико-математических наук, научный консультантavc238@mail.ru
Всего: 1

Ссылки

Сохацкий Ф. Н. Об ассоциативности многоместных операций // Дискретная математика. 1992. Т. 4. №1. С. 66-84.
Сосинский Л. М. О представлении функций бесповторными суперпозициями в трехзначной логике // Проблемы кибернетики. М.: Наука, 1964. Вып. 12. С. 57-68.
Белоусов В. Д. n-Арные квазигруппы. Кишинев: Штиинца, 1972. 277с.
Черемушкин А. В. Некоторые асимптотические оценки для класса сильно зависимых функций // Вестник Томского госуниверситета. Приложение. 2006. №17. C. 87-94.
Черемушкин А. В. Аналоги теорем Глускина - Хоссу и Малышева для сильно зависимых n-арных операций // Дискретная математика, 2018. Т. 30. Вып. 2. С. 15-24.
Bruck R. H. A survey of binary systems. Berlin; Heidelberg; New York: Springer, 1958. 185 p.
Post E. L. Polyadic groups // Trans. Amer. Math. Soc. 1940. V.48. No. 2. P. 208-350.
Черемушкин А. В. Теорема Поста для сильно зависимых n-арных полугрупп // Дискретная математика. 2019. Т. 31. №2. С. 153-158.
Глускин Л. М. Позиционные оперативы // Математич. сборник. 1965. Т. 68(110). №3. С.444-472.
Hosszu M. On the explicit form of n-group operations // Publ. Math. 1963. V. 10. No. 1-4. P. 88-92.
Гальмак А. М., Воробьев Г. Н. О теореме Поста - Глускина - Хоссу // Проблемы физики, математики и техники. 2013. Вып. 1(14). С. 55-59.
Черемушкин А. В. Бесповторная декомпозиция сильно зависимых функций // Дискретная математика. 2004. Т. 16. Вып.3. С. 3-42.
Черемушкин А. В. Декомпозиция и классификация дискретных функций. М.: Курс, 2018. 288с.
Khodabandeh H. and Shahryari M. On the automorphisms and representations of polyadic groups // Commun. Algebra. 2012. V.40. No. 6. P. 2199-2212.
 Свойства еильно зависимых n-арных полугрупп | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/10

Свойства еильно зависимых n-арных полугрупп | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/10