Теорема Коши — Дэвенпорта

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

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

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

Пусть $A,B\subseteq {\mathbb {Z} }_{p},\ A\not =\emptyset ,\ B\not =\emptyset$. Определим $A+B=\left\lbrace {a+b\mod p:a\in A,b\in B}\right\rbrace$. Тогда $|A+B|\geq \min \left({|A|+|B|-1,p}\right)$

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

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

$A=\left\lbrace {a_{1}<\dots <a_{n}}\right\rbrace$

$B=\left\lbrace {b_{1}<\dots <b_{m}}\right\rbrace$

числа $a_{1}+b_{1},a_{2}+b_{1}\dots ,a_{n}+b_{1}$ и $a_{n}+b_{2},\dots ,a_{n}+b_{m}$ всегда различны.

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

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

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

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

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

Поэтому основная сложность заключается в доказательстве $|A+B|\geq |A|+|B|-1$ когда $|A|+|B|\leq p$.

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

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

• $A$ и $B$ не пересекаются

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

От первой ситуации можно избавиться с помощью сдвига элементов одного из множеств, так как $\forall s:|(A+s)+B|=|(A+B)+s|=|A+B|$. Если же все такие сдвиги полностью лежат во множестве $B$ (не ограничивая общности, предполагаем, что $|A|\leq |B|$), то легко показать, что $b\in B\Rightarrow b+(a_{2}-a_{1})\in B$ для любых $a_{1},a_{2}\in A$, то есть $B$ представляет собой зацикленную бесконечную арифметическую прогрессию с разностью $a_{2}-a_{1}$. Ввиду особенностей группы вычетов по простому модулю, это означает, что $B={\mathbb {Z} }_{p}$, а это приводит к простейшему случаю $|A|+|B|>p$.

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

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

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

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

${\begin{matrix}{\rm {supp}}(f)=A\\{\rm {supp}}({\widehat {f}})={\tilde {A}}\\{\rm {supp}}(g)=B\\{\rm {supp}}({\widehat {g}})={\tilde {B}}\\\end{matrix}}$

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

${\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$

${\rm {supp}}(f*g)\subset {\rm {supp}}(f)+{\rm {supp}}(g)=A+B$

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

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

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

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

В 1964 году Эрдёш и Хейльбронн предположили, что для множества $A\oplus A=\left\lbrace {a+b:a,b\in A,a\not =b}\right\rbrace$ верно $|A\oplus A|\geq 2|A|-3$. Это доказали в 1994 году Диас да Сильва и Хамидаон, используя теорию представлений симметрических групп (специальный раздел теории представлений). Они доказали даже более общий результат, а именно:

${\Bigg \lbrace }{\sum \limits _{a\in A'}a\ :\ A'\subset A,|A'|=m}{\Bigg \rbrace }\geq m|A|-m^{2}+1$

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

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

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

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

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

$|A{+}_{S}B|=\#\left\lbrace {a+b:a\in A,b\in B,a-b\not \in S}\right\rbrace \leq |A|+|B|-2|S|-1$

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

Как говорилось выше, аналитическое доказательство использует тот факт, что ${\rm {supp}}(A*B)\subset A+B$. Соответственно, для усложнённой формы задачи нужно модифицировать операцию свёртки так, чтобы для новой операции $\circ$ выполнялось ${\rm {supp}}(A\circ B)\subset A{+}_{S}B$. Однако исходное доказательство существенно использовало то, что ${\widehat {f*g}}={\widehat {f}}\cdot {\widehat {g}}$, так что важно проследить за тем, чтобы ${\widehat {f\circ g}}$ также подчинялась каким-то общим законам.

Очевидный способ построения модифицированной свёртки, для которой выполняется ${\rm {supp}}(A\circ B)\subset A{+}_{S}B$ состоит в ограничении обычной свёртки. Грубое построение даёт следующую формулу:

$(f\circ g)(x)=\sum \limits _{a+b=x}{f(a)g(b)\prod \limits _{d\in S}{[a-b=d]}}$

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

$(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 )}}}$

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

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

$(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 )}}}$,

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

$(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 )}}}$

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

${\widehat {f\circ g}}(x)=\sum \limits _{k=0}^{|S|}{c(k){\widehat {f}}(x+k){\widehat {g}}(x+|S|-k)}$,

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

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

Эта оценка не точна - ранее, в 2002 году, Пан и Сун доказали, используя алгебраические методы, в числе более сильного утверждения, что $|A{+}_{S}B|\geq |A|+|B|-|S|-2$.

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

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

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

$\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$,

где $P$ - некоторый многочлен. Например, в случае $P(x,y)=x-y$ такая задача сводится к гипотезе Эрдёша-Хельбронна. Случай $p(x_{1},\dots ,x_{n})=\prod \limits _{1\leq i<j\leq n}{(x_{i}-x_{j})}$ представляет её аналог для нескольких множеств.

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

Пусть $P(x,y)$ - однородный многочлен степени $d$ над произвольным полем характеристики $p$, причём существуют $i\in [0;|A|),\ j\in [0;|B|)$, для которых его коэффициенты при $x^{i}y^{d-i}$ и $x^{d-j}y^{j}$ не равны нулю. Рассмотрим многочлен $P_{*}(x)=P(x,1)$ и его разложение $P_{*}(x)=(x+1)^{s}(x+\alpha _{1})^{t_{1}}\dots (x+\alpha _{k})^{t_{k}}$. Обозначим $N(P_{*})=\max \limits _{k\geq 0}\left\lbrace {p^{k}\cdot \#\left\lbrace {i:t_{i}\geq p^{k}}\right\rbrace }\right\rbrace$. Пусть также дан любой многочлен $R(x,y)$ степени ${\rm {deg}}R<d$. Тогда ${\Bigg \vert }{\oplus _{P+R}\sum \limits _{k=1}^{n}{A_{k}}}{\Bigg \vert }\geq \min \left\lbrace {p-s,\ |A|+|B|-1-d-N(P_{*})}\right\rbrace$

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

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

Пусть $f(x_{1},\dots ,x_{n})=a_{1}{x_{1}}^{k}+\dots +a_{n}{x_{n}}^{k}+g(x_{1},\dots ,x_{n})$ - полином, такой, что ${\rm {deg}}\ g<k$. Тогда $\#\left\lbrace {f(x_{1},\dots ,x_{n}):x_{1}\in A_{1},\dots ,x_{n}\in A_{n}}\right\rbrace \geq \sum \limits _{i=1}^{n}{\left\lfloor {\frac {|A_{i}|-1}{k}}\right\rfloor }+1$ Если же $k\geq n$, то аналогичное неравенство выполняется даже при наложении на набор $(x_{1},\dots ,x_{n})$ условия $x_{i}\not =x_{j}$ для $i\not =j$.

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

Пусть $f(x_{1},\dots ,x_{n})={x_{1}}^{k}+\dots +{x_{n}}^{k}+g(x_{1},\dots ,x_{n})$ - полином, такой, что ${\rm {deg}}g<k$. Тогда $\#\left\lbrace {f(x_{1},\dots ,x_{n}):x_{1}\in A_{1},\dots ,x_{n}\in A_{n}}\right\rbrace \geq \sum \limits _{i=1}^{n}{q_{i}}+1$, где $q_{i}=\min \limits _{i\leq j\leq n:j\equiv i{\pmod {k}}}{\left\lfloor {\frac {|A_{j}|-j}{k}}\right\rfloor }$

См. также

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