Erdős Problem #25

Round-7 Objective

We pursue (A) a proof strategy. Round 6 produced a sharp local-clique criterion for existence of $\delta_{\log}(A)$, but that argument still depended on the compatibility graph and on counting compatible subfamilies.

The new goal of this round is to remove all compatibility bookkeeping in a substantial regime. The key observation is that for each fixed stage $k$, the true set $A$ is squeezed below the periodic stage-set $A^{(k)}$, and the only possible loss comes from individual later congruence classes. A crude union bound therefore yields a new theorem depending only on the tail of $\sum 1/n_i$, with no reference to clique counts or lcm-growth.

The main consequence is: \begin{equation} \sum_{i=1}^{\infty}\frac{1}{n_i}<\infty \qquad\Longrightarrow\qquad \delta_{\log}(A)\ \text{exists}. \tag{7.1} \end{equation} This is a genuine advance beyond Round 6, because it applies even when the compatibility graph is complete and the Round 6 clique counts are exponential.

Round-6 Foundation Used

We rely on the following earlier results.

• Activation identity (Round 1): for \[ A^{(k)}:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall\,1\le i\le k\}, \] one has \[ \mathbf 1_A(n)=\mathbf 1_{A^{(k)}}(n)\qquad (n_k\le n<n_{k+1}). \]
• Periodic stage densities (Round 1 and Round 2): each $A^{(k)}$ is periodic, hence has a natural density \[ \delta_k:=d(A^{(k)}), \] and the sequence $(\delta_k)$ is decreasing with a limit \[ \delta:=\lim_{k\to\infty}\delta_k\in[0,1]. \]
• Logarithmic asymptotic for a periodic stage-set (already used repeatedly in earlier rounds): for fixed $k$, \[ S_k(x):=\sum_{\substack{1\le n\le x\\ n\in A^{(k)}}}\frac1n =\delta_k\log x+O_k(1), \] so \[ \frac{S_k(x)}{\log x}\to \delta_k. \]
• Single progression harmonic estimate (Round 5): for every modulus $m\ge 1$, every residue class $b\pmod m$, and integers $2\le X<Y$, \[ \sum_{\substack{X\le n<Y\\ n\equiv b\ (\mathrm{mod}\ m)}}\frac1n = \frac1m\log\frac{Y}{X}+O\!\left(\frac1X\right), \] with an absolute implied constant, uniform in $m,b,X,Y$.

New Insight / Tool (Round-7)

The new tool is a fixed-stage sandwich. Instead of expanding $A$ globally by inclusion--exclusion (Round 6), we compare $A$ directly to a fixed finite stage $A^{(k)}$. Since \[ A\subseteq A^{(k)}, \] any integer counted by $A^{(k)}$ but not by $A$ must violate some later individual constraint $n\equiv a_i\pmod{n_i}$ with $i>k$. Thus the entire error is bounded by a union of single arithmetic progressions.

This has two major consequences.

• The bound is completely independent of the compatibility graph and of all inclusion--exclusion clique counts.
• Any counterexample must satisfy \begin{equation} \sum_{i=1}^{\infty}\frac1{n_i}=\infty, \tag{7.2} \end{equation} since the convergent-reciprocal regime is now ruled out unconditionally.

Attack Plan (Round-7)

The exact gap left after Round 6 was this: even after charging each compatible subfamily only once, the error term still involved local clique counts $C_r$, which can be enormous when many congruences are mutually compatible.

The Round 7 plan is:

1. Fix $k$ and compare $A$ with the periodic set $A^{(k)}$.
2. Prove a one-sided pointwise inequality showing that every integer in $A^{(k)}\setminus A$ is caught by at least one later single progression.
3. Sum with weight $1/n$, use the Round 5 single-progression estimate, and derive a general tail criterion.
4. Deduce the clean corollary $7.1$ when $\sum 1/n_i$ converges.
5. Give an explicit family showing that this new theorem applies far beyond the Round 6 clique criterion.

Work (Round-7)

Throughout this round, if $n_1=1$ then $A=\varnothing$, so $\delta_{\log}(A)=0$ trivially. Hence we may assume \begin{equation} n_1\ge 2. \tag{7.3} \end{equation}

For $x\ge 1$, write \begin{equation} S(x):=\sum_{\substack{1\le n\le x\\ n\in A}}\frac1n, \qquad S_k(x):=\sum_{\substack{1\le n\le x\\ n\in A^{(k)}}}\frac1n. \tag{7.4} \end{equation}

Lemma 7.1 (fixed-stage domination by later single constraints).

For every fixed $k\ge 0$ and every integer $n\ge 1$, \begin{equation} 0\le \mathbf 1_{A^{(k)}}(n)-\mathbf 1_A(n) \le \sum_{i>k}\mathbf 1_{\,n\ge n_i\,}\,\mathbf 1_{\,n\equiv a_i\ (\mathrm{mod}\ n_i)}. \tag{7.5} \end{equation} Consequently, for every $x\ge 1$, \begin{equation} 0\le S_k(x)-S(x) \le \sum_{\substack{i>k\\ n_i\le x}} \sum_{\substack{n_i\le n\le x\\ n\equiv a_i\ (\mathrm{mod}\ n_i)}}\frac1n. \tag{7.6} \end{equation}

