Множества, свободные от решений линейных уравнений

• Автор: Саргсян, Ваге Гнелович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 53 с.

Оглавление
Введение

Глава 1. Асимптотика логарифма числа (ДД)-МСС в группах простого порядка

1.1 Определения и вспомогательные утверждения

1.2 Основная лемма

1.3 Доказательство асимптотики логарифма

Глава 2. Оценки числа (к,1)-сумм в группах простого порядка

2.1 Основные понятия

2.2 Нижняя оценка числа (к, /)-сумм в группах простого порядка

2.3 Верхняя оценка числа (к, I)-сумм в группах простого порядка

Глава 3. Оценки максимальной мощности (£;Д)-МСС в абелевых группах

3.1 Основные понятия
3.2 Максимальная мощность (к,/)-МСС в циклических группах
3.3 О максимальной мощности (кД)-МСС в абелевых группах
Список литературы

Введение
Теория перечисления, связанная с проблемами существования, построения и подсчета числа элементов заданного множества, обладающих некоторыми свойствами, представляет собой важный раздел дискретной математики. К проблемам теории перечисления относятся, например, задачи о числе п-вершинных неизоморфных графов с определенными свойствами, числе решений задач целочисленного линейного программирования или о числе изомеров химических элементов. Традиционным и широко используемым методом решения подобных задач является классический метод производящих функций, связанный с использованием перечислительных теорем Пойя, де Брейна и Робинсона. Однако метод производящих функций требует существования разрешимых рекуррентных соотношений, что не всегда выполняется.
В теории перечисления достаточно часто возникают задачи оценки числа множеств с запретами. Такими являются, например, задачи о числе связных подмножеств, с заданной мощностью границы, в графах, числе антицепей в унимодальных частично упорядоченных множествах, числе независимых множеств в регулярных графах и о числе множеств, свободных от решений линейных уравнений (МСРЛУ), в конечных абелевых группах. Как правило, для таких задач отсутствуют разрешимые рекуррентные соотношения. В связи с этим для решения этих задач разработали метод контейнеров. Сущность данного метода состоит в том, что для оценки мощности семейства, которое мы оцениваем, строится система, так

называемых «контейнеров», такая, что каждый элемент семейства содержится полностью или частично в некотором контейнере из построенной системы. В случае, когда мы имеем дело с задачей нахождения числа объектов, обладающих свойством наследственности, для нахождения нижней оценки логарифма этого числа часто бывает достаточно оценить снизу размер максимального по мощности объекта, обладающего свойством наследственности. Метод контейнеров позволяет не только получать достаточно точные оценки, а в некоторых случаях и асимптотики. В частности, методом контейнеров получены асимптотика числа множеств, свободных от сумм (МСС), в начальном отрезке натуральных чисел (гипотеза Камерона-Эрдёша), асимптотика числа МСС в конечных абелевых группах четного порядка, и асимптотика числа МСС в группах простого порядка.
Основными задачами диссертации являются оценка числа МСРЛУ в циклических группах, нахождение максимальной мощности МСРЛУ в конечных абелевых группах и оценка числа подмножеств, представимых в виде суммы и разности заданного числа подмножеств в циклических группах. Для решения этих задач существенно использовались результаты из теории сложения множеств (например, теоремы Коши-Давенпорта, Полларда, Кнезера, Воспера). При получении верхних оценок используется техника, связанная с преобразованиями Фурье.
В диссертации получена асимптотика логарифма числа МСРЛУ в группах простого порядка, найдено точное значение максимальной мощности МСРЛУ в циклических группах, улучшена нижняя оценка максимальной мощности МСРЛУ в конечных абелевых группах, а также найдено точное значние максимальной мощности МСРЛУ в конечных абелевых группах при некоторых ограничениях на их экспоненту. Получены верхнюю и нижнюю оценки числа подмножеств, представимых в виде суммы и разности заданного числа подмножеств в группах простого порядка.

Положим 7£о = [(А; + /)N1 + 1, Ь. Покажем, что для любого х 6 Ко выполняется неравенство

Рг(х<£ кА-1А) < ( (31)
Пусть (х
Рг(х Аь4 — /Л) <
< Рг((х( Н
... к{х + --- + х9к- хчш
< Рг((хр + + х]} - х{}+1
... к(хп + ... + х1--хЦ1
= Рг((х1£АЧ---Ух111£А)&...к(хп£АЧ---Ух1кп+1£А))
= Рг ((х*1 £ Л) V V (*& $А)) ... Рг {(хп£ А) V V (*& * А))
= Рг ((х1 € А)к ... &(х+г £ Л)) ... Рг ((х}" € А)к ... к(хп+1 Е Л))
= (1 - Рг ((х}1 € А)к ... к{х]}+1 Е А))) х
... х (1 -Рг ((х(п е А)к ... к(х{п+1 еА))). (32)
Легко видеть, что для любого X Е 7Ко векторы
(х-г(к-1 - 1),гг) Е СЭк,1,ь(х)> 1 < * < [х/(к + /)] ,

попарно не пересекаются.
Отсюда и из (32) следует справедливость неравенства (31).
Положим С3 = ЗЬ + 1, (3 + 1 )Ь — (к + 1)Мк,1 — 1], 3 = 1
Заметим также, что для любого х Е С3, 3 = К > к + I — 1, векторы
(х - (к + 1 - 1 )(Ь - г),Ь - г
Г V
к-1 I