MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is the following true?

For any $c\in (0,1)$ there exists $f(c)>0$ such that for any subset $A\subset \{1,2,\dots,n\}$ of cardinality $|A|\geq cn$, the set $$B=\left\{ k \in \{1,2,\dots,n!\} \colon \text{ there is } a \in A \text{ that divides } k\right\}$$ of numbers having at least one divisor in $A$ satisfies $$|B|\geq f(c) n!.$$

Of course, $n!$ may be replaced to the any common multiple of elements of $A$, or we may ask about densities or probabilities.

I do not know the answer even for $A=\{ cn\ $consecutive integers$\}$

share|cite|improve this question
This is an interesting question indeed. Thank you for sharing it, I look forward to seeing the responses. – Tyler Clark Nov 20 '10 at 14:50
The worst sets I can think of are those of large smooth numbers. What is the probability that a large number have no $n$-smooth factor of size in $[n/2,n]$? It's definitely positive, and probably greater than $e^{-\gamma}$ by my calculations, but I can't see if it approaches 1. If it does, the answer is probably no, and if it doesn't, the answer is probably yes. (The reasoning for large smooth numbers is that the sets which are bad for us are those that the probabilities $(P(a|m))_{a\in A}$ are very dependent, i.e. LCM(A) is relatively small) – Dror Speiser Nov 20 '10 at 17:36
Edit: "no $n^{u}$-smooth factor, where $\rho (u)=c$, $\rho$ being Dickman's function of size ...". – Dror Speiser Nov 20 '10 at 19:00
up vote 3 down vote accepted

The asymptotic version is certainly false. Let $\varepsilon (x,y)$ be the density of numbers having a divisor in the interval $[x,y]$, then Besicovitch proved in "On the density of certain sequences of integers" that $$\liminf_{x\to \infty} \varepsilon (x,2x)=0.$$ Later, Erdos improved this to $$\varepsilon(x,2x)\sim(\log x)^{-\delta +o(1)} , \delta \approx 0.086.$$ Denoting $H(x,y,z)$ to be the number of elements in $\{1,2,\dots,x\}$ which have a divisor in the interval $[y,z]$, some sharper estimates are given in this paper of Kevin Ford.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.