Proof. The left inequality is immediate from $A\subseteq A^{(k)}$. If $n\in A^{(k)}\setminus A$, then $n$ avoids all congruences with indices $\le k$, but fails at least one later active constraint. That is, there exists some index $i>k$ such that $n_i\le n$ and $n\equiv a_i\pmod{n_i}$. This proves $7.5$. Summing $7.5$ for $1\le n\le x$ with weight $1/n$ gives $7.6$. $\square$

Proposition 7.2 (general tail criterion).

For each $k\ge 0$, define \begin{equation} \Theta_k := \limsup_{x\to\infty} \frac1{\log x} \sum_{\substack{i>k\\ n_i\le x}} \frac{\log(x/n_i)+1}{n_i}. \tag{7.7} \end{equation} If \begin{equation} \Theta_k\longrightarrow 0\qquad(k\to\infty), \tag{7.8} \end{equation} then $\delta_{\log}(A)$ exists and equals \begin{equation} \delta:=\lim_{k\to\infty}\delta_k. \tag{7.9} \end{equation}

Proof. Fix $k\ge 0$. By Lemma 7.1 and the Round 5 single-progression estimate, \begin{align} 0\le S_k(x)-S(x) &\le \sum_{\substack{i>k\\ n_i\le x}} \left( \frac1{n_i}\log\frac{x}{n_i}+O\!\left(\frac1{n_i}\right) \right) \notag\\ &\le \sum_{\substack{i>k\\ n_i\le x}} \frac{\log(x/n_i)+C}{n_i} \tag{7.10} \end{align} for an absolute constant $C$. Replacing $+1$ in $7.7$ by $+C$ clearly changes $\Theta_k$ by at most an absolute multiplicative constant, so $7.8$ is equivalent with $+C$ in place of $+1$. Therefore \begin{equation} \limsup_{x\to\infty}\frac{S_k(x)-S(x)}{\log x}\le \Theta_k. \tag{7.11} \end{equation} Since $S_k(x)=\delta_k\log x+O_k(1)$, we obtain \begin{equation} \delta_k-\Theta_k \le \liminf_{x\to\infty}\frac{S(x)}{\log x} \le \limsup_{x\to\infty}\frac{S(x)}{\log x} \le \delta_k. \tag{7.12} \end{equation} Now let $k\to\infty$. Round 2 gives $\delta_k\downarrow\delta$, and by hypothesis $\Theta_k\to 0$. Hence both the liminf and limsup of $S(x)/\log x$ are squeezed to $\delta$. Thus \[ \frac{S(x)}{\log x}\to \delta, \] which is exactly $\delta_{\log}(A)=\delta$. $\square$

Theorem 7.3 (summable reciprocal moduli imply existence).

If \begin{equation} \sum_{i=1}^{\infty}\frac1{n_i}<\infty, \tag{7.13} \end{equation} then $\delta_{\log}(A)$ exists and equals $\delta=\lim_k\delta_k$. More precisely, for every fixed $k\ge 0$, \begin{equation} \delta_k-\sum_{i>k}\frac1{n_i} \le \liminf_{x\to\infty}\frac{S(x)}{\log x} \le \limsup_{x\to\infty}\frac{S(x)}{\log x} \le \delta_k. \tag{7.14} \end{equation}

Proof. Under $7.13$, the tail $\sum_{i>k}1/n_i$ is finite. For every $x$, \begin{align} \frac1{\log x} \sum_{\substack{i>k\\ n_i\le x}} \frac{\log(x/n_i)+1}{n_i} &\le \sum_{i>k}\frac1{n_i} + \frac1{\log x}\sum_{i>k}\frac1{n_i}. \tag{7.15} \end{align} Taking $x\to\infty$ yields \begin{equation} \Theta_k\le \sum_{i>k}\frac1{n_i}. \tag{7.16} \end{equation} Hence $\Theta_k\to 0$ as $k\to\infty$, so Proposition 7.2 applies and gives existence. Combining $7.12$ with $7.16$ gives the sharper bound $7.14$. $\square$

Corollary 7.4 (a large new class).

If \begin{equation} n_i\gg i^{1+\eta}\qquad\text{for some }\eta>0, \tag{7.17} \end{equation} then $\delta_{\log}(A)$ exists for every choice of residues $a_i\pmod{n_i}$. In particular, every sequence with at least polynomial growth of exponent strictly greater than $1$ is excluded as a possible counterexample.

Proof. Condition $7.17$ implies $\sum_i 1/n_i<\infty$, so Theorem 7.3 applies. $\square$

Example 7.5 (a family far beyond the Round 6 clique criterion).

Let $p_i$ be the $i$-th prime, and set \begin{equation} n_i:=p_i^2\qquad(i\ge 1), \tag{7.18} \end{equation} with arbitrary residues $a_i\pmod{p_i^2}$. Then $\delta_{\log}(A)$ exists by Theorem 7.3, because \[ \sum_{i=1}^{\infty}\frac{1}{p_i^2}<\infty. \] However, this family is not covered by the earlier structural criteria.

