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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

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

0050546^

САРГСЯН ВАГЕ ГНЕЛОВИЧ

МНОЖЕСТВА, СВОБОДНЫЕ ОТ РЕШЕНИЙ ЛИНЕЙНЫХ УРАВНЕНИЙ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

- 8 НОЯ 2012

Москва - 2012

005054634

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

Научный руководитель: доктор физико-математических наук,

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

Официальные оппоненты: доктор физико-математических наук,

профессор Леонтьев Владимир Константинович

кандидат физико-математических наук, доцент Дайняк Александр Борисович

Ведущая организация: Институт системного программирования РАН

Защита диссертации состоится 30 ноября 2012 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44».

Автореферат разослан «М» октября 2012 г.

/Ученый секретарь

диссертационного совета __

профессор Ü'pU^ l Трифонов Н.П.

-Ti-^ е ¿t, ■и. о, у

-р. л>

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

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

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

XI +... 4- Xk = yi + . •. + yi не имеет решений в А. Основными задачами являются оценка числа (к, I)-МСС в циклических группах, нахождение максимальной мощности (к, I)-МСС в абелевых группах и оценка числа подмножеств, представимых в виде суммы и разности заданного числа подмножеств в циклических группах.

Основым методом, используемым в диссертации для решения этих задач, является так называемый метод контейнеров. Ранее метод использовался A.A. Сапоженко1,2, Б. Грином и И. Ружей3'4, В. Львом, Т. Лу-чаком и Т. Шопом5 при решении перечислительных задач, приведенных выше. Суть метода заключается в том, что для оценки мощности семейства строится система контейнеров, такая, что каждый элемент семейства содержится полностью или «почти полностью» в некотором контейнере из построенной системы. Число контейнеров в силу их специального построения проще оценивать, чем число исходных множеств. В случае, когда

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

2Сапоженко A.A. Решение проблемы Камерона-Эрдёша для групп простого порлйка // Вычислительная математика и математическая физика. 2009. Т. 49. № 8. С. 1-7.

3Green В., Ruzsa I. Counting sum-seta and sum-free sets modulo a prime // Studia Sei. Math. Hungarica. 2004. 41. P. 285-293.

4Green В., Ruzsa I. Sum-free sets in abeiian groups // Israel J. Math. 2005. 147. P. 157-188.

5Lev V.F., Luczak Т., Schoen T. Sum-free sets in abeiian groups // Israel J. Math. 2001.125. P. 347-367.

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

Начало исследований в области оценки числа МСС было положено в работе П. Камерона6. В ней исследовалась задача нахождения хаусдор-фовой размерности семейства всех МСС в множестве натуральных чисел. Независимо друг от друга Н. Калкин, Н. Алон, П. Эрдёш и А. Гранвиль показали, что хаусдорфова размерность семейства всех МСС равна 1/2. Дальнейшие исследования были инициированы совместной работой7 П. Эрдёша и П. Камерона, в которой найдена асимптотика числа МСС в отрезке натуральных чисел от n/З до п и высказана гипотеза о том, что число МСС во всем отрезке натуральных чисел [1,п] есть 0(2п/2). Гипотеза была доказана независимо A.A. Сапоженко8 и Б. Грином9.

Если случай МСС изучался весьма интенсивно, то работ, изучающих (fc, О"МСС в конечных абелевых группах, практически нет. Для получения асимптотических результатов о числе (к, /)-МСС в группах простого порядка существенно использовались результаты теории сложения множеств (например, теоремы Коши-Давенпорта, Полларда). При доказательстве асимптотики логарифма числа (к, £)-МСС возникает необходимость оценки числа наборов (zi,..., Xk+i) G Ah+l, таких, что х\+.. .+Хк = = Хк+1 + • • • + ХШ- Для решения этой задачи используется техника, свя-

6 Cameron P.J. Cyclic automorphisms of a countable graph and random sum-free sets // Graphs Combin. 1985. 1. P. 129-135.

7Cameron Р.Л., Erdös P. On the number of sets of integers with various properties // Journal of Number Theory (Bnaff, AB,1988). Berlin: de Gruyter, 1990. P.61-79.

«Сапоженко A.A. Гипотеза Камерона-ЭрдЫа // Докл. РАН. 2003. Т. 393. № 6. С. 749-752.

"Green В. The Cameron-Erdös conjecture // Bull. London Math. Soc. 2004. 36(6). P. 769-778.

занная с преобразованиями Фурье.

Задачи о числе (к, ¿)-МСС и об их максимальной мощности в последние три десятилетия являются предметом активного изучения как за рубежом, так и в России. Основной вклад в данную область исследований внесли П. Камерон, П. Эрдёш, Н. Алон, В. Лев, A.A. Сапоженко, Б. Грин, Т. Лучак, Т. Шон, И. Ружа и другие.

Цель диссертационной работы

Основными целями диссертации являются получение оценок числа (к, /)-МСС в циклических группах, нахождение максимальной мощности (к, I)-МСС в конечных абелевых группах и получение оценок числа подмножеств, представимых в виде суммы и разности заданного числа подмножеств в циклических группах.

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

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

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

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

1. Получена асимптотика логарифма числа (к, Z)-MCC в группах простого порядка.

2. Получены нижняя и верхняя оценки числа (к, ¿)-сумм в группах простого порядка.

3. Найдено точное значение максимальной мощности (к, /)-МСС в циклических группах.

4. Улучшена нижняя оценка максимальной мощности (к, Z)-MCC в абелевых группах.

5. Найдено точное значение максимальной мощности (к, /)-МСС в абелевых группах при некоторых ограничениях на их экспоненту.

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

Работа носит теоретический характер. Метод контейнеров был распространён на случай произвольных линейных уравнений с коэффициентами -1 и 1.

Апробация результатов

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

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

-на семинаре «Дискретный анализ» под руководством A.A. Сапоженко, Т.В. Андреевой и А.Б. Дайняка (кафедра математической кибернетики ВМиК МГУ) в 2009-2012 гг.;

-на ежегодных международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2011» , «Ломоносов-2012» (Москва, 2011-2012 гг.);

-на XI международном семинаре «Дискретная математика и её приложения» (Москва, 18-23 июня 2012 г.).

Публикации

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

Структура и объем диссертации

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

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

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

Первая глава посвящена доказательству асимптотики логарифма числа (k, I)-МСС в группах простого порядка10. Группу вычетов по модулю п обозначим через Z„, а через SFkj(Zn) обозначим семейство всех (к, I)-МСС в Z„. Основный результат первой главы обобщает на случай произвольных к и I следующие теоремы:

Теорема 1 (В. Лев, Т. Шон) 11 Пусть р — достаточно большое простое число. Тогда выполняются неравенства

2L(p-2)/3J(p _ !)(! + 0(2-*iP)) < |SFa,i(Zp)| < где £\ и £2 — положительные константы.

Теорема 2 (Б. Грин, И. Ружа) 12 Пусть р — простое число. Тогда справедливо неравенство

где к(р)/р 0 при р —>■ оо, причем к(р) < р(log logp)2^3(logр)-1^9. Основным результатом первой главы является следующая

Теорема 3 Пусть р — достаточно большое простое число, к > 0 и I > 0 — целые числа, удовлетворяющие условию к+ 1 > 3 и к ф I (modp). Тогда выполняются неравенства

2)/Cfc+í)j(i + 0(1)) < \SFk,i{Zp)\ <

