Множества, свободные от произведений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный УНИВС,|Ц|||||| 11 им М В Ломоносова 'ЦЦЦЩЦ

□0306263 1

На правах рукописи

Петросян Тарон Гайкович

МНОЖЕСТВА, СВОБОДНЫЕ ОТ ПРОИЗВЕДЕНИЙ

01 01 09 - дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико - математических наук

Москва 2007

Работа выполнена на кафедре дискретной математики механико-математического факультета МГУ им М В Ломоносова

Научный руководитель

доктор физико-математических наук, профессор

Александр Антонович Сапоженко

Официальные оппоненты

доктор физико-математических наук руководитель отдела ИСП РАН Николай Николаевич Кузюрин

кандидат физико-магематических нау сотрудник ИППИ РАН Дмитрий Викторович Зиновьев

Ведущая организация

Вычислительный центр РАН

Защита диссертации состоится 18 мая 2007 г в 11 00 на заседании диссертационнного совета Д 501 001 44 в Московском государственном университете им М В Ломоносова по адресу 119992, ГСП-2, Москва Ленинские горы, МГУ, 2-ой учебный корпус, факультет ВМиК, аудитория 685

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ им М В Ломоносова http //www eme тзч га в разделе «Наука» - «Работа диссертационных советов» - «Д 501 001 44»