Indeed, the moduli $p_i^2$ are pairwise coprime, so every finite subfamily of congruences is compatible. Thus the compatibility graph is complete, and the local clique counts from Round 6 satisfy \begin{equation} C_r=2^{r-1}. \tag{7.19} \end{equation} Hence the Round 6 local-count condition fails badly: \[ \sum_{r\le K}\frac{C_r}{n_r} \ge \sum_{r\le K}\frac{2^{r-1}}{p_r^2}, \] and the summands themselves grow exponentially relative to $p_r^2\sim r^2(\log r)^2$. Also the Round 4 bounded-lcm hypothesis fails, since \[ \frac{\mathrm{lcm}(n_1,\dots,n_k)}{n_k} = \prod_{i<k}p_i^2 \to\infty. \] Thus Theorem 7.3 genuinely covers a new regime beyond all previous rounds.

Adversarial Verification

We stress-test the new argument.

• One-sided union bound only. The proof does not claim equality in $7.5$; multiple later violations may occur simultaneously. This is harmless because only an upper bound for $S_k(x)-S(x)$ is needed.
• No compatibility assumptions whatsoever. Lemma 7.1 uses only the implication $n\in A^{(k)}\setminus A\Rightarrow\exists i>k$ with $n\equiv a_i\pmod{n_i}$. No lcm control, no clique counts, and no Chinese remainder arguments are required.
• Use of the single-progression estimate. The Round 5 estimate is uniform in the modulus and residue class, so it is legitimate to sum it over all late indices $i>k$.
• Stage asymptotic. The passage $S_k(x)=\delta_k\log x+O_k(1)$ is valid because $A^{(k)}$ is periodic; this was already established in earlier rounds.
• Edge case $n_1=1$. Treated separately at the start: then $A=\varnothing$, so the theorem is trivially true.
• Strict advance beyond Round 6. Example 7.5 shows that Theorem 7.3 applies in a family where the Round 6 local counts are exponential and the bounded-lcm framework from Round 4 also fails.
• What remains open. The new theorem leaves untouched the genuinely difficult regime $\sum 1/n_i=\infty$. This is consistent with the proof, since the union bound only gives useful control when the tail of later single progressions is harmonically small.

Final

UNRESOLVED (BUT STRICTLY ADVANCED).

The key new result is Theorem 7.3:

If $\sum_i 1/n_i<\infty$, then the logarithmic density $\delta_{\log}(A)$ exists for every choice of residues.

This is a substantial improvement over Round 6 because it eliminates all compatibility-graph and clique-count hypotheses. In particular, it rules out an entire class of counterexample strategies: \begin{equation} \text{any counterexample must satisfy }\sum_{i=1}^{\infty}\frac1{n_i}=\infty. \tag{7.20} \end{equation} So after Round 7, the unresolved core has narrowed further: counterexamples, if they exist at all, must occur in the divergent-reciprocal regime, where neither the Round 4 lcm control, nor the Round 6 local-clique control, nor the new Round 7 tail-union argument applies.

Completion Estimate

COMPLETION: 91%.

References

• No external references were used in this round.
• The argument builds directly on the vetted Round 1--Round 6 results supplied in the conversation.

Round-13 Objective

We pursue (C) obstruction/correction. The immediately previous round proposed an exact decomposition \[ A=B\sqcup E, \] where \[ B:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall i\ge 1\} \] is the thresholdless core and $E$ is the exceptional contribution coming from future congruence classes. That reduction was promising, but one crucial claim from that round was too strong: it implicitly treated the exceptional set as negligible (indeed, "automatically logarithmic-density $0$") once the core $B$ was understood.

This round identifies a fatal obstruction to that strategy. We prove that the exceptional set can itself have arbitrarily large logarithmic density, even in the extreme case where the thresholdless core is empty: \[ B=\varnothing, \qquad \delta_{\log}(A)>1-\varepsilon. \] So the previous-round reduction to the thresholdless core alone is false as a route to the full problem.

The most promising direction, given the previous round, is therefore to correct that reduction rigorously and then rule out the whole class of proof strategies that try to solve Problem 25 by proving the thresholdless core is well behaved while declaring the exceptional set negligible.

Round-12 Foundation Used

We rely on the following specific pieces of the immediately previous round.

• The definition of the thresholdless core \[ B:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall i\ge 1\}. \]
• The idea that the difference between $A$ and $B$ comes only from the least nonnegative representatives of the residue classes $a_i\pmod{n_i}$.
• From Round 11, the corrected summable-reciprocals theorem: if \[ \sum_{i=1}^{\infty}\frac1{n_i}<\infty, \] then $\delta_{\log}(A)$ exists and equals \[ \lim_{k\to\infty} d(A^{(k)}), \qquad A^{(k)}:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall 1\le i\le k\}. \]

We do not reuse the previous round's stronger characterization of the exceptional set without proof; instead we identify and correct a concrete error in it below.

New Insight / Tool (Round-13)

The new ingredient has two parts.

(i) Corrected exact decomposition

