SOLVED (LEAN)
This has been resolved in some other way than a proof or disproof, and that resolution verified in Lean.
We say that $A\subseteq \mathbb{N}$ has property $P$ if, for all $n\geq 1$, there are only finitely many $a\in A$ such that $n+a$ is squarefree.
We say that $A$ has property $Q$ if there are infinitely many $n$ such that $n+a$ is squarefree for all $a<n$.
How fast must sequences $A=\{a_1<a_2<\cdots\}$ with properties $P$ or $Q$ increase?
Erdős
[Er81h] notes it is easy to see that there exist $A$ with property $P$, and that any set which increases sufficiently quickly has property $Q$.
He also asks about property $P'$, which is when there are infinitely many $n$ such that $n+a$ is squarefree for all $a\in A$, and property $P'_\infty$, which is when there are infinitely many $n$ such that $n+a$ is squarefree for all but finitely many $a\in A$.
Erdős also asks whether certain special sequences, such as $2^n\pm 1$ or $n!\pm 1$, have properties $P$ or $Q$.
Most of these questions have been resolved by van Doorn and Tao
[vDTa25]. In particular they show that any sequence with property $P$ has density $0$, but can have density going to $0$ arbitrarily slowly. They also show that any sequence with property $Q$ has upper density at most $6/\pi^2$, and sequences with property $Q$ exist with density equal to $6/\pi^2$.
They further show that any sequence with properties either $P'$ or $P'_\infty$ have upper density $<6/\pi^2$, and this is best possible in that for any $\epsilon>0$ there exist such sequences with lower density $>6/\pi^2-\epsilon$.
Finally, they also show that $2^n\pm 1$ and $n!\pm 1$ have property $Q$. It remains open whether these sequences have property $P$.
View the LaTeX source
This page was last edited 02 December 2025. 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 #1102, https://www.erdosproblems.com/1102, accessed 2026-04-11