10Саргсян В.Г. Асимптотика логарифма числа множеств, (к,1)-свободных от сумм, в группах простого порядка // Вестник Московского Университета, сер. 15. Вычислительная математика и кибернетика. 2012. № 2. С. 101-108.

"Lev V.F., Schoen Т. Cameron-Erdös modulo a prime // Finite Fields Appl. 2002. 8(1). P. 108-119.

I2Green В., Ruzsa I. Counting sum-sets and sum-free sets modulo a prime // Studia Sei. Math. Hungarica. 2004. 41. P. 285-293.

Заметим, что при достаточно большихр из теоремы 3 вытекает асимптотика логарифма числа \SFkti(Zp)\.

Множество d*A = {d-a | о € А} называется растяжением множества А. Заметим также, что если А 6 S-Fj^Zp), то для любого d 6 Zp \ {0} и всякого В С А растяжение d*В € SF^:[(Zp).

Доказательство нижней оценки основано на том, что всякое растяжение подмножеств множества из SFkj(Zp) также принадлежит семейству SFkti(Zp), и оценке количества растяжений подмножеств заданного множества:

Теорема 4 (В. Лев, Т. Шон) 13 Пусть р — простое число, X — подмножество последовательных элементов группы Zp и \Х\ < р/3 + 1. Тогда число всех растяжений подмножеств множества X есть

2И(1 _ - 1) + 0(р225'х'/6).

При доказательстве верхней оценки используется конструкция из работы Грина и Ружи, идея которой состоит в покрытии семейства (к, I)-МСС семейством контейнеров, таким, что каждое (к, ¿)-МСС почти содержится в некотором контейнере и каждый контейнер порождает не более чем о(рк+1~1) мультипликативных наборов, то есть наборов ..., Xk+i), таких, что xi +... + Xk = Хк+1 +... + Xk+i ■ Для оценки числа мультипликативных наборов используются определения и утверждения, приведенные ниже.

Пусть Ai,..., Ат — непустые подмножества группы Zp. Условимся через xai(z), • • •, ХАт(х) обозначать характеристические функции соответственно множеств Ai,..., Ат. Определим (xa¡ * • • • * ХАт)(х) как количество наборов (xi,..., хт) е Ai х ... х Ат, таких, что х = xj 4-... + хт. Положим