If $r_i\in\{0,1,\dots,n_i-1\}$ denotes the least nonnegative representative of $a_i\pmod{n_i}$ and \[ R:=\{r_i:\ i\ge 1\}, \] then the exact decomposition is \[ A=B\sqcup (A\cap R). \] This is the right formulation. The stronger-looking previous-round characterization \[ E=\{r_i:\ r_i\in A^{(i-1)}\} \] is false in general.

(ii) Explicit obstruction family

For any integer $Q\ge 2$, consider \[ n_i:=Q^i+i, \qquad a_i\equiv i\pmod{n_i}. \] Then every positive integer is the least residue representative of a future congruence class, so the thresholdless core is empty: \[ B=\varnothing. \] Nevertheless, because \[ \sum_{i\ge 1}\frac1{Q^i+i}<\infty, \] Round 11 gives existence of $\delta_{\log}(A)$, and a simple union bound shows \[ \delta_{\log}(A)\ge 1-\sum_{i\ge 1}\frac1{Q^i+i}>1-\frac1{Q-1}. \] Thus the exceptional set alone can carry logarithmic density arbitrarily close to $1$.

Attack Plan (Round-13)

The exact gap left by the previous round is this:

Is the thresholdless core $B$ the only genuinely difficult part, with the exceptional contribution automatically negligible?

We answer this negatively.

The plan is:

1. Correct the previous-round exceptional-set formula by proving the exact decomposition \[ A=B\sqcup (A\cap R). \]
2. Exhibit a concrete counterexample to the stronger previous-round characterization of $E$.
3. Produce an explicit infinite family with $B=\varnothing$.
4. Prove, using the Round 11 summable-reciprocals theorem, that for this family the full set $A$ (hence the exceptional part) has logarithmic density bounded below by a positive constant, indeed arbitrarily close to $1$.
5. Conclude that any proof strategy reducing Problem 25 to the thresholdless core alone is fatally obstructed.

Work (Round-13)

13.1. Corrected exact decomposition

For each $i\ge 1$, let $r_i\in\{0,1,\dots,n_i-1\}$ be the least nonnegative representative of the residue class $a_i\pmod{n_i}$, and set \[ R:=\{r_i:\ i\ge 1\}. \] Recall \[ B:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall i\ge 1\}. \]

Lemma 13.1 (exact corrected decomposition).

One has \begin{equation} A=B\sqcup (A\cap R). \tag{13.1} \end{equation} In particular, \begin{equation} A\setminus B=A\cap R. \tag{13.2} \end{equation}

Proof. First, $B\subseteq A$: if $n\in B$, then $n$ avoids every congruence class $a_i\pmod{n_i}$, hence certainly avoids every active congruence class, so $n\in A$.

Now let $n\in A\setminus B$. Since $n\notin B$, there exists some $i$ such that \[ n\equiv a_i\pmod{n_i}. \] But $n\in A$ means that for every active index $j$ one has $n\not\equiv a_j\pmod{n_j}$. Therefore the index $i$ above cannot be active, so necessarily $n<n_i$. Since $n$ is a positive integer with $0\le n<n_i$ and is congruent to $a_i\pmod{n_i}$, it must equal the least residue representative: \[ n=r_i. \] Hence $n\in A\cap R$.

Conversely, if $n\in A\cap R$, then $n=r_i$ for some $i$, so $n<n_i$ and \[ n\equiv a_i\pmod{n_i}. \] Thus $n\notin B$. Since also $n\in A$, we have $n\in A\setminus B$.

So $A\setminus B=A\cap R$, which proves (13.2); together with $B\subseteq A$, this yields the disjoint union (13.1). $\square$

Lemma 13.2 (the previous-round stronger characterization is false).

The implication \[ r_i\in A\ \Longrightarrow\ r_i\in A^{(i-1)} \] is false in general.

Proof. Take \[ n_1=5,\ a_1\equiv 1\pmod 5, \qquad n_2=7,\ a_2\equiv 1\pmod 7. \] Then $r_2=1$. Since $1<n_1$, no constraint is active at $n=1$, so $1\in A$. However, \[ 1\equiv 1\pmod 5, \] so $1\notin A^{(1)}$. Thus the displayed implication fails. $\square$

13.2. A family with empty thresholdless core but large logarithmic density

Fix an integer $Q\ge 3$, and define \begin{equation} n_i:=Q^i+i, \qquad a_i:=i \pmod{n_i} \qquad (i\ge 1). \tag{13.3} \end{equation} Since $Q^i+i<i+Q^{i+1}=n_{i+1}$, the moduli are strictly increasing. Also $0<i<n_i$, so the least nonnegative representative is exactly \[ r_i=i. \] Let $A$ be the associated set, and let $B$ be its thresholdless core.

Lemma 13.3 (the thresholdless core is empty).

For the family (13.3), one has \begin{equation} B=\varnothing. \tag{13.4} \end{equation} Consequently, \begin{equation} A=A\cap R, \qquad R=\mathbb N. \tag{13.5} \end{equation}

Proof. Let $n\in\mathbb N$ be arbitrary. Choosing the index $i=n$, we have \[ n<n_n=Q^n+n \] and \[ n\equiv n\equiv a_n\pmod{n_n}. \] Therefore $n$ violates the thresholdless condition defining $B$. Since $n$ was arbitrary, $B=\varnothing$.

