We know that from prime number theorem that the number of primes below $n$ is approximately $$\frac{n}{\log_en}.$$

$\star$ Given $n,m$, what is the largest list of pairwise coprime numbers that one can come up above $n$ and below $m$? Will it be asymptotically same as number of primes or something different? In particular can we replace $\log_en$ by something smaller? If so, how much smaller?


For a given $n$, let $P\subset\{2,3\dots,n\}$ be the set of primes up to $n$, and let $S\subset\{2,3\dots,n\}$ be any subset with pairwise coprime elements. Consider the function $f:S\to P$ that assigns to any $s\in S$ its smallest prime factor $p\in P$. It is clear that $f$ is an injection, whence $|S|\leq|P|$.

In short, the set of primes up to $n$ is the largest subset of $\{2,3,\dots,n\}$ with the given property.

Added 1. Péter Komjáth kindly called my attention to a 1962 survey by Paul Erdős (in Hungarian), which discusses some related problems. In particular, Problem 4 can be solved by the argument above: if $1\leq a_1<\dots<a_k\leq n$ are such that no $a_i$ divides the product of the other $a_j$'s, then $k\leq\pi(n)$. Problems 10 and 11 are based on a 1938 paper of Erdős and some later developments. Most relevant is Problem 18 that discusses the OP's question in general intervals. He denotes by $F(n,k)$ the maximal size of a subset $S\subset\{n+1,\dots,n+k\}$ with pairwise coprime elements, and he mentions that estimating this quantity is a difficult problem. In particular, he says that he is far from solving completely the problem of determining or estimating $\max_n F(n,k)$. I am sure that digesting the vast Erdős archive would bring up many related questions and results, in particular estimates for $F(n,k)$.

Added 2. The problem of estimating $F(n,k)$ (see previous section) is discussed in more detail in this 1971 paper of Erdős. See also the relevant OEIS entry.

  • $\begingroup$ oops I meant an interval. I was looking at joro's post and forgot to update. $\endgroup$ – user76479 Sep 23 '15 at 5:38
  • $\begingroup$ Using PNT we can count number of primes between $m$ and $n$. Do we have roughly the same statistics for number of pairwise coprime numbers between $m$ and $n$ (this was what was in my mind)? $\endgroup$ – user76479 Sep 23 '15 at 5:40
  • $\begingroup$ I think from your answer it should be same. $\endgroup$ – user76479 Sep 23 '15 at 5:42
  • 1
    $\begingroup$ @GH from MO: renyi.hu/~p_erdos/1962-23.pdf $\endgroup$ – Péter Komjáth Sep 23 '15 at 6:53
  • 1
    $\begingroup$ @Arul: See my added sections. $\endgroup$ – GH from MO Sep 23 '15 at 20:06

Your Answer

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