Htykuut

When we are working, for instance, in combinatorics or graph theory, sometimes we can have the following situation. For each number $m$ from an infinite set $mathbb Msubsetmathbb N$ we can construct an example $mathcal E(m)$ having the required properties. Moreover, for each $nge m$ we can use the example $mathcal E(m)$ for the construction of the example $mathcal E(n)$ having properties similar to these of $mathcal E(m)$. If we wish to obtain the respective asymptotic bound for $E(n)$ for all natural $n$, we encounter a problem to asymptotically estimate the approximation from below of the natural number $n$ by a number $m$ from the set $mathbb M$.

For instance, in my old and small work "On graphs without 4-cycles" I investigated the problem posed by Erich Friedman here: what is the maximal number $E(n)$ of edges an $n$-vertex graph without 4-cycles? I found the asymptotics $E(n)=frac{n^{3/2}}2left(1+Oleft(frac 1{ln n}right)right)$ as follows. We can easily prove that $E(n)lefrac{n+nsqrt{4n-3}}4$. We can obtain, using projective planes over finite fields, that $E(n)gefrac{(n-1)(sqrt{4n-3}+1)}4-1$ provided $n=q^2+q+1$ where $q$ is a power of a prime. Then, using Rosser's bounds [Ros] $frac n{ln n+2}<pi(n)<frac n{ln n-4}$ for $nge 55$, where $pi(n)$ is the quantity of prime numbers which are not greater than $n$, I was able to show that for every natural $nge 2$ there exists a prime number $pinleft[n-frac {6n}{ln n};nright]$. I finally obtained the asymptotics for $E(n)$ from the above results.

At the last week I met my old coauthor, Oleg Verbitsky who proposed me the following problem. Let $n$ be a natural number. What is the minimal number $d=d(n)$ such that for each number $n'ge n$ there exist coprime natural numbers $p,p'$ such that $n-dle ple n$ and $n'-dle p'le n'$?
In his research where the question appeared, it is well enough that $d(n)=o(n)$, hence Oleg do not need any specific bound for $d(n)$. However, he thinks that the function $d(n)$ is of independent interest.

To obtain the upper bound for $d(n)$, Oleg simply took a largest prime number not greater than $n$ (my number intuition immediately said that this bound should be too weak), and using the result by Baker, Harman and Pintz [BHP], saying that for sufficiently large $n$ there is a prime belonging to $[n-n^{0.525}, n]$ (by the way, this bound is asymptotically better than my above bound $n-frac {6n}{ln n}$), he obtained the bound $d(n)=o(n)$. But both of us are not number theorists, so my efforts to improve the bound may be an invention of a bicycle. So we decided that it is better to pose the question here. As usually, we are interested mainly in asymptotics of the function $d(n)$.

What have I tried? I expect that $d(n)$ is asymptotically very small (but not an independent on $m$ constant). I have the following evidence for this.

Let $k(l)$ be a number of different prime divisors of a number $l$. Then $k(l)le log_2 l$ and this bound can be (essentially) improved using the inequality $lge p_1 p_2dots p_{k(l)}$ instead of $lge 2times 2timesdots 2$ ($k(l)$ times), where $p_i$ is the $i$-th prime number (that is $p_1=2$, $p_2=3$ and so forth). Moreover, slightly decreasing $n$ to $m$ we should obtain $k(m)$ even essentially smaller than $k(n)$. For finding such a number $m$ we can use (the above) results on the prime numbers density.

So, let ${q_1,dots, q_{k(m)}}$ be the set of all prime divisors of the number $m$. Then among $d+1$ numbers $n', n'-1,dots n'-d$ about $(d+1)(1-q_1)ge (d+1)(1-p_1)$ are not divisible by $q_1$. Among these numbers about $(d+1)(1-q_1)(1-q_2)ge (d+1)(1-p_1)(1-p_2)$ are not divisible by $q_2$ and so on. Therefore if $(d(n)+1)(1-p_1)(1-p_2)dots (1-p_{k(m)})>1$ (which can be assured by a respectively small $d(n)$) then there should exist a coprime pair $p,p'$ such that $n-dle ple n$ and $n'-dle p'le n'$.

Thanks.

References

[BHP] R. Baker, G. Harman, J. Pintz, The difference between consecutive primes. II.
Proc. Lond. Math. Soc., (3) Ser. 83 (2001) 532-562.

[Ros] B. Rosser, Proc. London Math. Soc, 1939, v.45(2), p. 21-44.