Sh,m{Aь ■ • -, Ат) = {х 6 Zp I (xa, * ... * AxJ(z) > h}.

С использованием теорем Коши-Давенпорта и Полларда из теории сложения множеств получаем нижную оценку величины |5д:Г71(А1,... ,Ат)|.

13Lev V. F., Schoen Т. Cameron-Erdös modulo o prime // Finite Fields Appl. 2002. 8(1). P. 108-119.

Лемма 1 Пусть р — простое число, Ль..., Ат — непустые подмножества группы Хр, и Ь, > 0, такое, что (Лр)1^2 < шт(|Л1|,.. ,,|Лт|). Тогда справедлива оценка

|5л,т(Ль..., Ат)\ > тт(р, Щ + ... + |Ага| - ш + 2) - 2{кр)1'2.

Пусть Ь — натуральное число. Для каждого у е 2Р определим разбиение Яу^ группы на интервалы вида

Все интервалы из имеют длину Ь, а множество 1У = \ ^ имеет мощность р — Ь\р/Ь\ < Ь. Множество А С называется Ь-гранулированным, если для некоторого [¡б2ри некоторого разбиения Яу^ь растяжение ¿-к А является объединением несколькых интервалов ^ разбиения Яу^ (отличных от Jy)■ Через G¿(Zp) обозначим множество всех ¿-гранулированных подмножеств группы

Лемма 2 Справедлива оценка

Следующее утверждение является основным инструментом получения оценки числа мультипликативных наборов. В доказательстве используется техника, связанная с преобразованиями Фурье. Для любых целых г и j обозначим гА — ¿А — {^1 +... + — х^+1 —... — х^ | х\,...,х€ А}.

Лемма 3 Пусть А С Хр, |Л| = ар, и £\,Е2, £з — положительные действительные числа, Ь — натуральное число, к и1 — неотрицательные целые числа, удовлетворяющие условию к + 1 >2, ар — простое число, такое, что

Тогда существует подмножество А! С Zг, со следующими свойствами: А' является Ь-гранулированным;

= [гЬ+1+у,(г + 1)Ь + у], 0<г< \р/Ь\-1.

ш%р)\ <р2>!1.

(п) \А\А'\<еж

(iii) множество kA — IA содержит все элементы х е Zp, такие, что (ха' * ... * ХА'*Х-А' * ••• * Х-А1)(%) > (£2Р)Ш'\ за исключением не

4 V ' V

k I

более £зр элементов.

Вторая глава посвящена оценке числа подмножеств, представимых в виде суммы и разности заданного числа подмножеств в группах простого порядка14,15.

Пусть G — абелева группа, к > 0 к I > 0, к + I > 2. Подмножество В С G называется (к,1)-суммой, если существует подмножество А С G, такое, что

В = kA - 1А = {х 1 + ...+Хк— Хк+х - ... - Xk+i I xi,..., Xk+i € А}.

Через SSk,i(G) обозначим семейство всех (к,1)-сумм в G. Основный результат второй главы обобщает на случай произвольных к и / следующую теорему.

Теорема 5 (Б. Грин, И. Ружа) 16 Пусть р — простое число. Тогда справедливы неравенства

р22ф ^ |552Д)(2р)| < 2P/3+-W где к(р)/р -> 0 прир —>• оо, причем к(р) <С p(loglogp)2/'3(logp)~1/'9. Основным результатом второй главы является следующая

Теорема 6 Пусть р — достаточно большое простое число, к > 0 и I > 0 — целые числа, удовлетворяющие условию к +1 >2. Тогда выполняются неравенства

Ck[2P/(2(k+i)-i) < ¡SSk,i(Zp)\ < 2p/(^+D+°(p)) где Ck,i — положительная константа.

"Sargsyan V. Counting (k,l)-sumsets in groups of a prime order // Acta Universitatis Sapientiae, Informática. 2012. 4(1). P.33-47.

15Саргсян В.Г. О числе k-сумм в группах простого порядка // Дискретная математика. 2012. Т. 24. Вып. 3. С. 25-38.

"Green В., Ruzsa I. Counting sum-sets and sum-free sets modulo a prime // Studia Sei. Math. Hungarica. 2004. 41. P. 285-293.

Заметим, что при достаточно больших;? и к+1 = 2 из теоремы 6 вытекает асимптотика логарифма числа ^¿¡¡^¡(йр)!.

Доказательство нижней оценки проводится путем построения большого числа {к, £)-сумм. Положим Ь = \р/2(2(к + 1) — 1)] — 1. Построенные множества имеют следующий вид:

В(А) = к(А и {-2Ь, 21/}) - 1{А и {-2Ь, 2Ь», где А С [-Ь, Ь].

Нетрудно убедиться, что различные А С \—Ь, Ь] порождают различные множества В {А).

Доказывается лемма, которая утверждает, что число (А;, /)-сумм, содержащих заданную арифметическую прогрессию длины (к + 1)(Ь — 1) + 1, не меньше с^!;22£, где сщ — некоторая положительная константа.

Положим = (8(А; + /)2)/ ^ (4/3)1 и к+1-1

Х=[0,МК1]и У [[(г + 1)Ь/(к + 1)\- Л*,|,Г(» + 1)Ь/(к + 1)]}.

г=1

Множество А С \—Ь,Ь\ определим следующим образом:

А = А(С) = С \JXU-X,

где элементы множества С выбраны из [—Ь,Ь] \ {—X и X} случайно с вероятностью 1/2, независимо друг от друга.

Вероятностным методом доказывается, что существует по крайней мере подмножеств А С [—Ь, £], таких, что к А — 1А содержит арифметическую прогрессию [к — 1Ь, кЬ — I].

При доказательстве верхней оценки используется конструкция, идея которой состоит в покрытии семейства (к, I)-сумм семейством контейнеров. Доказательство верхней оценки основано на лемме 3.

В третьей главе исследуется максимальная мощность (к, I)-МСС в конечных абелевых группах.

Через Хк,¡(С) обозначим максимальную мощность (к,1)-МСС в абе-левой группе С?. Положим 5к,г{п) =НОД(п, к — I), и — наимень-

шее целое число из интервала [1,<^(п)], для которого существует число

he Zn \ {0}, такое, что выполняются неравенства

l + l

П - 1 - Hk,l{n) k + l

<(k-l)h<n-l-k

n-1- fik,i(n)

k + l

Заметим, что определение ^,г(га) корректно, потому что при =

существование числа к вытекает из неравенства

п — 1 — к

п - 1 - Sk,i(n) к + 1

- i + г

n-l-Sk,i(n)

k + l

+1 > Sk,i(n)

и того, что подгруппы группы 2„, порожденные соответственно элементами к —I и 6к,1(п), совпадают.

В параграфе 3.2 найдено точное значение максимальной мощности (к, ¿)-МСС в циклических группах.

Теорема 7 Для любого п выполняется равенство

d- 1 -

Ajt,i(Zn) - max

k + l

♦05}-

Через 0кЛ%п) обозначим максимальную мощность арифметической прогрессии, (к, /)-свободной от сумм в ЪП) содержащейся в некотором смежном классе нетривиальной подгруппы группы Ъп.

