Problem 143 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
Let $A\subset (1,\infty)$ be a countably infinite set such that for all $x\neq y\in A$ and integers $k\geq 1$ we have\[ \lvert kx -y\rvert \geq 1.\]Does this imply that $A$ is sparse? In particular, does this imply that\[\sum_{x\in A}\frac{1}{x\log x}<\infty\]or\[\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n)?\]

Picture
-------
[Given objects + constraints]  --->  [Count / structure]  --->  [Show bound / existence]

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Notation (if it appears above)
-----------------------------
- `o(g(n))` means "grows strictly smaller than g(n)" (ratio → 0 as n→∞).

Benchmarks / known results (from comments)
----------------------------------------
- Note that if $A$ is a set of integers then the condition implies that $A$ is
  a primitive set (that is, no element of $A$ is divisible by any other), for
  which the convergence of $\sum_{n\in A}\frac{1}{n\log n}$ was proved by
  Erd\H{o}s, and the upper bound\[\sum_{n<x}\frac{1}{n}\ll \frac{\log
  x}{\sqrt{\log\log x}}\]was proved by Behrend.
- This $O(\cdot)$ bound was improved to a $o(\cdot)$ bound by Erd\H{o}s,
  S\'{a}rk\H{o}zy, and Szemer\'{e}di.
- In and Erd\H{o}s mentions an unpublished proof of Haight that\[\lim
  \frac{\lvert A\cap [1,x]\rvert}{x}=0\]holds if the elements of $A$ are
  independent over $\mathbb{Q}$.
- Over the years Erd\H{o}s asked for various different quantitative estimates,
  for example\[\liminf \frac{\lvert A\cap [1,x]\rvert}{x}=0\]or even
  (motivated by Behrend's bound)\[\sum_{\substack{x <n\\ x\in
  A}}\frac{1}{x}\ll \frac{\log x}{\sqrt{\log\log x}}.\]In he offers \$500 for
  resolving the questions in the main problem statement above.