3
$\begingroup$

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 \begin{equation} \tfrac1n\,\ln p_n\to f(a,b)\tag{1} \end{equation} 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).

$\endgroup$
  • 1
    $\begingroup$ @AnthonyQuas : How will Stirling's formula account for the cancellations? Please review the definition of $p_n$ and $q_n$. $\endgroup$ – Iosif Pinelis Mar 8 '17 at 16:28
  • $\begingroup$ Sorry. I missed that. $\endgroup$ – Anthony Quas Mar 8 '17 at 17:31
  • $\begingroup$ @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$. $\endgroup$ – Iosif Pinelis Mar 8 '17 at 18:01
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Iosif Pinelis Mar 9 '17 at 4:06
  • $\begingroup$ 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. $\endgroup$ – Lucia Mar 9 '17 at 4:27
  • $\begingroup$ 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$. $\endgroup$ – Iosif Pinelis Mar 9 '17 at 5:16
  • $\begingroup$ 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$. $\endgroup$ – Iosif Pinelis Mar 9 '17 at 6:24
  • $\begingroup$ 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? $\endgroup$ – Pavel Kozlov Mar 9 '17 at 16:31
0
$\begingroup$

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})$$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Iosif Pinelis Mar 8 '17 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.