Параграф 3.2 содержит вспомогательное утверждение: теорему Дж.Е. Олсона17 о сложении множеств в абелевых группах. Данная теорема, дающая нижнюю оценку сложения двух множеств, необходима для оценки /?ь,г(2„). С использованием теоремы Олсона доказывается следующее утверждение.

Лемма 4 Для любого п справедливо

если к — I делится на п, то = О/

(и) если 1 <НОД(п, к — I) < п, то

^ < РкА^п) ^ max

2 п

г2{к + 1 + 2)];'

где — наименьший делительп, такой, что к—I не делится на гь а г2 — наименьший делитель п, такой, что к — I делится на гг;

"Olson J.E. On the sum of two sets in a group // Journal of Number Theory. 1984.18(18). P. 110-120.

(ш) если НОД(п, к — I) — 1, то

РкМ =

п

Р

где р — наименьший простой делитель п.

Через 74,г(2„) обозначим максимальную мощность арифметической прогрессии, (к, /)-свободной от сумм в Zn, не содержащейся ни в одном из смежных классов никакой нетривиальной подгруппы группы Ъп. При доказательстве теоремы 7 возникла задача оценки Доказывается следующее утверждение.

Лемма 5 Для любого п справедливо

Через обозначим максимальную мощность арифметической

прогрессии, (к, /)-свободной от сумм в циклической группе Ъп. В силу лемм 4 и 5 получаем точное значение величины а)у(Х„).

Теорема 8 Для любого п выполняется равенство

где г — наименьший делитель п, такой, что к — I не делится на г.

В параграфе 3.3 улучшена нижняя оценка максимальной мощности (к, /)-МСС в абелевых группах.

Теорема 9 Пусть С — абелева группа порядка п, а к и I — различные положительные целые числа. Тогда имеет место неравенство

где и — экспонента группы (2.

Доказательство утверждения основано на теореме 7 и оценке максимальной мощности (к, /)-МСС в абелевых группах:

если п < к +1 + Цк,1{п)\ если п>к + 1 + ук,1(п) + 1.

Теорема 10 (Б. Байнок) 18 Пусть d — делитель экспоненты, v абеле-вой группы G. Тогда справедливо неравенство

AM(G) > Aw(Zd)5-

Кроме того, в параграфе 3.3 найдено точное значение максимальной мощности (к, £)-МСС в абелевых группах при некоторых ограничениях на их экспоненту.

Теорема 11 Пусть G — абелева группа порядка п, а к и I — различные положительные целые числа. Тогда, если экспонента и группы G имеет делитель d, такой, что d $ {1,.. .,fikj{d)} (mod(fc +1)), то справедливо равенство

х fr* f ( d-l-fik,i{d) Лп\ Ам(С) = шах|Ц--z—j+ij-j.

Доказательство основано на теореме 8 и оценке максимальной мощности (к, /)-МСС в абелевых группах:

Теорема 12 (Я.О. Хамидун, А. Плань) 19 Пусть G — абелева группа порядка n, а к и I — различные положительные целые числа. Тогда справедливы неравенства

{71Л (ТЬ £[Т1) С Т1

ak,i{Zd)-: > < Ak,i{G) ^ max , max \ ak,i{"Ld)~:

d J \ к т £ d\v i a

где v — экспонента группы G, а е(п) = 1, если п — нечетное, и е(п) = О, иначе.

Благодарности

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

18Bajnok В. On the maximum size of a (k,l)-sum-free subset of an abelian group // Journal of Number Theory. 2009. 5(6). P. 953-971.

19Hamidoune Y.O., Plagne A. A new critical pair theorem applied to sum-free sets in Abelian groups // Commentalii Mathematici Helvetici. 2004. 79. P. 183-207.

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

1. Саргсян В.Г. Асимптотика логарифма числа множеств, (k,l)-свободных от сумм, в группах простого порядка // Вестник Московского Университета, сер. 15. Вычислительная математика и кибернетика. 2012. № 2. С. 101-108.

2. Саргсян В.Г. О числе множеств, k-свободных от нуля, в группах простого порядка // Сборник статей молодых учёных факультета ВМК МГУ. 2012. Вып. 9. С. 154-172.

3. Саргсян В.Г. О числе множеств, свободных от нуля, в группах простого порядка // Материалы XI Международного семинара «Дискретная математика и её приложения». Секция «Комбинаторный анализ». 18-23 июня, Москва, МГУ имени М.В.Ломоносова. М.: Изд-во механико-математического факультета МГУ, 2012. С. 266-269.

4. Саргсян В.Г. О числе k-сумм в группах простого порядка // Дискретная математика. 2012. Т. 24. Вып. 3. С. 25-38.

5. Sargsyan V. Counting (к, l)-sumsets in groups of a prime order // Acta Universitatis Sapientiae, Informática. 2012. 4(1). P. 33-47.

6. Саргсян В.Г. Количество (к,1)-сумм в группах простого порядка // Сборник тезисов XIX Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов - 2012». Секция «Вычислительная математика и кибернетика». 9-13 апреля, Москва, МГУ имени М.В.Ломоносова. М.: МАКСПресс, 2012. С. 105.

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

Подписано в печать 24.10.2012 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 70 экз. Заказ 411.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8-495-939-3890. Тел./факс 8-495-939-3891.

Введение

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

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

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

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

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

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

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

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

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

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

3.2 Максимальная мощность (к,1)~МСС в циклических группах

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

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

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

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

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

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

В 1916 году для решения задач шифрования И. Шур (I. Schur) ввел понятие множества, свободного от сумм (МСС). Множество А называется свободным от сумм, если х + у ф А для любых ж, у Е А, другими словами, если уравнение х + у — z не имеет решений в А.

Классический результат И. Шура [39], утверждает, что натуральный ряд не может быть представлен в виде объединения конечного числа попарно непересекающихся МСС.

Для натуральных чисел тип обозначим через [га, п] множество натуральных чисел х, таких, что т < х < п.

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

Вместе с тем интенсивно рассматривались обобщения задачи о числе МСС. В частности, речь шла о числе множеств, (к, I)-свободных от сумм

М)-МСС).

Пусть к и I - неотрицательные целые числа, удовлетворяющие условию к + / > 3. Множество А называется (к, I) -свободным от сумм, если уравнение х\Л----+ хк = yi Н-----h yi не имеет решений в А.

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

1) оценка числа всех /)-МСС,

2) нахождение максимальной мощности (k,l)~МСС.

