The number of maximum primitive sets of integers

Abstract

A set of integers is \emph{primitive} if it does not contain an element dividing another. Denote by $f(n)$ the number of maximum-size primitive subsets of $\{1,\dots ,2n\}$. We prove that the limit $\alpha ={\lim }_{n\to \infty }f(n{)}^{1/n}$ exists. Furthermore, we present an algorithm approximating $\alpha$ with $(1+\epsilon )$ multiplicative error in $N(\epsilon )$ steps, showing in particular that $\alpha \approx 1.318$. Our algorithm can be adapted to estimate also the number of all primitive sets in $\{1,\dots ,n\}$. We address another related problem of Cameron and Erdős. They showed that the number of sets containing pairwise coprime integers in $\{1,\dots ,n\}$ is between $2^{\pi (n)}\cdot e^{(\frac{1}{2}+o(1))\sqrt{n}}$ and $2^{\pi (n)}\cdot e^{(2+o(1))\sqrt{n}}$. We show that neither of these bounds is tight: there are in fact $2^{\pi (n)}\cdot e^{(1+o(1))\sqrt{n}}$ such sets.

11 pages