Erdős Problem #278

Round 2 continuation for Erdős Problems #278, #279, #281

We write $d(S)$ for natural density when it exists, $\overline d(S)$ for upper density, and $\underline d(S)$ for lower density.

Problem 278

1) ROUND-2 OBJECTIVE

We pursue (C) obstruction/correction. Round 1 already settled the minimum-density part via Simpson's extremal theorem, but left the maximum-density question open in general. The most promising way to make strict progress is therefore to isolate a nontrivial family of moduli for which the maximum can be computed exactly, and to show that this family already contains a genuine partition/knapsack-type optimization.

2) Round-1 FOUNDATION USED

We use the following Round-1 facts without re-proving them.

1. The density problem reduces to a finite optimization problem modulo $N=\mathrm{lcm}(n_1,\dots,n_r)$.
2. If the moduli are pairwise coprime, the covered density is independent of the chosen residues.
3. Simpson's theorem settles the minimum-density question: the minimum is attained when all residues are aligned.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is an exact structured-family formula. For moduli of the form \[ A=\{q,qb_1,\dots,qb_m\}, \] with $q\ge 2$, with $b_1,\dots,b_m$ pairwise coprime, and with $(q,b_i)=1$ for every $i$, the maximum covered density can be written exactly as a labelled partition problem on the indices $1,\dots,m$.

For $q=3$ this becomes a two-way balancing problem, i.e. a precise number-partitioning obstruction inside Erdős Problem #278.

4) ATTACK PLAN (ROUND-2)

The gap after Round 1 was: "the maximum-density question is open in general, but can we say something mathematically sharper than that?"

We now prove two precise claims.

1. An exact maximum-density formula for the family $\{q,qb_1,\dots,qb_m\}$.
2. A corollary for $q=3$ showing that the optimization is equivalent to balancing the weights \[ w_i=-\log\!\left(1-\frac{1}{b_i}\right). \]

This overcomes the Round-1 obstacle by replacing a vague "no closed form is known" statement with a rigorous family-level theorem and an explicit optimization obstruction.

5) WORK (ROUND-2)

Theorem.

Let $q\ge 2$, and let $b_1,\dots,b_m$ be pairwise coprime positive integers, each coprime to $q$. Consider the moduli \[ A=\{q,qb_1,\dots,qb_m\}. \] Then the maximum density of integers covered by a suitable choice of congruences modulo these moduli is \[ 1-\frac{1}{q}\min_{I_1\sqcup\cdots\sqcup I_{q-1}=[m]} \sum_{j=1}^{q-1}\ \prod_{i\in I_j}\left(1-\frac{1}{b_i}\right), \] where the minimum runs over all labelled partitions of $[m]=\{1,\dots,m\}$ into $q-1$ (possibly empty) parts, and empty products are interpreted as $1$.

Proof.

Let the chosen congruence modulo $q$ be $a_0 \pmod q$. Translating all congruences by the same integer does not change the density of the union, so we may assume \[ a_0\equiv 0 \pmod q. \]

Now consider a chosen congruence $a_i \pmod{qb_i}$. If $a_i\equiv 0\pmod q$, then \[ a_i(qb_i)\subseteq 0(q), \] so that congruence contributes nothing outside the already-covered class $0\pmod q$. Hence in any optimal configuration we may assume \[ a_i\not\equiv 0\pmod q \qquad (1\le i\le m). \]

For each residue class $j\in\{1,\dots,q-1\}$ modulo $q$, define \[ I_j:=\{\,i\in[m]: a_i\equiv j\pmod q\,\}. \] These sets form a labelled partition of $[m]$.

Fix $j\in\{1,\dots,q-1\}$. Every integer $x\equiv j\pmod q$ can be written uniquely as \[ x=j+qt. \] For $i\in I_j$, because $a_i\equiv j\pmod q$ and $(q,b_i)=1$, the condition \[ x\equiv a_i\pmod{qb_i} \] is equivalent to a single congruence \[ t\equiv c_i \pmod{b_i} \] for a uniquely determined residue class $c_i \pmod{b_i}$.

Thus, within the residue class $x\equiv j\pmod q$, the congruences coming from the indices $i\in I_j$ forbid exactly one residue class modulo each $b_i$. Since the $b_i$ are pairwise coprime, the Chinese remainder theorem shows that the density of $t$ avoiding all these forbidden classes is \[ \prod_{i\in I_j}\left(1-\frac{1}{b_i}\right). \] Therefore the density of uncovered integers inside the class $j\pmod q$ is exactly that product, and since each class modulo $q$ has density $1/q$, the total uncovered density is \[ \frac{1}{q}\sum_{j=1}^{q-1}\prod_{i\in I_j}\left(1-\frac{1}{b_i}\right). \]

