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$.

  • $\begingroup$ What are "relative primes"? $\endgroup$
    – Igor Rivin
    Feb 20, 2011 at 19:37
  • $\begingroup$ Asterios: Numbers relatively prime to $n$? Relatively prime pairs? $\endgroup$ Feb 20, 2011 at 19:54
  • 1
    $\begingroup$ my question is about relatively primes per pairs. $\endgroup$ Feb 20, 2011 at 20:15
  • $\begingroup$ @Andres: Although my question is about co-primes to each other i do not also know the answer to the same question about relatively primes to $n$ $\endgroup$ Feb 20, 2011 at 20:22
  • 1
    $\begingroup$ By the way, for I = [200,220], I can find at most 6 numbers relatively prime to each other. Check the westzynthius question in my post to find clues to other intervals which have small sets of mutually relatively prime numbers. Gerhard "Ask Me About System Design" Paseman, 2011.02.20 $\endgroup$ Feb 20, 2011 at 22:59

2 Answers 2


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.

  • $\begingroup$ I agree that f(n) >= h(n-1). However, it may be that h(n) < j(m) where m is a number with n distinct prime factors, and j(m) is the smallest integer j such that any interval of j numbers contains at least one relatively prime to m. Thus an interval of length h(n-1) may not be long enough to ensure a subset of n mutually relatively prime integers. (It is believed, but not proven, that j(m)<=h(n) for any m with n distinct prime factors.) Gerhard "Ask Me About System Design" Paseman, 2011.02.20 $\endgroup$ Feb 21, 2011 at 5:43
  • $\begingroup$ Also, regarding the Hagedorn paper, he uses j(n) for Jacobsthal's function and h(n) for j(P_n), or j evaluated at the nth primorial. Hagedorn talks about both but focuses on h(n). Gerhard "Ask Me About System Design" Paseman, 2011.02.20 $\endgroup$ Feb 21, 2011 at 7:12
  • $\begingroup$ Yes, I defined my $h(n)$ to be the same as his $h(n)$, and as I said it is based on Jacobsthal's function. $\endgroup$ Feb 21, 2011 at 11:21
  • $\begingroup$ I note that Jacobsthal has come up on MO before: mathoverflow.net/questions/17526/… $\endgroup$ Feb 21, 2011 at 11:38
  • $\begingroup$ I found a slide presentation online which has h(24) < j(m) for m a number with 24 distinct prime factors. Work of Hajdu and Saradha resolve a problem of Recaman and progress on a generalization by Pomerance. Slide 13 of math.tifr.res.in/~vvaish/seminar/events/2011-02-04-saradha/… may be of interest. Gerhard "Ask Me About System Design" Paseman, 2011.06.10 $\endgroup$ Jun 11, 2011 at 1:54

In what follows, I will have most variables ranging over positive integers (or sets of positive integers, or even sets of sets of positive integers). Let $n \gt 1$, and consider an interval $I$ of $n$ consecutive integers $[a+1,\ldots, a+n]$. Consider the subset $L$ (depending on $I$) of $P(I)$ of $I$ intersected with maximal antichains in the integer divisibility poset (actually quasi order, but most of the time will be spent in the positive integer part, which looks like a lattice; $0 \lt -a \lt n$ may be considered later), so $M \in L$ iff 1) for all $x,y \in M$, either $x=y$ or $\gcd(x,y)=1$ and 2) for all $z \in I - M$ there is $x \in M$ with $\gcd(x,z) \gt 1$ .

Since any two consecutive positive integers are coprime, one has $\card(M) \ge 2$. If $d$ is a multiple of $\pi(n)$ primorial and $d$ happens to be in $M$, then $\card(M) \lt 4$. However, in this same interval containing $d$, we can choose a set $N$ that "looks like" ${d+1, d+2, \ldots, d+p_k}$ where $k$ is $O(\pi(n))$ and $p_j$ is the $j$th (positive) prime. Based on this example, I am confident (but can not yet prove) that a lower bound for the maximum of the cardinalities of sets in $L$ is $\pi(n/2) + 1$.

UPDATE 2011.02.23 Asterios Gantzounis has done some thinking for me. He points out that the problem I have been studying shows that any proposed lower bound of the form $\pi(qn)$ where $q$ is a positive rational number will be broken. Thus $q$ cannot be a constant, but is more likely of the form $1/(u(n)\log(n))$, where $u(n) > 1$ for sufficiently large $n$ and $u(n)$ is likely a small (compared to $\log(n)$) rational function of $\log(n)$ and iterated $\log$'s of $n$. END UPDATE 2011.02.23

Now let $I_t =\{ m \in I, m $is an integer multiple of $t\}$ For any $M \in L$, we must have $\card(M \cap I_t) \lt 2$ for any prime $t$. So an upper bound for $\card(M)$ is $\pi(n) + \rho(n)$, where $\rho(n)$ is the largest number of integers relatively prime to $P_n$ (the $n$th primorial) in any subset of shape $I$ (collection of $n$ consecutive integers).

I do not have a good expression for $\rho(n)/n$, but it is related to the product $\prod_{i \le n} (1 - 1/p_i)$. I am trying to bound this product from below by $1/2\ln(n\ln(n))$, but there are some recent oscillation results by Diamond and Pintz that make me unsure when the bound actually holds. It is related to the MathOverflow question Erik Westzynthius's cool upper bound argument: update? which I will update soon (but with results modulo oscillation, rather than absolute results).

UPDATE 2011.02.25 I have posted (as an answer to the linked question above) a new estimate to the Jacobsthal function which may apply to upper bounds to this problem and to Gerry Myerson's generalization. I invite constructive comments and polite corrections regarding this estimate. END UPDATE 2011.02.25

Gerhard "Ask Me About System Design" Paseman, 2011.02.20

  • $\begingroup$ Not being a subscriber to Journal de Théorie des Nombres de Bordeaux, I would be grateful to (willing to barter with) anyone who gave me (an English version preferably of) vol. 21 (2009), 523-533 Oscillation of Mertens' product formula, or a nice function h(n) and assurances (proof) that 1/h(n)ln(n ln(n)) is less than the nth Mertens product. Gerhard "Will Estimate For Money/Preprints" Paseman, 2011.02.20 $\endgroup$ Feb 20, 2011 at 22:18
  • $\begingroup$ PPS, I have access to Carella's refinement of Diamond and Pintz, but won't spend as much time on it unless I get trusted assurances that it is worth spending much time reviewing. Gerhard "Won't Review Much For Free" Paseman, 2011.02.20 $\endgroup$ Feb 20, 2011 at 22:21
  • $\begingroup$ @Gerhard:Is the Weszynthious article anywhere free on the internet? Thank you for the answer $\endgroup$ Feb 21, 2011 at 7:18
  • $\begingroup$ No (as far as I know), but I may be able to send you a copy of the original German article. (Especially if you can send me a copy of D. & P.'s oscillation article!) Also, after I finish my writeup to my question on this, I can provide a summary in English of much of W.'s article. Gerhard "Ask Me About System Design" Paseman, 2011.02.20 $\endgroup$ Feb 21, 2011 at 7:37
  • $\begingroup$ the theorem of westzynthious does not implie that there is not a lower bound of the form $π(an)$ where a is a positive rational? $\endgroup$ Feb 23, 2011 at 16:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.