¿Qué tamaño puede tener un conjunto de números enteros se si todos los pares tienen pequeñas mcd?

Question

Supongamos $A\subset[1,N]$ es un conjunto de números enteros. Si por cualquier distintos $a,b\in A$ tenemos $(a,b)\leq M$, a continuación, cómo de grande puede $|A|$ ser?

Si $M=1$ entonces $|A|$ es en la mayoría de las $\pi(N)$ desde el mapa de $a\mapsto P_+(a)$ (que envía a $a$ a su más grande el primer factor) es una inyección a la de los números primos, y así los números primos ellos mismos son los más eficientes. Si $M=N$, entonces podemos tomar $|A|=N$. ¿Qué acerca de la $M$ entre ambos? Puede usted batir los números primos? Sería seguro asumir que $A$ consiste únicamente en $M$-suave números, ya que podemos descomponer $A=A_1\cup A_2$ donde cada una de las $a\in A_1$ es $M$-suave y cada una de las $a\in A_2$ tiene un primer factor que, al menos,$M+1$. Los grandes factores primos que aparecen como divisores en $A_2$ no se pueden repetir, por lo $|A_2|\leq \pi(N)$.

Answer 1

Vamos a demostrar que la máxima cardinalidad de un conjunto para $M^2\leq N$ tiene un tamaño igual a $$\pi(N)+\sum_{1<n\leq M} \pi(p(n))$$ where $p(n)$ is the smallest prime factor of $n$. Since $$\sum_{1<n\leq M} \pi(p(n))\sim \frac{M^2}{2\log^2 M},$$ this proves that Ilya Bogdanov's example of including all pairwise products of primes not exceeding $M$ es casi óptimo en términos de asymptotics.

Como usted sugiere en la pregunta, este problema es equivalente a la construcción de la mayor subconjunto $A\subset S_M(N)$ tal que $\gcd(a,b)\leq M$ por cada $a,b\in A$ donde $S_M(N)$ es el conjunto de $n\leq N$ cuyo mayor factor principal es en la mayoría de las $M$.

Para ver por qué, supongamos que $A$ satisface $\gcd(a,b)\leq M$ por cada $a,b\in A$. A continuación, cada primer que es mayor que $M$ puede dividir en más de un elemento de $A$. Si $p>M$ divide $a\in A$, en $a=p$ sólo ayuda a crear un conjunto mayor $A$. Desde estos primos no interactúan con el $M$-suave números, la prueba está completa.

Deje $T(N,M)$ indicar el tamaño máximo de un conjunto de $A\subset S_M(N)$. A continuación, el tamaño del subconjunto más grande de $[1,N]$ parejas con las $\gcd$'s delimitada por $M$ es $$\pi(N)-\pi(M)+T(N,M).$$

Como se ha mencionado por Fedja en los comentarios s, el razonamiento por encima de los números primos se extiende a todos los números enteros. Considerando los números primos $p,q\leq M$ tal que $pq>M$, vemos que no sólo puede ser exactamente un número divisible por $pq$. Del mismo modo para cualquier $p,q,r$ con $pq,qr,rp\leq M$ e $pqr>M$ sólo puede haber un número en nuestro set divisible por $pqr$. Así nos encontramos con que el tamaño máximo es la suma de los números enteros cuyo mayor correcto divisor es menor que $M$. Dado que la mayor correcto divisor de $n$ es igual a $n/p(n)$ donde $p(n)$ es el menos el primer factor, podemos agrupar las cosas basándonos en esto, y tenemos que $$T(N,M)=\sum_{1<p\leq M}\sum_{n\leq M:\ p(n)\geq p}1.$$ Reorganización de este es igual $$\sum_{1<n\leq M}\sum_{p\leq p(n)}1=\sum_{n\leq M}\pi\left(p(n)\right),$$ and for composite $n$ $p(n)\leq\sqrt{n}$, so the primes dominate this sum. Thus asymptotically we have $$T(N,M)\sim\sum_{p\leq M}\pi(p)\sim\frac{M^{2}}{2\log^{2}M}.$$