Dual View Random Solved Random Open
PROVED (LEAN) This has been solved in the affirmative and the proof verified in Lean.
Let $k\geq 2$. Is there an integer $n_k$ such that, if $D=\{ 1<d<n_k : d\mid n_k\}$, then for any $k$-colouring of $D$ there is a monochromatic subset $D'\subseteq D$ such that $\sum_{d\in D'}\frac{1}{d}=1$?
This follows from the colouring result of Croot [Cr03]. Croot's result allows for $n_k \leq e^{C^k}$ for some constant $C>1$ (simply taking $n_k$ to be the lowest common multiple of some interval $[1,C^k]$). Sawhney has observed that there is also a doubly exponential lower bound, and hence this bound is essentially sharp.

Indeed, we must trivially have $\sum_{d|n_k}1/d \geq k$, or else there is a greedy colouring as a counterexample. Since $\prod_{p}(1+1/p^2)$ is finite we must have $\prod_{p|n_k}(1+1/p)\gg k$. To achieve the minimal $\prod_{p|n_k}p$ we take the product of primes up to $T$ where $\prod_{p\leq T}(1+1/p)\gg k$; by Mertens theorems this implies $T\geq C^{k}$ for some constant $C>1$, and hence $n_k\geq \prod_{p\mid n_k}p\geq \exp(cC^k)$ for some $c>0$.

The existence of such an $n_k$ is mentioned in problem B2 of Guy's collection [Gu04].
Additional thanks to: Mehtaab Sawhney
Proof expositions (0)
If you would like to contribute an exposition of a proof related to this problem, please message a moderator or leave your exposition as a comment.

No proof expositions yet.
Comments (0) Proof claims (0)
More information and links
This page was last edited 28 September 2025. (View history) (View the LaTeX source)

When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:

T. F. Bloom, Erdős Problem #45, https://www.erdosproblems.com/45, accessed 2026-09-01

From the external database. (You can help update this.)
Formalised statement? Yes
OEIS Possible
Reactions
Likes holyterror
Open to collaboration None
Currently working on None
Looks difficult None
Looks tractable None
Could be formalisable None
Working on formalising None