Русская Википедия:Теорема Коши — Дэвенпорта

Теорема Коши — Дэвенпорта — результат аддитивной комбинаторики, названный в честь Огюстена Коши и Гарольда Дэвенпорта, утверждающий, что размер множества сумм двух множеств в группе вычетов <math>{\mathbb Z}_p</math> никогда не оказывается существенно меньше, чем сумма их размеров.

Теорема была предложена Гансом Хейльбронном как нерешённая задача Гарольду Дэвенпорту, который решил её и опубликовал доказательство в 1935 году.^[1]

Формулировка

Шаблон:Рамка Пусть <math>A,B \in {\mathbb Z}_p,\ A \not = \emptyset,\ B \not = \emptyset</math>. Определим <math>A + B = \left\lbrace{a+b \mod p : a \in A, b \in B }\right\rbrace</math>.

Тогда <math>|A+B| \ge \min\left({|A| + |B| - 1, p}\right)</math> Шаблон:Конец рамки

Суть нетривиальности

Для множеств целых (или вещественных) чисел аналогичное утверждение очевидно, поскольку для

<math>A=\left\lbrace{a_1 < \dots < a_n}\right\rbrace</math>

<math>B=\left\lbrace{b_1 < \dots < b_m}\right\rbrace</math>

числа <math>a_1+b_1,a_2+b_1\dots,a_n+b_1</math> и <math>a_n+b_2,\dots,a_n+b_m</math> всегда различны.

Аналогичное доказательство не проходит в кольце вычетов, где натуральные числа «зацикливаются». Для кольца <math>{\mathbb Z}_m</math> при составном <math>m</math> утверждение попросту неверно, поскольку там существуют подгруппы <math>G</math> (арифметические прогрессии с разностью, делящей <math>m</math>), для которых <math>G+G=G</math> (это вообще, по определению, всегда верно для подгрупп).

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

Способы доказательства

Крайний случай

Если <math>\min\left({|A| + |B| - 1, p}\right) = p</math>, то утверждение <math>A+B={\mathbb Z}_p</math> доказывается элементарно, поскольку для любого <math>x</math> множества <math>A</math> и <math>\left\lbrace{x-b : b \in B}\right\rbrace</math> пересекаются просто ввиду своего размера, по принципу Дирихле.

Поэтому основная сложность заключается в доказательстве <math>|A+B| \ge |A|+|B|-1</math> когда <math>|A|+|B| \le p</math>.

Комбинаторное доказательство

Для комбинаторного доказательства используется очевидный факт, что <math>(A \cap B) + (A \cup B) \subset A+B</math>. Если <math>0 < |A \cap B| < \min\left\lbrace{|A|,|B|}\right\rbrace</math>, то это позволяет применить индукцию по размеру меньшего из этих двух множеств. Иначе возможны две ситуации:

<math>A</math> и <math>B</math> не пересекаются

одно из множеств полностью содержится в другом

От первой ситуации можно избавиться с помощью сдвига элементов одного из множеств, так как <math>\forall s: |(A+s)+B|=|(A+B)+s|=|A+B|</math>. Если же все такие сдвиги полностью лежат во множестве <math>B</math> (не ограничивая общности, предполагаем, что <math>|A| \le |B|</math>), то легко показать, что <math>b \in B \Rightarrow b+(a_2-a_1) \in B</math> для любых <math>a_1,a_2 \in A</math>, то есть <math>B</math> представляет собой зацикленную бесконечную арифметическую прогрессию с разностью <math>a_2-a_1</math>. Ввиду особенностей группы вычетов по простому модулю, это означает, что <math>B = {\mathbb Z}_p</math>, а это приводит к простейшему случаю <math>|A|+|B| > p</math>.^[2]

Алгебраическое доказательство

