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

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

$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})\not =0\},$

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

Если $P$ является постоянной ненулевой функцией, например $P(x_{1},\ldots ,x_{n})=1$ для любого $x_{1},\ldots ,x_{n}$, затем $S$ это обычное множество $A_{1}+\cdots +A_{n}$ который обозначается $nA$ если $A_{1}=\cdots =A_{n}=A.$

Когда

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

S записывается как $A_{1}\dotplus \cdots \dotplus A_{n}$ который обозначается $n^{\wedge }A$ если $A_{1}=\cdots =A_{n}=A.$

Обратите внимание, что | С | > 0 тогда и только тогда, когда существуют $a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}$ с $P(a_{1},\ldots ,a_{n})\not =0.$

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

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

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

где $A+B:=\{a+b{\pmod {p}}\mid a\in A,b\in B\}$, то есть мы используем модульную арифметику . Его можно обобщить на произвольные (не обязательно абелевы) группы с помощью преобразования Дайсона . Если $A,B$ являются подмножествами группы $G$, затем

$|A+B|\geq \min\{p(G),\,|A|+|B|-1\}$

где $p(G)$ — размер наименьшей нетривиальной подгруппы $G$ (мы установили его $1$ если такой подгруппы нет).

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

Прямым следствием теоремы Коши-Дэвенпорта является следующее: для любой последовательности S, состоящей из p −1 или более ненулевых элементов, не обязательно различных, $\mathbb {Z} /p\mathbb {Z}$, каждый элемент $\mathbb {Z} /p\mathbb {Z}$ может быть записана как сумма элементов некоторой подпоследовательности (возможно, пустой) S .

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

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

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

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

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

Комбинаторная теорема о нулевом месте

Мощным инструментом в изучении нижних оценок мощностей различных ограниченных сумм является следующий фундаментальный принцип: комбинаторный Nullstellensatz . Позволять $f(x_{1},\ldots ,x_{n})$ быть многочленом над полем $F$. Предположим, что коэффициент при мономе $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}$ являются конечными подмножествами $F$ с $|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$.

Этот инструмент был основан на статье Н. Алона и М. Тарси в 1989 г. и разработан Алоном, Натансоном и Рузой в 1995–1996 годах, и переформулирован Алоном в 1999 году.

См. также

• Полиномиальный метод в комбинаторике

Ссылки

• Герольдингер, Альфред; Ружа, Имре З., ред. (2009). Комбинаторная теория чисел и аддитивная теория групп . Курсы повышения квалификации по математике CRM в Барселоне. Эльшольц, К.; Фрейман, Г.; Хамидун, Йо; Хегивари, Н.; Каройи, Г.; Натансон, М.; Солимоси, Дж.; Станческу, Ю. С предисловием Хавьера Силлеруэло, Марка Ноя и Ориола Серры (координаторов DocCourse). Базель: Биркхойзер. ISBN  978-3-7643-8961-1 . Збл   1177.11005 .
• Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Тексты для аспирантов по математике . Том. 165. Шпрингер-Верлаг . ISBN  0-387-94655-1 . Збл   0859.11003 .

Внешние ссылки

• Вайсштейн, Эрик В. «Гипотеза Эрдеша-Хейльбронна» . Математический мир .