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

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

${displaystyle S = {a_ {1} + cdots + a_ {n}: a_ {1} в A_ {1}, ldots, a_ {n} в A_ {n} mathrm {и} 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$

S записывается как ${displaystyle A_ {1} dotplus cdots dotplus A_ {n}}$ который обозначается ${displaystyle n ^ {клин} A}$ если ${displaystyle A_ {1} = cdots = A_ {n} = A}$. Обратите внимание, что |S| > 0 тогда и только тогда, когда существуют ${displaystyle a_ {1} в A_ {1}, ldots, a_ {n} в 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 ^ {клин} A | geq min {p, 2 | A | -3}}$ если п это простое и А непустое подмножество поля Z/пZ.^[7] Впервые это подтвердили Ж. А. Диаш да Силва и Ю. О. Хамидун в 1994 г.^[8]кто показал это

${displaystyle | n ^ {клин} 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} в A_ {1}, ldots, a_ {n} в A_ {n}}$ такой, что ${displaystyle f (a_ {1}, ldots, a_ {n}) ot = 0}$.

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

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

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

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

• Герольдингер, Альфред; Ружа, Имре З., ред. (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.