# numbers divisible by at least one of many numbers

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$\}$

-
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

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.