Erdős Problem #279

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 279

1) ROUND-2 OBJECTIVE

We pursue (C) obstruction/correction. Round 1 only gave heuristic density considerations. The strongest promising direction is to determine whether the unresolved issue is really one of density or one of finiteness. The new theorem below shows that density is not the obstruction at all.

2) Round-1 FOUNDATION USED

We use two Round-1 ideas.

1. The reformulation: an integer $m$ is covered once there is a modulus $n$ with \[ m\equiv a_n\pmod n \] and with $n$ small enough relative to $m$ so that the quotient $t=(m-a_n)/n$ automatically satisfies $t\ge k$.
2. For pairwise coprime moduli, finite-prefix avoidance densities factor exactly.

3) NEW INSIGHT / TOOL (ROUND-2)

The new insight is that for pairwise coprime moduli, the exceptional set has upper density $0$ for every choice of residues, not merely for some probabilistically chosen one.

In particular, for the primes and any fixed $k\ge 1$, the set of integers not representable as \[ a_p+t p \qquad (t\ge k) \] has upper density $0$ for every residue choice $(a_p \bmod p)_p$.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was this: the heuristic suggested an uncovered proportion about $1/\log x$, but there was no rigorous theorem.

We now prove a sharp partial result:

For any pairwise coprime sequence $(n_i)$ with $\sum_i 1/n_i=\infty$, and for any fixed $k\ge 1$, every choice of residues gives an exceptional set of upper density $0$.

This cleanly isolates the remaining difficulty in Erdős Problem #279: the open problem is not about achieving density $0$, but about upgrading density $0$ to finiteness.

5) WORK (ROUND-2)

Theorem.

Let \[ 1<n_1<n_2<\cdots \] be pairwise coprime positive integers with \[ \sum_{i=1}^\infty \frac{1}{n_i}=\infty. \] Fix $k\ge 1$, and choose arbitrary residues $a_i \pmod{n_i}$. Define \[ E_k(\mathbf a) := \left\{ m\in\mathbf N : \text{there do not exist } i\ge 1 \text{ and } t\ge k \text{ with } m=a_i+t n_i \right\}. \] Then \[ \overline d\big(E_k(\mathbf a)\big)=0. \]

Proof.

Fix $r\ge 1$, and let \[ N_r:=n_1n_2\cdots n_r. \] Define the finite-prefix avoidance set \[ B_r(\mathbf a) := \{\,m\in\mathbf Z : m\not\equiv a_i \pmod{n_i}\ \text{for all } 1\le i\le r\,\}. \] Because the moduli $n_1,\dots,n_r$ are pairwise coprime, the Chinese remainder theorem gives a bijection \[ \mathbf Z/N_r\mathbf Z \longrightarrow \mathbf Z/n_1\mathbf Z \times \cdots \times \mathbf Z/n_r\mathbf Z. \] Hence the proportion of residue classes modulo $N_r$ that avoid all $a_i \pmod{n_i}$ is exactly \[ \prod_{i=1}^r \left(1-\frac{1}{n_i}\right). \] Therefore \[ d\big(B_r(\mathbf a)\big)=\prod_{i=1}^r \left(1-\frac{1}{n_i}\right), \] and this value is independent of the chosen residues.

Now let $m\ge (k+1)n_r$. If $m\notin B_r(\mathbf a)$, then for some $1\le i\le r$ we have \[ m\equiv a_i\pmod{n_i}. \] Write \[ m=a_i+t n_i. \] Since $0\le a_i\le n_i-1$ and $n_i\le n_r$, we get \[ m-a_i\ge (k+1)n_r-(n_i-1)\ge (k+1)n_i-(n_i-1) > k n_i. \] Because $m-a_i$ is divisible by $n_i$, it follows that $t\ge k$.

So every integer $m\ge (k+1)n_r$ outside $B_r(\mathbf a)$ is already covered by one of the first $r$ progressions with quotient at least $k$. Equivalently, \[ E_k(\mathbf a)\cap[(k+1)n_r,\infty)\subseteq B_r(\mathbf a). \] Taking upper densities, \[ \overline d\big(E_k(\mathbf a)\big)\le d\big(B_r(\mathbf a)\big) = \prod_{i=1}^r \left(1-\frac{1}{n_i}\right). \] This holds for every $r$. Since $\sum_i 1/n_i=\infty$, the infinite product on the right tends to $0$. Therefore \[ \overline d\big(E_k(\mathbf a)\big)=0. \] This proves the theorem. $\square$

