Is there always an $O(n)$ number dividing only $O(1)$ among a set of $n$ numbers $\le n^2$? Let $n\in\mathbb{N}$, $S\subseteq\mathbb{N}_{\le n^2}$, $|S|=n$. Is there always an $m=O(n)$ dividing only $O(1)$ numbers from $S$?
Since the question wasn't clear to some people, here's a version with no weird big-$O$: are there $k,c\in\mathbb{N}$ such that for every $n\in\mathbb{N}$ and every set $S$ of $n$ natural numbers all of which are $\le n^2$, there exists an $m\in\mathbb{N}$ such that $m≤kn$ and the number of multiples of $m$ that are in $S$ is $\le c$?
I'm also interested in the $c=0$ case.
If it helps anyone I've done some empirical testing for the $c=0$ case. The first column is $n$, the second is the maximum of smallest possible $m$ over all suitable $S$, and the third is the ratio $m/n$.
2 5 2.5 
3 7 2.33333 
4 9 2.25 
5 13 2.6 
6 17 2.83333 
7 19 2.71429 
8 23 2.875 

It's a bit late (sorry) but there will be no better time than now to explain the motivation. It is to obtain a tight asymptotic bound on a function related to the separating words problem in automata theory. Here you can find the definition and my $\Omega(n^{1/2})$ lower bound. A positive answer would imply that this bound is tight by improving the analysis in Lemma 3 of Robson's "Separating strings with small automata" (if $c>0$ then just join the automata). If you're interested in tight-bounding this function you can also assume that the distance between any two numbers in $S$ is at least $n$, but I thought that "$|S|=n$" was neater. The most significant thing here for people trying to solve I think is that, well, I don't really follow the paper after section 2 but primes seem to only come up in similar contexts so it might be that a positive answer would easily imply an improvement on Robson's bound on separating words (by taking off the $log^{3/5}n$, which maybe "only comes from" this number-theoretic question), a problem that was open in the years 1989-2020 (finally solved by Chase) and famous during some of them.
The best upper bound for $m$ that I know is $O(n \log n)$, from the aforementioned Lemma 3. Consider prime numbers greater than $n$, each number in $S$ can be divisible by at most two of them. Therefore $m$ can be some prime number between $n$ and the prime number $2n$ primes after $n$, the latter of which is $O(n \log n)$ by the prime number theorem.
I don't know where this should go but I think I've proven that the general case implies the $c=0$ case. Assume that $c=c_g,k=k_g$ works, then we'll prove that $c=0,k=c_g k_g$ works. Take some $n_0,S_0$ then take the appropriate $m$ for $c=c_g,k=k_g,n=c_g n_0,S=\{xi \mid x\in S_0, 1\le i\le c_g\}$. This $m$ is $\le k_g c_g n_0$ and does not divide any number in $S_0$.
 A: 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$
