[Math] Lower bound of the number of relatively primes(each-other) in an interval

nt.number-theoryprime numbers

I am trying to find lower and upper bounds for the number of integers that are coprime in pairs in an interval of length n.

What are the best bounds that we have?

Is that true that in any interval of length $n$ there is a set with at least $π(n)$ integers that are relatively prime to each other? Here $π(n)$ is the number of primes less or equal to $n$.

Best Answer

Let's turn the question around and let $f(n)$ be the number of consecutive integers required to guarantee that $n$ of them are pairwise relatively prime. E.g., $f(4)=6$ because you can find a set of 5 consecutive integers no 4 of which are pairwise relatively prime ($\lbrace2,3,4,5,6\rbrace$ will do) but given any set of 6 consecutive integers there must be 4 that are relatively prime (the three odd ones are pairwise relatively prime, and there will be an even that's not a multiple of 3 or 5, and it will be relatively prime to each of the odds).

I think that $f(n)=h(n-1)$, where $h(n)$ is (based on) the Jacobsthal function: $h(n)$ is the number of consecutive integers required to guarantee that one of them will not be a multiple of any of the first $n$ primes. E.g., $h(3)=6$ because you can find a set of 5 consecutive integers each of which is divisible by (at least) one of 2, 3, or 5 ($\lbrace2,3,4,5,6\rbrace$ will do) but given 6 consecutive integers only 3 can be even, and of the three odds, only one can be a multiple of 3, and only one can be a multiple of 5.

Now, why should $f(n)=h(n-1)$? Well, if you have $n$ pairwise coprime integers, it must be the case that (at least) one is not divisible by any of the first $n-1$ primes, for if each of your $n$ integers is divisible by one (or more) of the first $n-1$ primes, then two of them must be divisible by the same prime, hence, not relatively prime. Thus, $f(n)\ge h(n-1)$. I can't quite see my way through a proof that $h(n)\ge f(n+1)$, so there's still some work to be done here.

Anyway, the point is, lots of work has been done on the Jacobsthal function, including estimates. A good reference is Thomas R Hagedorn, Computation of Jacobsthal's function $h(n)$ for $n\lt50$, Math Comp 78 (2009) 1073-1087. As the title indicates, the paper is mostly concerned with computing Jacobsthal's function, but the author does summarize the history and gives many references.

Related Question