Пусть G - множество с определенной на нем операцией сложения. Семейство всех (/с, Z)-MCC в G обозначим через SFkj(G). Множество, (2,1)-свободное от сумм, называется просто множеством, свободным от сумм (МСС).

Н. Калкин (N. Calkin) [15] и, независимо, Н. Алон (N. Alón) [10] доказали, что 1 log|SF2il([l,n])| <п/2.

Решение гипотезы Камерона-Эрдёша и асимптотика числа МСС в отрезке [1,п] были найдены методом контейнеров (А. А. Сапоженко [2] и, независимо, Б. Грином (В. Green) [22]). Доказано, что

5F2il([l,n])|~crW2^2, где т(п) принимает только два значения в зависимости от четности п.

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

В 1991 году Н. Алон [10] получил следующую оценку сверху числа МСС в произвольных конечных группах

2f(i+o(i))

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

1 Здесь и далее log х = log2 х

В 2002 году А.А. Сапоженко [1] и, независимо, Лев-Лучак-Шон (В. Lev, Т. Luczak, Т. Schoen) [27] получили асимптотику максимально возможного числа МСС для конечных абелевых групп, содержащих хотя бы одну подгруппу индекса 2. Группу вычетов по модулю п обозначим через Ъп.

В 2002 году В. Лев и Т. Шон [28] доказали, что если р - достаточно большое простое число, то справедливы оценки

2L(p-2)/3JQ9 + 0(2-S1P)) < \SF2,I(ZP)\ < 2Р/2-£2Р, где Е\ и £2 - положительные константы.

В 2005 году Б. Грин и И. Ружа (I. Ruzsa) [23] использованием преобразований Фурье получили асимптотику логарифма числа МСС в конечных абелевых группах. Они доказали, что для любой конечной абелевой группы G справедливо log|SF2>i(G)|~A2|i(G), где А2д((?) - максимальная мощность МСС в G (см. теоремы 4 и 5).

В 2009 году А. А. Сапоженко [3] получил асимптотику числа МСС в группах простого порядка.

Теорема 1. Для любого a Е { — 1,1} существует константа са, такая, что для любого е > 0 существует натуральное число N, такое, что для любого простого р видар = a (mod 3), такого, что р > N, выполняются неравенства

- са(р - l)2LO-2)/3j < ^ +

Для произвольных к и I вопросы о числе (А:,/)-МСС в абелевых группах практически не исследовались.

Выделим основные работы о числе (к,1)~МСС в отрезке натуральных чисел [1 ,п].

В 1996 году Н. Калкин и А. Тайлор (А. Taylor) [16] доказали, что при к > 3 и I = 1 выполняется равенство

В 1998 году Н. Калкин и Дж. Томсон (J. Thomson) [17] расширили эту оценку на все пары (к,1), к > 4/ — 1 и I > 1.

В 2000 году Т. Шон [37] получил асимптотику для IS'F^Ql,п])| при некоторых ограничениях на к и /.

Теорема 2. Если к > I > 3 - положительные целые числа и где г = п (mod в), 0 < г < в, в - наименьшее натуральное число, не являющееся делителем к — I, <pr{x) ~ количество положительных чисел т < г, для которых НОД(т,х) = 1, и <-р(х) = (рх{х).

В 1998 году Ю. Билу (Уи. ВПи) [14] при к = 3 и в 2001 году Т. Шон [38] при к = 2 доказали, что

В 2003 году В. Лев [29] получил верхнюю оценку для ^^¿([^ п])|.

Теорема 3. Если (к, I) ^ ф, то существует положительная константа £ — е(к,1), такая, что

SFkJ([l,n])\ = 0(2^n/k). то

SFM([1, п])| = Ш + <pr{ß) + о(1))

