DISPROVED (LEAN)
This has been solved in the negative and the proof verified in Lean.
Is the set of odd integers not of the form $2^k+p$ the union of an infinite arithmetic progression and a set of density $0$?
Erdős called this conjecture 'rather silly'.
Romanoff
[Ro34] showed that the set of odd integers of this form has positive density. Using covering congruences Erdős
[Er50] proved that the set of odd integers which are not of this form contains an infinite arithmetic progression.
Chen
[Ch23] has proved the answer is no.
See also
[9],
[10], and
[11].
View the LaTeX source
This page was last edited 05 April 2026. View history
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 #16, https://www.erdosproblems.com/16, accessed 2026-05-21
