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

В аддитивной теории чисел и комбинаторике , ограничено sumset имеет вид

{\ Displaystyle S = \ {a_ {1} + \ cdots + a_ {n}: \ a_ {1} \ in A_ {1}, \ ldots, a_ {n} \ in A_ {n} \ \ mathrm {и } \ P (a_ {1}, \ ldots, a_ {n}) \ not = 0 \},}

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

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

{\ Displaystyle P (x_ {1}, \ ldots, x_ {n}) = \ prod _ {1 \ leq i <j \ leq n} (x_ {j} -x_ {i}),}

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

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

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

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

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

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

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

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

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

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

где A - конечное непустое подмножество поля F , а p ( F ) - простое число p, если F имеет характеристику p , и p ( F ) = ∞, если F имеет характеристику 0. Различные расширения этого результата были даны формулами Нога Алон , М.Б. Натансон и И. Ружа в 1996 г. ^[9] QH Hou и Zhi-Wei Sun в 2002 г. ^[10] и Дж. Кароли в 2004 г. ^[11]

Комбинаторный Nullstellensatz [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Герольдингер, Альфред; Ружа, Имре З., ред. (2009). Комбинаторная теория чисел и аддитивная теория групп . Курсы повышения квалификации по математике CRM Барселона. Elsholtz, C .; Freiman, G .; Хамидун, юноша; 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. Lett . 15 (6): 1263–1276. arXiv : math.CO/0610981 . Bibcode : 2006math ..... 10981S . DOI : 10.4310 / MRL.2008.v15.n6.a15 .
Чжи-Вэй Сунь : Обзор некоторых гипотез Эрдеш-Хейльбронна, Льва и Сневили ( PDF ).
Вайсштейн, Эрик В. "Гипотеза Эрдеша-Хейльбронна" . MathWorld .

[1] Натансон (1996), стр.44

[GR1412-2] Geroldinger & Ruzsa (2009) pp.141-142

[3] Натансон (1996), стр.48

[GR53-4] Geroldinger & Ruzsa (2009) стр.53

[5] MathWorld Вольфрама, Теорема Коши-Дэвенпорта, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html , по состоянию на 20 июня 2012 г.

[GR143-6] Герольдингер и Ружа (2009) стр.143

[7] Натансон (1996) стр.77

[8] Диаш да Силва, JA; Хамидун, Й.О. (1994). «Циклические пространства для производных Грассмана и аддитивная теория». Бюллетень Лондонского математического общества . 26 (2): 140–146. DOI : 10.1112 / БЛМ / 26.2.140 .

[Alon1996-9] а б Алон, Нога ; Натансон, Мелвин Б.; Ружа, Имре (1996). «Полиномиальный метод и ограниченные суммы классов конгруэнции» (PDF) . Журнал теории чисел . 56 (2): 404–417. DOI : 10,1006 / jnth.1996.0029 . Руководство по ремонту 1373563 .

[10] Хоу, Цин-Ху; Сунь, Чжи-Вэй (2002). «Ограниченные суммы в поле» . Acta Arithmetica . 102 (3): 239–249. Bibcode : 2002AcAri.102..239H . DOI : 10,4064 / aa102-3-3 . Руководство по ремонту 1884717 .

[11] Каройи, Дьюла (2004). «Проблема Эрдеша – Хейльбронна в абелевых группах». Израильский математический журнал . 139 : 349–359. DOI : 10.1007 / BF02787556 . Руководство по ремонту 2041798 .

[Alon1999-12] а б Алон, Нога (1999). "Комбинаторный Nullstellensatz" (PDF) . Комбинаторика, теория вероятностей и вычисления . 8 (1–2): 7–29. DOI : 10.1017 / S0963548398003411 . Руководство по ремонту 1684621 .

[13] Алон, Нога ; Тарси, Майкл (1989). «Нигде-нулевая точка в линейных отображениях». Combinatorica . 9 (4): 393–395. DOI : 10.1007 / BF02125351 . Руководство по ремонту 1054015 .

[1]