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

• Омельянов, Кирилл Георгиевич
• кандидат физико-математических наук
• 2006

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

Введение

1 О числе множеств, свободных от сумм (МСС), в Zv

1.1 Основные понятия.

1.2 Постановка задачи и классификация МСС.

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

1.4 Структура максимальных МСС 1-го и 4-го рода

1.5 Нижние оценки числа МСС в Zv.

2 О числе МСС в отрезке натуральных чисел [1 ,п]

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

2.2 О числе МСС в отрезке [(| + е)п, п].

2.3 О числе МСС в отрезке [n3/4log п,п].

2.4 О числе независимых множеств в графах Кэли.

2.5 Оценки констант Камерона-Эрдеша.

Введение диссертации (часть автореферата) на тему «О числе множеств, свободных от сумм»

Значительное место в математике занимают перечислительные задачи, связанные с проблемами доказательства существования, построения и подсчета числа элементов заданного множества, обладающих некоторыми свойствами. Речь может идти, например, о числе решений задач целочисленного линейного программирования, числе n-вершинных графов с определенными свойствами или о числе изомеров химических элементов. В диссертации решаются некоторые перечислительные задачи комбинаторной теории чисел и теории групп. Оценивается число свободных от сумм подмножеств множества {1,.,п}, то есть подмножеств, в которых не существует решений уравнения х + у = z. Оценивается число свободных от сумм подмножеств в группе Zp и описывается структура максимальных по мощности таких подмножеств. Эти задачи относятся к классу проблем оценки числа объектов с ограничениями на структуру. К таким объектам относятся коды, исправляющие ошибки, антицепи в частичных порядках, независимые множества в графах, слова с запрещенными фрагментами. Особенность работы в том, что для решения теоретико-числовых задач используются методы теории графов.

Множество S целых чисел называется свободным от сумм (МСС), если для любых a,b G S число а + Ъ не принадлежит множеству S. Обозначим через S{m, п) семейство всех подмножеств S С {i е N : ш < а; < п}, свободных от сумм. Пусть s(m,n) = |S(m,n)|, s(n) = |5(l,n)|.

Понятие свободных от сумм множеств ввел, по всей видимости, И. Шур (I. Schur) в 1916 г. для решения задач шифрования. Знаменитая теорема Шура утверждает невозможность разбиения множества {1.,п} на фиксированное, не зависящее от п число попарно непересекающихся множеств, свободных от сумм. Дальнейшие исследования множеств, свободных от сумм, были инициированы известной гипотезой Камерона-Эрдеша. В 1988 г. П. Камерон и П. Эрдеш [22] предположили, что s(n) = 0( 2п'2).

Обоснованием для этого предположения служило то, что любое подмножество множества нечетных чисел отрезка [1, п] свободно от сумм, также как и любое подмножество натуральных чисел отрезка [ |гг/2J + 1, п], а число МСС иного вида, по-видимому, относительно мало. П. Камерон и П. Эрдеш доказали, что s(n/3,n) = 0(2П/2), и, кроме того, что существуют константы со и с\, для которых s(n/3,n) ~ с02Г"/21 при четных п, s{n/3,n) при нечетных п. Будем называть со и С\ константами Камерона-Эрдеша.

Н. Алон [21] в 1991 г. и Н. Калкин [23] в 1990 г. независимо доказали, что1 logs(n) ~

Автор и А. А. Сапоженко [12] в 2002 г. доказали, что для всякого е > 0

5((1/4 + £)п, п)=0(Т>2).

Ими же [13] в 2003 г. было доказано, что

5(n3/,4\/logn, п) = 0(2П/2).

Гипотеза Камерона-Эрдеша была доказана независимо А. А. Сапоженко [18] в 2003 г. и Б. Грином [25] в 2004 г. Пусть 5х(п) — семейство всех подмножеств множества

1 Здесь и далее logm = log2 m. нечетных чисел отрезка [1,п] и s1(n) = |51(n)|.

Теорема (А. А. Сапоженко [18]) s(n) ~ s(n/3, л) + s1(n). Из этой теоремы из того, что sx(n) = 2Г"/21, следует, что s{n) ~ (со + 1)2^1 при четных п, s(n) ~ (Cl + 1)2^ при нечетных п.

П. Камерон и П. Эрдеш [22] получили довольно грубые оценки констант со, с\. Задачу вычисления констант Со, С\ с требуемой точностью естественно называть уточненной задачей Камерона-Эрдеша. Н. Алон считал эту задачу весьма актуальной и высказывал предположение, что ее решение будет сопряжено с значительными трудностями. Отметим, что Н. Алон одним из первых получил оценки величины s(n). Основной целью диссертации является решение уточненной задачи Камерона-Эрдеша.

Автором получены верхние и нижние оценки констант Камерона-Эрдеша, дающие первые два десятичных знака их точного значения (см. теорему 18).

Задача об оценке числа МСС решалась также для абелевых групп.

Пусть G — конечная абелева группа порядка п. Множество S элементов группы G называется свободным от сумм (МСС), если для любых u,v G S элемент u+v ф S. Если S — свободное от сумм множество, и для каждого МСС Т в G выполняется неравенство |5| > |Т|, то будем говорить, что S — максимальное свободное от сумм множество в G. Мощность максимального МСС в G будем обозначать через А(С). Обозначим через fi(G) плотность максимального МСС в группе G, то есть ji{G) = A(G)/n. Семейство всех множеств, свободных от сумм, в группе G обозначим через

S(G). Очевидно, что

S{G)\ > (1)

Естественно ввести величину a(G) =n-1 log |5(G)|.

Из неравенства (1) следует, что <?(G) > fi(G). Определим функцию v(G) следующим образом:

• Если п делится на2 р = 2 (mod 3) и р — наименьшее такое число, положим

G) = 1 +

