# Asymptotics for the number of digits of the ratio of binomial coefficients

Let $a$ and $b$ be distinct positive real numbers. Let $(a_n)$ and $(b_n)$ be sequences of natural numbers such that $a_n\sim an$ and $b_n\sim bn$. All the limit relations here are for $n\to\infty$. Let $p_n$ and $q_n$ be the coprime natural numbers such \begin{equation*} \frac{p_n}{q_n}=\frac{a_n^{(n)}}{b_n^{(n)}}\left[=\binom{a_n+n-1}n\Big/\binom{b_n+n-1}n\right], \end{equation*} where $x^{(n)}:=x(x+1)\dots(x+n-1)$ is the Pochhammer rising factorial.

It then appears that $$\tfrac1n\,\ln p_n\to f(a,b)\tag{1}$$ for some positive real function $f$ and any distinct positive real numbers $a$ and $b$. (Here, in view of an immediate cancellation, such as $\frac{2\cdot3\cdot4}{3\cdot4\cdot5}=\frac25$, without loss of generality $a+1\le b$.)
This may be not hard to prove, using the prime number theorem (or maybe some refinement of it) together maybe with summation by parts.

Some easy remarks added: By Stirling's formula, $\tfrac1n\,\ln a_n^{(n)}\sim\ln n\to\infty$. However, because of the cancellations, $\frac1n\,\ln p_n$ seems likely to have a finite limit. Anyway, $\limsup_n \frac1n\,\ln p_n\le(a+1)\ln 2<\infty$, since $p_n\le\binom{a_n+n-1}n\le2^{a_n+n-1}=2^{(a+1+o(1))n}$.

However, $(1)$ may be well known. In such a case, it would be good to have a reference. Otherwise, it would be good to have a hopefully short and efficient proof, preferably with an explicit expression for $f(a,b)$. The case when $a$ and $b$ are natural numbers would be enough for my current needs (which arose in some work in approximation theory/numerical analysis).

• @AnthonyQuas : How will Stirling's formula account for the cancellations? Please review the definition of $p_n$ and $q_n$. Mar 8, 2017 at 16:28
• Sorry. I missed that. Mar 8, 2017 at 17:31
• @ZachTeitler : The limit of this sequence is easy to find by Stirling's formula -- it is $\infty$. However, because of the cancellations, $\frac1n\,\ln p_n$ seems likely to have a finite limit. Anyway, it is easy to see that $\limsup_n \frac1n\,\ln p_n\le(a+1)\ln 2<\infty$. Mar 8, 2017 at 18:01

So here is an answer, edited first from an unproved guess at the correct $f(a,b)$ and then a terse proof. The following version has a few more details added.

I claim that $$f(a,b)=\int_0^{b+1} \left(\left\lfloor \frac{a+1}x\right\rfloor -\left\lfloor\frac ax\right\rfloor -\left\lfloor\frac{b+1}x\right\rfloor +\left\lfloor\frac bx\right\rfloor\right)^+\,dx.$$

This is derived from the exact expression: $$\log p_n=\sum_p\left(\sum_{k=1}^\infty \left(\left\lfloor \frac{a_n+n-1}{p^k}\right\rfloor -\left\lfloor \frac{a_n-1}{p^k}\right\rfloor- \left\lfloor \frac{b_n+n-1}{p^k}\right\rfloor +\left\lfloor \frac{b_n-1}{p^k}\right\rfloor\right)\log p \right)^+$$

Firstly from the exact expression, I claim that the contribution of those primes less than $n^{2/3}$ is at most $n^{2/3}\log n$, so that it suffices to consider only those primes in the range $[n^{2/3},(b+2)n]$. To see this, first notice that for each $p$ and $k$, the expression in the inner parentheses takes only values 0 and $\pm 1$. Also each $p$ only makes a contribution for powers up to $\log n/\log p$, so the maximum contribution from any $p$ is $O((\log n/\log p)\times \log p)=O(\log n)$. Hence the upper bound for the combined contribution for $p<n^{2/3}$. For larger primes, clearly only the first power matters.

Let $$S_n=\sum_{p<(b+2)n}\left(\left(\left\lfloor \frac{a_n+n-1}{p}\right\rfloor -\left\lfloor \frac{a_n-1}{p}\right\rfloor- \left\lfloor \frac{b_n+n-1}{p}\right\rfloor +\left\lfloor \frac{b_n-1}{p}\right\rfloor\right)\log p \right)^+,$$ so that by the above, $\log p_n=S_n+o(n)$.

