Proving it is impossible; on Erdős problem
arXiv:2508.18270
Abstract
Erdős and Graham asked for the minimum density missed by one chosen residue class for each of a prescribed collection of moduli. We give exact expressions for natural structured families and relate one of them to hard balanced-partition instances. For binary-encoded lists of moduli, allowing repetitions, even deciding whether the minimum is zero is NP-hard.
5 pages