• Если п не делится ни на одно из чисел р = 2 (mod 3) и делится на 3, положим

• Если п делится лишь на числа р = 1 (mod 3), положим v{G) = | — 3^, где т — наибольший из порядков элементов группы G.

Введем следующую классификацию. Отнесем группу G к типу I, если п делится на р = 2 (mod 3). Отнесем группу G к типу II, если п не делится ни на одно из чисел р = 2 (mod 3) и делится на 3. К типу III отнесем все остальные группы. П. X. Диананда и X. П. Яп [24] в 1969 г. доказали для групп типа I и II, что

KG) = "(С)- (2)

Этот же результат был получен для некоторых групп типа III. X. П. Яп [34, 35] в 1972 и 1975 гг. доказал справедливость равенства (2) для групп вида Zp2 х Zv и Zpq х Zp. А. X. Ремтулла и А. П. Стрит [31] в 1970 г. доказали справедливость равенства (2) для групп вида Z™. Отметим, что доказательства для этих специальных случаев оказались значительно сложнее предыдущих. В 2004 г. Б. Грин и И. Ружа [27] доказали справедливость равенства (2) для всех конечных абелевых групп.

В. Лев, Т. Лучак и Т. Шон [28] в 2001 г. и, независимо, А. А. Сапоженко [16] в 2002 г. получили асимптотику |S(G)| для абелевых групп четного порядка.

23десь и далее предполагается, что р — простое число.

Теорема 1 (А. А. Сапоженко [16]) Для достаточно больших четных п для любой абелевой группы G порядка п с числом подгрупп индекса 2, равным t, t. 2f - < |S(G)| < t ■ 2? + 2n^~c\ (3) где с > 0,017.

Для каждого множества S положим —S = {s : —s е S}. Будем говорить, что свободное от сумм множество S G Zp, является множеством

• 1-го рода, если р = Зк + 2,

• 2-го рода, если р = Зк + 1 и —S ф S,

• 3-го рода, если р = Зк + 1, —S = S и S является арифметической прогрессией,

• 4-го рода, если р — Зк+1, —S = S и S не является арифметической прогрессией. В 1970 г. X. П. Яп [33] определил структуру максимальных МСС 2-го и 3-го рода.

Теорема 2 (Н. P. Yap [33]) Пусть р = Зк +1, S — максимальное МСС в G = Zp. Если —S ф S, то

S= {а + id] i = 1,2,., k}, (4) где (х, у) = (а, d) — ненулевое решение сравнения

2х + (к- \)у = 0 (mod р). (5)

И обратно, если (х,у) = (a,d) — ненулевое решение сравнения (5), то множество S, задаваемое равенством (4), является максимальным МСС в G, таким, что —S ф S. Всего G содержит р — 1 различных максимальных МСС, таких, что —S ф S. Более того, для задаваемого равенством (4) максимального МСС S верно, что множество

S* = -S U S = {-(а + Ы), -(а + (к - 1 )d),a + d,.,a + kd}, таково, что S* П (S - S) = 0 и S* U {S - S) = G.

Пусть X, Z — множества целых чисел, положим X d: Z = {х zt z : х Е X,z £ Z}.

Теорема 3 (Н. P. Yap [33]) Пусть р = Зк+1 и S — максимальное МСС в G = Zp. Если —S = S, то либо S U (S + S) = G, либо

S = {a+ id;i = 1,2, .Д}, (6) где (х, у) = (a, d) — ненулевое решение сравнения

2х + (k +1)у = 0 (mod р). (7)

