Logo
All Random Solved Random Open
OPEN
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}?\]

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}$: we 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}$.

See also [425].

Additional thanks to: Rishika Agrawal