Corollary (primes).

Take $n_i=p_i$ to be the primes. Then for every fixed $k\ge 1$ and every choice of residues $a_p \pmod p$, \[ \overline d\!\left( \left\{ m : m\neq a_p+t p \text{ for all primes } p \text{ and all } t\ge k \right\} \right) =0. \]

Thus, in Problem #279, the unresolved issue is not density zero but finite exceptionality.

6) ADVERSARIAL VERIFICATION

1. Threshold check. The proof only uses the implication \[ m\ge (k+1)n_r \ \text{ and }\ m\equiv a_i\pmod{n_i} \Longrightarrow m=a_i+t n_i \text{ with } t\ge k. \] This is valid because $a_i\le n_i-1$.

2. Why only upper density? From \[ E_k(\mathbf a)\cap[(k+1)n_r,\infty)\subseteq B_r(\mathbf a) \] we get an upper-density bound. That is exactly what is needed to conclude $\overline d(E_k(\mathbf a))=0$.

3. Does this prove the original problem? No. A set can have upper density $0$ and still be infinite. So the argument does not settle finiteness.

4. Is pairwise coprimality essential? Yes. The exact factorisation \[ d(B_r(\mathbf a))=\prod_{i\le r}(1-1/n_i) \] comes from the Chinese remainder theorem and can fail without pairwise coprimality.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 proves a substantial weakening of the target statement:

For the primes (indeed, for any pairwise coprime sequence with divergent reciprocal sum), the exceptional set has upper density $0$ for every choice of residues and every fixed $k\ge 1$.

So Erdős Problem #279 is now sharply reduced to the problem of upgrading "upper density $0$" to "finite".

8) COMPLETION ESTIMATE

COMPLETION: 45%.

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.

Erdős Problem #279: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

For each $k\ge3$, choose $0\le a_p<p$ for all primes so every sufficiently large integer equals $a_p+tp$ for some prime $p$ and $t\ge k$.

All supplied versions considered: 279.tex. The supplied density-zero exception theorem is valid but cannot establish finiteness. I test the natural coherent choices of residues and prove they all have infinite exceptions.

2) WORK

Fix an integer $r\ge0$ and choose $a_p$ to be its least nonnegative residue modulo $p$. For any prime $q>r$, let $m=r+q$. If $m=a_p+tp$, then congruence modulo $p$ implies $p\mid(m-r)=q$, so $p=q$. Since $q>r$, $a_q=r$, and therefore $t=1$. Thus every $m=r+q$ with $q>r$ prime is exceptional whenever $k\ge2$. Infinitely many such $q$ exist. No single fixed integer residue pattern can solve the problem.

For $r=0$ this describes the obstruction especially precisely. If $m$ is composite and $m\ge k^2$, its smallest prime divisor $p$ satisfies $p\le\sqrt m$, so $m/p\ge\sqrt m\ge k$, yielding a representation. Every prime remains exceptional. Hence for the zero residues the exceptional set is exactly the primes, up to finitely many smaller integers.

This exhibits a concrete family compatible with the source's density-zero conclusion while still having infinitely many exceptions; no probabilistic or heuristic density estimate is needed for the noncoverage proof.

3) ADVERSARIAL VERIFICATION

The quotient restriction is essential: without $t\ge k$, a prime covers itself using $p=m,t=1$. The fixed shift is chosen once, independently of $p$. The argument does not treat arbitrary independently chosen residues and therefore is not a disproof of the question.

4) FINAL

UNRESOLVED. A successful residue choice must avoid these coherent-shift obstructions while ensuring coverage for every sufficiently large integer. No such choice has been constructed.

5) SOURCES CHECKED

Full 279.tex read; exact $k\ge3$ quantifier checked in the formal-conjectures ErdosProblems/279.lean file on 2026-09-23.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 8%

