El número de factores primos de la diferencia de dos números

Question

Como es costumbre, definir $\omega(m)$ a ser el número de los distintos números primos dividiendo $m$. También, vamos a $P(m)$ representan el conjunto de los números primos divisores de $m$. Deje $S=\{p_1,p_2,\ldots,p_n\}$ ser un conjunto de $n$ distintos números primos números, cada uno con $O(n)$ bits.

Deje $a$ $b$ ser de dos números positivos tales que $P(a)\subseteq S$, $P(b)\subseteq S$ y tenemos que $\omega(a), \omega(b)\leq n$.

Podemos obtener algunas asintótica límites en $\omega(a-b)$ como una función de la $n$ ? Es trivial ver que $\omega(a-b)\leq \log(\max(a,b))$. Idealmente queremos enlazado $\omega(a-b)$ como una función de la $n$. Incluso de los límites de la orden de $O(2^n)$ parecen interesantes.

Si no podemos hacer esto, los ejemplos de tales $a,b$ que no permiten que cualquier bound puede ser interesante conocer. Suponiendo que obligado en términos de $n$ no es posible, podemos obtener mejores límites en $\omega(a-b)$ en términos de $a,b$ de la trivial.

Si le ayuda, usted puede elegir establecer $S$ $n$ distintos números primos sin embargo, usted como siempre y como cada uno de los prime ha $O(n)$ bits.

Puede ser esta pregunta es trivial. Moderadores, por favor siéntase libre de cerrar si es así. Me encontré con este problema, mientras que trabajar en un problema en la informática teórica.

Answer 1

Usted no puede conseguir a cualquier obligado, debido a que requieren que el $P(a)\subseteq S$ $P(b)\subseteq S$ no impide que cualquier número de la división $a-b$.

Por ejemplo, supongamos $S=\{3,5\}$ y dejar $$ N_K = \prod_{i=4}^K p_i $$ ser el producto de números primos de $p_4=7$ cualquier $p_K$ le gusta. Luego hay algunos exponentes $x,y>0$ tal que $3^x \equiv 5^y \equiv 1 \pmod{N_K}$, por ejemplo múltiplos de $\phi(N_K)$ (Euler totient) de trabajo, de ahí que si $$ a=5^{\phi(N_K)} \quad b=3^{\phi(N_K)} \\ \implica N_K \mediados de los a-b \implica \omega(a-b)\ge K $$ (también se puede tomar $b=1$ si usted lo permite).

El general de los límites para la $\omega(a-b)$ debe ser ligeramente mejor que el $\log(a-b)$ (es decir $a>b$ a keep it simple), MathWorld da $\omega(x)\sim \log x/\log\log x$ para primorials que es el peor de los casos. Si en general se puede encontrar una $2^n$-lisa número $a$ cerca de una de las arbitrariamente grande primorial $\#$, de modo que $b=a-\#=O(2^n)$, entonces estás atascado con esencialmente los mismos límites. Mi conjetura es que algo así es posible, aunque no puedo afirmarlo con certeza.