A Miscellany of Erdős Problems

NEW

Problem: Let $F(n;t)$ be the maximum size of a set $A\subseteq\{1,\dots,n\}$ such that no two elements $x<y$ of $A$ satisfy

This matches the surrounding Erdős question about forcing a “large” difference $a_j-a_i$ dividing $a_j$. The literal inequality cannot mean all $n$, since small $n$ give boundary failures; the natural statement is asymptotic: for each fixed $t$ and $\varepsilon>0$, prove $F(n;t)<(1+\varepsilon)n/2$ for all sufficiently large $n$.

Result: The asymptotic statement is true for every fixed $t$. In fact,

The lower bound follows from the odd integers: if $x<y$ are odd, then $y-x$ is even and cannot divide $y$. Hence

For the upper bound, fix $t$ and $\eta>0$. Choose finitely many odd primes $P$, all $>t$, such that

is large; this is possible by Euler’s divergence of $\sum_p1/p$. For $m\le n$, put

Let $A\subseteq[n]$ be admissible and $B=[n]\setminus A$. For each $p\in P$, if $2rp\in A$, then $(2r-1)p\notin A$, since their difference is $p>t$ and $p\mid 2rp$. Thus

Summing over $p\in P$,

For fixed $P$, on each parity class the functions $1_{p\mid m}$ are asymptotically independent, so

for all sufficiently large $n$. Hence, by Cauchy–Schwarz, if

then the weighted inequality gives

so

Therefore

Choosing $\mu$ sufficiently large and then $n$ sufficiently large gives

Since $\eta>0$ is arbitrary,

Together with the odd-number construction, the limit is $1/2$. Taking $\eta<\varepsilon/2$ proves in particular

for all sufficiently large $n$, and the same holds for every fixed larger $t$.

Citation: Problem source: Richard K. Guy, “A Miscellany of Erdős Problems,” Amer. Math. Monthly 90 (1983), 118–120. The proof above is self-contained apart from Euler’s classical divergence of the reciprocal-prime series.