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

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.

kodlu
  • 10.4k
  • 2
  • 36
  • 55