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

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

Ганс Гейльбронн запропонував теорему як нерозв'язану задачі Гарольду Девенпорту, який розв'язав її та опублікував доведення 1935 року.

Формулювання

Нехай $A,B\in {\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)$

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

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

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

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

Для множини цілих (або дійсних) чисел аналогічне твердження очевидне, оскільки для

Випадок простого модуля цікавий, тому що виявляється проміжним між цими двома. Якби теорема виявилася хибною, то це означало б, що побудова кільця лишків сама по собі, навіть не маючи підгруп, містить якусь структуру, близьку до арифметичної прогресії. Але теорема істинна.

Способи доведення

Крайній випадок

Якщо $\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 }$

Див. також

• Множина сум