SFk+hk([l,n])\ = (l + o(l))2^+l^.

SFktl({l,n])\=ckiltn2*+0(2№n) если V1 < ъ k-i

5Ffc>i([l,n])| < + 4,i,n)2п¥ + 0(2(^"e)n) если ^y > и n])| < (cM,n + c'kl + с",+

6Ci/b'Lb — ^ ^ где 0 - наименьшее натуральное число, не являющееся делителем к — I, и

Ск1о= 2 tf-t-V+W,

1=1 (t,0)=l k-l-1 к~1 Г г=0 с' = 2

2k-l I ' с» 5

Z к — 1

Q = {(М) | ^ < \ и I < 9} U {(А;, I) | > i w /с < 27} U {(11,10)}U

К и К и

U{(fc, к-2) I /с е [12,18]}и{(/с, fc-4) | к е [14, 20]}и{(А;, к-6) \ к е [25,29]}.

Нахождение максимальной мощности (к,1)-МСС в абелевых группах является одной из задач диссертации. Этой задаче посвящено значительное число работ.

Пусть G - абелева группа, и

A = max \А\.

AeSFKl(G)

Что касается задачи нахождения максимальной мощности МСС, то она окончательно решена. Основные результаты по теме нахождения максимальной мощности МСС и описания структуры максимальных по включению МСС изложены в работах [12, 20, 23, 24, 25, 26, 30, 35, 36], [40]-[48]. Приведем обзор основных результатов о максимальной мощности МСС.

В 1969 году Х.П. Яп (Н.Р. Yap) и П. Диананда (P. Diananda) [20] получили верхнюю и нижнюю оценки величины Л2д(С), показав, что

Теорема 4. Пусть С - абелева группа порядка п. Тогда выполняются неравенства max d\v d+1 п

-d <x2ÁG)< t d + 1 n d где v - экспонента группы G.

В частности, если п делится на простое р = 2 (mod 3), то

СV + 1)п

3V где р - наименьшее такое простое число; если п не делится ни на какое простое р = 2 (mod 3), но 3|п, то

А2д (G) =

Окончательное решение задачи о максимальной мощности МСС в абе-левых группах, получено в работе [23] Б. Грином и И. Ружей в 2005 году.

Теорема 5. (Теорема 1.5, [23]) Пусть G - абелева группа порядка п. Если п делится только на простые р = 1 (mod 3), то выполняется равенство v - 1 )п a2,i(g9 где и - экспонента группы G.

Зи

Теперь выделим основные работы о максимальной мощности (/с, /)-МСС.

В 2001 году Т. Биер (Т. Bier) и А.Я.М. Чин (A.Y.M. Chin) [13] рассматривали задачу о максимальной мощности (k,l)-МСС в группах простого порядка, показав, что

A M(ZP) =

В 2002 году А. Плань (A. Plagne) [33] показал, что любое максимальное по мощности множество А Е SFkj(Zp) является арифметической прогрессией, при простом р и таx(k, I) > 3.

Р- 1 к + 1

В 2004 году Я.О. Хамидун (Y. О. Hamidoune) и А. Плань [24] использованием обобщения теоремы о критических парах (теорема Воспера) для конечных абелевых групп доказали следующее утверждение.

Теорема 6. Пусть G - абелева группа порядка п, а к и I - различные положительные целые числа. Тогда справедливы неравенства

Т1Л (TL — 6\П) ( TL Л \ Ay(G) < max (-^.тах^.^)-) j , где atkjfäd) ~ максимальная мощность арифметической прогрессии, (к, I) -свободной от сумм, в Z^, и и - экспонента группы G, а е{п) = 1, если п - нечетное, и е(п) = 0, иначе.

В 2007 году Б. Байнок (В. Bajnok) [11] использованием алгоритма Евклида и теоремы Кнезера, получил верхнюю и нижнюю оценки максимальной мощности (к, ¿)-МСС в абелевых группах, а также вычислил точное значение максимальной мощности (/с,/)-МСС в абелевых группах при некоторых ограничениях на их экспоненту (теоремы 7-9). Определим ökti(d) равенством ök,i(d) =НОД(о(, к — I).

Теорема 7. Пусть G - абелева группа порядка п, а к и I - различные положительные целые числа. Тогда справедливы неравенства max d\v d- 1 - ök,i(d) к + l где v - экспонента группы G. 1)^1 ^\k,i{G) ^ max J d I d\n d-2 k + l 1)i

Теорема 8. Пусть G - абелева группа порядка п, а к и I - различные положительные целые числа. Тогда если экспонента v имеет делитель d, такой, что d {1,., 5k,i(d)} (mod (к + /)), то выполняется равенство п k,i{G) = A/^(Z„)—.

В случае циклических групп получена следующая формула для максимальной мощности (k,l)~МСС.

Теорема 9. Пусть к и I - различные положительные целые числа. Тогда для любого п справедливо равенство max {afc)Z(Zd)^) , d\n К Ci J где akjfäd) ~ максимальная мощность арифметической прогрессии, (к, I) -свободной от сумм, в Z^.

