PROVED
This has been solved in the affirmative.
Let $A\subseteq \{1,\ldots,N\}$ be such that, for all $a,b\in A$, the product $ab$ is not squarefree.
Is the maximum size of such an $A$ achieved by taking $A$ to be the set of even numbers and odd non-squarefree numbers?
A problem of Erdős and Sárközy.
Weisenberg has provided the following positive proof. It is clear that such a maximal $A$ must contain all non-squarefree numbers. It therefore suffices to find the largest size of a subset of all squarefree numbers in $\{1,\ldots,N\}$ such that any two have at least one prime factor in common. By the result of Chvátal
[Ch74] discussed in
[701] this is maximised by the set of all even squarefree numbers.
An alternative proof was independently found by Alexeev, Mixon, and Sawin
[AMS25].
See also
[848].
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Desmond Weisenberg
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 #844, https://www.erdosproblems.com/844, accessed 2026-04-11
