Logo
All Random Solved Random Open
2 solved out of 7 shown (show only solved or open)
OPEN - $500
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)?\]
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.

Additional thanks to: Zachary Chase and Desmond Weisenberg
SOLVED
A set $A\subset \mathbb{N}$ is primitive if no member of $A$ divides another. Is the sum \[\sum_{n\in A}\frac{1}{n\log n}\] maximised over all primitive sets when $A$ is the set of primes?
Erdős [Er35] proved that this sum always converges for a primitive set. Lichtman [Li23] proved that the answer is yes.
Additional thanks to: Jared Lichtman
OPEN
Let $A\subseteq \mathbb{N}$, and for each $n\in A$ choose some $X_n\subseteq \mathbb{Z}/n\mathbb{Z}$. Let \[B = \{ m\in \mathbb{N} : m\not\in X_n\pmod{n}\textrm{ for all }n\in A\}.\] Must $B$ have a logarithmic density, i.e. is it true that \[\lim_{x\to \infty} \frac{1}{\log x}\sum_{\substack{m\in B\\ m<x}}\frac{1}{m}\] exists?
Davenport and Erdős [DaEr37] proved that the answer is yes when $X_n=\{0\}$ for all $n\in A$. 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].

OPEN
Let $A\subseteq \{1,\ldots,N\}$ be such that there is no solution to $at=b$ with $a,b\in A$ and the smallest prime factor of $t$ is $>a$. Estimate the maximum of \[\frac{1}{\log N}\sum_{n\in A}\frac{1}{n}.\]
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 merely 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].

Additional thanks to: Desmond Weisenberg
OPEN
Consider the two-player game in which players alternately choose integers from $\{2,3,\ldots,n\}$ to be included in some set $A$ (the same set for both players) such that no $a\mid b$ for $a\neq b\in A$.

The game ends when no legal move is possible. One player wants the game to last as long as possible, the other wants the game to end quickly. How long can the game be guaranteed to last for?

At least $\epsilon n$ moves? (For $\epsilon>0$ and $n$ sufficiently large.) At least $(1-\epsilon)\frac{n}{2}$ moves?

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.

SOLVED
What is the size of the largest $A\subseteq \{1,\ldots,n\}$ such that in the set \[\left\{ \sum_{a\in S} a : \emptyset\neq S\subseteq A\right\}\] no two distinct elements divide each other?
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].

Additional thanks to: Stijn Cambie
OPEN
Is there a necessary and sufficient condition for a sequence of integers $b_1<b_2<\cdots$ that ensures there exists a primitive sequence $a_1<a_2<\cdots$ (i.e. no element divides another) with $a_n \ll b_n$ for all $n$?

In particular, is this always possible if there are no non-trivial solutions to $(b_i,b_j)=b_k$?

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].