Ограниченный набор сумм - Restricted sumset

В аддитивная теория чисел и комбинаторика, а ограниченный набор сумм имеет форму

${displaystyle S={a_{1}+cdots +a_{n}: a_{1}in A_{1},ldots ,a_{n}in A_{n} mathrm {and} P(a_{1},ldots ,a_{n})ot =0},}$

куда ${displaystyle A_{1},ldots ,A_{n}}$ конечные непустые подмножества поле F и ${displaystyle P(x_{1},ldots ,x_{n})}$ является полиномом над F.

Когда ${displaystyle P(x_{1},ldots ,x_{n})=1}$, S это обычный сумма ${displaystyle A_{1}+cdots +A_{n}}$ который обозначается nA если ${displaystyle A_{1}=cdots =A_{n}=A}$; когда

${displaystyle P(x_{1},ldots ,x_{n})=prod _{1leq i<jleq n}(x_{j}-x_{i}),}$

S записывается как ${displaystyle A_{1}dotplus cdots dotplus A_{n}}$ который обозначается ${displaystyle n^{wedge }A}$ если ${displaystyle A_{1}=cdots =A_{n}=A}$. Обратите внимание, что |S| > 0 тогда и только тогда, когда существуют ${displaystyle a_{1}in A_{1},ldots ,a_{n}in A_{n}}$ с ${displaystyle P(a_{1},ldots ,a_{n})ot =0}$.

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

В Теорема Коши – Дэвенпорта названный в честь Огюстен Луи Коши и Гарольд Давенпорт утверждает, что для любого простого п и непустые подмножества А и B циклической группы простого порядка Z/пZ у нас есть неравенство^[1][2]

${displaystyle |A+B|geq min{p, |A|+|B|-1}.,}$

Мы можем использовать это, чтобы вывести Теорема Эрдеша – Гинзбурга – Зива.: дана любая последовательность из 2п−1 элемент в Z/п, Существуют п элементы, суммирующиеся с нулем по модулю п. (Здесь п не обязательно должно быть простым.)^[3][4]

Прямое следствие теоремы Коши-Дэвенпорта: для любого множества S из п−1 или более ненулевых элементов, не обязательно различных Z/пZ, каждый элемент Z/пZ можно записать как сумму элементов некоторого подмножества (возможно, пустого) S.^[5]

Теорема Кнезера обобщает это на общие абелевы группы.^[6]

Гипотеза Эрдеша – Хейльбронна

В Гипотеза Эрдеша – Хейльбронна поставленный Пол Эрдёш и Ганс Хайльбронн в 1964 году говорится, что ${displaystyle |2^{wedge }A|geq min{p,2|A|-3}}$ если п это простое и А непустое подмножество поля Z/пZ.^[7] Впервые это подтвердили Ж. А. Диаш да Силва и Ю. О. Хамидун в 1994 г.^[8]кто показал это

${displaystyle |n^{wedge }A|geq min{p(F), n|A|-n^{2}+1},}$

куда А конечное непустое подмножество поля F, и п(F) является простым п если F характерен п, и п(F) = ∞, если F имеет характеристику 0. Различные расширения этого результата были даны Нога Алон, М. Б. Натансон и И. Ружа в 1996 г.^[9] К. Х. Хоу и Чжи-Вэй Сунь в 2002,^[10]и Г. Кароли в 2004 году.^[11]

Комбинаторный Nullstellensatz

Мощным инструментом изучения нижних оценок мощности различных ограниченных сумм является следующий фундаментальный принцип: комбинаторный Nullstellensatz.^[12] Позволять ${displaystyle f(x_{1},ldots ,x_{n})}$ - многочлен над полем F. Предположим, что коэффициент при мономе ${displaystyle x_{1}^{k_{1}}cdots x_{n}^{k_{n}}}$ в ${displaystyle f(x_{1},ldots ,x_{n})}$ отличен от нуля и ${displaystyle k_{1}+cdots +k_{n}}$ это общая степень из ${displaystyle f(x_{1},ldots ,x_{n})}$. Если ${displaystyle A_{1},ldots ,A_{n}}$ конечные подмножества F с ${displaystyle |A_{i}|>k_{i}}$ за ${displaystyle i=1,ldots ,n}$, то есть ${displaystyle a_{1}in A_{1},ldots ,a_{n}in A_{n}}$ такой, что ${displaystyle f(a_{1},ldots ,a_{n})ot =0}$.

