Behrendsova věta - Behrends theorem - Wikipedia

v aritmetická kombinatorika, Behrendova věta uvádí, že podmnožiny celá čísla od 1 do ${ displaystyle n}$ ve kterém žádný člen množiny není násobkem žádného jiného, ​​musí mít a logaritmická hustota to jde na nulu jako ${ displaystyle n}$ se zvětší. Věta je pojmenována po Felix Behrend, který ji publikoval v roce 1935.

Prohlášení

Logaritmická hustota množiny celých čísel od 1 do ${ displaystyle n}$ lze definovat nastavením hmotnosti každého celého čísla ${ displaystyle i}$ být ${ displaystyle 1 / i}$a vydělením celkové hmotnosti soupravy ${ displaystyle log n}$ (nebo ekvivalentně pro účely asymptotická analýza, vydělením ${ displaystyle n}$dílčí součet harmonická řada ). Výsledné číslo je 1 nebo blízké 1, když sada obsahuje všechna celá čísla v tomto rozsahu, ale menší, když chybí celá čísla, a zvláště když jsou chybějící celá čísla malá.^[1]

Podmnožina ${ displaystyle {1, tečky n }}$ je nazýván primitivní pokud má vlastnost, že žádný prvek podmnožiny není násobkem žádného jiného prvku. Behrendova věta uvádí, že logaritmická hustota jakékoli primitivní podmnožiny musí být malá. Přesněji řečeno, logaritmická hustota takové množiny musí být ${ displaystyle O (1 / { sqrt { log log n}})}$.^[1]

Pro nekonečné primitivní sekvence je maximální možná hustota menší, ${ displaystyle o (1 / { sqrt { log log n}})}$.^[2]

Příklady

Existují velké primitivní podmnožiny ${ displaystyle {1, tečky n }}$. Tyto sady však stále mají malou logaritmickou hustotu.

• V podmnožině ${ displaystyle { lceil (n + 1) / 2 rceil, tečky n }}$, všechny dvojice čísel jsou v faktoru menším než dva od sebe, takže žádné dva nemohou být násobky. Zahrnuje přibližně polovinu čísel z ${ displaystyle 1}$ na ${ displaystyle n}$. Podle Dilworthova věta (pomocí rozdělení celých čísel do řetězců mocnin dvou vynásobených lichým číslem) má tato podmnožina maximální mohutnost mezi všemi podmnožinami, ve kterých žádné dva nejsou násobky. Ale protože všechny jeho prvky jsou velké, má tato podmnožina pouze nízkou logaritmickou hustotu ${ displaystyle O (1 / log n)}$.
• Další primitivní podmnožinou je sada prvočísla. Navzdory tomu, že v prvním příkladu je méně prvočísel než počet prvků, má tato množina větší logaritmickou hustotu, ${ displaystyle O ( log log n / log n)}$, podle divergence součtu převrácených hodnot prvočísel.

Obě tyto podskupiny mají významně nižší logaritmickou hustotu, než je vazba daná Behrendovou větou. Řešení domněnky G. H. Hardy, oba Paul Erdős a Subbayya Sivasankaranarayana Pillai ukázal, že pro ${ displaystyle k přibližně log log n}$, množina čísel s přesně ${ displaystyle k}$ prime factor (počítáno s multiplicitou) má logaritmickou hustotu

${ displaystyle { frac {1 + o (1)} { sqrt {2 pi log log n}}},}$

přesně odpovídá formě Behrendovy věty.^[3] Tento příklad je nejlepší možný v tom smyslu, že žádná jiná primitivní podmnožina nemá logaritmickou hustotu se stejnou formou a větší počáteční konstantou.^[4]

Dějiny

Tato věta je známá jako Behrendova věta, protože Felix Behrend dokázal to v roce 1934,^[1] a publikoval ji v roce 1935.^[5] Paul Erdős stejný výsledek prokázal při jízdě vlakem v roce 1934, kdy cestoval z Maďarska do Cambridge, aby unikl v té době rostoucímu antisemitismu Evropy, ale při svém příjezdu zjistil, že Behrendův důkaz je již znám.^[1]

Reference