Случайные уравнения над свободными полурешётками Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Вахрамеев Михаил Анатольевич

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

Похожие темы научных работ по математике , автор научной работы — Вахрамеев Михаил Анатольевич

Random equations over free semilattices

In the paper, we study equations in one variable over free semilattices. We show that the average number of solutions of a random equation over a free semilattice of 3n + 2 • 2n a rank n is equal to -. It is proved that the average number of irreducible components of algebraic sets defined by equations over a free semilattice of a countable rank is equal to 1.

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

2017 Теоретические основы прикладной дискретной математики №36

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ

СЛУЧАЙНЫЕ УРАВНЕНИЯ НАД СВОБОДНЫМИ ПОЛУРЕШЁТКАМИ

Институт математики им. С. Л. Соболева СО РАН, г. Омск, Россия

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

Установлено, что среднее число решений уравнения над свободной полурешёткой 3n + 2 ■ 2n ^

ранга n равно -. Доказано, что среднее число неприводимых компонент

алгебраических множеств, определяемых уравнениями над свободной полурешёткой счётного ранга, равно 1.

Ключевые слова: свободная полурешётка, уравнение, неприводимые компоненты. DOI 10.17223/20710410/36/1

RANDOM EQUATIONS OVER FREE SEMILATTICES

M. A. Vakhrameev Sobolev Institute of Mathematics, Omsk, Russia E-mail: vahrmih@yandex.ru

In the paper, we study equations in one variable over free semilattices. We show

that the average number of solutions of a random equation over a free semilattice of 3n + 2 ■ 2n

a rank n is equal to — —. It is proved that the average number of irreducible components of algebraic sets defined by equations over a free semilattice of a countable rank is equal to 1.

Keywords: free semilattice, equation, irreducible components.

В современной математике генерация и изучение свойств случайных алгебраических объектов является одним из важных и интересных направлений. Порождение случайных групповых уравнений рассматривалось в работах [1, 2], относительно разрешимости случайных уравнений в группах см. также [3]. С помощью работ [4, 5] понятие уравнения можно определить для произвольной алгебраической системы функционального языка. Таким образом, можно рассматривать и изучать характеристики уравнений над многими классами алгебраических систем, в частности над полурешётками [6].

В данной работе исследуются вероятностные характеристики множества решений уравнений над свободными полурешётками. Вычисляется среднее число решений случайно сгенерированного уравнения (теорема 3), а также среднее число неприводимых компонент алгебраического множества, определённого уравнением над свободной полурешёткой (теорема 4). Каждая теорема иллюстрируется примером для свободной полурешётки ранга 2.

1. Основные определения

Полурешёткой называется полугруппа, удовлетворяющая тождествам ху = ух (коммутативности) и хх = х (идемпотентности). В работе рассматривается свободная полурешётка Еп ранга п с множеством свободных порождающих а1 . ап и с присоединённой единицей е (Ух € Еп (хе = ех = х)).

Произвольный неединичный элемент а из Еп допускает единственное представление в виде произведения а = аг1 аг2 . агк, где г1 < г2 < . < , к ^ п. Число к будем называть длиной элемента а и обозначать |а|. Длину элемента е полагаем равной 0.

Пусть X = —множество переменных; Еп-термом т(X) будем называть одно из следующих выражений: эд(Х)с, эд(Х), с, где эд(Х) —произведение переменных хг € X; с — элемент полурешётки Еп. Уравнением над Еп называется равенство двух Еп-термов: з(Х) = ¿(X), хотя бы один из которых содержит переменные. Элементы полурешётки Еп, входящие в запись уравнения, будем называть константами.

Решением уравнения ) = ¿(X) называется набор значений переменных хг, подстановка которых в уравнение ) = ¿(X) обращает его в верное равенство. Уравнение, имеющее хотя бы одно решение, называется совместным. Уравнение, не имеющее решений, называется несовместным. Множество всех решений уравнения ) = ¿(X) будем обозначать Урп(з^) = ¿(X)).

Пример 1. Уравнение а1а2х1 = а3а4х2 является совместным. Одним из его решений является набор х1 = а3а4, х2 = а1а2. Уравнение а1а2х1 = а3а4 является несовместным, поскольку при любом значении переменной х1 в левой части уравнения будет присутствовать элемент а2, который не содержится в правой части.

Все уравнения над полурешёткой Еп можно разделить на два типа:

1) уравнения, в которых переменные присутствуют только в одной части; будем называть такие уравнения уравнениями I типа;

2) уравнения, обе части которых содержат переменные — уравнения II типа.

Заметим, что любое уравнение II типа имеет решение над Еп. В самом деле, выбирая каждую из переменных , входящих в уравнение, равной произведению констант левой и правой частей, получим верное равенство.

В работе рассматриваются уравнения над полурешёткой Еп от одной переменной. Множество всех таких уравнений обозначим через Едп. Будем обозначать: Ед^ —множество всех уравнений I типа из Едп, Ед^ —множество всех уравнений II типа из Едп. Уравнения из Ед^ представимы либо в виде с1х = с2, с1, с2 € Еп, либо в виде с3 = с4х, с3,с4 € Еп, а уравнения из Ед^ имеют вид с5х = с6х, с5,с6 € Еп. Поскольку |Еп| = 2п, легко видеть, что |Е^| = 2 ■ 2п ■ 2п = 2 ■ 4п, а |Е^| = 2п ■ 2п = 4п.

Все уравнения из множества Ед^ совместны. Найдём количество совместных в Ед^. Допустим, уравнение из Ед^ имеет вид с1х = с2. Для того чтобы такое уравнение было совместным, необходимо, чтобы константа с1 состояла только из букв, входя-

щих в состав константы с2, и никаких других. Таким образом, количество совместных уравнений данного вида равно

Здесь Скк — количество вариантов выбрать константу с2, состоящую из к букв, а Ск — количество допустимых констант С1, состоящих из в букв, входящих в состав с2. Аналогично рассуждая для уравнений вида с3 = с4х, получим, что количество совместных уравнений из Е^ равно 2 ■ 3п.

2. Математическое ожидание числа решений случайно выбранного уравнения

Так как множества ЕдП и Е^П конечны, на них можно ввести равномерную вероятностную меру и определить следующие случайные величины. Пусть — случайная величина, равная количеству решений случайно выбранного уравнения из ЕдП, а £2 — случайная величина, равная количеству решений случайно выбранного уравнения из ЕдП. Отметим, что случайные величины и £2 могут принимать целые значения от 0 до 2п.

Теорема 1. Математическое ожидание числа решений случайно выбранного уравнения из Е^П равно 1:

Доказательство. В Е^ содержится 2 ■ 4п уравнений, при этом только 2 ■ 3п из них являются совместными. Учитывая, что все варианты выбора уравнения равновероятны, получаем Р[^1 = 0]

Далее, предположим, что уравнение ха = Ь, а,Ь Е имеет хотя бы одно решение. Это означает, что а может содержать только буквы из Ь. Допустим, что |Ь| = в, |а| = Ь, где Ь ^ в ^ п. Любое решение такого уравнения обязано содержать все буквы из Ь, не входящие в состав а, и при этом может содержать любые буквы из а. Следовательно, количество решений такого уравнения равно 2*, т.е. однозначно определяется длиной элемента а. Получаем, что число всех уравнений, имеющих ровно 2* решений, равно

количество вариантов выбрать константу Ь, содержащую все

С* 2п 4 (здесь Сп —число слов длины Ь, т. е. число всех вариантов выбора

константы а, а ^ С— к=0

буквы из а). Аналогичные рассуждения верны и для уравнений вида с Таким образом, имеем