A Miscellany of Erdős Problems

NEW

Problem: Reconstructed statement: for fixed $t\ge0$, let $F(n;t)$ be the largest size of a set $A\subseteq\{1,\dots,n\}$ such that whenever $x<y$ are in $A$ and $y-x\mid y$, one has $y-x\le t$. The conjecture asks whether

for every fixed $t$. This is the natural formalization because the surrounding Erdős problem concerns forcing a “large” difference $a_j-a_i$ dividing $a_j$. If $t$ were allowed to vary with $n$, the claim would be false, since $t\ge n$ gives $F(n;t)=n$.

Result: The conjecture is true.

The lower bound is immediate: the odd integers in $[n]$ form an admissible set for every $t$, since the difference of two odd numbers is even and cannot divide the larger odd number. Hence

For the upper bound, fix $\varepsilon>0$. Choose a finite set $P$ of odd primes $p>t$ such that

is large; this is possible by divergence of $\sum_p1/p$.

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

Summing over $p\in P$, with $w(m)=\#\{p\in P:p\mid m\}$, gives

For fixed $P$, divisibility by the primes in $P$ is asymptotically independent within each parity class, so on both the even and odd integers $\le n$, $w$ has mean $\mu+o(1)$ and variance at most $\mu+o(1)$. By Cauchy–Schwarz,

Therefore

Choosing $P$ so that $\mu$ is sufficiently large, and then taking $n$ large, yields

Since $\varepsilon>0$ is arbitrary,

Together with the odd-number construction, this proves

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.