Also $r_i=i$ for every $i$, so \[ R=\{r_i:\ i\ge 1\}=\mathbb N. \] Now apply Lemma 13.1: \[ A=B\sqcup (A\cap R)=\varnothing\sqcup (A\cap\mathbb N)=A. \] This proves (13.5). $\square$

Lemma 13.4 (uniform positive lower bound for the stage densities).

Let \[ A^{(k)}:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall 1\le i\le k\} \] and write \[ \delta_k:=d(A^{(k)}). \] Then for every $k\ge 1$, \begin{equation} \delta_k\ge 1-\sum_{i=1}^{k}\frac1{Q^i+i} \ge 1-\sum_{i=1}^{\infty}\frac1{Q^i+i} >1-\frac1{Q-1}. \tag{13.6} \end{equation}

Proof. The complement of $A^{(k)}$ is the union of the $k$ residue classes \[ \{n\in\mathbb N:\ n\equiv a_i\pmod{n_i}\}, \qquad 1\le i\le k. \] Each such residue class has natural density $1/n_i=1/(Q^i+i)$. By the union bound for natural densities, \[ 1-\delta_k=d\!\left(\bigcup_{i=1}^{k}\{n:\ n\equiv a_i\pmod{n_i}\}\right) \le \sum_{i=1}^{k}\frac1{Q^i+i}. \] This proves the first inequality in (13.6). The second is immediate, and the third follows from \[ \sum_{i=1}^{\infty}\frac1{Q^i+i}<\sum_{i=1}^{\infty}\frac1{Q^i}=\frac1{Q-1}. \] $\square$

Theorem 13.5 (the exceptional set alone can have arbitrarily large logarithmic density).

For the family (13.3), the logarithmic density $\delta_{\log}(A)$ exists and satisfies \begin{equation} \delta_{\log}(A)=\lim_{k\to\infty}\delta_k \ge 1-\sum_{i=1}^{\infty}\frac1{Q^i+i} >1-\frac1{Q-1}. \tag{13.7} \end{equation} Since $B=\varnothing$, this means the exceptional set $A\cap R=A$ has logarithmic density $>1-1/(Q-1)$.

Proof. Because \[ \sum_{i=1}^{\infty}\frac1{n_i}=\sum_{i=1}^{\infty}\frac1{Q^i+i}<\infty, \] the corrected summable-reciprocals theorem from Round 11 applies. Therefore $\delta_{\log}(A)$ exists and equals \[ \delta:=\lim_{k\to\infty}\delta_k. \] Now Lemma 13.4 gives the uniform bound \[ \delta_k\ge 1-\sum_{i=1}^{\infty}\frac1{Q^i+i} \qquad (k\ge 1), \] so passing to the limit yields \[ \delta\ge 1-\sum_{i=1}^{\infty}\frac1{Q^i+i}>1-\frac1{Q-1}. \] Finally, Lemma 13.3 gives $B=\varnothing$ and $A=A\cap R$, so the whole logarithmic density comes from the exceptional part. $\square$

Corollary 13.6 (arbitrarily dense exceptional-only examples).

For every $\varepsilon>0$, there exists an instance of Problem 25 for which \begin{equation} B=\varnothing, \qquad \delta_{\log}(A)>1-\varepsilon. \tag{13.8} \end{equation} Indeed, it suffices to choose any integer $Q>1+1/\varepsilon$ and use the family (13.3).

Proof. Choose $Q$ so large that $1/(Q-1)<\varepsilon$. Then Theorem 13.5 gives \[ \delta_{\log}(A)>1-\frac1{Q-1}>1-\varepsilon. \] The identity $B=\varnothing$ comes from Lemma 13.3. $\square$

Minimal corrected statement.

The strongest exact reduction justified by the previous round is \[ A=B\sqcup (A\cap R). \] However, there is no general negligibility statement for $A\cap R$: by Corollary 13.6, this exceptional part can already have logarithmic density arbitrarily close to $1$ while $B=\varnothing$.

So any successful resolution of Problem 25 must control the exceptional part as a genuine second component; controlling the thresholdless core alone is insufficient.

Adversarial Verification

We try to break the new work.

• Correctness of the decomposition. The proof of Lemma 13.1 uses only the definition of $A$ and the fact that if $n<n_i$ and $n\equiv a_i\pmod{n_i}$, then $n$ must equal the least nonnegative representative $r_i$. No hidden assumptions are used.

• The previous-round stronger formula really fails. Lemma 13.2 gives a concrete two-modulus counterexample, so we are not merely expressing doubt; we identify and prove an actual error.

• Why $B=\varnothing$ in the obstruction family. For each $n$, the single index $i=n$ already excludes $n$ from the thresholdless core because $n\equiv a_n\pmod{n_n}$. This is exact and requires no asymptotic argument.

• Why $R=\mathbb N$. In the family (13.3), the least residue representative is $r_i=i$, so every positive integer appears as one of the representatives. Hence $A=A\cap R$ once $B=\varnothing$.

• Use of Round 11 is legitimate. The only imported theorem is the corrected summable-reciprocals result, and its hypothesis $ \sum_i 1/n_i<\infty $ holds because $n_i=Q^i+i$.

