Множества, свободные от произведений тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Петросян, Тарон Гайкович

• Петросян, Тарон Гайкович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Петросян, Тарон Гайкович

Введение \

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).

Список литературы диссертационного исследования кандидат физико-математических наук Петросян, Тарон Гайкович, 2007 год

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.