This quantity depends only on the partition $(I_1,\dots,I_{q-1})$, not on the finer residues modulo the $b_i$.

Conversely, every labelled partition $(I_1,\dots,I_{q-1})$ can be realised: for each $i\in I_j$, choose any residue $a_i\pmod{qb_i}$ satisfying $a_i\equiv j\pmod q$ (for instance, by fixing any residue modulo $b_i$ and using the Chinese remainder theorem). Hence the possible uncovered densities are exactly the quantities above. Minimising uncovered density is equivalent to maximising covered density, which proves the formula. $\square$

Corollary ($q=3$).

For moduli \[ A=\{3,3b_1,\dots,3b_m\}, \] with the $b_i$ pairwise coprime and each coprime to $3$, the maximum covered density is \[ 1-\frac{1}{3}\min_{S\subseteq[m]} \left( \prod_{i\in S}\left(1-\frac{1}{b_i}\right) + \prod_{i\notin S}\left(1-\frac{1}{b_i}\right) \right). \]

If we write \[ \alpha_i:=1-\frac{1}{b_i} \qquad\text{and}\qquad w_i:=-\log \alpha_i, \] then the product of the two displayed terms is the fixed constant $\prod_{i=1}^m \alpha_i$. Hence minimising their sum is equivalent to making them as equal as possible, i.e. equivalent to minimising \[ \left| \sum_{i\in S} w_i-\sum_{i\notin S} w_i \right|. \] So this family of moduli already contains a genuine balanced-partition optimization.

6) ADVERSARIAL VERIFICATION

1. Why may we assume $a_0=0$? Because simultaneous translation of all residue classes simply translates the covered set, and density is translation-invariant.

2. Why may we discard the case $a_i\equiv 0\pmod q$? Because such a congruence is contained in the already-covered class $0\pmod q$, so it never increases the union.

3. Are empty parts allowed? Yes. If $I_j=\emptyset$, the uncovered density in the class $j\pmod q$ is $1$, which is exactly the empty-product value.

4. Is pairwise coprimality of the $b_i$ really needed? Yes. The proof uses the Chinese remainder theorem inside each residue class modulo $q$. If the $b_i$ are not pairwise coprime, the factorisation of the avoidance density can fail.

5. Spot check. For $A=\{3,6,15\}$ the theorem gives \[ 1-\frac13\min\!\left\{\frac12+\frac45,\ 1+\frac25\right\} = 1-\frac{13}{30} = \frac{17}{30}. \] A direct brute-force check over all $3\cdot 6\cdot 15=270$ residue choices agrees with $\frac{17}{30}$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 does not solve the general maximum-density question, but it gives a rigorous obstruction/correction:

1. the family $\{q,qb_1,\dots,qb_m\}$ admits an exact partition formula for the maximum density;
2. in the special case $q=3$, the optimization is exactly a balanced-partition problem in the weights $-\log(1-1/b_i)$.

So the correct sharpened statement is that Erdős Problem #278 already contains a nontrivial partition optimization even on a very structured subfamily.

8) COMPLETION ESTIMATE

COMPLETION: 60%.

9) REFERENCES

1. P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographies de L'Enseignement Mathématique 28, Geneva, 1980.
2. R. J. Simpson, Exact coverings of the integers by arithmetic progressions, Discrete Mathematics 59 $1986$, 181--190.
3. Stijn Cambie, Proving it is impossible; on Erdős problem #278, arXiv:2508.18270, 2025.

Problem 278: removing an unnecessary coprimality hypothesis

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. The target is to determine the best attainable coverage density for prescribed moduli. I read all of 278.tex, including its labelled-partition formula. Cambie's primary paper already contains the $q=3$ prime-factor partition reduction, so that reduction should not be represented as a new discovery. I extend the supplied formula slightly and derive an explicit bound on the value lost through imperfect balancing.

2) WORK

