Skip to main content
6 of 6
replaced http://mathoverflow.net/ with https://mathoverflow.net/

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

Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63