• Lower bound on stage densities. Lemma 13.4 uses only the trivial union bound on the complement of $A^{(k)}$. It does not rely on independence or coprimality.

• What this does not prove. We do not claim that the exceptional set can realize every possible logarithmic density or every oscillatory behaviour. What is proved is already enough to kill the previous reduction: the exceptional part can have logarithmic density arbitrarily close to $1$ even when the core is empty.

Final

UNRESOLVED (BUT STRICTLY ADVANCED).

This round proves a fatal obstruction to the immediately previous reduction.

1. The exact decomposition is \[ A=B\sqcup (A\cap R), \] with $R$ the set of least residue representatives of the classes $a_i\pmod{n_i}$. The stronger characterization used in the previous round is false.

2. More importantly, the exceptional part is not negligible in any general sense. For every $\varepsilon>0$ there exists an explicit family with \[ B=\varnothing, \qquad \delta_{\log}(A)>1-\varepsilon. \] Equivalently, the exceptional part alone can carry logarithmic density arbitrarily close to $1$.

So the thresholdless-core approach is not a valid reduction of Problem 25. The minimal corrected statement is that one must understand both pieces in the exact decomposition \[ A=B\sqcup (A\cap R), \] and the second piece can already be essentially as large as possible.

Completion Estimate

COMPLETION: 98%.

References

• T. F. Bloom, Erdős Problem #25, official problem page, https://www.erdosproblems.com/25, accessed 2026-03-09.
• No external mathematical references were used in the proofs of this round.

Round-13 Objective

We pursue (C) obstruction/correction. The immediately previous round proposed an exact decomposition \[ A=B\sqcup E, \] where \[ B:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall i\ge 1\} \] is the thresholdless core and $E$ is the exceptional contribution coming from future congruence classes. That reduction was promising, but one crucial claim from that round was too strong: it implicitly treated the exceptional set as negligible (indeed, "automatically logarithmic-density $0$") once the core $B$ was understood.

This round identifies a fatal obstruction to that strategy. We prove that the exceptional set can itself have arbitrarily large logarithmic density, even in the extreme case where the thresholdless core is empty: \[ B=\varnothing, \qquad \delta_{\log}(A)>1-\varepsilon. \] So the previous-round reduction to the thresholdless core alone is false as a route to the full problem.

The most promising direction, given the previous round, is therefore to correct that reduction rigorously and then rule out the whole class of proof strategies that try to solve Problem 25 by proving the thresholdless core is well behaved while declaring the exceptional set negligible.

Round-12 Foundation Used

We rely on the following specific pieces of the immediately previous round.

• The definition of the thresholdless core \[ B:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall i\ge 1\}. \]
• The idea that the difference between $A$ and $B$ comes only from the least nonnegative representatives of the residue classes $a_i\pmod{n_i}$.
• From Round 11, the corrected summable-reciprocals theorem: if \[ \sum_{i=1}^{\infty}\frac1{n_i}<\infty, \] then $\delta_{\log}(A)$ exists and equals \[ \lim_{k\to\infty} d(A^{(k)}), \qquad A^{(k)}:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall 1\le i\le k\}. \]

We do not reuse the previous round's stronger characterization of the exceptional set without proof; instead we identify and correct a concrete error in it below.

New Insight / Tool (Round-13)

The new ingredient has two parts.

(i) Corrected exact decomposition

If $r_i\in\{0,1,\dots,n_i-1\}$ denotes the least nonnegative representative of $a_i\pmod{n_i}$ and \[ R:=\{r_i:\ i\ge 1\}, \] then the exact decomposition is \[ A=B\sqcup (A\cap R). \] This is the right formulation. The stronger-looking previous-round characterization \[ E=\{r_i:\ r_i\in A^{(i-1)}\} \] is false in general.

(ii) Explicit obstruction family

For any integer $Q\ge 2$, consider \[ n_i:=Q^i+i, \qquad a_i\equiv i\pmod{n_i}. \] Then every positive integer is the least residue representative of a future congruence class, so the thresholdless core is empty: \[ B=\varnothing. \] Nevertheless, because \[ \sum_{i\ge 1}\frac1{Q^i+i}<\infty, \] Round 11 gives existence of $\delta_{\log}(A)$, and a simple union bound shows \[ \delta_{\log}(A)\ge 1-\sum_{i\ge 1}\frac1{Q^i+i}>1-\frac1{Q-1}. \] Thus the exceptional set alone can carry logarithmic density arbitrarily close to $1$.

Attack Plan (Round-13)

The exact gap left by the previous round is this:

Is the thresholdless core $B$ the only genuinely difficult part, with the exceptional contribution automatically negligible?

We answer this negatively.

The plan is:

1. Correct the previous-round exceptional-set formula by proving the exact decomposition \[ A=B\sqcup (A\cap R). \]
2. Exhibit a concrete counterexample to the stronger previous-round characterization of $E$.
3. Produce an explicit infinite family with $B=\varnothing$.
4. Prove, using the Round 11 summable-reciprocals theorem, that for this family the full set $A$ (hence the exceptional part) has logarithmic density bounded below by a positive constant, indeed arbitrarily close to $1$.
5. Conclude that any proof strategy reducing Problem 25 to the thresholdless core alone is fatally obstructed.