Автореферат разослан « { ^ » апреля 2007 г

Ученый секретарь диссертационного совета

профессор

Н П Трифонов

Общая характеристика работы

Актуальность темы

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

Основным методом, используемым в диссертации, является, так называемый, метод контейнеров, разработанный А А Сапоженко Кратко суть метода заключается в следующем Пусть Т и V являются семействами подмножеств множества S Будем говорить, что семейство V покрывает семейство если для любого элемента F £ Т существует такой элемент (называемый контейнером) Р € V, что F С Р Для семейства объектов, число которых требуется найти, строится некоторое специальное покрывающее семейство контейнеров Число контейнеров в силу их специального построения проще оценивать, чем число исходных объектов С помощью метода контейнеров получены эффективные верхние оценки, а в некоторых случаях и асимптотически неулучшаемые результаты До последнего времени данный метод применялся к задаче оценки числа МСП только в классе конечных абелевых групп В диссертации метод контейнеров применяется для произвольных конечных групп

Начало исследований в области оценки числа множеств, свободных от произведений, было положено в работе П Камерона (Cameron, Р )1 В ней исследовалась задача нахождения хаусдорфовой размерности семейства всех множеств, свободных от сумм (МСС2), в множестве натуральных чисел Независимо друг от друга Н Калкин (Calkm, N ), Н Алон

1Сашегоп, PJ , Cychc automorphisms of a countable graph and random sum-free sets, Graphs Combm , 1 (1985), 129-135

2Когда операция на множестве коммутативна, то подмножества, свободные от произведений, этого множества принято называть множествами свободными от сумм

(Alón, N ), П Эрдеш (Erdôs, Р) и А Гранвиль (Granville, А ) показали, что хаусдорфова размерность семейства всех МСС равна 1/2 Дальнейшие исследования были инициированы совместной работой3 П Эрдеша и П Камерона, в которой найдена асимптотика числа множеств, свободных от сумм, в отрезке натуральных чисел от п/3 до п и высказывают гипотезу о том, что число МСС во всем отрезке натуральных чисел [1, п] есть 0(2п/2) Гипотеза была доказана независимо А А Сапоженко4 и Б Грином5 (Green, В )

Если абелев случай изучался весьма интенсивно, то работ, изучающих множества, свободные от произведений, в произвольных конечных группах практически нет Для получения асимптотических результатов о числе МСС в конечных абелевых группах существенно использовались результаты теории сложения множеств о структуре и нижних оценках мощности суммы множеств (например, известная теорема Кнезера), которые затем применялись для доказательства расширительности графов Кэли Значительной трудностью, возникающей при переходе к некоммутативным группам, является отсутствие таких же сильных результатов о структуре и мощности суммы множеств, как в абелевом случае Другое затруднение вносят некоммутативность операции в группе и, как следствие, разные размеры произведения (левых или правых) смежных классов Это усложняет доказательство расширительности и построение подходящих графов Кэли В диссертационной работе эти проблемы преодолеваются с помощью детального анализа взаимного расположения левых и правых смежных классов, их произведений, выбора подходящего разбиения группы для построения непересекающихся графов Кэли Преодоление перечисленных выше трудностей делает возможным применение метода контейнеров При доказательстве асимптотики логарифма числа МСП возникает необходимость оценки числа так называемых троек Шура, то есть троек (х, у, z) G А3, таких, что ху = z Для решения этой задачи используется техника, связанная с преобразованиями Фурье

Задачи о числе и мощности максимального МСП в последние два десятилетия являются предметом активного изучения как за рубежом, так и в России Основной вклад в данную область исследований внесли следующие математики H Алон, Б Грин, П Камерон, В Лев , Т Лучак, И Ружа, А А Сапоженко, П Эрдеш, X П Яп и другие

3Cameron, Р Л, Erelos, Р , On the number of sets with various properties, Number Theory (Banff, AB, 1988), 61-79, de Gruyter, Berlin, 1990

4 А А Сапоженко, Гипотеза Камерона-Эрдеша, Математические вопросы кибернетики Выпуск 13 Изд-во Физматлит 2004

5Green, В , The Cameron Erdas Conjecture, Bull London Math Soc 36 (2004), no 6, 769-778

Цель работы

Основной целью диссертации является получение оценок числа МСП в конечных группах В процессе решения этой задачи возникла необходимость оценки размера максимального множества, задачи которая в абелевом случае широко исследована

Методы исследования

В работе используются методы теории графов, комбинаторики и функционального анализа В частности, применяются метод контейнеров и техника, связанная с преобразованиями Фурье

Научная новизна

Все результаты диссертации являются новыми и состоят в следующем

1 Найдена асимптотика числа множеств, свободных от произведений, в группах, содержащих хотя бы одну подгруппу индекса 2

2 Установлена асимптотика логарифма числа множеств, свободных от произведений, в конечных группах, таких, что мощность максимального МСП не меньше трети порядка группы

3 Установлена оценка числа множеств, свободных от произведений, в группах содержащих нормальную подгруппу простого индекса

4 Найден размер максимального множества, свободного от произведений, в конечных группах, содержащих нормальную подгруппу простого индекса р, р = 2 (mod 3)

Теоретическая и практическая ценность

Работа носит теоретический характер Расширена область применения метода контейнеров на случай некоммутативных групп Полученные при этом методы могут применяться при решении задач перечисления объектов с ограничениями на структуру

Апробация работы

Результаты диссертации докладывались и обсуждались на следующих семинарах и конференциях

- на семинаре "Дискретная математика и математическая кибернетика" под руководством В Б Алексеева, А А Сапоженко и С А Ложкина (кафедра математической кибернетики ВМиК МГУ) в марте 2007 г,

- на семинаре "Избранные вопросы алгебры" под руководством М В Зайцева, А А Михалева и И А Чубарова (кафедра высшей алгебры механико-математического факультета МГУ) в октябре 2006 г,

- на семинаре "Кольца и модули" под руководством В Н Латышева, А В Михалева и В А Артамонова (кафедра высшей алгебры механико-математического факультета МГУ) в 2005 г,

- на семинаре "Математические вопросы кибернетики" под руководством О Б Лупанова (механико-математический факультет МГУ) в 2004

г,

- на семинаре "Дискретный анализ" под руководством А А Сапо-женко, Н Н Кузюрина и В П Воронина (кафедра математической кибернетики ВМиК МГУ) в 2004-2007 гг,

- International Conference KROMSH-2006 The Seventeenth Crimean Autumn Mathematical School-Symposium (Crimea, Laspi-Batihman, Septembe 17-29, 2006)

- на XVI Международной школе-семинаре "Синтез и сложность управляющих систем" (Санкт-Петербург, 26-30 июня 2006 г),

- на XIV Международной конференции "Проблемы теоретической кибернетики" (Пенза, 23-28 мая 2005 г),

- на VIII Международном семинаре "Дискретная математика и ее приложения"(Москва, 2-6 февраля 2004 г),

- на VI Международной конференции "Дискретные модели в теории управляющих систем" (Москва, 7-11 декабря 2004 г),

Публикации

Основное содержание диссертации опубликовано в 6 работах [1-6], список которых приведен в конце автореферата Работ, написанных в соавторстве, нет

Структура и объем работы

Диссертация состоит из введения, трех глав и списка литературы Текст диссертации изложен на 52 страницах Список литературы содержит 39 наименований

Краткое содержание диссертации

Во введении излагается постановка решаемых в диссертации задач, формулируются основные цели работы и кратко описывается ее содержание

Первая глава посвящена оценке числа множеств, свободных от произведений, в конечных группах, содержащих подгруппу индекса 2 Получена асимптотика6 данного числа Этот результат обобщает на случай

6ТГ Петросян, О числе множеств, свободных от произведений, в группах четного порядка, Дискретная математика, 17 (2005), No 1, 89-101

произвольных конечных групп следующую теорему

[Сапоженко7, Lev-Luczak-Schoen8] Для любой абелевой группы G четного порядка п с числом подгрупп индекса 2, равным t, выполняются неравенства

t 2п/2 _ 2(n/4)(l+e(n)) < |PF(G)| < t 2n'2 + 2n(1/2"c), (1)

где с - положительная постоянная, а е(п) —» 0 при п —> оо

Доказательство проводится путем построения графов Кэли на объединениях смежных классов по некоторой подгруппе рассматриваемой группы Путем выбора смежных классов и правила, по которому соединяются ребра в графе Кэли, достигается регулярность данного графа Становится возможным применение оценок числа независмых множеств в регулярных графах, полученных А А Сапоженко

[Сапоженко9, Теорема 4] Пусть Г - п-вершинный регулярный граф степени к Тогда

\ЦТ)\ < 2?(1+0(V^T)) (2)

