Behrends teorem

I aritmetisk kombinatorik säger Behrends teorem att delmängderna av heltal från 1 till $n$ där ingen medlem av mängden är en multipel av någon annan måste ha en logaritmisk densitet som går till noll som $n$ blir stor. Teoremet är uppkallat efter Felix Behrend , som publicerade det 1935.

Påstående

Den logaritmiska tätheten för en uppsättning heltal från 1 till $n$ kan definieras genom att ställa in vikten för varje heltal $i$ till $1/i$ , och dividera totalen vikten av mängden med ${\displaystyle n}:$ te delsumman av övertonsserien (eller, ekvivalent för asymptotisk analys , dividera med $\log n$ ). Det resulterande talet är 1 eller nära 1 när mängden inkluderar alla heltal i det intervallet, men mindre när många heltal saknas, och särskilt när de saknade heltalen i sig själva är små.

En delmängd av $\{1,\dots n\}$ kallas primitiv om den har egenskapen att inget delmängdselement är en multipel av något annat element. Behrends teorem säger att den logaritmiska densiteten för varje primitiv delmängd måste vara liten. Mer exakt måste den logaritmiska densiteten för en sådan mängd vara $O(1/{\sqrt {\log \log n}})$ .

För oändliga primitiva sekvenser är den maximalt möjliga densiteten mindre, $o(1/{\sqrt {\log \log n}})$ .

Exempel

Det finns stora primitiva delmängder av $\{1,\dots n\}$ . Dessa uppsättningar har dock fortfarande liten logaritmisk densitet.

I delmängden $\{\lceil (n+1)/2\rceil ,\dots n\}$ är alla par av tal inom en faktor av mindre än två av varandra, så inga två kan vara multiplar. Den inkluderar ungefär hälften av siffrorna från $1$ till $n$ . Enligt Dilworths teorem (med en partition av heltal i potenskedjor av två multiplicerat med ett udda tal) har denna delmängd maximal kardinalitet bland alla delmängder där inte två är multipler. Men eftersom alla dess element är stora, har denna delmängd låg logaritmisk densitet, endast $O(1/\log n)$ .
En annan primitiv delmängd är uppsättningen primtal . Trots att det finns färre primtal än antalet element i föregående exempel, har denna uppsättning större logaritmisk densitet, $O(\log \log n/\log n)$ , enligt divergensen av summan av primtalens reciproka .

Båda dessa delmängder har betydligt mindre logaritmisk densitet än den gräns som ges av Behrends teorem. Genom att lösa en gissning om GH Hardy visade både Paul Erdős och Subbayya Sivasankaranarayana Pillai att för $k\approx \log \log n$ , uppsättningen av tal med exakt $k$ primtalsfaktorer (räknade med multiplicitet) har logaritmisk densitet

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

exakt matchande formen av Behrends sats. Detta exempel är bäst möjligt i den meningen att ingen annan primitiv delmängd har logaritmisk densitet med samma form och en större ledande konstant.

Historia

Denna teorem är känd som Behrends teorem eftersom Felix Behrend bevisade den 1934 och publicerade den 1935. Paul Erdős bevisade samma resultat, på en tågresa 1934 från Ungern till Cambridge för att undkomma den växande antisemitismen i Europa, men på hans ankomst upptäckte han att Behrends bevis redan var känt.