Number of prime factors of difference of two numbers As is the custom, define $\omega(m)$ to be number of distinct primes dividing $m$. Also, let $P(m)$ represent set of primes divisors of $m$. Let $S=\{p_1,p_2,\ldots,p_n\}$ be a set of $n$ distinct primes numbers, each having $O(n)$ bits.
Let $a$ and $b$ be two positive numbers such that  $P(a)\subseteq S$, $P(b)\subseteq S$ and we get that $\omega(a), \omega(b)\leq n$. 
Can we get some asymptotic bounds on $\omega(a-b)$ as a function of $n$ ? It's trivial to see that $\omega(a-b)\leq \log(\max(a,b))$. Ideally we want to bound $\omega(a-b)$ as a function of $n$. Even bounds of order of $O(2^n)$ seem interesting. 
If we cannot do this, examples of such $a,b$ which do not allow any such bound can be interesting to know. Assuming that bound in terms of $n$ is not possible, can we get better bounds on $\omega(a-b)$ in terms of $a,b$ than the trivial ones. 
If it helps, you can choose set $S$ of $n$ distinct primes however you like as long as each prime has $O(n)$ bits.  
May be this question is trivial. Moderators, please feel free to close it if so. I came across this problem while working on a  problem in theoretical computer science.
 A: You cannot get any such bound, because requiring that $P(a)\subseteq S$ and $P(b)\subseteq S$ does not prevent any number from dividing $a-b$.
For example, let $S=\{3,5\}$ and let
$$
N_K = \prod_{i=4}^K p_i
$$
be the product of primes from $p_4=7$ up to any $p_K$ you like. Then there are some exponents $x,y>0$ such that $3^x \equiv 5^y \equiv 1 \pmod{N_K}$, for example multiples of $\phi(N_K)$ (the Euler totient function) will work, hence if
$$
a=5^{\phi(N_K)} \quad b=3^{\phi(N_K)} \\
\implies N_K \mid a-b \implies \omega(a-b)\ge K
$$
(you can also take $b=1$ if you allow it).
The general bounds for $\omega(a-b)$ should be slightly better than $\log(a-b)$ (say $a>b$ to keep it simple), MathWorld gives $\omega(x)\sim \log x/\log\log x$ for primorials which is the worst case. If in general you can find a $2^n$-smooth number $a$ close to an arbitrarily large primorial $\#$ so that $b=a-\#=O(2^n)$, then you're stuck with essentially the same bounds. My guess is that something like this is possible, though I can't say for certain.
