How large can a subset of $\{1,\ldots,N\}$ be if all pairwise LCMs of its elements are lower bounded?

Question

Consider the set $\{1,2,\ldots,N\}$. Let $LCM(a,a')$ denote the lowest common multiple of the integers $a,a'.$

We say that $A\subset \{1,2,\ldots,N\}$ is $M-$good if $LCM(a,a')\geq M,$ for all $a\neq a' \in A.$

How large can the size $|A|$ be for an $M-$good set, as a function of $M,N.$ Specifically let $N\rightarrow \infty$ and $M=M(N)$ also go to infinity.

Is it possible to have, say, $M=N+1$ and $|A|\geq c N$, for some constant $c\in(0,1)$? If not, what is the order of $|A|$?

Also, how slowly must $M$ grow with $N$ to have $|A| \geq c N$, with $c \in (0,1)$?

Answer 1

You're asking for the size of a maximum independent set in the graph with vertices $\{1,2,\ldots,N\}$ and edges $(i,j)$ whenever $\text{lcm}(i,j) < M$.

I tried it in the case $M=N+1$ for $N$ up to $65$. It appears that the maximum $|A| = \lceil N/2 \rceil$, which is attained when $A = \{x: \lceil (N+1)/2 \rceil \le x \le N \}$.

Answer 2

Robert Israel's answer actually answers your first question with $c \geq 1/2$. I would only like to add that his example is actually the truth, in other words when $M=N+1$ then $c=1/2$.

Let us define a partially ordered set (poset) where $a \leq b$ if and only if $a$ divides $b$. Your $N+1$ good set must be an antichain in this poset. We can decompose this set into disjoint chains $\{x,2x,4x,8x, \ldots \}$ where $x$ is an odd number. The set $ \{ x : \lceil (N+1)/2 \rceil\ \leq x \leq N \}$ is an antichain with size equal to the number of odd numbers less than or equal to $N$. Since every antichain can have at most one element from a chain, Robert Israel's set is of optimal size.

Note that Dilworth's theorem (https://en.wikipedia.org/wiki/Dilworth%27s_theorem) guarantees that this strategy will always work when one would like to find an antichain of maximal size in a poset.