Lower bound of the number of relatively primes(each-other) in an interval - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T09:32:08Z http://mathoverflow.net/feeds/question/56099 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56099/lower-bound-of-the-number-of-relatively-primeseach-other-in-an-interval Lower bound of the number of relatively primes(each-other) in an interval asterios gantzounis 2011-02-20T19:32:14Z 2011-02-28T05:36:59Z <p>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. </p> <blockquote> <p>What are the best bounds that we have?</p> <p>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$.</p> </blockquote> http://mathoverflow.net/questions/56099/lower-bound-of-the-number-of-relatively-primeseach-other-in-an-interval/56110#56110 Answer by Gerhard Paseman for Lower bound of the number of relatively primes(each-other) in an interval Gerhard Paseman 2011-02-20T22:01:24Z 2011-02-25T19:45:38Z <p>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$ .</p> <p>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$.</p> <p><B>UPDATE 2011.02.23</B> 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$. <B>END UPDATE 2011.02.23</B></p> <p>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). </p> <p>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 <a href="http://mathoverflow.net/questions/37679/erik-westzynthiuss-cool-upper-bound-argument-update" rel="nofollow">http://mathoverflow.net/questions/37679/erik-westzynthiuss-cool-upper-bound-argument-update</a> which I will update soon (but with results modulo oscillation, rather than absolute results).</p> <p><B>UPDATE 2011.02.25</B> 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. <B>END UPDATE 2011.02.25</B></p> <p>Gerhard "Ask Me About System Design" Paseman, 2011.02.20</p> http://mathoverflow.net/questions/56099/lower-bound-of-the-number-of-relatively-primeseach-other-in-an-interval/56142#56142 Answer by Gerry Myerson for Lower bound of the number of relatively primes(each-other) in an interval Gerry Myerson 2011-02-21T05:26:29Z 2011-02-21T05:26:29Z <p>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). </p> <p>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. </p> <p>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. </p> <p>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. </p>