论文标题
ERDS问题的计数版本
The counting version of a problem of Erdős
论文作者
论文摘要
一组$ a $的自然数字拥有属性$ \ mathcal {p} _h $，如果没有不同的元素$ a_0，a_1，\ dots，a_h \ in a $ a_0 $，将产品$ a_1a_2 \ dots a_h dots a_h a_h $。 ERDS确定了$ \ {1，\ ldots，n \} $具有属性$ \ Mathcal {p} _2 $的最大大小。最近，Chan，Győri和Sárközy解决了该案例$ H = 3 $，最后也通过Chan解决了总体情况，最大尺寸为$π（n）+θ_H（\ frac {n^{2/（h+1）}}}}}}} {（\ log n）^2}^{2}}}}}}}} {（\ log n）^}}}}）$。 在此注释中，我们考虑了此问题的计数版本，并表明$ \ {1，\ ldots，n \} $具有属性$ \ MATHCAL {p} _H $是$ t（n）\ cdot e^{θ（n） （3.517 \ dots）^{π（n）} $。对于$ h> 2 $，我们证明拥有属性$ \ Mathcal {p} _h $的子集数为$ t（n）\ cdot e^{\ sqrt {n}（1+o（1+o（1））} $。 这是一个罕见的例子，其中还确定了指数中低阶项的数量级。
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_1a_2\dots a_h$. Erdős determined the maximum size of a subset of $\{1,\ldots, 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 $π(n)+Θ_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,\ldots, n\}$ possessing property $\mathcal{P}_h$ is $T(n)\cdot e^{Θ(n^{2/3}/\log n)}$ for a certain function $T(n)\approx (3.517\dots)^{π(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.