Пусть к > 0 и / > 0 целые числа, удовлетворяющие условию к +1 > 2. Подмножество В CG называется (к, I)-суммой, если существует подмножество А С G, такое, что

В = кА - 1А = {xi Н-----Ь хк - хк+1-----хк+1 | xi,., хш € ^4}.

В диссертационной работе рассматривается еще одна естественная перечислительная задача: оценка числа всех (fc,/)-сумм. Одной из задач диссертации является получение верхней и нижней оценок числа (к,1)-сумм в группах простого порядка. Семейство всех (к,1)-сумм в G обозначим через SSk1i(G).

В 2004 году Б. Грин и И. Ружа [21] доказали следующее утверждение.

Теорема 10. (Теорема 2, [21]) Пусть р - простое число. Тогда справедливы неравенства p22Pß ^ \SS2,o{ZP)\ < 2p/3+K{p) где к(р)/р —У 0 при р —>■ сю, причем к(р) p(log logp)2//3(logp)-1^9.

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

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

Диссертация состоит из трёх глав.

В первой главе получена асимптотика логарифма числа (А;,/)-МСС в группах простого порядка. В параграфе 1.1 даются определения и доказываются вспомогательные утверждения. В параграфе 1.2 доказывается утверждение, являющееся основным инструментом доказательства верхних оценок. Основным результатом главы является следующая

Теорема (пар. 1.3, теорема 14). Пусть р - достаточно большое простое число, к > О и I > 0 целые числа, удовлетворяющие условию к + I > 3 и к ф I (mod р). Тогда выполняются неравенства p2[(p-2)/(k+i)\ (1 + 0(1)) < |SFkti(Zp)\ <

Вторая глава диссертации посвящена оценке числа (А;,/)-сумм в группах простого порядка. В параграфе 2.2 вводятся некоторые определения и доказывается нижняя оценка числа (А;,/)-сумм. В параграфе 2.3 доказывается верхняя оценка числа (А;,/)-сумм. Основным результатом главы является следующая

Теорема (пар. 2.1, теорема 15). Пусть р - достаточно большое простое число, к > 0 и I > 0 целые числа, удовлетворяющие условию к + I > 2. Тогда выполняются неравенства

Cki2p/(2(k+i)-i) < |sSk,i(Zp)\ < 2р/(к+1+1)+о(р)} где Ckj - положительная константа.

В третьей главе исследуется максимальная мощность (к,1)-МСС в конечных абелевых группах. В параграфе 3.2 найдено точное значение максимальной мощности (А;, /)-МСС в циклических группах. В параграфе 3.3 улучшена нижняя оценка максимальной мощности (А;,/)-МСС в абелевых группах, и найдено точное значение максимальной мощности (/с, /)-МСС в абелевых группах при некоторых ограничениях на их экспоненту.

Через ¡J>k,i(d) обозначим наименьшее целое число из интервала [1, dkj(d)], для которого существует число h Е {0}, такое, что выполняются неравенства

1 + 1 d- 1 - fik,i(d) к +1 (к— l)h < d — 1 — к d- 1 - Hk,i{d) к +1

Главными результатами третьей главы являются следующие утверждения.

Теорема (пар. 3.2, теорема 18). Пусть к и I - различные положительные целые числа. Тогда для любого п выполняется равенство d- 1 - ¡1к,М)

Afc,í(Zn) = max d\n 1 i к + 1

Теорема (пар. 3.3, теорема 19). Пусть С - абелева группа порядка п, а к и I - различные положительные целые числа. Тогда справедливо неравенство k,i(G) > max \ d\v { где и - экспонента группы G. d k +1 1 n d

Теорема (пар. 3.3, теорема 20). Пусть G - абелева группа порядка п, а к и I - различные положительные целые числа. Тогда, если экспонента v имеет делитель d, такой, что d ^ {1,., fj,kti(d)} (mod (к + I)), то справедливо равенство d - 1 - Hk,i{d)

Afc.iCG) = max d\u k + l

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

1. Получена асимптотика логарифма числа (к, ¿)-МСС в группах простого порядка (теорема 14).

2. Получены верхняя и нижняя оценки числа (А;,/)-сумм в группах простого порядка (теорема 15).

3. Найдено точное значение максимальной мощности (/с,/)-МСС в циклических группах (теорема 18).

4. Улучшена нижняя оценка максимальной мощности (к,1)~МСС в абеле-вых группах (теорема 19).

5. Найдено точное значение максимальной мощности (к,1)-МСС в абе-левых группах при некоторых ограничениях на их экспоненту (теорема 20).

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

2. Сапоженко A.A. Гипотеза Камерона-Эрдёша // Докл. РАН. 2003. Т. 393. № 6. С. 749-752.

3. Сапоженко А. А. Решение проблемы Камерона-Эрдёша для групп простого порядка // Вычислительная математика и математическая физика. 2009. Т. 49. № 8. С. 1-7.

4. Саргсян В. Г. Асимптотика логарифма числа множеств, (к,1)-свободных от сумм, в группах простого порядка // Вестник Московского Университета, сер. 15. Вычислительная математика и кибернетика. 2012. № 2. С. 101-108.

5. Саргсян В. Г. О числе множеств, /с-свободных от нуля, в группах простого порядка // Сборник статей молодых учёных факультета ВМК МГУ. 2012. Вып. 9. С. 154-172.