For moduli $\{q,qb_1,\ldots,qb_m\}$, let $q\ge2$, $b_i\ge2$, and assume only that the $b_i$ are pairwise coprime. The hypothesis $(q,b_i)=1$ in the supplied attempt is unnecessary. Normalize the class modulo $q$ to zero. Assign every other congruence to a nonzero class $j$ modulo $q$; one placed in the zero class can be moved out without losing coverage. Write its representative as $j+qc_i$. Then \[ j+qt\equiv j+qc_i\pmod{qb_i} \quad\Longleftrightarrow\quad t\equiv c_i\pmod{b_i}, \] by ordinary integer cancellation, with no coprimality requirement involving $q$. The Chinese remainder theorem for the $b_i$ proves \[ D_{\max}=1-\frac1q\min_{I_1\sqcup\cdots\sqcup I_{q-1}=[m]} \sum_{j=1}^{q-1}\prod_{i\in I_j}(1-1/b_i). \]

For $q=3$, put $w_i=-\log(1-1/b_i)$, $W=\sum_iw_i$, and let $\delta$ be the least achievable absolute difference of the two subset weight sums. The formula becomes exactly \[ D_{\max}=1-\frac23e^{-W/2}\cosh(\delta/2). \] Assigning each successive weight to the currently lighter bin leaves discrepancy at most $w_{\max}$: after an assignment the new discrepancy is $|d-w_i|$, which preserves this bound inductively. Consequently \[ 1-\frac23e^{-W/2}\cosh(w_{\max}/2) \le D_{\max}\le1-\frac23e^{-W/2}. \] This is a rigorous approximation interval available without solving the exact partition problem. For example $q=3$, $(b_1,b_2)=(3,4)$ violates the old extra hypothesis but is allowed here. Placing the two moduli in separate classes yields the optimum \[ D_{\max}=1-\frac13(2/3+3/4)=\frac{19}{36}. \] Putting them together gives only $1/2$.

3) ADVERSARIAL VERIFICATION

The two-bin greedy assignment proves a bound, not optimality. The logarithms require $b_i>1$, unlike the source's overly broad positive-integer wording. Pairwise coprimality of the $b_i$ remains essential for the product calculation. A hard partition instance does not by itself prove that no conceivable general formula exists.

4) FINAL

UNRESOLVED. The structured formula has a broader domain and a quantitative balancing bound. Arbitrary prescribed moduli still require a different analysis.

5) SOURCES CHECKED

The complete supplied version; S. Cambie, Proving it is impossible; on Erdős problem #278, equations and reduction checked at https://arxiv.org/html/2508.18270v1, 2026-09-23. The removal of the extra coprimality condition and the discrepancy estimate are proved above.

6) COMPLETION ESTIMATE

Subjective progress toward a general determination of optimal density. COMPLETION: 15%

Problem 278

FORMAL RESTATEMENT

Fix distinct positive integers $n_1<n_2<\dots<n_r$. For each $i$ choose a residue $a_i\in \mathbb{Z}/n_i\mathbb{Z}$, and form the union of congruence classes \[ U(\mathbf a)\;:=\;\bigcup_{i=1}^r \{m\in \mathbb{Z}:\ m\equiv a_i \pmod{n_i}\}. \] Because $U(\mathbf a)$ is periodic modulo $N:=\operatorname{lcm}(n_1,\dots,n_r)$, the density $\operatorname{d}(U(\mathbf a))$ exists and equals $|U(\mathbf a)\cap[0,N-1]|/N$.

1. (Maximum-density question) Determine, in terms of $n_1,\dots,n_r$, the value of \[ \max_{\mathbf a}\ \operatorname{d}(U(\mathbf a)). \]
2. (Minimum-density question) Show that the minimum \[ \min_{\mathbf a}\ \operatorname{d}(U(\mathbf a)) \] is attained when all $a_i$ are "the same" in the sense that there exists $a\in\mathbb{Z}$ with $a_i\equiv a\pmod{n_i}$ for every $i$ (equivalently, all chosen classes contain a common integer).

QUICK LITERATURE/CONTEXT CHECK

The second question is known: Simpson proved that among all choices of residues, the covered density is minimized when the classes have a common intersection (e.g. all $a_i\equiv 0$), and in that case inclusion--exclusion gives the explicit value. This is stated as Lemma 2.3 in Simpson $1986$ and is also quoted as Lemma 1 in Sun $1991$. A recent note by Cambie $2025$ discusses Problem 278 and explains why a simple closed form for the maximum density should not be expected in general.

ATTACK PLAN

