Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 M\subset\mathbb N$ we can construct an example $\mathcal E(m)$ having the required properties. Moreover, for each $n\ge 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}}2\left(1+O\left(\frac 1{\ln n}\right)\right)$ as follows. We can easily prove that $E(n)\le\frac{n+n\sqrt{4n-3}}4$. We can obtain, using projective planes over finite fields, that $E(n)\ge\frac{(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 $n\ge 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 $n\ge 2$ there exists a prime number $p\in\left[n-\frac {6n}{\ln n};n\right]$. 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-d\le p\le n$ and $n'-d\le 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 there is a prime between, roughly, $n$ and something like $n-\sqrt n$ (by the way, which 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 $l\ge p_1 p_2\dots p_{k(l)}$ instead of $l\ge 2\times 2\times\dots 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-d\le p\le n$ and $n'-d\le p'\le n'$.



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

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

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.