6. Саргсян В. Г. О числе к-сумм в группах простого порядка // Дискретная математика. 2012. Т. 24. Вып. 3. С. 25-38.

7. Sargsyan V. Counting (/с, ¿)-sumsets in groups of a prime order // Acta Universitatis Sapientiae, Informatica. 2012. 4(1). P. 33-47.

8. Alon N. Independent sets in regular graphs and sum-free subsets of abelian groups // Israel J. Math. 1991. 73. P. 247-256.

9. BajnokB. On the maximum size of а (к, I)-sum-free subset of an abelian group // Journal of Number Theory. 2009. 5(6). P. 953-971.

10. Balasubramanian R., Prakash G. Large sum-free sets in abelian groups // http://arxiv.org/pdf/math/0502374v2.pdf 22 pp.

11. Bier Т., Chin A. Y. M. On (к, I)-sets in cyclic groups of odd prime order // Bull. Austral. Math. Soc. 2001. 63. P. 115-121.

12. Bilu Yu. Sum-free sets and related sets //Combinatorica. 1998. 18(4). P. 449-459.

13. Calkin N.J. On the number of sum-free set // Bull. London Math. Soc. 1990. 22. P. 140-144.

14. Calkin N. J., Taylor A. C. Counting sets of integers, no к of which sum to another // Journal of Number Theory. 1996. 57. P. 323-327.

15. Calkin N. J., Thomson J. M. Counting generalized sum-free sets // Journal of Number Theory. 1998. 68. P. 151-160.

16. Cameron P. J. Cyclic automorphisms of a countable graph and random sum-free sets // Graphs Combin. 1985. 1. P. 129-135.

17. Cameron P. J., Erdos P. On the number of sets of integers with various properties // Journal of Number Theory(Bnaff,AB, 1988). Berlin: de Gruyter, 1990. P. 61-79.

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

19. Green B., Ruzsal. Counting sum-sets and sum-free sets modulo a prime // Studia Sci. Math. Hungarica. 2004. 41. P. 285-293.

20. Green B. The Cameron-Erdos conjecture // Bull. London Math. Soc. 2004. 36(6). P. 769-778.

21. Green B., Ruzsa I. Sum-free sets in abelian groups // Israel J. Math. 2005. 147. P. 157-188.

22. HamidouneY.O., PlagneA. A new critical pair theorem applied to sum-free sets in Abelian groups // Commentarii Mathematici Helvetici. 2004. 79. P. 183-207.

23. Deshouillers J.-M., Freiman G. A. On sum-free sets modulop //Functiones et Approximatio XXXV. 2006. P. 7-15.

24. Deshouillers J.-M., Lev V. F. A refined bound for sum-free sets in groups of prime order // Bull. London Math. Soc. 2008. 40(5). P. 863-875.

25. Lev V. F., Luczak T., Schoen T. Sum-free sets in abelian groups // Israel J. Math. 2001. 125. P. 347-367.

26. Lev V. F., Schoen T. Cameron-Erdos modulo a prime // Finite Fields Appl. 2002. 8(1). P. 108-119.

27. Lev V. F. Sharp estimates for the number of sum-free sets // Journal fur die reine und angewandte Mathematik (Crelle's Journal). 2003. 555. P. 1-25.

28. Lev V. F. Large sum-free sets in Z/pZ // Israel J. Math. 2006. 154. P. 221234.

29. Nathanson M.B. Additive number theory: Inverse problems and the geometry of sumsets, Graduate Texts in Mathematics 165. Berlin, Heidelberg, New York: Springer-Verlag, 1996.

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

31. PlagneA. Maximal (kj)~free sets in Z/pZ are arithmetic progressions // Bull. Austral. Math. Soc. 2002. 65. P. 137-144.

32. Pollard J. M. A generalization of the theorem of Cauchy and Davenport // J. London Math. Soc. 1974. 8(2). P. 460-462.

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

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

35. Schoen T. A note on the number of (k, I)-sum-free sets // Electronic Journal of Combinatorics. 2000. 7(1). P. 1-8.

36. Schoen T. The number of (2, 3)-sum-free subsets of {1, 2,., n} // Acta Arithmetica. 2001. 98(2). P. 155-163.

37. Schur I. Uber die Kongruenz xm + ym = zm (mod p) // Jahresber. Deutsch. Math. Verein. 1916. 25. P. 114-117.

38. Street A.P. Maximal sum-free sets in cyclic groups of prime-power order // Bull. Austral. Math. Soc. 1971. 4. P. 407-418.

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

40. YapH.P. The number of maximal sum-free sets in Cp // Nanta Math. 1968. 2(1). P. 68-71.

41. YapH.P. Maximal sum-free sets of groups elementsin //J. London Math. Soc. 1969. 44. P. 131-136.

42. YapH.P. Structure of maximal sum-free sets in Cp // Acta Arithmetica. 1970. 17. P. 29-35.

43. Yap H.P. Structure of maximal sum-free sets in groups of order 3p // Proc. Japan Acad. 1970. 46. P. 758-762.

44. YapH.P. Maximal sum-free sets in finite abelian groups // Bull. Austral. Math. Soc. 1971. 4. P. 217-223.

45. YapH.P. Maximal sum-free sets in finite abelian groups, II // Bull. Austral. Math. Soc. 1971. 5. P. 43-54.

46. YapH.P. Maximal sum-free sets in finite abelian groups, III // Journal of Number Theory. 1973. 5. P. 293-300.