---

Claim. I. Z. Ruzsa, Few multiples of many primes, the Theorem. For a set $Q=\{p_1<\cdots<p_n\}$ of primes, let $m(Q,N)$ be the least number, over intervals $I$ of length $N$, of integers in $I$ divisible by some $p_j$. Ruzsa proves: "Let $\varrho\geq3$ and write $k=[\varrho]$. There is a constant $C$ depending only on $\varrho$ such that for every $n>n_0(\varrho)$ there is a set $Q=\{p_1<\ldots<p_n\}$ of primes satisfying $m(Q,\varrho p_n)<C(n\log n)^{1-1/k}$." The proof is a random construction: the primes lie in $(\alpha N,\beta N)$ with $N=[Kn\log n]$, and a random subset of $[1,N]$ with inclusion probability of order $N^{-1/k}$ contains a whole residue class for many of them.

Ruzsa does not state a consequence for Problem 860, but one follows. For large $n$ the bound $C(n\log n)^{1-1/k}$ is below $n$, so an interval of length $\varrho p_n$ cannot hold $n$ distinct multiples, one of each prime of $Q$, and so not one of each prime up to $p_n$. Hence $h(p_n)>\varrho p_n$. The primes of $Q$ lie in $(\alpha N,\beta N)$ with $\beta=1/\varrho$ and $\alpha>\beta/2$, and $N=[Kn\log n]$ grows by a factor tending to one from $n$ to $n+1$; since $h$ is nondecreasing, $h(x)>(\varrho/2-o(1))x$ for all large $x$. As $\varrho$ is arbitrary, $h(n)/n\to\infty$. The site's commentary and the second version of arXiv:2607.26450 credit this consequence to Ruzsa. The paper is compiled at Ruzsa (1995).

Covers. The lower bound $h(n)/n\to\infty$. The order of magnitude of $h(n)$, which the problem asks to estimate, stays open.

Acceptance. The result is refereed: Studia Sci. Math. Hungar. 30 (1995), 123--125. The link is the paper's record in the Hungarian Academy's repository. The site's commentary records the result on a problem it labels open, which is not acceptance.

Depends on. Nothing on this wiki; the argument is the paper's own.