# 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$$.

• @Arthur there are three quantifiers there (one hidden in big-O) so I don't know how to describe it in terms of quantities. Could you tell me more specifically what I should clarify? Nov 27, 2020 at 19:19
• Wait, upon a third reread, I think I have understood what you want. I need to use the sleep, apparently. Nov 27, 2020 at 19:25
• @Arthur third time's a charm :) Nov 27, 2020 at 19:26
• Can $m$ depend on $S$, or only on $n$? Nov 27, 2020 at 19:27
• @HewWolff looks right to me, although perhaps it's easier to imagine it as $\exists_{k,c} \forall_{n, S} \exists_{m\le kn} \text{[...]} |S \cap m\mathbb{Z}|\le c$ Nov 27, 2020 at 19:36

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$$
• Great, I see how it works now. I'm trying to see how close you can get to the $n\log n$ upper bound with this method. It seems that it can give $n (\log n)^{o(1)}$ for any $o(1)$ exponent. Jul 1, 2021 at 23:11
• @BartMichels are you talking about the upper bound on $m$? Jul 2, 2021 at 0:13
• Yes, the max of the minimal $m$ when $S$ varies through all subsets of $[n^2]$. Jul 2, 2021 at 7:03