The counting version of a problem of Erdős (Q2225400): Difference between revisions
From MaRDI portal
Latest revision as of 12:25, 24 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The counting version of a problem of Erdős |
scientific article |
Statements
The counting version of a problem of Erdős (English)
0 references
8 February 2021
0 references
Let the function \(\pi(n)\) denote the number of primes up to \(n\). For a positive integer \(h\), a set of positive integers \(A\) is said to have to property \(\mathcal{P}_h\), if for distinct \(a_0,a_1,a_2,\ldots,a_h\) elements of \(A\), the product \(a_1a_2\cdots a_h\) is never a multiple of \(a_0\). \textit{P. Erdős} [Mitt. Forsch.-Inst. Math. Mech. Univ. Tomsk 2, 74--82 (1938; Zbl 0020.00504)] determined the the maximum of \(|A|\) for \(A\subseteq \{1,2,\ldots,n\}\) with property \(\mathcal{P}_2\) as \(\pi(n)+ \Theta( \frac{n^{2/3}}{(\log n)^2})\). Analogous results have been obtained for the \(\mathcal{P}_h\). The paper under review investigates function \(H_h(n)\), which counts the sets \(A\subseteq \{1,2,\ldots,n\}\) with property \(\mathcal{P}_h\). With a function \(T(n)\) defined explicitly in terms of the sequence primes, \(H_2(n)=T_n \exp(\theta(\frac{n^{2/3}}{(\log n)^2}))\), and for \(h\geq 3\),\( H_h(n)=T_n \exp(\sqrt{n} \pm \Theta(\sqrt{n} \log \log n/\log n)).\)
0 references
problem of Erdős on integers
0 references
multiplicative basis
0 references
enumeration of primitive sets
0 references
enumeration of multiplicative Sidon sets
0 references
0 references