Teorema de Behrend

Sobre subconjuntos de los números enteros en los que ningún miembro del conjunto es múltiplo de ningún otro

En combinatoria aritmética , el teorema de Behrend establece que los subconjuntos de los números enteros de 1 a 1 en los que ningún miembro del conjunto es múltiplo de otro deben tener una densidad logarítmica que tienda a cero a medida que 1 se hace grande. El teorema recibe su nombre en honor a Felix Behrend , quien lo publicó en 1935. ${\displaystyle n}$ ${\displaystyle n}$

Declaración

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

Un subconjunto de 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 . ^[1] ${\displaystyle \{1,\dots n\}}$ ${\displaystyle O(1/{\sqrt {\log \log n}})}$

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

Ejemplos

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

• En el subconjunto , todos los pares de números están dentro de un factor de menos de dos entre sí, por lo que no pueden existir dos múltiplos. Incluye aproximadamente la mitad de los números de a . Por el teorema de Dilworth (que utiliza una partición de los números 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 como todos sus elementos son grandes, este subconjunto tiene una densidad logarítmica baja, solo . ${\displaystyle \{\lceil (n+1)/2\rceil ,\dots n\}}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle O(1/\log n)}$
• Otro subconjunto primitivo es el conjunto de los números primos . A pesar de que existen menos números primos que el número de elementos del ejemplo anterior, este conjunto tiene mayor densidad logarítmica, , según la divergencia de la suma de los recíprocos de los primos . ${\displaystyle O(\log \log n/\log n)}$

Ambos subconjuntos tienen una densidad logarítmica significativamente menor que el límite dado por el teorema de Behrend. Al resolver una conjetura de GH Hardy , tanto Paul Erdős como Subbayya Sivasankaranarayana Pillai demostraron que, para , el conjunto de números con factores primos exactos (contados con multiplicidad) tiene densidad logarítmica ${\displaystyle k\approx \log \log n}$ ${\displaystyle k}$

${\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 densidad logarítmica con la misma forma y una constante principal mayor. ^[4]

Historia

Este teorema se conoce como teorema de Behrend porque Felix Behrend lo demostró en 1934, ^[1] y lo publicó en 1935. ^[5] Paul Erdős demostró el mismo resultado, en 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 prueba de Behrend ya era conocida. ^[1]

Referencias

1. Sárközy, A. (2013), "Sobre las propiedades de divisibilidad de secuencias de números enteros", en Graham, Ronald L. ; Nešetřil, Jaroslav (eds.), Las matemáticas de Paul Erdős, I , Algorithms and Combinatorics, vol. 13 (2.ª ed.), Berlín: Springer, págs. 221–232, doi :10.1007/978-3-642-60408-9_19, MR  1425189. Véase en particular la pág. 222.
2. Erdős, P .; Sarközy, A .; Szemerédi, E. (1967), "Sobre un teorema de Behrend" (PDF) , Revista de la Sociedad Matemática Australiana , 7 : 9–16, MR  0209246
3. Erdős, P. (1948), "Sobre los números enteros que tienen exactamente K {\displaystyle K} factores primos" (PDF) , Anales de Matemáticas , Segunda Serie, 49 : 53–66, doi :10.2307/1969113, MR  0023279
4. Erdős, P .; Sarközy, A .; Szemerédi, E. (1967), "Sobre un problema extremo relacionado con secuencias primitivas" (PDF) , Revista de la Sociedad Matemática de Londres , Segunda Serie, 42 : 484–488, doi :10.1112/jlms/s1-42.1.484, MR  0218325
5. Behrend, Felix (enero de 1935), "Sobre secuencias de números no divisibles entre sí", Journal of the London Mathematical Society , s1-10 (1): 42–44, doi :10.1112/jlms/s1-10.37.42