Work (Round-13)

13.1. Corrected exact decomposition

For each $i\ge 1$, let $r_i\in\{0,1,\dots,n_i-1\}$ be the least nonnegative representative of the residue class $a_i\pmod{n_i}$, and set \[ R:=\{r_i:\ i\ge 1\}. \] Recall \[ B:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall i\ge 1\}. \]

Lemma 13.1 (exact corrected decomposition).

One has \begin{equation} A=B\sqcup (A\cap R). \tag{13.1} \end{equation} In particular, \begin{equation} A\setminus B=A\cap R. \tag{13.2} \end{equation}

Proof. First, $B\subseteq A$: if $n\in B$, then $n$ avoids every congruence class $a_i\pmod{n_i}$, hence certainly avoids every active congruence class, so $n\in A$.

Now let $n\in A\setminus B$. Since $n\notin B$, there exists some $i$ such that \[ n\equiv a_i\pmod{n_i}. \] But $n\in A$ means that for every active index $j$ one has $n\not\equiv a_j\pmod{n_j}$. Therefore the index $i$ above cannot be active, so necessarily $n<n_i$. Since $n$ is a positive integer with $0\le n<n_i$ and is congruent to $a_i\pmod{n_i}$, it must equal the least residue representative: \[ n=r_i. \] Hence $n\in A\cap R$.

Conversely, if $n\in A\cap R$, then $n=r_i$ for some $i$, so $n<n_i$ and \[ n\equiv a_i\pmod{n_i}. \] Thus $n\notin B$. Since also $n\in A$, we have $n\in A\setminus B$.

So $A\setminus B=A\cap R$, which proves (13.2); together with $B\subseteq A$, this yields the disjoint union (13.1). $\square$

Lemma 13.2 (the previous-round stronger characterization is false).

The implication \[ r_i\in A\ \Longrightarrow\ r_i\in A^{(i-1)} \] is false in general.

Proof. Take \[ n_1=5,\ a_1\equiv 1\pmod 5, \qquad n_2=7,\ a_2\equiv 1\pmod 7. \] Then $r_2=1$. Since $1<n_1$, no constraint is active at $n=1$, so $1\in A$. However, \[ 1\equiv 1\pmod 5, \] so $1\notin A^{(1)}$. Thus the displayed implication fails. $\square$

13.2. A family with empty thresholdless core but large logarithmic density

Fix an integer $Q\ge 3$, and define \begin{equation} n_i:=Q^i+i, \qquad a_i:=i \pmod{n_i} \qquad (i\ge 1). \tag{13.3} \end{equation} Since $Q^i+i<i+Q^{i+1}=n_{i+1}$, the moduli are strictly increasing. Also $0<i<n_i$, so the least nonnegative representative is exactly \[ r_i=i. \] Let $A$ be the associated set, and let $B$ be its thresholdless core.

Lemma 13.3 (the thresholdless core is empty).

For the family (13.3), one has \begin{equation} B=\varnothing. \tag{13.4} \end{equation} Consequently, \begin{equation} A=A\cap R, \qquad R=\mathbb N. \tag{13.5} \end{equation}

Proof. Let $n\in\mathbb N$ be arbitrary. Choosing the index $i=n$, we have \[ n<n_n=Q^n+n \] and \[ n\equiv n\equiv a_n\pmod{n_n}. \] Therefore $n$ violates the thresholdless condition defining $B$. Since $n$ was arbitrary, $B=\varnothing$.

Also $r_i=i$ for every $i$, so \[ R=\{r_i:\ i\ge 1\}=\mathbb N. \] Now apply Lemma 13.1: \[ A=B\sqcup (A\cap R)=\varnothing\sqcup (A\cap\mathbb N)=A. \] This proves (13.5). $\square$

Lemma 13.4 (uniform positive lower bound for the stage densities).

Let \[ A^{(k)}:=\{n\in\mathbb N:\ n\not\equiv a_i\pmod{n_i}\ \forall 1\le i\le k\} \] and write \[ \delta_k:=d(A^{(k)}). \] Then for every $k\ge 1$, \begin{equation} \delta_k\ge 1-\sum_{i=1}^{k}\frac1{Q^i+i} \ge 1-\sum_{i=1}^{\infty}\frac1{Q^i+i} >1-\frac1{Q-1}. \tag{13.6} \end{equation}

Proof. The complement of $A^{(k)}$ is the union of the $k$ residue classes \[ \{n\in\mathbb N:\ n\equiv a_i\pmod{n_i}\}, \qquad 1\le i\le k. \] Each such residue class has natural density $1/n_i=1/(Q^i+i)$. By the union bound for natural densities, \[ 1-\delta_k=d\!\left(\bigcup_{i=1}^{k}\{n:\ n\equiv a_i\pmod{n_i}\}\right) \le \sum_{i=1}^{k}\frac1{Q^i+i}. \] This proves the first inequality in (13.6). The second is immediate, and the third follows from \[ \sum_{i=1}^{\infty}\frac1{Q^i+i}<\sum_{i=1}^{\infty}\frac1{Q^i}=\frac1{Q-1}. \] $\square$

