О числе множеств, свободных от сумм Омельянов Кирилл Георгиевич

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

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

Множество S целых чисел называется свободным от сумм (МСС), если для любых а,Ь Є S число а + Ъ не принадлежит множеству S. Обозначим через S{m, п) семейство всех подмножеств S С {х Є N : т х п}, свободных от сумм. Пусть s(m,n) = \S(m,n)\, s(n) = \S(l,n)\.

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

Обоснованием для этого предположения служило то, что любое подмножество множества нечетных чисел отрезка [1, п] свободно от сумм, также как и любое подмножество натуральных чисел отрезка [_n/2j + 1, п], а число МСС иного вида, по-видимому, относительно мало. П. Камерон и П. Эрдеш доказали, что s(n/3,n) = 0(2n/2), и, кроме того, что существуют константы со и Сі, для которых s(n/3,n) c02 /2l при четных п, s(n/3,n) Cl2 2l при нечетных п. Будем называть CQ и С\ константами Камерона-Эрдеша. Н. Алон [21] в 1991 г. и Н. Калкин [23] в 1990 г. независимо доказали, что1 logs(n) -. Автор и А. А. Сапоженко [12] в 2002 г. доказали, что для всякого є 0 e((l/4+ е)п, п)=0(2"/2). Ими же [13] в 2003 г. было доказано, что 5(n3/4\/bi ,n) = 0(2n/2). Гипотеза Камерона-Эрдеша была доказана независимо А. А. Сапоженко [18] в 2003 г. и Б. Грином [25] в 2004 г. Пусть 5х(п) — семейство всех подмножеств множества 1 Здесь и далее logm = log2 m. нечетных чисел отрезка [1,п] и s1(n) = 51(n). Теорема (А. А. Сапоженко [18]) s(n) s(n/3, п) + зг(п). Из этой теоремы из того, что sx(n) = 2Г"/21, следует, что в(п) (со + 1)2 1 при четных п, s(n) (Cl + 1)2 / при нечетных п.

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

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

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

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

Пусть G — конечная абелева группа порядка п. Множество S элементов группы G называется свободным от сумм (МСС), если для любых u,v Є S элемент u+v . S. Если S — свободное от сумм множество, и для каждого МСС Т в G выполняется неравенство 5 \Т\, то будем говорить, что S — максимальное свободное от сумм множество в G. Мощность максимального МСС в G будем обозначать через X(G). Обозначим через fi(G) плотность максимального МСС в группе G, то есть n{G) = \(G)/n. Семейство всех множеств, свободных от сумм, в группе G обозначим через S(G). Очевидно, что \S{G)\ 2"(0. (1) Естественно ввести величину a(G)=n-1\og\S(G)\. Из неравенства (1) следует, что cr(G) fi(G). Определим функцию v{G) следующим образом: Если п делится на2 р = 2 (mod 3) и р — наименьшее такое число, положим Если п не делится ни на одно из чисел р = 2 (mod 3) и делится на 3, положим u(G) = . Если п делится лишь на числа р = 1 (mod 3), положим v{G) = — зт где т — наибольший из порядков элементов группы G.

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

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

В. Лев, Т. Лучак и Т. Шон [28] в 2001 г. и, независимо, А. А. Сапоженко [16] в 2002 г. получили асимптотику 5(G) для абелевых групп четного порядка. 23десь и далее предполагается, что р — простое число. Теорема 1 (А. А. Сапоженко [16]) Для достаточно больших четных п для любой абелевой группы G порядка п с числом подгрупп индекса 2, равным t, t. 2f - 2T(1+0W 5(G) t 2f + 2 c\ (3) где c 0,017.

Для каждого множества S положим —S = {s : — s Є S}. Будем говорить, что свободное от сумм множество S Є 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 = {a+ id;i = 1,2,...,k}, (4) где (х, у) = (a, d) — ненулевое решение сравнения 2х + (к - l)y = 0 (modp). (5) И обратно, если (х,у) = (a,d) — ненулевое решение сравнения (5), то множество S, задаваемое равенством (4), является максимальным МСС в G, таким, что —S ф S. Всего G содержит р — 1 различных максимальных МСС, таких, что —S ф S. Более того, для задаваемого равенством (4) максимального МСС S верно, что множество S = SUS = {-(a + kd), -(а + (k- l)d),a + d,...,a + kd}, таково, что S П (S - S) = 0 и S U {S - S) = G. Пусть X, Z — множества целых чисел, положим XdtZ = {xdtz: xX,zZ}. Теорема 3 (Н. P. Yap [33]) Пусть р = Зк+1 и S — максимальное МСС в G = Zp. Если —S = S, то либо S U (S + S) = G, либо S = {a + id; г = 1,2, ...Д}, (б) где (х, у) = (a, d) — ненулевое решение сравнения 2х + (k +1)у = 0 (mod р). (7) И обратно, если (х,у) = (a,d) — ненулевое решение сравнения (7), то S, задаваемое равенством (6), является максимальным МСС в G и —S = S. Всего G содержит =i различных максимальных МСС, таких, что S представимо в виде арифметической прогрессии и —S = S.

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

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

Графом Кэли, порожденным множеством А, назовем граф САІУ) на множестве натуральных чисел V, такой, что пара чисел (u,v) Є V х V является ребром тогда и только тогда, когда \и — v\ Є А или и + v Є А. Будем говорить, что множество А порождает граф CA{V). ЧИСЛО всех независимых множеств графа G обозначим через 1(G).

Как уже говорилось, основной целью диссертации является решение уточненной задачи Камерона-Эрдеша. Эта задача решается с использованием методов теории графов, а именно, путем подсчета числа независимых множеств в графах Кэли специального вида. Независимые множества в графах это известный и хорошо исследованный объект (см, например, [1], [2], [3], [4], [7], [8], [9] и [10]), поэтому переход к оценке числа независимых множеств дает возможность пользоваться многими известными результатами и техниками. Отметим, что графы Кэли использовались Н. Алоном при получении асимптотики логарифма s(n). Заметим, что из теоремы 17 и того, что s1 ) — 2Г"/21, следует, что для получения оценок констант Камерона-Эрдеша достаточно оценить число множеств семейства S(га/3, га). Эта задача сводится, в свою очередь, к суммированию рядов LfJ-i 2Гп/21+ -М) t=0 где s(t,n) = \S{t,n)\, S(t,n) = {S Є SdJJ - t,n) : [fj - t Є S}. Сложность заключается в том, что выписать в явном виде значения величин s(t,n) не представляется возможным. Нижние оценки констант Камерона-Эрдеша получаются путем вычисления на компьютере частичных сумм этих рядов, то есть величин т-1 Ci(T,n) = tfnM+J2Kt,n), t=0 где і = 0,1. Для получения верхних оценок требуется оценить остатки этих рядов, то есть величины LfJ-i t=T где і = 0,1. Эта задача решается с помощью следующих соображений. Доказывается, что для свободного от сумм подмножества целочисленного отрезка [п/3, п] определяющую роль играет расположение первых двух и последнего его элемента. Этот факт дает возможность оценивать число интересующих нас МСС числом независимых множеств в графах Кэли. Использующиеся в работе графы Кэли порождаются множеством А, мощность которого равна двум или единице. Ранее использовались регулярные или "почти" регулярные графы Кэли, множества вершин которых представляли собой один или два "непрерывных" целочисленных интервала. Особенность работы в том, что в ней оценивается количество независимых множеств в графах Кэли "поврежденных" удалением части вершин, то есть с нарушенной регулярной структурой. Верхняя оценка числа независимых множеств в таких графах представляет отдельный интерес и может использоваться при решении других задач. Заметим, что описанный в диссертации метод дает возможность получить сколь угодно точные оценки констант Камерона-Эрдеша, и точность эта зависит лишь от доступных вычислительных ресурсов.

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

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

