Problem #784: Let $C>0$. Does there exist a $c>0$ (depending on $C$) such...

---

Progress

An example of Schinzel and Szekeres [ScSz59] shows that this would be best possible (up to the value of $c$).

See also [542].

In the comments jif has noted that the answer is trivially no for every $C\geq 1$ with $A=\{1\}$. Presumably (as is usual in these kind of questions) the assumption that $1\not\in A$ is intended. jif also notes that a lower bound of $(1-C)x$ is trivial by the union bound if $0<C<1$.

Let $H_C(x)$ be the minimum value of\[\#\{ m\leq x : a\nmid m\textrm{ for all }a\in A\}\]as $A$ ranges over all subsets of $\{2,\ldots,\lfloor x\rfloor\}$ with $\sum_{n\in A}\frac{1}{n}\leq C$, so that this question asks whether\[H_C(x)\gg \frac{x}{(\log x)^{O_C(1)}}\]for all $C>0$.

For $C=1$ it is known that\[H_1(x)\asymp \frac{x}{\log x}.\]The lower bound is due to Ruzsa [Ru82], and the upper bound is due to Saias [Sa98]. More precise estimates (including a conjectured asymptotic formula of $\sim c\frac{x}{\log x}$ for an explicit $c\approx 0.878$) are given by Weingartner [We25].

For fixed $C>1$ Ruzsa answered this question in the negative, and in fact\[H_C(x)=x^{e^{1-C}+o(1)}.\]This was improved by Weingartner [We25] who proved (for any fixed $C>1$)\[H_C(x)\asymp \frac{x^{e^{1-C}}}{\log x}.\]Together these answer the given question (positively for $0<C\leq 1$ and negatively for $C>1$).