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

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

2011-02-20T19:32:14Z

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

Answer by Gerhard Paseman for Lower bound of the number of relatively primes(each-other) in an interval

2011-02-20T22:01:24Z

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 http://mathoverflow.net/questions/37679/erik-westzynthiuss-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

Answer by Gerry Myerson for Lower bound of the number of relatively primes(each-other) in an interval

2011-02-21T05:26:29Z

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.