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ős [Er35], and the upper bound\[\sum_{n<x}\frac{1}{n}\ll \frac{\log x}{\sqrt{\log\log x}}\]was proved by Behrend [Be35]. This $O(\cdot)$ bound was improved to a $o(\cdot)$ bound by Erdős, Sárkőzy, and Szemerédi [ESS67].


In [Er73] and [Er77c] Erdő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ő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 [Er97c] he offers \$500 for resolving the questions in the main problem statement above.

This was partially resolved by Koukoulopoulos, Lamzouri, and Lichtman [KLL25], who proved that we must have\[\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n).\]See also [858].

This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.

View the LaTeX source

Erdős [Er35] proved that this sum always converges for a primitive set. Lichtman [Li23] proved that the answer is yes.

View the LaTeX source

Davenport and Erdős [DaEr36] proved that the answer is yes when $X_n=\{0\}$ for all $n\in A$. An alternative elementary proof was later given by Davenport and Erdős in [DaEr51].

The problem considers logarithmic density since Besicovitch [Be34] showed examples exist without a natural density, even when $X_n=\{0\}$ for all $n\in A$.

This is very similar to [25].

View the LaTeX source

This page was last edited 17 October 2025.

Alexander [Al66] and Erdős, Sárközi, and Szemerédi [ESS68] proved that this maximum is $o(1)$ (as $N\to \infty$). This condition on $A$ is a weaker form of the usual primitive condition. If $A$ is primitive then Behrend [Be35] proved\[\frac{1}{\log N}\sum_{n\in A}\frac{1}{n}\ll \frac{1}{\sqrt{\log\log N}}.\]An example of such a set $A$ is the set of all integers in $[N^{1/2},N]$ divisible by some prime $>N^{1/2}$.

See also [143].

View the LaTeX source

A number theoretic variant of a combinatorial game of Hajnal, in which players alternately add edges to a graph while keeping it triangle-free. This game must trivially end in at most $n^2/4$ moves, and Füredi and Seress [FuSe91] proved that it can be guaranteed to last for $\gg n\log n$ moves. Biró, Horn, and Wildstrom [BPW16] proved that it must end in at most $(\frac{26}{121}+o(1))n^2$ moves.

This type of game is known as a saturation game.

Erdős does not specify which player goes first, which may result in different answers.

View the LaTeX source

A problem of Erdős and Sárkőzy. The greedy algorithm shows that\[\lvert A\rvert\geq (1-o(1))\log_3 n\]is possible, but Erdős and Sárkőzy speculated that $\lvert A\rvert=(1-o(1))\log_2n$ is possible.

In [Er98] Erdős reports (but gives no reference) that Sándor has proved that $\lvert A\rvert=(1-o(1))\log_2 n$ is achievable, taking $A=\{ 2^i+m2^m : 0\leq i<m\}$ and $n=2^{m-1}+m2^m$.

Erdős, Lev, Rauzy, Sándor, and Sárközy [ELRSS99] proved that\[\lvert A\rvert > \log_2 n -1\]is achievable, taking $A=\{2^m-2^{m-1},2^m-2^{m-2},\ldots,2^m-1\}$. This property also implies that $\sum_{a\in S}a$ are distinct for distinct subsets $S$, whence [1] implies\[\lvert A\rvert \leq \log_2 n+\tfrac{1}{2}\log_2\log n+O(1),\]and likely $\lvert A\rvert\leq \log_2n+O(1)$.

See also [13].

View the LaTeX source

A problem of Erdős, Sárközy, and Szemerédi [ESS68]. It is known that\[\sum \frac{1}{b_n\log b_n}<\infty\]and\[\sum_{b_n<x}\frac{1}{b_n} =o\left(\frac{\log x}{\sqrt{\log\log x}}\right)\]are both necessary. (The former is due to Erdős [Er35], the latter to Erdős, Sárközy, and Szemerédi [ESS67].)

One can ask a similar question for sequences of real numbers, as in [143].

View the LaTeX source