Is there always an $O(n)$ number dividing only $O(1)$ among a set of $n$ numbers $\le n^2$?

Solution 1:

No. Let $g(n) = \log\log\log\log n$. Let $f(n) = \log\log n$.

We construct $S \subseteq [n\log n]$ with $|S| = n$ and each $m \le ng(n)$ dividing at least $g(n)$ elements of $S$. The construction is flexible to the exact choice of parameters.

Fix $n \ge 1$ large. Let $P = \prod_{g(n) < p < f(n)+g(n)} p$, the product being over primes. Let $B = \{m \le ng(n) : (m,P) = 1\}$. We define $$S := \{jP : 1 \le j \le n/2\} \cup \{jb : b \in B, 1 \le j \le g(n)\}.$$ Standard estimates imply $$|P| \le \exp\Big((1+o(1))\left((f(n)+g(n))-f(n)\right)\Big) = (1+o(1))\log n$$ and $$|B| \le ng(n)\frac{\log g(n)}{\log f(n)}.$$ Since $|P| \le 2\log n$ and $ng(n)^2 < nf(n)$, we have have $S \subseteq [n\log n]$. And we have $$|S| \le \frac{n}{2}+|B|g(n) \le n,$$ since $g(n)^2\log g(n) = o(\log f(n))$ (if you want $|S| = n$, just add $n-|S|$ arbitrary things less than $n\log n$ to $S$). Now take $m \le ng(n)$. If $m \in B$, then clearly $m$ divides at least $g(n)$ elements of $S$. Otherwise, there is some prime $p > g(n)$ so that $p \mid m$. Therefore, $m \mid (\frac{m}{p}j')P$ for $1 \le j' \le g(n)$ shows $m$ divides at least $g(n)$ elements of $S$. We're done. $\square$

Solution 2:

Here's a thought that may help someone else to make progress.

Take $c \geq 0$ and $m \geq 1$, and assume that there exists $S$ such that every integer $k < m$ is at least $c+1$ times a divisor of an element of $S$. The question asks to show that when $c$ is sufficiently large, one must have $m = O(n)$.

The assumption can be reformulated by saying that for every $f : \{1, \ldots, n^2 \} \to \mathbb R_{\geq 0}$ one has $$ \sum_{k \leq m} f(k) \leq \frac1{c+1} \sum_{s \in S} \sum_{d \mid s} f(d) \,.$$ One can then try to optimize a choice of $f$ that gives the best bound on $m$. Taking $f$ constant gives the trivial bound that $$\begin{align*} m &\ll n \cdot \text{ the maximal order of the divisor function at } n^2 \\ & \ll n \cdot \exp(C \log n / \log \log n) \end{align*}$$ for some $C > 0$.

Presumably a good choice of $f$ would take into account arithmetical information about $S$.