14
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ This is an interesting question indeed. Thank you for sharing it, I look forward to seeing the responses. $\endgroup$
    – Tyler Clark
    Commented Nov 20, 2010 at 14:50
  • 3
    $\begingroup$ 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) $\endgroup$
    – Dror Speiser
    Commented Nov 20, 2010 at 17:36
  • $\begingroup$ Edit: "no $n^{u}$-smooth factor, where $\rho (u)=c$, $\rho$ being Dickman's function of size ...". $\endgroup$
    – Dror Speiser
    Commented Nov 20, 2010 at 19:00

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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