Prime divisors of the respectively minimal binomial coefficients

Question

In view of Chebyshev's approach to prime numbers, I would like to ask about the regularities and peculiarities of the two sequences $\ \beta(n)\ $ and $\ \gamma(n),\ $ which I define as follows:

• $\ \beta(n)\ $ is the smallest integer $\ b\ $ such that $\ \binom bn\ $ has at least $\ n\ $ different prime divisors;
• $\ \gamma(n)\ $ is the smallest integer $\ c\ $ such that $\ \binom cn\ $ has at least $\ n\ $ different prime divisors $\ p\gt n$.

Of course it would be nice (but not realistic?) to compute these two sequences or give a sharp estimate. Even not so sharp bounds but with explicit scope of application like for every $\ n\ge 720\ $ (or whatever the constant) rather than for almost all... would be still interesting, I'd think, and possibly can find some applications (say, combinatorial).

The properties under the consideration can be monotonicity of the sequences $\ \beta\ $ and $\ \gamma\ $ (including the deviations from the monotonicity); also the frequency of occurrences of prime numbers as $\ \beta(n)\ $ or $\ \gamma(n)\ $ respectively. Would they be more common in $\ \gamma\ $ then in $\ \beta\,$?

Answer 1

I'll just consider the second of the two problems posed. Changing notation slightly, it asks for the least natural number $n=n(k)$ such that $(n+1)(n+2)\cdots (n+k)$ is divisible by $k$ primes all larger than $k$. First I claim that $n(k) \le Ck^{e}$ for some constant $C$. To see this note that $$ \sum_{n\le N} \sum_{p>k, p|(n+1)\cdots (n+k)} 1 = \sum_{k<p\le N} \sum_{j=1}^{k} \sum_{n\le N, p|(n+j)} 1 = \sum_{k< p \le N} k \Big( \frac{N}{p} +O(1)\Big), $$ and using $\sum_{p\le x} 1/p = \log \log x + B + O(1/\log x)$ this is $$ = kN \log \frac{\log N}{\log k} + O\Big(\frac{N}{\log k}\Big). $$ If $N >C k^e$ for some large $C$ then this exceeds $kN$, and we deduce that there is some $n \le N$ with $(n+1)\cdots (n+k)$ containing $k$ primes all larger than $k$. This easy argument may be found in Theorem 3.3 (part 3) of Erdos and Turk.

My guess would be that $n(k) \ge k^{e-\epsilon}$ for any $\epsilon >0$, but this seems difficult to show. One can see easily that $n(k) \ge c k^2$ for some small positive constant $c$. To prove this, note that if $n\le k^2-k$ then each $n+j$ (with $1\le j\le k$) can have at most one prime factor larger than $k$. So if we can show that there are integers in $[n,n+k]$ that are $k$-smooth (all prime factors below $k$) then clearly $(n+1)\cdots (n+k)$ cannot be divisible by $k$ primes larger $k$. Choose $r=\lceil \sqrt{n+k}\rceil$ and $s = \lceil \sqrt{r^2 - (n+k)}\rceil$. Then $r^2-s^2$ can be checked to be in $[n,n+k]$ (if $n\le ck^4$ for a suitable $c$), and $r^2-s^2=(r+s)(r-s)$ is clearly $(r+s)$-smooth. This shows that if $n\le ck^2$ then the interval $[n,n+k]$ will contain $k$-smooth numbers. (In fact, it shows that the interval $[x,x+cx^{1/4}]$ contains $\sqrt{x}$-smooth numbers.) Erdos and Turk (see Theorem 3.3 part 1) showed that $n(k) \ge k^{2+\delta}$ for some small $\delta>0$, and this remains the best known.

To show why the problem of getting lower bounds for $n(k)$ is difficult, let me isolate a consequence which is not yet known. If the bound $n(k) \ge k^A$ holds for all large $k$, then every interval $[x,x+x^{1/A}]$ must contain a $x^{1/A}$-smooth number. This consequence is only known for $A<2.5$; this follows from the argument involving $r^2-s^2$ given above, and was noted in a paper of Friedlander and Lagarias (which appeared in J Number Theory). So proving the expected lower bound of $n(k) \ge k^{e-\epsilon}$ would have interesting, as yet unknown, consequences.