# Weighted maximal number of disjoint singly-generated ideals in the divisibility poset for $\{1,2,\ldots,n\}$

In the mathoverflow question here the asymptotic growth of antichains in the divisibility poset ${\cal P}_n$ of the set of natural numbers $\{1,\ldots,n\}$ is considered. I have a somewhat dual question.

Consider a packing'' of disjoint singly generated ideals (upsets) ${\cal C}_x$ where $${\cal C}_x=\{x,y_1 x, y_1 y_2 x, \ldots \} \in \{1,2,\ldots,n\}$$ with $y_i$ natural numbers greater than 1. To be precise, an ideal $\cal C$ is a collection of sets such that if $A\in {\cal C}$ and $A \subset B$ we have $B \in {\cal C}$. I consider only ideals generated by a single integer $x,$ which I call ${\cal C}_x$ and I consider only the integers $\{1,\ldots,n\}$ not the whole set of natural numbers.

Thus, $x$ is the minimal element in the ideal ${\cal C}_x$ and I require that ${\cal C}_{x'}\cap {\cal C}_x=\emptyset$ whenever $x \neq x'.$ The cost of an ideal ${\cal C}_x$ is simply

$f({\cal C}_x)=1/x$

where $x$ is its minimal element. I want to find a collection of disjoint ideals ${\cal M}=\{C_{x_1},\ldots,C_{x_m}\}$ which maximizes the cost $$f({\cal M})=\sum_{i=1}^m f(C_{x_i})=\sum_{i=1}^m \frac{1}{x_i}$$ for large $n$.

Edit 1: There is a side condition to the maximization, which I forgot to write, sorry. To be able to include both $x\neq x'$ in $\cal M$ they must not divide each other in addition to their LCM being strictly greater than $n$.

Edit 2: It seems to me the condition in Edit 1 is superfluous, since if $LCM(x,x')$ is strictly larger than $n$ the condition of either of $x,x'$ not dividing the other is automatically satisfied. However, subsets of $\{1,\ldots,n\}$ where no element of the subset divides another have been investigated for a long time, under the terminology primitive sets''. So I suppose I am asking about how small can $f({\cal M})$ be, in comparison to primitive sets which achieve $f$ of $O\left(\frac{\log n}{\sqrt{\log \log n}}\right)$

An upper bound of $\lceil \frac{n+1}{2}\rceil$ is known on the size of a collection obeying this LCM condition, see this previous MO question here. However, the size maximizing sets that are easy to find are essentially mostly integers from $[n/2,n]$ and the value of $f$ they give is constant (since it is $H_n-H_{n/2}$). However, it is known that for so called primitive sets in $\{1,\ldots,n\}$ considered by Behrend, Erdos and others (sets of integers satisfying the non-divisibility conditions) the value of $f$ is proved to be asymptotically $\frac{\log n}{\sqrt{\log \log n}}$.

It seems like some pruning of primitive sets by removing their members in $[2,\sqrt{n+1})\cap \mathbb{N}$ and pruning multiples of small primes we should get a collection with cost $f$ possibly not much lower than primitive sets.

• The set up is not clear for me, sorry. Are $y_1,y_2,\dots$ fixed numbers? If yes --- are they chosen so that $C_x\cap C_{x'}=\varnothing$, or it is our constraint to choose $x_1,x_2,\dots$ so that the resulting sets are disjoint? – Ilya Bogdanov Nov 27 '15 at 6:54
• Is there a condition which ensures that the chains have a certain length? Why can't you take $C_x=\{x\}$ and obtain costs $\sim\log n$? – Jan-Christoph Schlage-Puchta Nov 27 '15 at 12:02
• @IlyaBogdanov:Thanks for your comment please see edit. – kodlu Nov 27 '15 at 23:17
• @Jan-ChristophSchlage-Puchta:Thanks, please see edit. – kodlu Nov 27 '15 at 23:18
• Is $m$ fixed? If not, why is not the answer $H_n$ for chains $C_i=\{i\}$? – Fedor Petrov Nov 28 '15 at 9:28