И обратно, если (х,у) = (a,d) — ненулевое решение сравнения (7), то S, задаваемое равенством (6), является максимальным МСС в G и —S = S. Всего G содержит различных максимальных МСС, таких, что S представимо в виде арифметической прогрессии и —S = S.

В 2001 г. автор [11] описал структуру максимальных МСС 1-го и 4-го рода (см. теоремы 7 и 8). Кроме того, была получена нижняя оценка числа МСС в группах простого порядка (см. теоремы 9 и 10).

В. Лев и Т. Шон [29] в 2002 г. доказали, что для простых р

1)(1 + 0(2-£Р)) < \S(Zp)\ < 20,498р, где е > 0 — абсолютная константа. В 2004 г. Б. Грин и И. Ружа [26] доказали, что j(Zp) = 1/3 + о(1). В том же году они доказали [27], что a{G) = n{G) + о(1) для всех конечных абелевых групп G.

Несмотря на то, что вопрос об асимптотическом поведении числа МСС в группах остается открытым, для некоторых типов групп такие асимптотики получены. Пусть р = Зк + 2. Отнесем группу G к типу 1(р), если она принадлежит типу I и р — наименьший простой делитель вида ЗА; + 2 порядка группы п. Обозначим через N(G,p) число элементов порядка р в группе G. В работе [27] Б. Грин и И. Ружа доказали, что для любой группы G типа 1(р) справедливо следующее равенство. где W — 1 при р — 2, и W — 1/2 иначе. Заметим, что это утверждение является обобщением теоремы 1.

Графом Кэли, порожденным множеством А, назовем граф Ca(V) на множестве натуральных чисел V, такой, что пара чисел (u,v) е V х V является ребром тогда и только тогда, когда \и — v\ G А или и + v & А. Будем говорить, что множество А порождает граф Ca(V). Число всех независимых множеств графа G обозначим через

Как уже говорилось, основной целью диссертации является решение уточненной задачи Камерона-Эрдеша. Эта задача решается с использованием методов теории графов, а именно, путем подсчета числа независимых множеств в графах Кэли специального вида. Независимые множества в графах это известный и хорошо исследованный объект (см, например, [1], [2], [3], [4], [7], [8], [9] и [10]), поэтому переход к оценке числа независимых множеств дает возможность пользоваться многими известными результатами и техниками. Отметим, что графы Кэли использовались Н. Алоном при получении асимптотики логарифма s(n). Заметим, что из теоремы 17 и того, что s1(n) = 2Г"/21, следует, что для получения оценок констант Камерона-Эрдеша достаточно оценить число множеств семейства S(n/3, га). Эта задача сводится, в свою очередь, к суммированию рядов где s(t,n) = |5(i,n)|, S(t,n) = {S e 5([fJ - t,n) : [fj - t e S}. Сложность заключается в том, что выписать в явном виде значения величин s(t,n) не представляется

S(G)\ = W-N(G,P)-2^n(l + op(l)),

1(G). t=о возможным. Нижние оценки констант Камерона-Эрдеша получаются путем вычисления на компьютере частичных сумм этих рядов, то есть величин т-1 4=0 где i = 0,1. Для получения верхних оценок требуется оценить остатки этих рядов, то есть величины

LfJ-i t=T где i = 0,1. Эта задача решается с помощью следующих соображений. Доказывается, что для свободного от сумм подмножества целочисленного отрезка [п/3,п] определяющую роль играет расположение первых двух и последнего его элемента. Этот факт дает возможность оценивать число интересующих нас МСС числом независимых множеств в графах Кэли. Использующиеся в работе графы Кэли порождаются множеством А, мощность которого равна двум или единице. Ранее использовались регулярные или "почти" регулярные графы Кэли, множества вершин которых представляли собой один или два "непрерывных" целочисленных интервала. Особенность работы в том, что в ней оценивается количество независимых множеств в графах Кэли "поврежденных" удалением части вершин, то есть с нарушенной регулярной структурой. Верхняя оценка числа независимых множеств в таких графах представляет отдельный интерес и может использоваться при решении других задач. Заметим, что описанный в диссертации метод дает возможность получить сколь угодно точные оценки констант Камерона-Эрдеша, и точность эта зависит лишь от доступных вычислительных ресурсов.

В диссертации получены нижние оценки числа и описана структура МСС в группах простого порядка. Ввиду того, что асимптотика числа МСС в Zp еще не найдена, нижние оценки этого числа и информация о структуре максимальных МСС в Zp могут оказаться полезными при получении указанной асимптотики.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Омельянов, Кирилл Георгиевич, 2006 год

1. Алексеев В. Е., О влиянии локальных ограничений на сложность нахождения числа независимых множеств графа, Комбинаторно-алгебраические методы в прикладной математике, Горький, 1982, с. 3-13.