По построению графа Кэли пересечение каждого МСП с множеством вершин данного графа является независимым множеством Это позволяет использовать оценки числа независимых множеств в регулярных графах для оценки числа МСП В некоторых случаях требуется более сильная оценка числа независимых множеств Для этого устанавливается свойство расширительности графа Кэли Пусть d(N) обозначает границу множества N Граф называется 5-расширителем, если для любого независимого множества N верно неравенство

\N\<(l-6)\d(N)\

Исходя из построения графа Кэли, граница множества есть произведение двух множеств Таким образом, возникает необходимость оценки мощности произведения двух множеств Для этого применяются некоторые результаты из теории сложения множеств Например, следующая теорема

7А А Сапоженко, О числе множеств, свободных от сумм, в вбедееъга группах, Вестник Моек Ун-та сер 1, 2002, 4, 14-17

8Lev, V F Luc?ak, Т , Schoen, Т , Sum-free sets m abehan groups, Israel J Math 125 (2001), 347367

9A А Сапоженко, О числе независимых множеств в расширителях, Дискретная математика,

13 (2001), 1, 56-62

[Olson10, Th 2] Пусть А и В являются конечными непустыми подмножествами группы G, тогда существует подмножество S множества АВ и подгруппа Н группы G, такие, что |5| > ]А\ + |Б| — |ii|, и либо SH = S, либо HS = S

Установление свойства расширительности графа Кэли позволяет применить теорему о числе независимых множеств в расширителях

