Теорема Кнезера (комбинаторика)

В разделе математики, известном как аддитивная комбинаторика , теорема Кнезера может относиться к одной из нескольких связанных теорем относительно размеров определенных сумм в абелевых группах . Они названы в честь Мартина Кнезера , опубликовавшего их в 1953 году. ^{[ 1 ]} и 1956 год. ^{[ 2 ]} Их можно рассматривать как расширение теоремы Коши-Дэвенпорта , которая также касается сумм в группах, но ограничена группами, порядок которых является простым числом . ^{[ 3 ]}

Первые три утверждения относятся к суммам, размер которых (в различных смыслах) строго меньше суммы размеров слагаемых. Последнее утверждение касается случая равенства меры Хаара в связных компактных абелевых группах.

Строгое неравенство

Если $G$ является абелевой группой и $C$ является подмножеством $G$ , группа $H(C):=\{g\in G:g+C=C\}$ является стабилизатором $C$ .

Мощность

Позволять $G$ быть абелевой группой . Если $A$ и $B$ являются непустыми конечными подмножествами $G$ удовлетворяющий $|A+B|<|A|+|B|$ и $H$ является стабилизатором $A+B$ , затем ${\begin{aligned}|A+B|&=|A+H|+|B+H|-|H|.\end{aligned}}$

Это утверждение является следствием приведенного ниже утверждения для групп LCA, полученного путем специализации на случае, когда объемлющая группа дискретна. Самостоятельное доказательство содержится в учебнике Натансона. ^{[ 4 ]}

Нижняя асимптотическая плотность в натуральных числах

Основной результат статьи Кнезера 1953 г. ^{[ 1 ]} является вариантом теоремы Манна о плотности Шнирельмана .

Если $C$ является подмножеством $\mathbb {N}$ , тем ниже асимптотическая плотность $C$ это число ${\underline {d}}(C):=\liminf _{n\to \infty }{\frac {|C\cap \{1,\dots ,n\}|}{n}}$ . Теорема Кнезера для нижней асимптотической плотности утверждает, что если $A$ и $B$ являются подмножествами $\mathbb {N}$ удовлетворяющий ${\underline {d}}(A+B)<{\underline {d}}(A)+{\underline {d}}(B)$ , то существует натуральное число $k$ такой, что $H:=k\mathbb {N} \cup \{0\}$ удовлетворяет следующим двум условиям:

(A+B+H)\setminus (A+B)

конечно,

и

{\underline {d}}(A+B)={\underline {d}}(A+H)+{\underline {d}}(B+H)-{\underline {d}}(H).

Обратите внимание, что $A+B\subseteq A+B+H$ , с $0\in H$ .

Мера Хаара в локально компактных абелевых (LCA) группах

Позволять $G$ быть группой LCA с мерой Хаара $m$ и пусть $m_{*}$ обозначим внутреннюю меру, индуцированную $m$ (мы также предполагаем $G$ Хаусдорф, как всегда). Мы вынуждены рассматривать внутреннюю меру Хаара как сумму двух $m$ -измеримых множеств может не быть $m$ -измеримый. Сац 1 из статьи Кнезера 1956 года ^{[ 2 ]} можно сформулировать следующим образом:

Если $A$ и $B$ непусты $m$ -измеримые подмножества $G$ удовлетворяющий $m_{*}(A+B)<m(A)+m(B)$ , то стабилизатор $H:=H(A+B)$ компактен и открыт. Таким образом $A+B$ компактен и открыт (и, следовательно, $m$ -измеримый), являющийся объединением конечного числа смежных классов $H$ . Более того, $m(A+B)=m(A+H)+m(B+H)-m(H).$

Равенство в связных компактных абелевых группах

Поскольку связные группы не имеют собственных открытых подгрупп, из предыдущего утверждения немедленно следует, что если $G$ подключен, то $m_{*}(A+B)\geq \min\{m(A)+m(B),m(G)\}$ для всех $m$ -измеримые множества $A$ и $B$ . Примеры, где

m_{*}(A+B)=m(A)+m(B)<m(G)

( 1 )

можно найти, когда $G$ это тор $\mathbb {T} :=\mathbb {R} /\mathbb {Z}$ и $A$ и $B$ являются интервалами. Сац 2 из статьи Кнезера 1956 года ^{[ 2 ]} говорит, что все примеры множеств, удовлетворяющих уравнению ( 1 ) с ненулевыми слагаемыми, являются их очевидными модификациями. Точнее: если $G$ — связная компактная абелева группа с мерой Хаара $m,$ $A$ и $B$ являются $m$ -измеримые подмножества $G$ удовлетворяющий $m(A)>0,m(B)>0$ и уравнение ( 1 ), то существует непрерывный сюръективный гомоморфизм $\phi :G\to \mathbb {T}$ и есть закрытые интервалы $I$ , $J$ в $\mathbb {T}$ такой, что $A\subseteq \phi ^{-1}(I)$ , $B\subseteq \phi ^{-1}(J)$ , $m(A)=m(\phi ^{-1}(I))$ , и $m(B)=m(\phi ^{-1}(J))$ .

Примечания

^ Jump up to: ^а ^б Кнезер, Мартин (1953). «Оценки асимптотической плотности множеств сумм». Математика З. (на немецком языке). 58 : 459-484. дои : 10.1007/BF01174162 . S2CID 120456416 . Збл 0051.28104 .
^ Jump up to: ^а ^б ^с Кнезер, Мартин (1956). «Множества сумм в локально компактных абелевых группах». Математика З. (на немецком языке). 66 :88-110. дои : 10.1007/BF01186598 . S2CID 120125011 . Збл 0073.01702 .
^ Герольдингер и Ружа (2009 , стр. 143)
^ Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Тексты для аспирантов по математике . Том. 165. Шпрингер-Верлаг . стр. 109–132. ISBN 0-387-94655-1 . Збл 0859.11003 .

Ссылки

Герольдингер, Альфред; Ружа, Имре З. , ред. (2009). Комбинаторная теория чисел и аддитивная теория групп . Курсы повышения квалификации по математике CRM в Барселоне. Эльшольц, К.; Фрейман, Г.; Хамидун, Йо; Хегивари, Н.; Каройи, Г.; Натансон, М.; Солимоси, Дж. ; Станческу, Ю. С предисловием Хавьера Силлеруэло, Марка Ноя и Ориола Серры (координаторов DocCourse). Базель: Биркхойзер. ISBN 978-3-7643-8961-1 . Збл 1177.11005 .
Гринкевич, Давид (2013). Структурная аддитивная теория . Развитие математики . Том. 30. Спрингер . п. 61. ИСБН 978-3-319-00415-0 . Збл 1368.11109 .
Тао, Теренс ; Ву, Ван Х. (2010), Аддитивная комбинаторика , Кембридж : Издательство Кембриджского университета , ISBN 978-0-521-13656-3 , Збл 1179.11002

[Kneser53-1] Jump up to: ^а ^б Кнезер, Мартин (1953). «Оценки асимптотической плотности множеств сумм». Математика З. (на немецком языке). 58 : 459-484. дои : 10.1007/BF01174162 . S2CID 120456416 . Збл 0051.28104 .

[Kneser56-2] Jump up to: ^а ^б ^с Кнезер, Мартин (1956). «Множества сумм в локально компактных абелевых группах». Математика З. (на немецком языке). 66 :88-110. дои : 10.1007/BF01186598 . S2CID 120125011 . Збл 0073.01702 .

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

[4] Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Тексты для аспирантов по математике . Том. 165. Шпрингер-Верлаг . стр. 109–132. ISBN 0-387-94655-1 . Збл 0859.11003 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]