2. Алексеев В. Е., О числе тупиковых независимых множеств в графах из наследственных классов, сб. «Комбинаторно-алгебраические методы в дискретной оптимизации», Горький, 1991, с. 5-8.

3. Алексеев В. Е., Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок, Дискретный анализ и исследование операций, Серия 1, 1999, Т. 6, № 4, с. 3-19.

4. Воронин В. П., Демакова Е. В., О числе независимых множеств для некоторых семейств графов, Труды 4-й международной конференции «Дискретные модели в теории управляющих систем», Красновидово, 19-25 июня 2000 г., Изд. МАКС-Пресс, с. 145-149.

5. Гаврилов Г. П., Сапоженко А. А. «Задачи и упражнения по дискретной математике», М.: Наука, ФИЗМАТЛИТ, 2004, 416 с.

6. Дистель Р., «Теория графов», — Новосибирск: Изд-во инс-та математики, 2002, 336 с.

7. Ф. Харари, Э. Палмер, «Перечисление графов», — М: Мир, 1977, 324 с.8. «Комбинаторный анализ. Задачи и упражнения. Под редакцией К. А. Рыбникова.», — М.: Наука, 1982, 368 с.

8. Рыбников К. А., «Введение в комбинаторный анализ», 2 изд. — М: Изд-во МГУ, 1985, 308 с.

9. Зыков А. А., «Основы теории графов», — М.: Наука, 1987, 384 с.

10. Омельянов К. Г., О числе множеств, свободных от сумм, в группах простого порядка, Материалы V молодежной научной школы по дискретной математике и ее приложениям (Москва, 12-17 ноября 2001 г.), с. 78-82.

11. Омельянов К. Г., Сапоженко А. А., О числе множеств, свободных от сумм, в отрезке натуральных чисел, Дискретная математика (2002) 14, No 3, 2002, 3-7.

12. Омельянов К. Г., Сапоженко А. А., О числе и структуре множеств, свободных от сумм, в отрезке натуральных чисел, Дискретная математика, (2003) 15, No 4, с. 11-15.

13. Омельянов К. Г., О числе независимых множеств в «поврежденных» графах Кэли, Дискретная математика, (2005) 17, No 3, с. 105-108.

14. Сапоженко А. А., О числе независимых множеств в расширителях, Дискретная математика (2001) 13, No 1, 56-62.

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

16. Сапоженко А. А., О числе независимых множеств в графах, Труды VIII международной конференции по проблемам теоретической кибернетики (Казань, 27-31 мая 2002 г.), с. 85-93.

17. Сапоженко А. А., Доказательство гипотезы Камерона-Эрдеша о числе множеств, свободных от сумм, Сб. "Математические вопросы кибернетики Вып. 12, 2003, с. 5-14.

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

19. Фрейман Г. А., Сложение конечных множеств, Изв. Высш. Учебн. Завед., Математика, 6(13), (1959), 202-213.

20. Alon N., Independent sets in regular graphs and Sum-Free Subsets of Finite Groups, Israel Journal of Math. 73 (1991), No 2, pp. 247-256.

21. Cameron P., Erdos P., On the number of sets of integers with various properties, In: Number Theory, Proc. 1st Conf. Can. Number Theory Assoc., Banff/Alberta (Mollin, R. A., Ed) 1988. De Gruyter, Berlin, 1990, pp. 61-79.

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

23. Diananda P. H., Yap H. P., Maximal sum-free sets of elements of finite groups, Proc. Japan Acad. 45 (1969) 1-5.

24. Green B. The Cameron-Erdos conjecture, Bull. London Math. Soc. Vol. 36 Part 6 (November 2004), p. 769-778.

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

26. Green В., Ruzsa I., Sum-free sets in abelian groups, Israel J. Math, 147 (2005), 157189.

27. Lev V. F., Luczak Т., Schoen Т., Sum-free sets in abelian groups, Israel Journal of Mathematics, 125 (2001), 347-367.

28. Lev V. F., Schoen Т., Cameron-Erdos modulo a prime, Finite Fields and their Applications, 8 (1) (2002), 108-119.

29. Mann H. В., Addition theorems: the adddition theorems of group theory and number theory, Interscience, New York, 1965.

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

31. Yap H. P., The number of maximal sum-free sets in Cp, Nanta Mathematica 2 (1) (1968), pp. 68-71.

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

33. Yap H. P., Maximal sum-free sets in finite abelian groups. IV, Nanta Math., 5 (1972), no. 3, 70-75.

34. Yap H. P., Maximal sum-free sets in finite abelian groups. V, Bull. Austral. Math. Soc., 13 (1975), no. 3, 337-342.