Случайные уравнения над свободными полурешётками | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/1

Случайные уравнения над свободными полурешётками

Исследуются уравнения от одной переменной над свободными полурешётками. Установлено, что среднее число решений уравнения над свободной полурешёткой 3 п + 2 • 2n ранга n равно -. Доказано, что среднее число неприводимых компонент 3 • 2п алгебраических множеств, определяемых уравнениями над свободной полурешёткой счётного ранга, равно 1.

Random equations over free semilattices.pdf Введение В современной математике генерация и изучение свойств случайных алгебраических объектов является одним из важных и интересных направлений. Порождение случайных групповых уравнений рассматривалось в работах [1, 2], относительно разрешимости случайных уравнений в группах см. также [3]. С помощью работ [4, 5] понятие уравнения можно определить для произвольной алгебраической системы функционального языка. Таким образом, можно рассматривать и изучать характеристики уравнений над многими классами алгебраических систем, в частности над полурешётками [6]. В данной работе исследуются вероятностные характеристики множества решений уравнений над свободными полурешётками. Вычисляется среднее число решений случайно сгенерированного уравнения (теорема 3), а также среднее число неприводимых компонент алгебраического множества, определённого уравнением над свободной полурешёткой (теорема 4). Каждая теорема иллюстрируется примером для свободной полурешётки ранга 2. 1. Основные определения Полурешёткой называется полугруппа, удовлетворяющая тождествам xy = yx (коммутативности) и xx = x (идемпотентности). В работе рассматривается свободная полурешётка Fn ранга n с множеством свободных порождающих a1,... ,an и с присоединённой единицей е (Vx Е Fn (xe = ex = x)). Произвольный неединичный элемент а из Fn допускает единственное представление в виде произведения а = ail ai2 ... aik, где i1 < i2 < ... < ik, k ^ n. Число k будем называть длиной элемента а и обозначать | a |. Длину элемента е полагаем равной 0. Пусть X = {xi, ..., xm} -множество переменных; Fn-термом т(X) будем называть одно из следующих выражений: w(X)c, w(X), c, где w(X) -произведение переменных xi Е X; c - элемент полурешётки Fn. Уравнением над Fn называется равенство двух Fn-термов: s(X) = t(X), хотя бы один из которых содержит переменные. Элементы полурешётки Fn, входящие в запись уравнения, будем называть константами. Решением уравнения s(X) = t(X) называется набор значений переменных xi, подстановка которых в уравнение s(X) = t(X) обращает его в верное равенство. Уравнение, имеющее хотя бы одно решение, называется совместным. Уравнение, не имеющее решений, называется несовместным. Множество всех решений уравнения s(X) = t(X) будем обозначать VFn(s(X) = t(X)). Пример 1. Уравнение a1a2x1 = a3a4x2 является совместным. Одним из его решений является набор x1 = a3a4, x2 = a1a2. Уравнение a1a2x1 = a3a4 является несовместным, поскольку при любом значении переменной x1 в левой части уравнения будет присутствовать элемент a2, который не содержится в правой части. Все уравнения над полурешёткой Fn можно разделить на два типа: 1) уравнения, в которых переменные присутствуют только в одной части; будем называть такие уравнения уравнениями I типа; 2) уравнения, обе части которых содержат переменные - уравнения II типа. Заметим, что любое уравнение II типа имеет решение над Fn. В самом деле, выбирая каждую из переменных xk, входящих в уравнение, равной произведению констант левой и правой частей, получим верное равенство. В работе рассматриваются уравнения над полурешёткой Fn от одной переменной. Множество всех таких уравнений обозначим через Eqn. Будем обозначать: Eqn - множество всех уравнений I типа из Eqn, Eqn - множество всех уравнений II типа из Eqn. Уравнения из Eqn^ представимы либо в виде c1x = c2, c1,c2 Е Fn, либо в виде c3 = c4x, c3, c4 Е Fn, а уравнения из Eq2n имеют вид c5x = c6x, c5 ,c6 Е Fn. Поскольку |Fn| = 2n, легко видеть, что |Eqn| = 2 ■ 2n ■ 2n = 2 ■ 4n, a |Eqn| = 2n ■ 2n = 4n. Все уравнения из множества Eq2n совместны. Найдём количество совместных в Eqn. Допустим, уравнение из Eqn имеет вид c1x = c2. Для того чтобы такое уравнение было совместным, необходимо, чтобы константа c1 состояла только из букв, входящих в состав константы c2, и никаких других. Таким образом, количество совместных уравнений данного вида равно nk Е Ck Е Ck = зп Здесь СП - количество вариантов выбрать константу c2, состоящую из k букв, а C'jS - количество допустимых констант ci, состоящих из s букв, входящих в состав c2. Аналогично рассуждая для уравнений вида c3 = c4x, получим, что количество совместных уравнений из Е^П равно 2 ■ 3П. 2. Математическое ожидание числа решений случайно выбранного уравнения Так как множества Eq^ и Е^Л конечны, на них можно ввести равномерную вероятностную меру и определить следующие случайные величины. Пусть £i - случайная величина, равная количеству решений случайно выбранного уравнения из Eq1n, а £2 - случайная величина, равная количеству решений случайно выбранного уравнения из Eq2n. Отметим, что случайные величины и £2 могут принимать целые значения от 0 до 2n. Теорема 1. Математическое ожидание числа решений случайно выбранного уравнения из Е^П равно 1: E£i = 1. Доказательство. В Eqn содержится 2 ■ 4n уравнений, при этом только 2 ■ 3n из них являются совместными. Учитывая, что все варианты выбора уравнения равновероятны, получаем P[£i = 0] 2 • 4n - 2 • 3n 4П_3л Cn2n t (здесь Cn - число слов длины t, т. е. число всех вариантов выбора константы a, а Cnk-t k=0 n-t буквы из a). Аналогичные рассуждения верны и для уравнений вида c Таким образом, имеем ^cdi, c, dd (( Fn. 2 . 4n 4n Далее, предположим, что уравнение xa = b, a,b E Fn, имеет хотя бы одно решение. Это означает, что a может содержать только буквы из b. Допустим, что |b| = s, |a| = t, где t ^ s ^ n. Любое решение такого уравнения обязано содержать все буквы из b, не входящие в состав a, и при этом может содержать любые буквы из a. Следовательно, количество решений такого уравнения равно 2t, т.е. однозначно определяется длиной элемента a. Получаем, что число всех уравнений, имеющих ровно 2t решений, равно n-t Ct Ck Cn Z^ Cn-t k=0 n- t количество вариантов выбрать константу b, содержащую все 4n 3n 4n = 12 ■ Cn 2n если I если I -иначе. 0; Cn 2n P[6 = 1] 2г, где 0 ^ i ^ n; 2 4n 4 n 0 Математическое ожидание £i равно 4n _ 3n n Ci 2'n-i E£i = 0 ■ --+ £ 2i - 2n n - V C i 4n ^ п 4 i=0 n 4n i=0 Теорема доказана. Пример 2. Рассмотрим полурешётку F2, порождённую множеством {а1, а2}, т. е. состоящую из элементов {е, а\, а2, а\а2}. Выпишем все уравнения из множества Eq^ (табл. 1). Таблица 1 Уравнение Количество решений Уравнение Количество решений X = £ 1 x = a2 1 xai = £ 0 xai = a2 0 xa2 = £ 0 xa2 = a2 2 xaia2 = £ 0 xaia2 = a2 0 x = ai 1 x = aia2 1 xai = ai 2 xai = aia2 2 xa2 = ai 0 xa2 = aia2 2 xaia2 = ai 0 xaia2 = aia2 4 £ = x 1 a2 = x 1 £ = xai 0 a2 = xai 0 £ = xa2 0 a2 = xa2 2 £ = xaia2 0 a2 = xaia2 0 ai = x 1 aia2 = x 1 ai = xai 2 aia2 = xai 2 ai = xa2 0 aia2 = xa2 2 ai = xaia2 0 aia2 = xaia2 4 Составим ряд распределения случайной величины ^ а 0 1 2 3 4 p 14/32 8/32 8/32 0 2/32 Математическое ожидание E£i = 1 • 8/32 + 2 • 8/32 + 4 • 2/32= 1 совпадает с результатом теоремы 1. Теорема 2. Математическое ожидание числа решений случайно выбранного уравнения из Eq2n равно in '3х n 2 Доказательство. Поскольку |Eqn | = 4n, получаем 2n 2n tEq2 (t) I 2n E& = E t P[6 = t] = E = 4n E tEqn(t), t=о t=о 4 4 t=0 где Eqn(t) -количество уравнений из Eq2n, имеющих ровно t решений. Поскольку каждое уравнение участвует в полученной сумме ровно один раз, то 1 2n 1 7n E tEqn(t) = - E |VF„(s(x) = f (x))l, 4 t=0 4 s{x)=f{x)eEql где \VFn(s(x) = f (x))| - количество решений уравнения s(x) = f (x) E Eqn. Обозначим через rn(a) количество уравнений, удовлетворяющих точке а E Fn. Изменив порядок суммирования, получаем E6 = 4n E |VFn(s(x) = f(x))| = 1 E rn(a). 4 s(X)=/(X)eEq2 4 aGF„ Пусть xb = xc - произвольное уравнение из Eq- (все уравнения этого типа совместны) и a Е F- - его решение. Представим константы b и c в виде b = da', c = da'', где d не содержит букв из a, a' и a" могут содержать только буквы из a. Предположим, что |a| = l. Тогда a' и a'' - подмножества некоторого слова из l букв, d - подмножество некоторого слова из n - l букв. Количество уравнений, удовлятворяющих точке a, равно n-l l l rn(a) = E СП-I E Cj E Cj = 2n-l ■ 2l ■ 2l = 2n+l. i=0 j=0 j=0 Подставляя этот результат в выражение для математического ожидания, получаем 1 1 n 1 n 1 /o\ n = T- E rn(a) = - E Cn2n+l = - ■ 2n E Cn2l = - ■ 3n = ' Л- ^ y ' Л - - An П О- \ 4 aEFn 4 1=0 4 l=0 2 \ Теорема доказана. ■ Пример 3. Вновь рассмотрим полурешётку F2 и выпишем уравнения из Eq, (табл. 2). Таблица 2 Уравнение Количество решений Уравнение Количество решений x - x 4 x - xa2 2 ^ca i - x* 2 xai - xa2 1 X&2 - x 2 xa2 - xa2 4 xa\a^ - x 1 xaia2 - xa2 2 x• - ^xa* i 2 x - xaia2 1 xai - xai 4 xai - xaia2 2 xa2 - xai 1 xa2 - xaia2 2 xaia2 - xai 2 xaia2 - xaia2 4 Составим ряд распределения случайной величины £2: £2 0 1 2 3 4 p 0 4/16 8/16 0 4/16 Видим, что математическое ожидание E£2 = 1 ■ 4/16 + 2 ■ 8/16 + 4 ■ 4/16 = 36/16 = 9/4 совпадает с результатом теоремы 2. Теперь найдём математическое ожидание случайной величины £, равной количеству решений случайно выбранного уравения из Eq . Теорема 3. Математическое ожидание числа решений случайно выбранного уравнения из Eq равно 3- + 2 ■ 2- E£ = 3 ■ 2- Доказательство. Случайная величина £ может быть представлена в виде £ £' + £'', где ' I 0, если уравнение из Eq-, w | 0, если уравнение из Eq-, 1 £i иначе; I £2 иначе. 1 2 2 2 1 1 Поскольку \Eql| = 2|E^I, то E£' =3 ■ 0 + ^ = 3 E£i и E£'' = 3 ■ 0 + ^ E& = 3 E&. Используя теоремы 1 и 2, получаем 2 1 2 1/3 \n 3n + 2 • 2n * = *+E? = 3 E?i + 1 e^2 = 2 + i(1) =^2^. Теорема доказана. ■ Пример 4. Выпишем все уравнения от одной переменной над полурешёткой F2 (табл. 3). Таблица 3 Уравнения Количество решений Уравнение Количество решений x = £,£ = x 1 x = x 4 xai = £, £ = xai 0 ^ca i - 2 xa2 = £, £ = xa2 0 xa2 = x 2 xaia2 = £, £ = xa3 0 xaia2 = x 1 x = ai, ai = x 1 - ^ca i 2 xai = ai, ai = xai 2 xai = xai 4 xa2 = ai, ai = xa2 0 xa2 = xai 1 xaia2 = ai, ai = xaia2 0 xaia2 = xai 2 x = a2, a2 = x 1 x = xa2 2 xai = a2, a2 = xai 0 xai = xa2 1 xa2 = a2, a2 = xa2 2 xa2 = xa2 4 xaia2 = a2, a2 = xaia2 0 xaia2 = xa2 2 x = aia2, aia2 = x 1 x = xaia2 1 xai = aia2, aia2 = xai 2 xai = xaia2 2 xa2 = aia2, aia2 = xa2 2 xa2 = xaia2 2 xaia2 = aia2, aia2 = xaia2 4 xaia2 = xaia2 4 Составим таблицу распределения случайной величины e 0 1 2 3 4 p 14/48 12/48 16/48 0 6/48 Математическое ожидание E£ = 1 ■ 12/48 + 2 ■ 16/48 + 4■ 6/48 = 68/48 = 17/12, очевидно, соответствует теореме 3. Будем рассматривать уравнения над полурешёткой F, которые в своей записи содержат только константы из полурешётки Fn. Например, для n = 2 будем рассматривать те уравнения над F, в записи которых могут присутствовать только константы £,ai,a2,a\a2, т.е. элементы полурешётки F2. Определим случайную величину ф, равную количеству неприводимых компонент множества решений случайно выбранного уравнения над F с константами из Fn. Теорема 4. Математическое ожидание числа неприводимых компонент множества решений случайно выбранного уравнения над F c константами из Fn равно Еф = 1. Доказательство. Рассмотрим уравнения I типа, т. е. уравнения вида xa = a' или a' = xa, где a, a' E Fn. Множество решений любого такого уравнения конечно, потому что x может состоять только из букв, входящих в состав a'. Это означает, что случайная величина ф для любого из уравнений данного вида равна количеству решений этого уравнения. Таким образом, для уравнений I типа ф может принимать следующие значения: 0,1, 2, 4,... , 2k,... , 2n. Теперь рассмотрим уравнения II типа. Представим их в виде xab = xa'b, где a,a',b E Fn и a П a' = 0. Поскольку любое решение такого уравнения имеет вид x = aa't, координатная полурешётка множества решений V(xab = xa'b) вкладывается в полурешётку F*, порождённую множеством |ai... an ...} U {t}. В таком случае, как следует из работы [7], множество V(xab = xa'b) является неприводимым. Следовательно, ф = 1 для любого уравнения II типа. Обобщим вышесказанное. Имеем, что ф = 0 для 2(4n - 3n) несовместных уравнений I типа. Далее, ф = 1 для всех уравнений II типа и для уравнений I типа, имеющих ровно одно решение, т.е. для 4n + 2СП2п уравнений. Наконец, по формуле (1) ф = 2' для 2Cn 2п-г уравнений I типа, где i = 1, 2,... ,n. Таким образом, получаем 2(4n - 3n) 4n + 2Cn ■ 2n ™ . 2Cn2n-г 1 2СП2п ™ . 2C2n Еф = 0 ■ --- + 1--1-n-+ E 2г-n-= - + -- + E 2г-- и 3 ■ 4n 3 ■ 4n г= 3 ■ 4n 3 3 ■ 4n г= 3 ■ 4 n г 1 ,2C.2n-г 12 n C. ■ 2n 12 г=0 n 12 Cn ^ + E 2^7" = ^ + ^ E ^^ = ^ + ^ ■ ^ ^ = 1. О ^-' О Л n О О ^-' /1 г) О О On О О 3 г=0 3 ■ 4n 3 3 г=0 4n 3 3 2n 3 3 Теорема доказана. ■

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

свободная полурешётка, уравнение, неприводимые компоненты, free semilattice, equation, irreducible components

Авторы

ФИООрганизацияДополнительноE-mail
Вахрамеев Михаил АнатольевичИнститут математики им. С. Л. Соболева СО РАНаспирантvahrmih@yandex.ru
Всего: 1

Ссылки

Oilman R., Myasnikov A., and Roman'kov V. Random equations in nilpotent groups // J. Algebra. 2012. V.352. No. 1. P. 192-214.
Oilman R., Myasnikov A., and Roman'kov V. Random equations in free groups // Groups Complexity Cryptol. 2011. V. 3. No. 2. P. 257-284.
Roman'kov V. Equations over groups // Groups Complexity Cryptol. 2012. V. 4. No. 2. P. 191-239.
Daniyarova E., Miasnikov A., and Remeslennikov V. Unification theorems in algebraic geometry // Algebra and Discrete Mathematics. Hackensack, 2008. P. 80-112.
Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н Алгебраическая геометрия над алгебраическими системами. II. Основания // Фундамент. и прикл. матем. 2012. Т. 17. №1. С.65-106.
Шевляков А. Н. Эквивалентные уравнения над полурешетками // Сиб. электрон. матем. изв. 2016. Т. 13. С. 478-490.
Шевляков А. Н. Элементы алгебраической геометрии над свободной полурешеткой // Алгебра и логика. 2015. Т. 54. №3. С. 399-420.
 Случайные уравнения над свободными полурешётками | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/1

Случайные уравнения над свободными полурешётками | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/1