The number of maximum primitive sets of integers

Source abstract

Abstract A set of integers is primitive if it does not contain an element dividing another. Let f ( n ) denote the number of maximum-size primitive subsets of {1,…,2 n }. We prove that the limit α = lim n→∞ f ( n ) 1/ n exists. Furthermore, we present an algorithm approximating α with (1 + ε ) multiplicative error in N ( ε ) steps, showing in particular that α ≈ 1.318. Our algorithm can be adapted to estimate the number of all primitive sets in {1,…, n } as well. We address another related problem of Cameron and Erdős. They showed that the number of sets containing pairwise coprime integers in {1,… n } is between ${2^{\pi (n)}} \cdot {e^{(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.