# Lower bound of the number of relatively primes(each-other) in an interval

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

• What are "relative primes"? – Igor Rivin Feb 20 '11 at 19:37
• Asterios: Numbers relatively prime to $n$? Relatively prime pairs? – Andrés E. Caicedo Feb 20 '11 at 19:54
• my question is about relatively primes per pairs. – Asterios Gkantzounis Feb 20 '11 at 20:15
• @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$ – Asterios Gkantzounis Feb 20 '11 at 20:22
• 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 – Gerhard Paseman Feb 20 '11 at 22:59

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.

• 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 – Gerhard Paseman Feb 21 '11 at 5:43
• 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 – Gerhard Paseman Feb 21 '11 at 7:12
• 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. – Gerry Myerson Feb 21 '11 at 11:21
• I note that Jacobsthal has come up on MO before: mathoverflow.net/questions/17526/… – Gerry Myerson Feb 21 '11 at 11:38
• 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 – Gerhard Paseman Jun 11 '11 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

• the theorem of westzynthious does not implie that there is not a lower bound of the form $π(an)$ where a is a positive rational? – Asterios Gkantzounis Feb 23 '11 at 16:48