В этой главе будем обозначать через G группу простого порядка Zp. Везде далее предполагается, что р — простое число. Множество S элементов группы G называется свободным от сумм (МСС), если для любых u,v Є S элемент и + v . S. Если S — свободное от сумм множество и для каждого МСС Т в G выполняется неравенство \S\ \Т\, то будем говорить, что S — максимальное свободное от сумм множество в G. Мощность максимального МСС в G будем обозначать через X(G). Положим А + В = {а + Ъ : а Є А, Ъ Є В}. 1.2 Постановка задачи и классификация МСС

Ставилась задача определить число и строение максимальных свободных от сумм множеств в группе Zp, что позволило бы вывести нижнюю оценку числа МСС в группах простого порядка. Введем следующую классификацию МСС в Zv. Будем говорить, что свободное от сумм множество S Є Zp, является множеством 1-го рода, если р = Зк + 2, 2-го рода, если р = Зк + 1 и —S ф S, 3-го рода, если р = Зк + 1, — S = S и S является арифметической прогрессией, 4-го рода, если р = 3k+l, —S = S и S не является арифметической прогрессией. В 1970 г. Х.П. Яп [33] определил структуру максимальных МСС 2-го и 3-го рода. Наша задача заключается в определении структуры максимальных МСС 1-го и 4-го рода. Следует отметить, что структура максимальных МСС 1-го рода, по всей видимости, уже была описана X. П. Япом в статье [32] в 1968-ом году, но найти эту статью автору, к сожалению, не удалось.

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

