Given a large enough integer $n\in\Bbb N$ and a real $r\in\big(0,\frac12\big]$ and $n_1\in\Bbb N_{> n}$ is the smallest integer such that $n_1=AB$ for two coprime integers $A$ bigger than but close to $\lceil n^{1-r}\rceil$ and $B$ smaller than but close to $\lfloor n^{r}\rfloor$ then is there an upper bound and average case (lower bound) estimate for $n_1-n$? Note if $n_1$ is prime then we have Cramer's conjecture for upper bound and average case bound given by prime number theorem.

I think something similar to $O((\log n)^c)$ upper bound is true (similar to Cramer's conjecture but due to coprimeness might be easier to show). Or is there an $\Omega(n^r)$ lower bound?

  • $\begingroup$ What do you mean by "smaller but close to" ? The question becomes more interesting if one requires $A \geq n^{1-r}$ and $B \geq n^r$. $\endgroup$ – js21 Oct 17 '16 at 14:02
  • $\begingroup$ why is it less interesting with $B\leq n^r$? $\endgroup$ – user94040 Oct 17 '16 at 16:23
  • $\begingroup$ the word "close" has no precise signification. By ignoring this "requirement", one can just take $B=1,A=n=n_1$. $\endgroup$ – js21 Oct 17 '16 at 16:32
  • $\begingroup$ What I meant is close to $\lfloor n^r\rfloor$. $\endgroup$ – user94040 Oct 17 '16 at 16:34

Put $B=\lfloor n^r\rfloor$, and let $n_0$ be the smallest integer larger than $n$, which is divisible by $B$. If for an integer $k$ we have $(\frac{n_0}{B}+k, B)=1$, then $n_1 = n_0+kB$ satisfies your condition. You can bound $k$ by Jacobsthal's function, by Iwaniec's estimate we get $n_1-n\ll n^r\log^2 n$.

If you rather have a better bound for $n_1-n$, and are willing to relax the bound for $B$ to $n^r/2\leq B\leq n^r$, say, you can argue as follows. Write $$ \#\{\nu\in[n, n+\Delta]:\exists p\in[n^r/2, n^r], p\mbox{ prime}\} = \sum_{p\in[n^r/2, n^r]} \left[\frac{n+\Delta}{p}\right]-\left[\frac{n}{p}\right]. $$ Now use Exponential sums and Vaughan's identity to give a lower bound for the sum over primes. Then use some combinatorial counting to show that the number of integers $\nu\in[n, n+\Delta]$, which are divisible by the square of a prime $p\in[n^r/2, n^r]$ is small.

The combinatorial part might become tricky, in case you get stuck there you could have a look at the literature dealing with the difference between squarefree numbers.

  • $\begingroup$ @Jan-ChristophSchlagePuchta So you think $O((\log n)^c)$ is not possible? $\endgroup$ – user94040 Oct 18 '16 at 14:23
  • $\begingroup$ Thank you very much. Is there an $\Omega(n^r)$ lower bound? $\endgroup$ – user94040 Oct 18 '16 at 14:25
  • $\begingroup$ $n_1=n_0+kB$ is not coprime to $B$ if $\frac{n_0}{B}\in\Bbb Z$ and so are you saying "$n_1=n_0+kB$ does not satisfy my condition". $\endgroup$ – user94040 Oct 18 '16 at 14:42
  • $\begingroup$ There are two conditions in your problem. $B$ should be close to $n^r$, and $n_1$ should be close to $n_0$. The optimal bound for $n_1-n_0$ depends on the bound for $n^r-B$, which you haven't specified. $\endgroup$ – Jan-Christoph Schlage-Puchta Oct 18 '16 at 15:04
  • $\begingroup$ Assume $n^r-B<f(n)$ for some slowly growing function $f(n)$. $\endgroup$ – user94040 Oct 18 '16 at 15:09

I will answer a question slightly different from yours. Let $a(n)$ be the smallest integer $\geq n$ such that $a(n) = b c$ with $(b,c) = 1$ and $b \geq n^r$, $c \geq n^{1-r}$. Then :

  • $a(n) - n \geq \frac{1}{2} n^{1-r}$ for infinitely many $n$.
  • $a(n) - n \ll n^{1-r} \log \log(3n)$.

The first point simply follows from the observation that the fractional part of $n^r$ is in $]0,\frac{1}{2}[$ for infinitely many $n$, so that $b \geq n^{r} + \frac{1}{2}$ in the decomposition $a(n) = bc$. Thus $a(n) = bc \geq (n^{r} + \frac{1}{2})n^{1-r} = n + \frac{1}{2} n^{1-r}. $

The second point follows from standard point-counting methods, by using the inequality $$\mathbb{1}_{(b,c)=1} \geq 1 - \sum_p \mathbb{1}_{p|b,p|c} .$$

Added : Let me expand what I meant by "standard point-counting methods". One has, for $\delta > n^{-r}$, $$ \sum_{b > n^{r}, c > n^{1-r} \\ bc \leq n(1+ \delta)} \mathbb{1}_{(b,c)=1} \geq N(n^r,n^{1-r},\delta) - \sum_p N \left( \frac{n^r}{p},\frac{n^{1-r}}{p}, \delta \right),$$ where $$ N(X,Y,\delta) = \sum_{b > X, c > Y \\ bc \leq XY(1+ \delta)} 1. $$ Now, let's assume $\delta < 1$. Then $N(X,Y,\delta) = 0$ if $X < (1+ \delta)^{-1}$ or $Y < (1+ \delta)^{-1}$. So let's assume that $X,Y \geq (1+ \delta)^{-1}$ (corresponding to $p \leq (1+\delta) n^r)$ above). Now, $$ N(X,Y,\delta) = \sum_{X < b \leq X(1 + \delta)} \left( \sum_{Y < c \leq \frac{XY(1+\delta)}{b}} 1\right) \\ = \sum_{X < b \leq X(1 + \delta)} \left( \frac{XY(1+\delta)}{b} - Y + O(1) \right) \\ = f(\delta) XY + O(1 + \delta X + \delta Y), $$ where $f(\delta) = (1 + \delta) \log(1+\delta) - \delta$. This implies $$N(n^r,n^{1-r},\delta) - \sum_{p \leq \delta n^{\frac{1}{2}}} N \left( \frac{n^r}{p},\frac{n^{1-r}}{p}, \delta \right) \geq c f(\delta) n + O(\delta n^{1-r} \log \log(3n)),$$ where $c = 1 - \sum_{p} p^{-2}$ is a positive constant. For $p > \delta n^{\frac{1}{2}}$, the quantity $N \left( \frac{n^r}{p},\frac{n^{1-r}}{p}, \delta \right)$ counts at most one $b$, and there are $\ll n^{\frac{1}{2} - r}$ choices for $c$, hence $$ N \left( \frac{n^r}{p},\frac{n^{1-r}}{p}, \delta \right) \ll n^{\frac{1}{2} - r} \sum_{n^r<bp\leq n^r(1+\delta)} 1. $$ Setting $k = pb$, we get $$ \sum_{p > \delta n^{\frac{1}{2}}} N \left( \frac{n^r}{p},\frac{n^{1-r}}{p}, \delta \right) \ll n^{\frac{1}{2} - r} \sum_{n^r<k\leq n^r(1+\delta)} \omega(k) \ll \delta n^{\frac{1}{2}} \log(3n) $$ Using that $f(\delta) \asymp \delta^2$, one gets the result with $\delta = Cn^{-r} \log \log(3n)$, the constant $C$ being chosen large enough.

  • $\begingroup$ @js2682 Is there a $n^{1-r+\epsilon}$ lower bound? $\endgroup$ – user94040 Oct 17 '16 at 16:21
  • $\begingroup$ ....for average case? and could you elaborate the std pc methods? $\endgroup$ – user94040 Oct 17 '16 at 16:22
  • $\begingroup$ There is no such lower bound since I just proved a smaller upper bound ! $\endgroup$ – js21 Oct 17 '16 at 16:30
  • $\begingroup$ well I am sorry for notations. what I meant is "is there a $n^{1-r}f(n)$ lower bound for average case?". $\endgroup$ – user94040 Oct 17 '16 at 16:32
  • $\begingroup$ Thank you I will provide my thoughts on upper bound as well. $\endgroup$ – user94040 Oct 17 '16 at 18:21

Your Answer

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