• Reduce both questions to a finite combinatorial problem in the cyclic group $\mathbb{Z}/N\mathbb{Z}$. Each congruence class $a_i \bmod n_i$ lifts to a coset of a subgroup of $\mathbb{Z}/N\mathbb{Z}$. Thus $\operatorname{d}(U(\mathbf a))$ is exactly the normalized size of a union of cosets in $\mathbb{Z}/N\mathbb{Z}$.
• For the minimum density, cite Simpson's theorem: \[ \operatorname{d}\!\left(\bigcup_{i=1}^r a_i(n_i)\right)\ \ge\ \operatorname{d}\!\left(\bigcup_{i=1}^r 0(n_i)\right), \] and the right-hand side is computed by inclusion--exclusion because all intersections are nonempty.
• For the maximum density, record what can be said cleanly: trivial bounds, easy cases (e.g. pairwise coprime moduli), and the finite-group optimization formulation. No general explicit formula is currently known.

WORK

Step 1: Density as a finite union problem.

Let $N=\operatorname{lcm}(n_1,\dots,n_r)$. For each $i$, \[ C_i(\mathbf a)\;:=\;\{x\in\mathbb{Z}/N\mathbb{Z}:\ x\equiv a_i \pmod{n_i}\} \] is a coset of the subgroup $H_i:=\{x\in\mathbb{Z}/N\mathbb{Z}:\ x\equiv 0\pmod{n_i}\}$. Then \[ \operatorname{d}(U(\mathbf a)) \;=\; \frac{1}{N}\left|\bigcup_{i=1}^r C_i(\mathbf a)\right|. \] So both the maximum and minimum density questions are finite optimization problems over residue choices in the cyclic group $\mathbb{Z}/N\mathbb{Z}$.

Easy cases for the maximum.

• If the $n_i$ are pairwise coprime, then by the Chinese Remainder Theorem every intersection $\bigcap_{j\in J} C_j(\mathbf a)$ is nonempty and has size $N/\operatorname{lcm}(n_j:j\in J)$ independent of $\mathbf a$. Hence $\operatorname{d}(U(\mathbf a))$ is independent of $\mathbf a$, and in particular \[ \max_{\mathbf a}\operatorname{d}(U(\mathbf a))=\min_{\mathbf a}\operatorname{d}(U(\mathbf a)) =\sum_{i=1}^r \frac1{n_i}-\sum_{i<j}\frac1{\operatorname{lcm}(n_i,n_j)}+\cdots+(-1)^{r+1}\frac1{\operatorname{lcm}(n_1,\dots,n_r)}. \]
• Always one has the crude bounds \[ \max_{\mathbf a}\operatorname{d}(U(\mathbf a))\le \min\!\Big(1,\ \sum_{i=1}^r \frac1{n_i}\Big) \qquad\text{and}\qquad \min_{\mathbf a}\operatorname{d}(U(\mathbf a))\ge 0. \]

The minimum density (Simpson).

Write $a(n):=\{m\in\mathbb{Z}:\ m\equiv a\pmod n\}$. The following is the key lemma.

Assuming this lemma, the second question is immediate because when all residues are aligned (e.g. $a_i\equiv 0$), every finite intersection is nonempty and has density exactly $1/\operatorname{lcm}(n_{i_1},\dots,n_{i_s})$. Therefore inclusion--exclusion gives \begin{align*} \operatorname{d}\!\left(\bigcup_{i=1}^r 0(n_i)\right) &=\sum_{i=1}^r\frac1{n_i}-\sum_{1\le i<j\le r}\frac1{\operatorname{lcm}(n_i,n_j)}+\cdots \\ &\hspace{13mm} +(-1)^{r+1}\frac1{\operatorname{lcm}(n_1,\dots,n_r)}. \end{align*} Moreover, the lemma shows this is the minimum possible covered density over all residue choices.

VERIFICATION

A quick sanity check with $n_1=2,n_2=4$: \[ \operatorname{d}(0(2)\cup 0(4))=\operatorname{d}(0(2))=\tfrac12, \] and inclusion--exclusion yields $\frac12+\frac14-\frac14=\frac12$. If instead one takes residues $a_1\equiv 0\pmod2$, $a_2\equiv 1\pmod4$, then the classes are disjoint mod $4$, giving density $\frac12+\frac14=\frac34>\frac12$, consistent with "aligned residues minimize coverage".

FINAL

FINAL: UNRESOLVED.

• The maximum-density question does not currently have a known general closed-form answer in terms of the $n_i$ alone; it is equivalent to a finite union-of-cosets maximization in $\mathbb{Z}/N\mathbb{Z}$.
• The minimum-density question is solved: Simpson proved the minimum occurs when the residue classes share a common integer (e.g. all $a_i\equiv 0$), and the minimum value is the full inclusion--exclusion alternating sum shown above.

COMPLETION ESTIMATE

Roughly 40%: the second part is complete; the first part is open/unsolved in general.