Основополагающую роль практически во всех доказательствах играют следующие две теоремы. Теорема 4 (A. L. Cauchy - Н. Davenport [30]) Пусть А и В — непустые подмножества группы G простого порядка. Тогда либо А + В — G, либо Л + Я И + В-1. Теорема 5 (A. G. Vosper [30]) Пусть G — аддитивная группа вычетов по модулю р, А, В — непустые подмножества G и С = А + В. Тогда либо \С\ \А\ + \В\, либо выполняется одно из следующих утверждений: (i)C = G, (и) \С\ = р - 1 и В = f - А, где f = С, (Иг) А и В принадлежат арифметическим прогрессиям с одинаковой разностью, (iv) \А\ = 1 или \В\ = 1. На нижеследующую теорему, доказанную А. X. Ремтуллой и А. П. Стрит [31] в 1970-ом году, существенным образом опирается доказательство теоремы 8. Теорема 6 (А. Н. Rhemtulla - А. P. Street [31]) Пусть G = Zp, гдер = Зк+1. Тогда всякое максимальное множество, свободное от сумм, S может быть отоб paotceuo при помощи некоторого автоморфизма в одно из следующих: (г) {k+l,k + 2,...,2k}, (ii) {k,k + l,...,2k-l}, (in) {k, k + 2, k + 3,..., 2k - 1,2k + 1}. Лемма 1 (H. P. Yap [33]) Пусть A = {a + id;i = 1,2,..., r} — подмножество Zm, где (m,d) = 1 и 2 r 1. Тогда A может быть представлено в форме арифметической прогрессии лишь двумя способами: A = {a + id; і — 1,2,..., г}, А = {а + (г + l)d + i(-d); і = 1,2,..., г}. Кроме того, нам потребуются следующие две леммы.

Лемма 2 Пусть G — Zp и (і) р = Ък + \, тогда \{G) — к, (И) р = Зк + 2, тогда \(G) = к + 1. Доказательство. Рассмотрим случай (і). Пусть р = Зк + 1 и S — произвольное максимальное МСС в Zp. Из равенства S П (S + S) = 0 и теоремы Коши-Давенпорта следует, что р — \S\ \S + S\ 2\S\ — 1. Пусть \S\ = к + г, где г 0, тогда р- (к + г) = 2к + 1 - г \S + S\ 2{к + г) - 1 или г 2/3. Следовательно, г = 0. Из того, что множество S = {к + 1, к + 2,..., 2к} является МСС следует, что A(G) = к. Рассмотрим случай (и). Из тех же соображений, что и в первом случае при \S\ = к + г, г 0 получим 2к + 2 — г \S + S\ 2(к + г) — 1 или г 1, и мы можем положить г = 1. Поскольку S = {к + 1,к + 2,...,2к + 1] — МСС, то Л(С) = к + 1.