Алгебраическое доказательство было представлено в 2004 году Теренсом Тао.^[3]. Его основой служит комбинаторная теорема о нулях. Если <math>|A+B| = (|A| - 1) + (|B'| - 1) < |A|+|B|-1</math>, где <math>B' \subset B</math>, то многочлен <math>P(x,y) = \prod \limits_{c \in C} {(x+y-c)}</math> имеет ненулевой коэффициент при <math>x^{|A|-1} y^{|B'|-1}</math>. Из этого, по комбинаторной теореме о нулях, следует, что при каких-то <math>x \in A, y \in B' \subset B</math> многочлен <math>P(x,y)</math> не обнуляется, а это, очевидно, не так, по определению <math>A+B</math>.^[2]

Аналитическое доказательство

Доказательство средствами гармонического анализа использует принцип неопределённости и свёртку функций над <math>{\mathbb Z}_p</math>. В качестве рассматриваемых функций используются такие <math>f,g</math>, что

<math>\begin{matrix}

{\rm supp}(f)=A \\ {\rm supp}(\widehat{f})=\tilde{A} \\ {\rm supp}(g)=B \\ {\rm supp}(\widehat{g})=\tilde{B} \\ \end{matrix}</math>

где <math>|\tilde{A}|=p+1-|A|</math> и <math>|\tilde{B}|=p+1-|B|</math>, причём пересечение <math>\tilde{A} \cap \tilde{B}</math> настолько мало, насколько только может быть при таких размерах. Используя свойства свёртки, в этом случае имеем:

<math>{\rm supp}(\widehat{f * g}) = {\rm supp}(\widehat{f} \cdot \widehat{g}) = {\rm supp}(\widehat{f}) \cap {\rm supp}(\widehat{g}) = |\tilde{A}|+|\tilde{B}|-p</math>

<math>{\rm supp}(f * g) \subset {\rm supp}(f)+{\rm supp}(g) = A+B</math>

Так как, по принципу неопределённости, <math>|{\rm supp}(f * g)|+|{\rm supp}(\widehat{f * g})| \ge p+1</math>, то из этого при правильном выборе <math>\tilde{A}</math> и <math>\tilde{B}</math> теорема Коши-Дэвенпорта следует напрямую.^[4]

Вариации и обобщения

Поскольку везде ниже речь пойдёт о подмножествах конечного поля, то в любой оценке размера множества сумм нужно делать поправку на то, что если множества, откуда берутся слагаемые, очень велики по размеру, то сумма занимает всё поле. Поэтому для удобства изложения везде ниже запись <math>|Q| \ge n</math> относительно любого множества сумм <math>Q</math> (например, <math>Q=A+B</math>) означает, что <math>|Q| \ge \min\left\lbrace{p, n}\right\rbrace</math>

Запрет на сложение равных элементов

В 1964 году Эрдёш и Хейльбронн предположили, что для множества <math>A \oplus A = \left\lbrace{a+b : a, b \in A, a \not = b}\right\rbrace</math> верно <math>|A \oplus A| \ge 2 |A| - 3</math>^[5]. Это доказали в 1994 году Диас да Сильва и Хамидаон, используя теорию представлений симметрических групп (Шаблон:Iw теории представлений). Они доказали даже более общий результат^[6], а именно:

<math>\Bigg\lbrace{ \sum \limits_{a \in A'} a\ :\ A' \subset A, |A'|=m }\Bigg\rbrace \ge m|A| - m^2 + 1</math>

При <math>m=2</math> это утверждение в точности совпадает с гипотезой Эрдёша и Хейльбронна.

Эта оценка оказалась не самой лучшей - в 1996 году Алон, Натанзон и Ружа доказали, что <math>\Bigg\lbrace{ \sum \limits_{a \in A'} a\ :\ A' \subset A, |A'|=m }\Bigg\rbrace \ge m|A| - \binom{m+1}{2} + 1</math>.

Естественным образом возник вопрос - можно ли сказать что-то подобное вообще про <math>A \oplus B = \left\lbrace{a+b : a \in A, b \in B, a \not = b}\right\rbrace</math>. Этот вопрос может быть решён с помощью модификации алгебраического доказательства основной теоремы Коши-Дэвенпорта, если добавить к рассматриваемому многочлену один множитель, то есть рассматривать <math>P(x,y) = (x-y) \prod \limits_{c \in C} {(x+y-c)}</math>, где <math>A+B \subset C</math>.^[2]

Запрет на элементы с заданными разностями

В 2009 году была опубликована модификация аналитического доказательства, позволяющая показать, что для произвольного конечного множества <math>S \subset {\mathbb Z}_p</math> выполняется неравенство

<math>|A {+}_{S} B| = \# \left\lbrace{a+b : a \in A, b \in B, a - b \not \in S}\right\rbrace \le |A|+|B|-2|S|-1</math>

Шаблон:Hider</math>

(квадратные скобки используются в смысле нотации Айверсона), но такой подход не позволяет раскрыть произведение по <math>d \in S</math> и работать с ним аналитически. Поэтому уместно ввести функцию <math>\lambda : {\mathbb Z_p} \to {\mathbb C}</math> (для начала произвольную) и рассмотреть следующую операцию:

<math>(f \circ g)(x) = \sum \limits_{a+b=x} {f(a)g(b) \prod \limits_{d \in S} {\Big({\lambda(a-b) - \lambda(d)}\Big)}}</math>

Очевидно, что если <math>a-b \in S</math>, то произведение по <math>d \in S</math> обнуляется, так что <math>{\rm supp}(f \circ g) \subset A {+}_{S} B</math>.

Следующий шаг состоит в выборе конкретной функции <math>\lambda</math>. Для удобства анализов коэффициентов Фурье функции <math>f \circ g</math> уместно связать <math>\lambda</math> с корнями из единицы (поскольку в основе идеи коэффициентов Фурье лежат свойства корней из единицы). Например,

<math>(f \circ g)(x) = \sum \limits_{a+b=x} {f(a)g(b) \prod \limits_{d \in S} {\Big({e_p(a-b) - e_p(d)}\Big)}} = \sum \limits_{t} {f(a) g(b) \prod \limits_{d \in S} {\Big({e_p(t-(x-t)) - e_p(d)}\Big)}}</math>,

где <math>e_p(k) = e^{2 \pi \frac{k}{p} i}</math> - корень из едеиницы. Однако явное рассмотрение коэффициента Фурье такой функции не даёт нужного результата. Чтобы получить удобную в использовании формулу, степени корня из единицы <math>t-(x-t)=2t-x</math> и <math>d</math> нужно преобразовать одинаковым линейным преобразованием, получив соответственно <math>x-t</math> и <math>t-d</math> и рассматривать операцию

<math>(f \circ g)(x) = \sum \limits_{t} {f(a) g(b) \prod \limits_{d \in S} {\Big({e_p(x-t) - e_p(t-d)}\Big)}}</math>

Тогда из перестановки слагаемых в явном выражении <math>\widehat{f \circ g}</math> можно вывести, что

<math>\widehat{f \circ g}(x) = \sum \limits_{k=0}^{|S|} {c(k) \widehat{f}(x+k) \widehat{g}(x+|S|-k)}</math>,

где <math>c(k)</math> - коэффициенты, зависящие только от <math>S</math>.

Далее выбираются множества <math>\tilde{A}, \tilde{B}</math>, аналогично аналитическому доказательству основной теоремы. Но теперь они обязательно выбираются так, чтобы их элементы шли подряд - это позволяет контролировать <math>\widehat{A \circ B}(x)</math> и получить нужную оценку, действуя так же, как в основном доказательстве.

}}

Эта оценка не точна - ранее, в 2002 году, Пан и Сун доказали, используя алгебраические методы, в числе более сильного утверждения, что <math>|A {+}_{S} B| \ge |A| + |B| - |S| - 2</math>.^[7]

Также в своей работе Пан и Сун высказали гипотезу, что вычитаемое 2 можно заменить на 1 если <math>|S|</math> чётно. Авторы работы 2009 года (обобщающей аналитический метод) предположили, что для этого достаточно даже условия <math>A \not = B</math>.^[8]

Полиномиальные ограничения на слагаемые

Сильное обобщение задачи Коши-Дэвенпорта состоит в выведении общего метода для оценки через размеры <math>A</math> и <math>B</math> размера множества вида

<math>\oplus_P \sum \limits_{k=1}^{n} {A_k} = \left\lbrace{a_1+\dots+a_n : a_i \in A_i, P(a_1,\dots,a_n) \not = 0}\right\rbrace</math>,

где <math>P</math> - некоторый многочлен. Например, в случае <math>P(x,y)=x-y</math> такая задача сводится к гипотезе Эрдёша-Хельбронна. Случай <math>p(x_1,\dots,x_n) = \prod \limits_{1 \le i < j \le n} {(x_i-x_j)}</math> представляет её аналог для нескольких множеств.

В 2002 году Пан и Сун рассмотрели этот вопрос для многочленов от двух переменных <math>P(x,y)</math> и доказали следуюющий результат^[7]:

Шаблон:Рамка Пусть <math>P(x,y)</math> - однородный многочлен степени <math>d</math> над произвольным полем характеристики <math>p</math>, причём существуют <math>i \in [0;|A|),\ j \in [0;|B|)</math>, для которых его коэффициенты при <math>x^{i} y^{d-i}</math> и <math>x^{d-j} y^{j}</math> не равны нулю. Рассмотрим многочлен <math>P_{*}(x) = P(x,1)</math> и его разложение <math>P_{*}(x) = (x+1)^{s} (x+\alpha_1)^{t_1} \dots (x+\alpha_k)^{t_k}</math>. Обозначим <math>N(P_{*}) = \max \limits_{k \ge 0} \left\lbrace{p^{k} \cdot \# \left\lbrace{i : t_i \ge p^{k}}\right\rbrace}\right\rbrace</math>. Пусть также дан любой многочлен <math>R(x,y)</math> степени <math>{\rm deg} R < d</math>. Тогда

<math>\Bigg\vert{\oplus_{P+R} \sum \limits_{k=1}^{n} {A_k}}\Bigg\vert \ge \min \left\lbrace{p-s,\ |A|+|B|-1-d-N(P_{*})}\right\rbrace</math>

Шаблон:Конец рамки

Замена суммирования на полином

В 2008 году Сун получил следующий результат^[9]:

Шаблон:Рамка Пусть <math>f(x_1,\dots,x_n) = a_1 {x_1}^k + \dots + a_n {x_n}^k + g(x_1,\dots,x_n)</math> - полином, такой, что <math>{\rm deg}\ g < k</math>.

Тогда <math>\#\left\lbrace{f(x_1,\dots,x_n) : x_1 \in A_1, \dots, x_n \in A_n}\right\rbrace \ge \sum \limits_{i=1}^{n} {\left\lfloor{\frac{|A_i|-1}{k}}\right\rfloor} + 1</math>

Если же <math> k \ge n</math>, то аналогичное неравенство выполняется даже при наложении на набор <math>(x_1,\dots,x_n)</math> условия <math>x_i \not = x_j</math> для <math>i \not = j</math>.

Шаблон:Конец рамки

В 2009 году этот результат в частном случае был усилен^[10]:

Шаблон:Рамка Пусть <math>f(x_1,\dots,x_n) = {x_1}^k + \dots + {x_n}^k + g(x_1,\dots,x_n)</math> - полином, такой, что <math>{\rm deg} g < k</math>.

Тогда <math>\#\left\lbrace{f(x_1,\dots,x_n) : x_1 \in A_1, \dots, x_n \in A_n}\right\rbrace \ge \sum \limits_{i=1}^{n} {q_i} + 1</math>,

где <math>q_i = \min \limits_{i \le j \le n : j \equiv i \pmod k} {\left\lfloor{\frac{|A_j|-j}{k}}\right\rfloor}</math> Шаблон:Конец рамки

См. также

Множество сумм

Примечания

Шаблон:Примечания

[1] Шаблон:Cite web

[Petrov1-2] 2,0 ^2,1 ^2,2 Математическая лаборатория имени П.Л.Чебышева, Курс лекций "Аддитивная комбинаторика", Лекция 1

[3] Шаблон:Cite web

[Tao_uncertainty-4] Шаблон:Cite web

[5] Шаблон:Cite web

[6] J.A. Dias da Silva, Y.O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994) 140–146

[2002_Pan_Sun-7] 7,0 ^7,1 Шаблон:Cite web

[8] Шаблон:Cite web

[9] Zhi-Wei Sun, "On value sets of polynomials over a field", Finite Fields and Their Applications 14 (2008) 470–481 Шаблон:Недоступная ссылка

[10] Hao Pan, Zhi-Wei Sun, "A new extension of the Erd'os-Heilbronn conjecture", J. Combin. Theory Ser. A 116(2009), no. 8, 1374–1381.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.