Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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.