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

$$\lim_{n\to\infty}\frac{F(n;t)}n=\frac12$$

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

$$F(n;t)\ge \lceil n/2\rceil .$$

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

$$\mu:=\sum_{p\in P}\frac1p$$

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

$$\#\{a\in A:a\text{ even},\,p\mid a\} \le \#\{b\in B:b\text{ odd},\,p\mid b\}.$$

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

$$\sum_{\substack{a\in A\\ a\text{ even}}} w(a) \le \sum_{\substack{b\in B\\ b\text{ odd}}} w(b).$$

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,

$$|A\cap 2\mathbb Z|-|B\cap(2\mathbb Z+1)| \le O\!\left(\frac n{\sqrt{\mu}}\right).$$

Therefore

$$|A| =|A\cap(2\mathbb Z+1)|+|A\cap2\mathbb Z| \le \frac n2+O\!\left(\frac n{\sqrt{\mu}}\right)+o(n).$$

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

$$|A|\le \left(\frac12+\varepsilon\right)n.$$

Since $\varepsilon>0$ is arbitrary,

$$\limsup_{n\to\infty}\frac{F(n;t)}n\le \frac12.$$

Together with the odd-number construction, this proves

$$\lim_{n\to\infty}\frac{F(n;t)}n=\frac12.$$

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.