← All problems

Erdős Problem #143 — Sparse sets with multiplicative separation

29 years old · traced to

Let AA be a countably infinite subset of (1,∞)(1, \infty) satisfying the separation condition that for every pair of distinct x,y∈Ax,y\in A and every integer k≥1k\ge 1,

∣kx−y∣≥1.|kx-y|\ge 1.

The question asks whether this forces AA to be “sparse,” and specifically asks whether either of the following conclusions must hold:

∑x∈A1xlog⁡x<∞,or∑x<n\x∈A1x=o(log⁡n)(n→∞).\sum_{x\in A}\frac{1}{x\log x}<\infty, \qquad\text{or}\qquad \sum_{\substack{x<n\x\in A}}\frac{1}{x}=o(\log n)\quad(n\to\infty).

The word “sparse” is not separately defined in the problem; these are the two concrete bounds given there. Erdős Problems, Problem #143

Background

This integer-dilation approximation problem goes back to Erdős in 1948. In its approximation form, it asks whether a sufficiently large set of positive reals must contain distinct elements α,β\alpha,\beta for which ∣nα−β∣|n\alpha-\beta| is arbitrarily small for some positive integer nn. The separation condition here rules out such a pair at every scale below 11. The integer setting explains the connection with primitive sets: for a set of integers, the condition is equivalent to saying that no distinct elements divide one another. The real-variable problem is a broader analogue, without the divisibility structure available for integers. Koukoulopoulos, Lamzouri, and Lichtman, Erdős’s integer dilation approximation problem and GCD graphs (2025) Erdős Problems, Problem #143

Classical results on primitive sets provide the benchmark. Erdős proved that every primitive set of integers PP satisfies ∑m∈P1/(mlog⁡m)<∞\sum_{m\in P}1/(m\log m)<\infty. Behrend proved an upper bound of order log⁡n/log⁡log⁡n\log n/\sqrt{\log\log n} for the reciprocal sum up to nn, and Erdős, Sárközy, and Szemerédi strengthened this to o(log⁡n)o(\log n). These results concern integer sets; they do not by themselves establish the corresponding convergence assertion for real sets obeying the separation condition. Koukoulopoulos, Lamzouri, and Lichtman (2025) Erdős Problems, Problem #143

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.