The counting version of a problem of Erdős

Abstract

A set $A$ of natural numbers possesses property ${\mathcal{P}}_h$, if there are no distinct elements $a_0,a_1,\dots ,a_h\in A$ with $a_0$ dividing the product $a_1{a}_2\dots a_h$. Erdős determined the maximum size of a subset of $\{1,\dots ,n\}$ possessing property ${\mathcal{P}}_2$. More recently, Chan, Győri and Sárközy solved the case $h=3$, finally the general case also got resolved by Chan, the maximum size is $\pi (n)+{\Theta }_h(\frac{n^{2/(h+1)}}{(\log n{)}^2})$. In this note we consider the counting version of this problem and show that the number of subsets of $\{1,\dots ,n\}$ possessing property ${\mathcal{P}}_h$ is $T(n)\cdot e^{\Theta (n^{2/3}/\log n)}$ for a certain function $T(n)\approx (3.517\dots {)}^{\pi (n)}$. For $h>2$ we prove that the number of subsets possessing property ${\mathcal{P}}_h$ is $T(n)\cdot e^{\sqrt{n}(1+o(1))}$. This is a rare example in which the order of magnitude of the lower order term in the exponent is also determined.

accepted, final version