[Сапоженко11, Теорема 2] Пусть Г = {V,E) — п-вершинный регулярный граф степени к, являющийся 5-расширителем для некоторого О <6 < 1 Тогда

\Х(Г)\ < 2?М+°(/¥))

Таким образом, доказывается что число "нетипичных"МСП, то есть, тех МСП, которые не содержатся в смежном классе по некоторой подгруппе индекса 2, мало (о(2"/2))

В параграфе 1 1 приводятся основные понятия и вспомогательные теоремы При доказательстве теоремы возникла задача оценки числа подгрупп с малым индексом Лемма 1 дает оценку числа подгрупп конечной группы, индекс которых не превосходит 16

Условимся через tk(G) обозначать число подгрупп индекса к группы G Определим функцию tk (х) следующим образом

tk(x) = maxtk(G), если х 6 N, а в противном случае tk(x) = О \G\=x

Лемма 1 Для любых натуральных чисел кип выполняется рекуррентное неравенство

Н^к^п/к)^1^1-1 (3)

Следствие 1. Существуют такие положительные константы с\ и С2, что to(n) < п — 1, ¿з(n) < Cin2, U(n) < с2п5

Параграф 1.2 содержит доказательство основного результата диссертации

Теорема 1. Для любой группы G порядка п с числом подгрупп индекса 2, равным t, t> 1,

t 2n/2 _ 2n(i+v(n))/4 < p^Qj < t 2n/2 + 2"(!/2-0) (4)

10Olson, J E , On the sum of two sets in a group, Journal of Number Theory, 18 (1984), 110-120 ПЛ А Саюженко, О числе независимых множеств в расширителях, Дискретная математика,

13 (2001), 1, 56-62

где е > О, ip(n) —> 0 при п —> оо и второе неравенство справедливо, начиная с некоторого п

Во второй главе рассматриваются группы, которые не содержат подгруппы индекса 2, но в которых есть нормальная подгруппа Я другого простого индекса Показано, что в этом случае число множеств, свободных от произведений, есть о(2"/2) Здесь также используется метод контейнеров Рассматриваются графы Кэли на парах смежных классов факторгруппы G/H Далее, как и при доказательстве теоремы 1, число МСП в группе оценивается сверху через число независимых множеств Параграф 2.1 содержит вспомогательные утверждения теорему Дж Е Олсона (Olson, J Е )12 о сложении множеств в группах Данная теорема, дающая нижнюю оценку произведения двух множеств, необходима для оценки границы независимых множеств в графах Кэли С помощью полученных оценок доказывается, что некоторые из этих графов обладают свойством расширительности

\N\<(l-S)\dN\,

где d(N) - граница независимого множества N в графе Кэли на рассматриваемой паре смежных классов

В параграфе 2.2 доказывается основной результат главы

Теорема 2. Пусть G конечная группа порядка п, а К - ее нормальная подгруппа наименьшего простого индекса Пусть ¡(7 К\ — р, р > 3, где р - простое число Тогда

Третья глава посвящена доказательству асимптотики логарифма максимального числа множеств, свободных от произведений, в конечных группах

Множество D б PF(G) называется максимальным множеством, свободным от произведений, если для любого Т Е PF(G) выполняется \D\ > \Т\

В 2005 Б Грин и И Ружа13 показали, что логарифм числа МСС в абелевых группах порядка п асимптотически равен A(G) + о(п), где A(G) - порядок максимального МСП В параграфе 3 1 данная теорема обобщается на случай произвольных конечных групп

1201son ЛЬ , On the svm of two sets m a group Journal of Number Theory, 18 (1984), 110-120

13Green, В , Ruzsa, I Z , Sum-free sets m abehan groups, Israel J Math 147 (2005), 157-189

Теорема 3. Пусть G конечная группа порядка п, X(G) >1/3 Тогда

|PF(G)| = 2А^+0(П^")_1/45) (5)

При доказательстве используется конструкция из работы Грина и Ружи, идея которой состоит в покрытии семейства МСП семейством, так называемых, почти МСП, то есть подмножеств группы, порождающих не более чем о(п2) мультипликативных троек, то есть троек (х, у, z), таких, что ху — z Для оценки числа мультипликативных троек используются преобразования Фурье характеристических функций множеств

В параграфе 3.2 найден размер максимального множества, свободного от произведений, в группах, содержащих нормальную подгруппу простого индекса р, р = 2 (mod 3) Пусть /¿(G) = A(G)/|G|

Теорема 4. Пусть G группа порядка п, содержащая нормальную подгруппу Н индексар, р = 2 (mod 3) Если в G нет нормальной, подгруппы индекса меньшего чем р, то

Следствиями этой теоремы являются утверждения о размере максимального МСП в группах порядков pq и рп, где ряд- простые числа, р < q, р ф 3k + 1

Следствие 2. Пусть G группа порядка pq и р ф Зк + 1 при любом keN Тогда

A (G) = q, (6)

если р = 3, и

A (G) =

если р = 2 (mod 3)

Следствие 3. Пусть G имеет порядок рп, где р - простое и р = 2 (mod 3) Тогда p,(G) = | + ^

Автор пользуется случаем, чтобы выразить искреннюю благодарность своему научному руководителю профессору А А Сапоженко за постановку задачи, постоянное внимание к работе, ценные замечания и полезное обсуждение

Публикации автора по теме диссертации

[1] Т Г Петросян, О числе множеств, свободных от произведений, в группах четного порядка, Дискретная математика, 17 (2005), No 1, 89-101

[2] ТГ Петросян, Верхняя оценка числа множеств свободных от произведений, в одном классе групп, Дискретная математика, 19 (2007), No 1, 76-88

[3] Т Г Петросян, Число множеств, свободных от произведений, VIII Международный семинар "Дискретная математика и ее приложения" -М Изд-во механико-математического факультета МГУ, 2004, сгр 358361

[4] Т Г Петросян, Множества, свободные от произведений, в группах, VI Международная конференция "Дискретные модели в теории управляющих систем" - М Издательский отдел Факультета ВМиК МГУ им М В Ломоносова, 2004, стр 204-206

[5]ТГ Петросян, О множествах, свободных от произведений, Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики" - М Изд-во механико-математического факультета МГУ, 2005, стр 120-121

[6] ТГ Петросян, Размер максимального множества, свободного от произведений, в группах порядка pq, Материалы Международной школы-семинара "Синтез и сложность управляющих систем" (Санкт-Петербург, июнь 2006) - М Изд-во механико-математического факультета МГУ, 2006, стр 85-88

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписан з к печати 11 04 2007 г Формат 60x90 1/16 Уст печл 0,75 Тираж 80 экз Заказ 185 Тел 939-35.90 Тел /Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им MB Ломоносова, 2-й учебный корпус, 627 к

Введение \

I Число множеств, свободных от произведений, в группах, содержащих подгруппу индекса

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

§ 2 Асимптотика числа МСП в группах, содержащих подгруппу индекса 2.

II Верхняя оценка числа МСП в одном классе групп

§ 1 Вспомогательные утверждения.

§ 2 Число МСП в группах, не содержащих подгрупп индекса

III Асимптотика логарифма числа МСП в конечных группах

§ 1 Асимптотика логарифма числа МСП

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

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

§ 1.3 Асимптотика.

§ 2 Размер максимального МСП в одном классе групп.

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

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

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

В диссертации получена асимптотика числа МСП и размер максимального МСП в некоторых классах конечных групп, асимптотика логарифма числа МСП в конечных группах, при некоторых ограничениях на размер максимального МСП, оценка числа МСП в конечных группах, в которых индекс нормальной подгруппы является простым числом, большим чем 2.

История вопроса

Понятие множества, свободного от сумм (МСС), было введено Шуром в 1916 году для решения задач шифрования. Множество А называется множеством, свободных от сумм (МСС), если нет троек (x,y,z) G А3, удовлетворяющих уравнению х + у = z. Шур [30] показал, что невозможно разбить начальный отрезок натуральных чисел на конечное число МСС.

Исследовались две естественные перечислительные задачи:

1) нахождение размера максимального МСС,

2) оценка числа всех МСС.

В [17, 1985] П. Камерон оценивал хаусдорфову размерность семейства всех МСС в множестве натуральных чисел и предположил, что она равна 1/2. Финитизацией данной проблемы стал вопрос о числе МСС в начальном отрезке натуральных чисел. Начало исследований в этом направлении было положено совместной работой П. Эрдеша (Erdos Р.) и П. Камерона (Cameron Р.) [18], в которой высказана гипотеза о том, что мощность семейства всех МСС |SF([l,n])| в отрезке натуральных чисел [1, га] есть 0(2П/2).

Н. Калкин (Calkin N.) [16,1990], независимо, П. Эрдеш (Erdos Р.) и А.

Гранвиль (Granville А.) (неопубликованно) и, независимо, Н. Алон (Alon N.) [15, 1991] доказали предположение Камерона, показав, что

SF([l,n])|

Решение гипотезы Камерона-Эрдеша и асимптотика числа МСС в отрезке [1,п] были найдены методом контейнеров ([13, Сапоженко) и, независимо, [21, Green]).

SF([l,n])|~c(n)2"/2, где с(п) принимает только два значения в зависимости от четности п.

Проблема нахождения асимптотики числа МСС в конечных абелевых группах открыта до сих пор. Приведем обзор основных результатов по данной тематике.

В [15, 1991] Н. Алон получил следующую оценку сверху числа МСС в произвольных конечных группах (обычно в случае рассмотрения МСС в произвольных группах этот объект называют множествами, свободными от произведений)

2f(l+o(l))

Далее данный результат уточнялся для разных подклассов конечных абелевых групп.

Сапоженко [12, 2002] и, независимо, Лев-Лучак-Шоп [25] получили асимптотику максимально возможного числа МСС для конечных абелевых групп, содержащих хотя бы одну подгруппу индекса 2. В 2004 [23, Green-Ruzsa] эта теорема была обобщена на случай абелевых групп порядка п, делящегося па простой число, сравнимое с 2 по модулю 3. Использованием преобразований Фурье в [23, Green-Ruzsa] была найдена асимптотика логарифма числа МСС в конечных абелевых группах с заданным размером максимального МСС.

Вопросы о числе МСП в некоммутативных конечных группах практически не исследовались. Введем определение МСП. Пусть G произвольная конечная группа. Подмножество А С G называется мноэюеетвом, свободными от произведений, если произведение любых двух элементов из А не принадлежит А. Множество D G PF(Cr) называется максимальным множеством, свободным от произведений, если для любого Т G PF(G) выполняется \D\ > |Т|.

Что касается задачи нахождения размера максимального МСС в конечных абелевых группах, то она окончательно решена. Данной задаче посвящено значительное число работ. Выделим основные из них. В [20, Diananda-Yap] был получен размер максимального МСС для всех конечных абелевых групп, порядок которых делится на простое число, не сравнимое с 1 по модулю 3. Размер максимального МСС в конечных абелевых группах, все простые делители порядка которых, сравнимы с 1 по модулю 3, был найден в [23, Green-Ruzsa] с помощью использования преобразований Фурье характеристических функций множеств в 2004 году.

Однако о размере максимального МСП в произвольных конечных группах практически ничего не известно. Исследование этой проблемы является одной из задач диссертации.

Важный вклад в данную область исследований внесли следующие математики: Н. Алой, Б. Грин, П. Диаианда, П. Камерон, В. Лев., Т. Лучак, И. Ружа, А.А. Сапоженко, П. Эрдеш, Х.П. Яп и другие.

Краткое содержание диссертации

Во введении обоснована актуальность темы исследования, сформулирована цель диссертации, описана структура диссертации и перечислены основные результаты диссертации.

В первой главе доказывается обобщение теоремы Сапоженко-Льва-Лучака-Шона на случай произвольных конечных групп, содержащих подгруппу индекса 2. Пусть PF(G) обозначает семейство всех МСП группы G.

Теорема 1. Для любой группы G порядка п с числом подгрупп индекса 2, равпым t, t > t. 2»/2 2n(1+°(1))/4 < |PF((?)| < t ■ Г'2 + 2n(1/2"£), (1) где б > 0.

Во второй главе рассматриваются конечные группы, не содержащие нормальной подгруппы индекса 2.

Теорема 2. Пусть порядок группы G равен п, а К - ее нормальная подгруппа наименьшего простого индекса. Пусть \G : К\ = р, р > 3. Тогда

2^<|PF(G)|<2?(i-T). (2)

В третьей главе установлена асимптотика логарифма числа МСП в конечных группах, в которых размер максимального МСП не меньше одной трети порядка группы, и найден размер максимального МСП в конечных группах, содержащих нормальную подгруппу простого индекса, сравнимого с 2 по модулю 3.

В параграфе 3.1 обобщается теорема Грипа-Ружи о числе МСС в конечных абелевых группах. Пусть A(Gr) обозначает размер максимального МСП в группе G.

Теорема 3. Пусть группа G имеет порядок п и X(G) > п/3. Тогда log|PF((7)| = А (С?) + 0(n(logn)-1/45). (3)

В параграфе 3.2 получен следующий результат о размере максимального МСП. Пусть n(G) = X(G)/\G\.

Теорема 4. Пусть G конечная группа, содерэюащая нормальную подгруппу Н индекса р, р = 2 (mod 3). Если в G нет нормальной подгруппы индекса меньшего чем р, то

Основные результаты диссертации

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

2. Установлена асимптотика логарифма максимального числа множеств, свободных от произведений, в конечных группах, в которых размер максимального МСП не меньше трети порядка группы.

3. Установлена оценка числа множеств, свободных от произведений, в группах, содержащих нормальную подгруппу простого индекса.

4. Найден размер максимального множества, свободного от произведений, в конечных группах, содержащих нормальную подгруппу простого индекса р, р = 2 (mod 3).

1. Э.Б. Винберг, Курс алгебры. - М.: Изд-во "Факториал", 1999.

2. Г.П. Гаврилов, А.А. Сапожепко, Задачи и упраэ/спепия по дискретной математике. 3-е изд. - М.: Изд-во "Физматлит", 2004.

3. А.И. Кострикин, Введение в алгебру. М.: Изд-во "Наука", 1977.

4. Т.Г. Петросяи, Число мпоэ/сеств, свободных от произведений, VIII Международный семинар "Дискретная математика и ее приложения". М.: Изд-во механико-математического факультета МГУ, 2004, стр. 358-3G1.

5. Т.Г. Петросян, Множества, свободные от произведений, в группах, VI Международная конференция "Дискретные модели в теории управляющих систем". М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова, 2004, стр. 204-206.

6. Т.Г. Петросян, О числе мпоэ/сеств, свободных от произведений, в группах четного порядка, Дискретная математика, 17 (2005), No. 1, 89-101.

7. Т.Г. Петросян. О множествах, свободных от произведений, Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики". М.: Изд-во механико-математического факультета МГУ, 2005, стр. 120.

8. Т.Г. Петросян, О верхней оценке числа мпоэ/сеств, свободных от произведений, Дискретная математика, 19 (2007), No. 1, стр. 76-88.

9. А.А. Сапоженко, О числе множеств, свободных от сумм, в абелевых группах, Вестник Моск. Ун-та сер.1, 2002, 4, 14-17.

10. А.А. Сапоженко, Гипотеза Камерона-Эрдеша, Математические вопросы кибернетики. Выпуск 13. Изд-во: Физматлит. 2004.

11. А.А. Сапоженко, Проблема Дедекинда и метод граничных функционалов. М.: Издательский отдел ф-та ВМиК МГУ, 2005.

12. Alon, N., Independent sets in regular graphs and sum-free subsets of finite groups, Israel Journal of Math., 73 (1991), 2, 247-256.

13. Calkin N.J., On the number of sum-free sets, Bull. London Math. Soc., 22 (1990), 140-144.

14. Cameron, P.J., Cyclic automorphisms of a countable graph and random sum-free sets, Graphs Combin., 1 (1985), 129-135.

15. Cameron, P.J; Erdos, P., On the number of sets with various properties, Number Theory (Banff, AB, 1988), 61-79, de Gruyter, Berlin, 1990.

16. Davenport H., On the addition of residue classes, J. London Math. Soc., 22 (1947), 100-101.

17. Diananda, P.H.; Yap, H.P., Maximal Sum-Free Sets of Elements of Finite Groups, Proc. Japan Acad. 45 (1969), no. 1, 1-5.

18. Green, В., The Cameron-Erdos Conjecture, Bull. London Math. Soc. 36 (2004), no. 6, 769-778.

19. Green, В.; Ruzsa, I.Z., Counting sumsets and sum-free sets modulo a prime, Studia Sci. Math. Hungarica 41 (2004), no.3, 285-293.

20. Green, В.; Ruzsa, I.Z., Sum-free sets in abelian groups, Israel J. Math. 147 (2005), 157-189.

21. Kedlaya, K.S., Product-Free Subsets of Groups, Arner. Math. Monthly 105 (1998), No. 10, 900-906.

22. Lev, V.F.; Luczak, Т.; Schoen, Т., Sum-free sets in abelian groups, Israel J. Math. 125 (2001), 347-367.

23. Lubotzky, A.; Segal, D., Subgroup Growth, Birkhauser, Basel, 2003.

24. Olson, J.E., On the sum of two sets in a group, Journal of Number Theory, 18 (1984), 110-120.

25. Rhemtulla, A.H.; Street, A.P., Maximal sum-free sets in finite abelian groups, Bull. Austral. Math. Soc. 2 (1970), 289-297.

26. Rhemtulla, A.H.; Street, A.P., Maximal sum-free sets in elementary abelian p-groups, Canadian Math. Bull 14 (1971), 73-81.

27. Schur, I., Uber die Kongruenz xm + ym = zm(modp), Jahresber. Deutsch. Math. Verein. 25 (1916), 114-117.

28. Street, A.P., Maxrnal sum-free sets in cyclic groups of prime-power order, Bull. Austral. Math. Soc. 4 (1971), 407-418.

29. Street, A.P., Maximal sum-free sets in abelian groups of order divisible by three, Bull. Austral. Math. Soc. 6 (1972), 439-441.

30. Yap, H.P., The number of maximal sum-free sets in Cp, Nanta Math. 2 (1968), No. 1, 68-71.

31. Yap, H.P., Maximal sum-free sets of group elements, J. London Math. Soc. 44 (1969), 131-136.

32. Yap, H.P., Structure of maximal sum-free sets in Cp, Acta Arithmetica 17 (1970), 29-35.

33. Yap, H.P., Structure of maximal sum-free sets in groups of order 3p, Proc. Japan Acad. 46 (1970), 758-762.

34. Yap, H.P., Maximal sum-free sets in finite abelian groups, Bull. Austral. Math. Soc. 4 (1971), 217-223.

35. Yap, H.P., Maximal sum-free sets in finite abelian groups, II, Bull. Austral. Math. Soc. 5 (1971), 43-54.

36. Yap, H.P., Maximal sum-free sets in finite abelian groups, III, Journal of Number Theory 5 (1973), 293-300.