Now for $\epsilon>0$, define three functions: \begin{align*} \bar g(x)&= \min\left(\max\left(\left\lfloor \frac{a+1+\epsilon}x\right\rfloor -\left\lfloor\frac{a-\epsilon}x\right\rfloor -\left\lfloor\frac{b+1-\epsilon}x\right\rfloor +\left\lfloor\frac{b+\epsilon}x\right\rfloor,0\right),1\right)\\ g(x)&= \min\left(\max\left(\left\lfloor \frac{a+1}x\right\rfloor -\left\lfloor\frac{a}x\right\rfloor -\left\lfloor\frac{b+1}x\right\rfloor +\left\lfloor\frac{b}x\right\rfloor,0\right),1\right)\\ \underline g(x)&= \min\left(\max\left(\left\lfloor \frac{a+1-\epsilon}x\right\rfloor -\left\lfloor\frac{a+\epsilon}x\right\rfloor -\left\lfloor\frac{b+1+\epsilon}x\right\rfloor +\left\lfloor\frac{b-\epsilon}x\right\rfloor,0\right),1\right)\\ \end{align*}

For all large $n$, we have $(a-\epsilon)n<a_n<(a+\epsilon)n$ and $(b-\epsilon)<b_n<(b+\epsilon)n$. For any such $n$, the $p$ summand in $S_n$ is between $\underline g(p/n)$ and $\bar g(p/n)$.

I next claim that $\int_0^{b+2} (\bar g-\underline g)=O(\epsilon\log(1/\epsilon))$. To see this, notice that if $x>2\epsilon$, $\lfloor \frac{c+\epsilon}x\rfloor$ and $\lfloor \frac{c-\epsilon}x\rfloor$ differ by at most 1, and they differ if $x\in \big((c-\epsilon)/n,(c+\epsilon)/n\big]$ for some $n$. The measure of the set where they differ is therefore $O(\epsilon\log(1/\epsilon))$, which proves the claim.

Now let $\underline h$ and $\bar h$ be continuous functions such that $\underline h\le \underline g\le \bar g\le\bar h$ and $\int_0^{b+2}(\bar h-\underline h) \le 2\int_0^{b+2}(\bar g-\underline g)$.

For large $n$, we now have $$\sum_{p<(b+2)n}\underline h(p/n)\log p \le S_n \le \sum_{p<(b+2)n}\bar h(p/n)\log p.$$

An equivalent formulation of the prime number theorem is that $\frac 1n\sum_{p<(b+2)n}\log p\,\delta_{p/n}$ converges in the weak topology to Lebesgue measure restricted to $[0,b+2]$. (This is a consequence of the fact that $\sum_{p<n}\log p=n+o(n)$).

Hence $S_n-n\int_0^{b+2}g=o(n)$, as required.

• There are pretty good, but not quite good, matches.The integral seems to converge slowly, and also the convergence in (1) does not seem fast. I think approximations to the $k$th prime presented e.g. in bit.ly/2mnFE6r (in particular, Cipolla's formula) may be useful here. Mar 9, 2017 at 4:06
• This looks like a fine answer to me; and it won't be too bad to justify using the prime number theorem and partial summation. Mar 9, 2017 at 4:27
• Better matches are obtained if the integration variable is changed from $t$ to $1/t$ (and then still numerical integration is used). The integral can also be expressed as a quadruple sum over some complicated subset of $\mathbb Z^4$. Mar 9, 2017 at 5:16
• The main difficulty seems to count accurately enough the number of multiples of a prime $p$ between $a_n$ and $a_n+n−1$ for large $p$, in particular for $p$ comparable with $n$. Mar 9, 2017 at 6:24
• Iosif, it seems you need to know not only distribution of primes in positive integer but in positive integer arithmetic progressions with difference $p$ too, am I right? Mar 9, 2017 at 16:31

This is only a partial solution. Write $\log(a_{n}^n)=n\log(a_{n})+\sum_{i=1}^{n-1}\log(1+\frac{i}{a_{n}})$.

For the first term, we have $\log(a_{n})=\log(a)+\log(n)+o(1)$.

For the second term, we have the following
$$a_{n}\int_{0}^{\frac{n-1}{a_{n}}}\log(1+x)dx\leq \sum_{i=1}^{n-1}\log(1+\frac{i}{a_{n}})\leq a_{n}\int_{\frac{1}{a_{n}}}^{\frac{n}{a_{n}}}\log(1+x)dx$$ Computations shows that both sides are equivalent to $$n(a+1)(\log(1+\frac{1}{a})-1)$$ Hence, $\log(a_{n}^n)=n\log(n) +n\left(\log(a)+(a+1)(\log(1+\frac{1}{a})-1)\right)$. Idem for $b_{n}^{n}$

So that $\frac{1}{n}\log(a_{n}^n)$ does not converge...

However, $\frac{1}{n}(\log(a_{n}^n)-\log(b_{n}^n))$ converges to $$\tilde{f}(a,b)= \log(\frac{a}{b})+b-a+(a+1)\log(1+\frac{1}{a})-(b+1)\log(1+\frac{1}{b})$$

• Using Stirling's formula, it is indeed easy to see that $\frac{1}{n}(\log(a_{n}^n)-\log(b_{n}^n))$ converges to $(a+1)\ln\frac{a+1}e-(b+1)\ln\frac{b+1}e$. However, this is not what the problem is about. Please review the definition of $p_n$ and $q_n$. Mar 8, 2017 at 18:24