Метод, использующий комбинаторный Nullstellensatz, также называется полиномиальным методом. Этот инструмент был основан на статье Н. Алона и М. Тарси в 1989 г.^[13] и разработан Алон, Натансон и Ружа в 1995-1996 годах,^[9] и переформулирована Алоном в 1999 году.^[12]

Смотрите также

• Метод полиномов в комбинаторике

Рекомендации

1. Натансон (1996) стр.44
2. Герольдингер и Ружа (2009), стр. 141–142
3. Натансон (1996) стр.48
4. Герольдингер и Ружа (2009) стр.53
5. MathWorld Вольфрама, теорема Коши-Дэвенпорта, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, по состоянию на 20 июня 2012 г.
6. Герольдингер и Ружа (2009) с.143
7. Натансон (1996) стр.77.
8. Dias da Silva, J. A .; Хамидун, Ю. О. (1994). «Циклические пространства для производных Грассмана и аддитивная теория». Бюллетень Лондонского математического общества. 26 (2): 140–146. Дои:10.1112 / blms / 26.2.140.
9. Алон, Нога; Натансон, Мелвин Б .; Ружа, Имре (1996). «Полиномиальный метод и ограниченные суммы классов конгруэнтности» (PDF). Журнал теории чисел. 56 (2): 404–417. Дои:10.1006 / jnth.1996.0029. МИСТЕР  1373563.
10. Хоу, Цин-Ху; Сунь, Чжи-Вэй (2002). «Ограниченные суммы в поле». Acta Arithmetica. 102 (3): 239–249. Bibcode:2002AcAri.102..239H. Дои:10.4064 / aa102-3-3. МИСТЕР  1884717.
11. Каройи, Дьюла (2004). «Проблема Эрдеша – Хейльбронна в абелевых группах». Израильский математический журнал. 139: 349–359. Дои:10.1007 / BF02787556. МИСТЕР  2041798.
12. Алон, Нога (1999). "Комбинаторный Nullstellensatz" (PDF). Комбинаторика, теория вероятностей и вычисления. 8 (1–2): 7–29. Дои:10.1017 / S0963548398003411. МИСТЕР  1684621.
13. Алон, Нога; Тарси, Майкл (1989). «Нигде-нулевая точка в линейных отображениях». Комбинаторика. 9 (4): 393–395. Дои:10.1007 / BF02125351. МИСТЕР  1054015.

• Герольдингер, Альфред; Ружа, Имре З., ред. (2009). Комбинаторная теория чисел и аддитивная теория групп. Продвинутые курсы математики CRM Барселона. Elsholtz, C .; Freiman, G .; Hamidoune, Y. O .; Hegyvári, N .; Károlyi, G .; Натансон, М .; Solymosi, J .; Станческу Ю. С предисловием Хавьера Чиллеруэло, Марка Ноя и Ориола Серры (координаторов DocCourse). Базель: Биркхойзер. ISBN  978-3-7643-8961-1. Zbl  1177.11005.
• Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм. Тексты для выпускников по математике. 165. Springer-Verlag. ISBN  0-387-94655-1. Zbl  0859.11003.

внешняя ссылка

• Сунь, Чжи-Вэй (2006). «Аддитивная теорема и ограниченные суммы». Математика. Res. Латыш. 15 (6): 1263–1276. arXiv:math.CO/0610981. Bibcode:2006математика ..... 10981S. Дои:10.4310 / MRL.2008.v15.n6.a15.
• Чжи-Вэй Сунь: О некоторых догадках Эрдеша-Хейльбронна, Льва и Сневили (PDF ), обзорный разговор.
• Вайсштейн, Эрик В. "Гипотеза Эрдеша-Хейльбронна". MathWorld.