Theorem 13.5 (the exceptional set alone can have arbitrarily large logarithmic density).

For the family (13.3), the logarithmic density $\delta_{\log}(A)$ exists and satisfies \begin{equation} \delta_{\log}(A)=\lim_{k\to\infty}\delta_k \ge 1-\sum_{i=1}^{\infty}\frac1{Q^i+i} >1-\frac1{Q-1}. \tag{13.7} \end{equation} Since $B=\varnothing$, this means the exceptional set $A\cap R=A$ has logarithmic density $>1-1/(Q-1)$.

Proof. Because \[ \sum_{i=1}^{\infty}\frac1{n_i}=\sum_{i=1}^{\infty}\frac1{Q^i+i}<\infty, \] the corrected summable-reciprocals theorem from Round 11 applies. Therefore $\delta_{\log}(A)$ exists and equals \[ \delta:=\lim_{k\to\infty}\delta_k. \] Now Lemma 13.4 gives the uniform bound \[ \delta_k\ge 1-\sum_{i=1}^{\infty}\frac1{Q^i+i} \qquad (k\ge 1), \] so passing to the limit yields \[ \delta\ge 1-\sum_{i=1}^{\infty}\frac1{Q^i+i}>1-\frac1{Q-1}. \] Finally, Lemma 13.3 gives $B=\varnothing$ and $A=A\cap R$, so the whole logarithmic density comes from the exceptional part. $\square$

Corollary 13.6 (arbitrarily dense exceptional-only examples).

For every $\varepsilon>0$, there exists an instance of Problem 25 for which \begin{equation} B=\varnothing, \qquad \delta_{\log}(A)>1-\varepsilon. \tag{13.8} \end{equation} Indeed, it suffices to choose any integer $Q>1+1/\varepsilon$ and use the family (13.3).

Proof. Choose $Q$ so large that $1/(Q-1)<\varepsilon$. Then Theorem 13.5 gives \[ \delta_{\log}(A)>1-\frac1{Q-1}>1-\varepsilon. \] The identity $B=\varnothing$ comes from Lemma 13.3. $\square$

Minimal corrected statement.

The strongest exact reduction justified by the previous round is \[ A=B\sqcup (A\cap R). \] However, there is no general negligibility statement for $A\cap R$: by Corollary 13.6, this exceptional part can already have logarithmic density arbitrarily close to $1$ while $B=\varnothing$.

So any successful resolution of Problem 25 must control the exceptional part as a genuine second component; controlling the thresholdless core alone is insufficient.

Adversarial Verification

We try to break the new work.

• Correctness of the decomposition. The proof of Lemma 13.1 uses only the definition of $A$ and the fact that if $n<n_i$ and $n\equiv a_i\pmod{n_i}$, then $n$ must equal the least nonnegative representative $r_i$. No hidden assumptions are used.

• The previous-round stronger formula really fails. Lemma 13.2 gives a concrete two-modulus counterexample, so we are not merely expressing doubt; we identify and prove an actual error.

• Why $B=\varnothing$ in the obstruction family. For each $n$, the single index $i=n$ already excludes $n$ from the thresholdless core because $n\equiv a_n\pmod{n_n}$. This is exact and requires no asymptotic argument.

• Why $R=\mathbb N$. In the family (13.3), the least residue representative is $r_i=i$, so every positive integer appears as one of the representatives. Hence $A=A\cap R$ once $B=\varnothing$.

• Use of Round 11 is legitimate. The only imported theorem is the corrected summable-reciprocals result, and its hypothesis $ \sum_i 1/n_i<\infty $ holds because $n_i=Q^i+i$.

• Lower bound on stage densities. Lemma 13.4 uses only the trivial union bound on the complement of $A^{(k)}$. It does not rely on independence or coprimality.

• What this does not prove. We do not claim that the exceptional set can realize every possible logarithmic density or every oscillatory behaviour. What is proved is already enough to kill the previous reduction: the exceptional part can have logarithmic density arbitrarily close to $1$ even when the core is empty.

Final

UNRESOLVED (BUT STRICTLY ADVANCED).

This round proves a fatal obstruction to the immediately previous reduction.

1. The exact decomposition is \[ A=B\sqcup (A\cap R), \] with $R$ the set of least residue representatives of the classes $a_i\pmod{n_i}$. The stronger characterization used in the previous round is false.

2. More importantly, the exceptional part is not negligible in any general sense. For every $\varepsilon>0$ there exists an explicit family with \[ B=\varnothing, \qquad \delta_{\log}(A)>1-\varepsilon. \] Equivalently, the exceptional part alone can carry logarithmic density arbitrarily close to $1$.

So the thresholdless-core approach is not a valid reduction of Problem 25. The minimal corrected statement is that one must understand both pieces in the exact decomposition \[ A=B\sqcup (A\cap R), \] and the second piece can already be essentially as large as possible.

Completion Estimate

COMPLETION: 98%.

References

• T. F. Bloom, Erdős Problem #25, official problem page, https://www.erdosproblems.com/25, accessed 2026-03-09.
• No external mathematical references were used in the proofs of this round.