Teorema de Behrend

En combinatoria aritmética , el teorema de Behrend establece que los subconjuntos de los enteros del 1 al${\displaystyle n}$en el que ningún miembro del conjunto es múltiplo de otro debe tener una densidad logarítmica que tiende a cero como${\displaystyle n}$se vuelve grande. El teorema lleva el nombre de Felix Behrend , quien lo publicó en 1935.

La densidad logarítmica de un conjunto de enteros del 1 al${\displaystyle n}$se puede definir estableciendo el peso de cada entero${\displaystyle i}$ser${\displaystyle 1/i}$y dividiendo el peso total del conjunto por el${\displaystyle n}$suma parcial de la serie armónica (o, equivalentemente para los fines del análisis asintótico , dividiendo por${\displaystyle \log n}$). El número resultante es 1 o cercano a 1 cuando el conjunto incluye todos los enteros en ese rango, pero menor cuando faltan muchos enteros, y particularmente cuando los enteros faltantes son pequeños. ^{[ 1 ]}

Un subconjunto de${\displaystyle \{1,\dots n\}}$Se denomina primitivo si tiene la propiedad de que ningún elemento del subconjunto es múltiplo de ningún otro elemento. El teorema de Behrend establece que la densidad logarítmica de cualquier subconjunto primitivo debe ser pequeña. Más precisamente, la densidad logarítmica de dicho conjunto debe ser${\displaystyle O(1/{\sqrt {\log \log n}})}$. ^{[ 1 ]}

Para secuencias primitivas infinitas, la densidad máxima posible es menor,${\displaystyle o(1/{\sqrt {\log \log n}})}$. ^{[ 2 ]}

Existen grandes subconjuntos primitivos de${\displaystyle \{1,\dots n\}}$Sin embargo, estos conjuntos aún presentan una baja densidad logarítmica.

• En el subconjunto${\displaystyle \{\lceil (n+1)/2\rceil ,\dots n\}}$, todos los pares de números están dentro de un factor menor que dos entre sí, por lo que no puede haber dos que sean múltiplos. Incluye aproximadamente la mitad de los números de${\displaystyle 1}$a${\displaystyle n}$Según el teorema de Dilworth (utilizando una partición de los enteros en cadenas de potencias de dos multiplicadas por un número impar), este subconjunto tiene la cardinalidad máxima entre todos los subconjuntos en los que no hay dos múltiplos. Pero debido a que todos sus elementos son grandes, este subconjunto tiene una densidad logarítmica baja, solo${\displaystyle O(1/\log n)}$.
• Otro subconjunto primitivo es el conjunto de los números primos . A pesar de que hay menos números primos que el número de elementos del ejemplo anterior, este conjunto tiene una mayor densidad logarítmica.${\displaystyle O(\log \log n/\log n)}$, según la divergencia de la suma de los recíprocos de los números primos .

Ambos subconjuntos tienen una densidad logarítmica significativamente menor que la cota dada por el teorema de Behrend. Resolviendo una conjetura de GH Hardy , tanto Paul Erdős como Subbayya Sivasankaranarayana Pillai demostraron que, para${\displaystyle k\approx \log \log n}$, el conjunto de números con exactamente${\displaystyle k}$Los factores primos (contados con multiplicidad) tienen densidad logarítmica.

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

que coincide exactamente con la forma del teorema de Behrend. ^{[ 3 ]} Este ejemplo es el mejor posible, en el sentido de que ningún otro subconjunto primitivo tiene una densidad logarítmica con la misma forma y una constante principal mayor. ^{[ 4 ]}

Este teorema se conoce como el teorema de Behrend porque Felix Behrend lo demostró en 1934 ^{[ 1 ]} y lo publicó en 1935. ^{[ 5 ]} Paul Erdős demostró el mismo resultado durante un viaje en tren en 1934 desde Hungría a Cambridge para escapar del creciente antisemitismo en Europa, pero a su llegada descubrió que la demostración de Behrend ya era conocida. ^{[ 1 ]}