Problem Statement
Let $F(n)$ be the maximum possible size of a subset $A\subseteq\{1,\ldots,n\}$ such that $a\nmid bc$ whenever $a,b,c\in A$ with $a\neq b$ and $a\neq c$. Is there a constant $C$ such that\[F(n)=\pi(n)+(C+o(1))n^{2/3}(\log n)^{-2}?\]
Categories:
Number Theory
Progress
Erdős [Er38] proved there exist constants $0<c_1\leq c_2$ such that\[\pi(n)+c_1n^{2/3}(\log n)^{-2}\leq F(n) \leq \pi(n)+c_2n^{2/3}(\log n)^{-2}.\]Erdős [Er69] gave a simple proof that $F(n) \leq \pi(n)+n^{2/3}$: define a graph with vertex set the union of those integers in $[1,n^{2/3}]$ with all primes $p\in (n^{2/3},n]$. We have an edge $u\sim v$ if and only if $uv\in A$. It is easy to see that every $m\leq n$ can be written as $uv$ where $u\leq n^{2/3}$ and $v$ is either prime or $\leq n^{2/3}$, and hence there are $\geq \lvert A\rvert$ many edges. This graph contains no path of length $3$ and hence must be a tree and have fewer edges than vertices, and we are done. This can be improved to give the upper bound mentioned by using a subset of integers in $[1,n^{2/3}]$.More generally, one can ask for such an asymptotic for the size of sets such that no $a\in A$ divides the product of $r$ distinct other elements of $A$, with the exponent $2/3$ replaced by $\frac{2}{r+1}$.
For further discussion and references concerning this generalisation to $r\geq 3$ see the comment by Wouter van Doorn.
See also [425].
Source: erdosproblems.com/793 | Last verified: January 16, 2026