23
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ @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? $\endgroup$
    – acupoftea
    Nov 27, 2020 at 19:19
  • $\begingroup$ Wait, upon a third reread, I think I have understood what you want. I need to use the sleep, apparently. $\endgroup$
    – Arthur
    Nov 27, 2020 at 19:25
  • $\begingroup$ @Arthur third time's a charm :) $\endgroup$
    – acupoftea
    Nov 27, 2020 at 19:26
  • 1
    $\begingroup$ Can $m$ depend on $S$, or only on $n$? $\endgroup$
    – Arthur
    Nov 27, 2020 at 19:27
  • 2
    $\begingroup$ @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$ $\endgroup$
    – acupoftea
    Nov 27, 2020 at 19:36

1 Answer 1

5
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jul 1, 2021 at 23:11
  • $\begingroup$ @BartMichels are you talking about the upper bound on $m$? $\endgroup$ Jul 2, 2021 at 0:13
  • $\begingroup$ Yes, the max of the minimal $m$ when $S$ varies through all subsets of $[n^2]$. $\endgroup$ Jul 2, 2021 at 7:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .