58 votos

Número de elementos en el conjunto$\{1,\cdots,n\}\cdot\{1,\cdots,n\}$

Dejar $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. ¿Hay alguna estimación para$|A_n|$? Lo será $o(n^2)$?

75voto

Mystica555 Puntos 21

Esta pregunta se conoce como la tabla de multiplicación del problema, y fue originalmente planteada por Erdős en 1955. Erdős demostrado que $|A_n|=o(n^2)$, y esto se ha sumado Tenenbaum en 1984. En 2008, Ford dio a la magnitud exacta y demostró que $$\left|\lbrace a\cdot b:\ a,b\leq N\rbrace\right|\asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}},$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}.$$

En 2010 Koukoulopoulos dio multidimensional generalizaciones de Ford resultado, demostrando que $$\left|\lbrace a_1\cdots a_{k+1}\ :\ a_i\leq N \text{ for all } \ i\rbrace\right|\asymp \frac{N^{k+1}}{(\log N)^{c_k}(\log\log N)^{3/2}},$$ where $$c_{k}=\int_{1}^{\frac{k}{\log(k+1)}}\log x\text{d}x=\frac{\log(k+1)+k\log\left(k\right)-k\log\log(k+1)-k}{\log(k+1)}.$$

Algunas referencias:

  • Ford 2008: La distribución de los números enteros con un divisor en un intervalo de tiempo dado. arXiv enlace

  • Koukoulopoulos 2010: Localizada de la Factorización de números Enteros. arXiv enlace

  • Koukoulopoulos de 2012: En el número de enteros en un generalizado de la tabla de multiplicación. arXiv enlace

Nota: Las fechas utilizadas arriba se refieren a las fechas de publicación (no necesariamente la fecha fijada para el arXiv).

15voto

Void Puntos 111

Permítanme dar aquí una respuesta con un rápido argumento de por qué es $o(n^2)$. No sé si es el mismo de Erdős original de la prueba. UPD: lo que realmente es, y que se menciona más arriba en un comentario por Kevin P. Costello.

La mayoría de los números de 1 a $n$ ha $\log \log n (1+o(1))$ primer divisores (contadas con multiplicidad) por Erdős-Kac teorema. A continuación, la mayoría de sus productos tienen $2\log \log n (1+o(1))$ factores primos, mientras que la mayoría de los números de 1 a $n^2$ nuevo $\log \log n (1+o(1))$ factores primos. Esto demuestra que los productos de dos números de 1 a $n$ son raros en $\{1,2,\dots,n^2\}$

11voto

psweeney Puntos 16

La respuesta es sí, para más información vea las referencias dadas en la Enciclopedia en línea de secuencias enteras .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X