1.4 Структура максимальных МСС 1-го и 4-го рода Теорема 7 Пусть р = Зк + 2, S — максимальное МСС в G = Zp. Тогда имеют место следующие равенства 1) S = S, 2) SU(S + S) = G, 3) S = {a + id;i = 0,1,...,к}, (1.1) где (х, у) = (a, d) — ненулевое решение сравнения 2х + ку = 0 (modp). (1.2) И обратно, если (х,у) = (а,й) — ненулевое решение сравнения (1.2), то задаваемое равенством (1.1) множество S является максимальным МСС в G и удовлетворяет свойствам 1) и 2). Всего G содержит различных максимальных МСС. Доказательство. Пусть p = 3k + 2nS — максимальное МСС в G = Zp. Докажем, что S = — S. Предположим обратное. Из того, что р — простое число следует, что к нечетно. Из леммы 2 следует, что \S\ = к + 1. Заметим, что для множества S = S U (-S) выполнено равенство S П (S + S ) = 0. Действительно, если предположить обратное, то найдутся элементы si, S2 Є S и s Є. S , такие, что справедливо равенство Si = s2 + s . Возможны два случая: а) s Є S, тогда Si является суммой элементов из S. Это противоречит тому, что S является МСС. б) s Є —S, тогда — s Є S и S2 = Si + (—s ). Это противоречит тому, что S является МСС. Справедливость равенства S = —S установлена. Из теоремы 4 и вышесказанного следует, что р — \S\ — 2к + 1 \S + S\ \S \ + \S\ — 1 = 15 1 + к и, соответственно, 5 = к + 1. Следовательно, —S = S и 5 + = 2к + 1. Из того, что S П (5 + S) = 0 и 5 + 5 + S = \G\, вытекает, что S U (S + S) = G. Докажем теперь, что S = {a + id; і = 0,..., к}, где (х, у) = (a, d) — есть ненулевое решение сравнения 2х + ку = 0 (mod р). Из теоремы Воспера, учитывая равенство 15 + 51 = 25 — 1, получаем, что S представимо в виде (1.1). Из равенства S = —S следует, что для некоторого 1 j к будет выполнено сравнение —а = а + jd (mod р) или 2a + jd = 0 (modp). (1.3) Предположим, что j к. Отметим нечетность j, ведь иначе будет справедливо сравнение 2{а + {j/2)d) = 0 (modp), что невозможно, так как элемент a+(j/2)d Є S и, следовательно, не сравним с нулем. Отсюда и из того, что к нечетно, вытекает неравенство j к — 2. Для множества S = {a + id; і = 0,1,..., j} справедливо равенство —S = S . Так как —S = S, то найдется хотя бы одна пара взаимно обратных элементов множества S вида а+ (j + i)d,a + (j + r)d, где 1 і, г к — j, тогда 2a+(2j + i + r)d = 0 (modp). Учитывая сравнение (1.3), получаем (j + і + r)d = 0 (mod р). (1.4) Заметим, что max(ji + г + г) = 2к — 1 р т mm(j + г + г) — 3 0, так что сравнение (1.4) не может выполняться и j = к. Таким образом, мы доказали, что 2а + kd = 0 (mod р). Докажем теперь, что если (х, у) — (a,d) — есть ненулевое решение (1.2), то S заданное равенством (1.1) — есть максимальное МСС, в G. Предположим, что S не являвся МСС. Тогда для некоторых 0 г к, 0 j 2к выполнено сравнение 2а + jd = а 4- id (mod р), учитывая сравнение 2a + kd = 0 (modp), получим (2(j - і) - k)d = 0 (modp). (1.5) Заметим, что max(2(j—i) — k) = ЗА; р и mm(2(j—і) — к) = —Зк —р, следовательно, 2(j — і) — к = 0, что невозможно, так как А; нечетно. Таким образом, сравнение (1.5) не может выполняться, и мы пришли к противоречию. Из леммы 2 следует, что S — максимальное МСС. Очевидно, что сравнение (1.2) имеет р—1, ненулевых решений, причем, если пара (о,d) является решением (1.2), то пара (а + kd,—d) также является решением (1.2). Из леммы 1 следует, что только эти пары задают соответствующее МСС. Таким образом, G содержит различных максимальных МСС. Теорема 8 Пусть р = Зк + 1 и S — максимальное МСС в G = Zp, такое, что -S = S uS\J{S + S) = G. Тогда S = {a, a + 2d, a + 3d,..., a + (k - l)d, a + (k+ l)d}, (1.6) где (x, y) = (a, d) — ненулевое решение сравнения 2x + (k + l)y = 0 (modp). (1.7) И обратно, при р 13, если (х,у) = (a, d) — ненулевое решение сравнения (1.7), то задаваемое равенством (1.6) множество S является максимальным МСС в G, таким, что —S — S, и S U (5 + S) = G. Всего при р 13 группа G содержит 2: различных максимальных МСС, таких, что —S = S и S U (S + S) = G.

Доказательство. Пусть р = ЗА; + 1и5 — максимальное МСС в G = Zv, такое, что -S = S и SU(S + S) = G. Так как \S + S\ = 2k + l 2\S\, то из теоремы Воспера следует, что множество S непредставимо в виде арифметической прогрессии. Так как любой автоморфизм переводит арифметическую прогрессию в арифметическую прогрессию, то из теоремы 8 следует, что S представимо в виде

Похожие диссертации на О числе множеств, свободных от сумм

Оценки числа независимых множеств в графах из некоторых классовДайняк Александр Борисович

Суммы случайного числа случайных величин: исследование безгранично делимых распределенийУмаров, Алишер Юсубжанович

Распределение граничных функционалов от сумм случайного числа дискретно распределенных слагаемыхРозуменко, Анатолий Михайлович

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

Закон больших чисел для взвешенных сумм случайных элементов в банаховом пространствеВолодин, Андрей Игоревич

Средние значения тригонометрических сумм в кольце гауссовых чиселСорокин Павел Николаевич

Короткие тригонометрические суммы с нецелой степенью натурального числаРахмонов, Парвиз Заруллоевич

Тригонометрические суммы Г. Вейля над кольцом целых алгебраических чиселКокорев, Антон Владимирович

Асимптотические свойства сумм независимых случайных величин со случайным числом слагаемыхЧжан Бо

Сумма характеров Гекке по последовательности сдвинутых простых чиселПанов Вячеслав Михайлович