Problem #856: Let $k\geq 3$ and $f_k(N)$ be the maximum value of...

---

Progress

Erdős [Er70] notes that\[f_k(N) \ll \frac{\log N}{\log\log N}.\]Indeed, let $A$ be such a set. This in particular implies that, for every $t$, there are $<k$ solutions to $t=ap$ with $a\in A$ and $p$ prime, whence\[\sum_{n\in A}\frac{1}{n}\sum_{p<N}\frac{1}{p}< k \sum_{t<N^2}\frac{1}{t} \ll \log N,\]and the bound follows since $\sum_{p<N}\frac{1}{p}\gg \log\log N$.

Improved bounds have been given by Tang and Zhang [TaZh25b], who proved bounds of the shape\[(\log N)^{b_k-o(1)}\leq f_k(N)\leq (\log N)^{c_k+o(1)}\]for some constants $0<b_k\leq c_k\leq 1$, and in particular\[(\log N)^{0.438}\leq f_3(N)\leq (\log N)^{0.889},\]say, for all large $N$. The exponents here are related to progress in the sunflower conjecture [857], to which this problem is closely related. For example, the exponents $c_k$ are $<1$ (and so the upper bound above is non-trivial) if and only if [857] holds for $k$-sunflowers.

The analogous question with natural density in place of logarithmic density (that is, we measure $\lvert A\rvert$ in place of $\sum_{n\in A}\frac{1}{n}$) is the subject of [536]. In particular Erdős [Er70] has constructed $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert \gg N$ where no four have the same pairwise least common multiple, and hence the interest of the natural density problem is the $k=3$ case.

A related combinatorial problem is asked at [857].