Problem 279

FORMAL RESTATEMENT

Fix an integer $k\ge 3$. For each prime $p$, choose a residue $a_p\in\mathbb{Z}/p\mathbb{Z}$ and consider the set \[ S(\mathbf a)\;:=\;\bigcup_{p\ \text{prime}}\ \{a_p+t\,p:\ t\in\mathbb{Z},\ t\ge k\}. \] Question: is there a choice of residues $(a_p)_{p\ \mathrm{prime}}$ such that $\mathbb{Z}\\setminus S(\mathbf a)$ is finite?

The problem also asks about replacing the primes by a more general set $A\subseteq\mathbb{N}$ and analogous hypotheses on the size of $A$ and on $\sum_{n\in A,\,n\le N}\frac1n$.

QUICK LITERATURE/CONTEXT CHECK

As stated in the problem text, the case $k=3$ already appears difficult and (to the best of my knowledge) remains open. The problem suggests it may hold under stronger "prime-like" hypotheses on a general set $A$, and notes that for $k=1$ and $k=2$ the corresponding statement is known for any $A$ with $\sum_{n\in A}1/n=\infty$ (again, this is as stated in the problem source).

ATTACK PLAN

• Rephrase the question as an "asymptotic covering system" problem: choose one residue class modulo each prime $p$, but the progression only starts at $a_p+k p$.
• Observe that for a large integer $m$, only primes $p\le m/k$ can represent $m$. Thus the available moduli increase with $m$, but slowly.
• Use heuristics from random residue choices: for large $m$, the chance that $m$ avoids all chosen classes for primes $p\le m/k$ should be about $\prod_{p\le m/k}(1-1/p)\asymp 1/\log m$ (Mertens). This suggests the uncovered set might be very sparse, but sparseness does not imply finiteness.

WORK (PARTIAL RESULTS AND OBSERVATIONS)

1) Trivialities for small $k$.

• If $k=1$ and $A$ is the set of all primes, the choice $a_p\equiv 0$ covers every integer $m>1$: take $p$ a prime divisor of $m$, so $m=0+(m/p)p$ with $t=m/p\ge 1$.
• For $k\ge 2$, primes themselves become the obstruction: if $a_p\equiv 0$ for all $p$, then every composite number is covered with $t\ge 2$, but primes are not (since $p=0+1\cdot p$). One needs residues that also cover all sufficiently large primes using smaller primes.

2) A useful reformulation.

Fix residues $(a_p)$. An integer $m$ is covered if there exists a prime $p\le m/k$ with \[ m\equiv a_p \pmod p. \] (Indeed, if $m\equiv a_p\pmod p$ then $m=a_p+t p$ for some $t\ge 0$, and for $m$ large relative to $p$ this will force $t\ge k$; a sufficient condition is $m\ge (k+1)p$ since then $t\ge k$ regardless of the representative $a_p\in\{0,\dots,p-1\}$.)

So the problem is to choose one residue mod each prime so that every sufficiently large $m$ lies in at least one chosen class for a prime $p$ that is not too large relative to $m$.

3) Heuristic density.

If residues were chosen "randomly and independently", then for a fixed large $m$ the probability that $m\not\equiv a_p\pmod p$ is $1-1/p$. If we (very heuristically) pretend these are independent over primes $p\le m/k$, we get \[ \mathbb{P}(m\ \text{uncovered})\approx \prod_{p\le m/k}\Big(1-\frac1p\Big)\asymp \frac{c}{\log m}. \] This suggests that one might hope to cover all but finitely many integers, but the heuristic is far from a proof: it only indicates that the uncovered set might have density $0$.

VERIFICATION

For $k=3$, a concrete test would require choosing residues for many primes and checking coverage up to a large range. Such computations provide evidence but do not resolve the finiteness of the exceptional set; the published problem explicitly notes that even $k=3$ is difficult.

FINAL

FINAL: UNRESOLVED. The existence of such a choice of residues for $k\ge 3$ (in particular $k=3$) is an open problem as posed.

COMPLETION ESTIMATE

About 15%: restatement + basic observations + heuristic; no proof known for $k\ge 3$.