numbers divisible by at least one of many numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:50:09Z http://mathoverflow.net/feeds/question/46716 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46716/numbers-divisible-by-at-least-one-of-many-numbers numbers divisible by at least one of many numbers Fedor Petrov 2010-11-20T06:31:32Z 2010-12-13T07:58:56Z <p>Is the following true?</p> <p>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!.$$</p> <p>Of course, $n!$ may be replaced to the any common multiple of elements of $A$, or we may ask about densities or probabilities.</p> <p>I do not know the answer even for $A=\{ cn\$consecutive integers$\}$</p> http://mathoverflow.net/questions/46716/numbers-divisible-by-at-least-one-of-many-numbers/49223#49223 Answer by Gjergji Zaimi for numbers divisible by at least one of many numbers Gjergji Zaimi 2010-12-13T07:58:56Z 2010-12-13T07:58:56Z <p>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 <a href="http://arxiv.org/abs/math.NT/0401223" rel="nofollow">this</a> paper of Kevin Ford.</p>