Twierdzenie Behrenda

W kombinatoryce arytmetycznej twierdzenie Behrenda stwierdza , że podzbiory liczb całkowitych od 1 do ${\ displaystyle n}$ , w których żaden element zbioru nie jest wielokrotnością jakiegokolwiek innego, muszą mieć gęstość logarytmiczną , która dąży do zera jako ${\ displaystyle n} }$ staje się duży. Twierdzenie nosi imię Felixa Behrenda , który opublikował je w 1935 roku.

Oświadczenie

Gęstość logarytmiczną zbioru liczb całkowitych od 1 do $i$ zdefiniować, ustawiając wagę każdej liczby całkowitej $Displaystyle$ 1 $1/i}$ dzieląc sumę waga zbioru przez $,$ sumę częściową szeregu harmonicznego (lub równoważnie dla celów analizy asymptotycznej dzielenie przez ${\ displaystyle \ log n}$ ). Wynikowa liczba wynosi 1 lub jest bliska 1, gdy zbiór zawiera wszystkie liczby całkowite z tego zakresu, ale jest mniejsza, gdy brakuje wielu liczb całkowitych, a zwłaszcza gdy brakujące liczby całkowite są same w sobie małe.

Podzbiór z ${\ Displaystyle \ {1, \ kropki n \}}$ nazywany jest prymitywnym , jeśli ma tę właściwość, że żaden element podzbioru nie jest wielokrotnością jakiegokolwiek innego elementu. Twierdzenie Behrenda mówi, że gęstość logarytmiczna dowolnego podzbioru pierwotnego musi być mała. Dokładniej, logarytmiczna gęstość takiego zestawu musi wynosić ${\ Displaystyle O (1/ {\ sqrt {\ log \ log n}})}$ .

W przypadku nieskończonych sekwencji pierwotnych maksymalna możliwa gęstość jest mniejsza. ${\ Displaystyle o (1 / {\ sqrt {\ log \ log n}})$ }

Przykłady

Istnieją duże prymitywne podzbiory ${\ Displaystyle \ {1, \ kropki n \}}$ . Jednak te zestawy nadal mają małą gęstość logarytmiczną.

$_$ podzbiorze _ mniej niż dwa, więc żadne dwa nie mogą być wielokrotnościami. Obejmuje około połowę liczb od ${\ displaystyle 1}$ do ${\ displaystyle n}$ . Zgodnie z twierdzeniem Dilwortha (przy użyciu podziału liczb całkowitych na łańcuchy potęg dwóch pomnożonych przez liczbę nieparzystą) ten podzbiór ma maksymalną liczność spośród wszystkich podzbiorów, w których żadne dwa nie są wielokrotnościami. Ale ponieważ wszystkie jego elementy są duże, ten podzbiór ma niską gęstość logarytmiczną, tylko ${\ Displaystyle O (1 / \ log n)}$ .
Innym pierwotnym podzbiorem jest zbiór liczb pierwszych . Pomimo tego, że jest mniej liczb pierwszych niż liczba elementów w poprzednim przykładzie, ten zestaw ma większą gęstość logarytmiczną, ${\ Displaystyle O (\ log \ log n / \ log n) }$ , zgodnie z rozbieżnością sumy odwrotności liczb pierwszych .

Oba te podzbiory mają znacznie mniejszą gęstość logarytmiczną niż granica określona przez twierdzenie Behrenda. Rozwiązując przypuszczenie GH Hardy'ego , zarówno Paul Erdős , jak i Subbayya Sivasankaranarayana Pillai wykazali, że dla ${\ Displaystyle k \ około \ log \ log n}$ zbiór liczb z dokładnie ${\ displaystyle k}$ czynniki pierwsze (liczone z krotnością) mają gęstość logarytmiczną

{\ Displaystyle {\ Frac {1 + o (1)}} {\ sqrt {2 \ pi \ log \ log n}}}}

dokładnie pasujące do postaci twierdzenia Behrenda. Ten przykład jest najlepszy z możliwych w tym sensie, że żaden inny prymitywny podzbiór nie ma gęstości logarytmicznej o tej samej postaci i większej stałej wiodącej.

Historia

To twierdzenie jest znane jako twierdzenie Behrenda, ponieważ Felix Behrend udowodnił je w 1934 roku i opublikował w 1935 roku. Paul Erdős udowodnił ten sam wynik podczas podróży pociągiem z Węgier do Cambridge w 1934 roku, aby uciec przed rosnącym antysemityzmem w Europie, ale na jego przybyciu odkrył, że dowód Behrenda był już znany.