Erdős Problem #278 — Extremal densities of unions of residue classes
Let be a finite set of positive integers. For residues , let
and let denote its natural density in . This density exists because is periodic modulo . The first question is to determine, for each such ,
The accompanying question asks whether the minimum of over the same choices is attained by a choice with all residues equal, meaning for some integer and every . Erdős Problem #278 Proving it is impossible; on Erdős problem #278
Background
The problem is attributed to Erdős and Graham, with a reference to their 1980 work. Its two extremal questions concern complementary densities: maximizing the covered proportion is equivalent to minimizing the uncovered proportion. Since every choice of residues gives a periodic union, density reduces to counting covered residue classes modulo the common period . This makes the extremal problem finite for each fixed set of moduli, though the number of residue choices can be large. Erdős Problem #278 Proving it is impossible; on Erdős problem #278
A natural comparison is the choice in which all congruences use the same integer . In that case, every finite intersection of the progressions is compatible, and the intersection for indices in has density . Inclusion–exclusion therefore gives an explicit density for this particular union. Erdős Problem #278
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.