← All problems

Erdős Problem #278 — Extremal densities of unions of residue classes

46 years old · traced to

Let A={n1<⋯<nr}A=\{n_1<\cdots<n_r\} be a finite set of positive integers. For residues ai∈{0,1,…,ni−1}a_i\in\{0,1,\ldots,n_i-1\}, let

U(a)=⋃i=1r(ai+niZ),U(\mathbf a)=\bigcup_{i=1}^r(a_i+n_i\mathbb Z),

and let d(U(a))d(U(\mathbf a)) denote its natural density in Z\mathbb Z. This density exists because U(a)U(\mathbf a) is periodic modulo L=lcm⁡(n1,…,nr)L=\operatorname{lcm}(n_1,\ldots,n_r). The first question is to determine, for each such AA,

max⁡0≤ai<nid(U(a)).\max_{0\le a_i<n_i} d(U(\mathbf a)).

The accompanying question asks whether the minimum of d(U(a))d(U(\mathbf a)) over the same choices is attained by a choice with all residues equal, meaning ai≡c(modni)a_i\equiv c\pmod{n_i} for some integer cc and every ii. 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 LL. 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 cc. In that case, every finite intersection of the progressions is compatible, and the intersection for indices in JJ has density 1/lcm⁡(nj:j∈J)1/\operatorname{lcm}(n_j:j\in J). Inclusion–exclusion therefore gives an explicit density for this particular union. Erdős Problem #278

References

Progress summary

Never refreshed

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.