4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ilya Bogdanov Nov 27 '15 at 6:54
  • $\begingroup$ 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$? $\endgroup$ – Jan-Christoph Schlage-Puchta Nov 27 '15 at 12:02
  • $\begingroup$ @IlyaBogdanov:Thanks for your comment please see edit. $\endgroup$ – kodlu Nov 27 '15 at 23:17
  • $\begingroup$ @Jan-ChristophSchlage-Puchta:Thanks, please see edit. $\endgroup$ – kodlu Nov 27 '15 at 23:18
  • $\begingroup$ Is $m$ fixed? If not, why is not the answer $H_n$ for chains $C_i=\{i\}$? $\endgroup$ – Fedor Petrov Nov 28 '15 at 9:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.