gpt pro 5.2 attempt on Math-743

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.