Erdoes #25 - working report - Erdős Problem a Day

Erdős problem 25 — wave 7a

Access date: 2026-07-27 UTC.

Claim labels

(a) elementary-rigorous: proved below from elementary counting, prime

factorisation, and the Chinese remainder theorem.

(b) rigorous-modulo-named-theorem: depends on the named theorem stated

at the point of use.

(c) plausible/structural-unverified: heuristic, search miss, or an

unchecked claim by somebody else.

(d) computational-only: established only by the stated finite

computation.

Outcome

(a) I prove a new positive regime relative to the results listed in the

live discussion: if

\[ \sup_{i\ne j}(n_i,n_j)<\infty, \]

then the set in the problem has a natural density, and I give that density

as an explicit finite sum of infinite products. Consequently, any

counterexample to problem 25 must have unbounded pairwise gcds among its

moduli.

This does not settle the unrestricted question. Its value is that it cleanly

removes every system whose shared prime-power part is bounded, leaving

unbounded common factors as a necessary obstruction. This agrees with, but

does not prove, the linked note's structural diagnosis that prime-power towers

are the hard case.

Step 0: mandatory live-page gate

I used the Bright Data browser, not direct curl, to read

<https://www.erdosproblems.com/25>, its LaTeX view, and its discussion thread.

The standalone verifier can repeat this with --audit-live.

Verbatim current statement

The following is copied verbatim from the live page's LaTeX view:

> Let $1\leq n_1<n_2<\cdots$ be an arbitrary sequence of integers, each with an associated residue class $a_i\pmod{n_i}$. Let $A$ be the set of integers $n$ such that for every $i$ either $n<n_i$ or $n\not\equiv a_i\pmod{n_i}$. Must the logarithmic density of $A$ exist?

Status and markers

(d) The live page reported:

status: OPEN;
0 claimed proofs for this problem;
Currently working on this problem: None;
Interested in collaborating: None;
likes: Svyable and holyterror;
all “looks difficult”, “looks tractable”, and formalisation-work markers:

None;

formalised statement: Yes;
seven comments;
last page edit: 20 January 2026;
listed relation: “This is a special case of [486].”

Therefore the requested stop condition was not triggered. In particular, the

structured “currently working” marker is None. A comment says Gérald

Tenenbaum is interested in the problem, but it does not mark him or anyone

else as a current worker.

The page expands [Er95] to Paul Erdős, *Some of my favourite problems in

number theory, combinatorics, and geometry*, Resenhas (1995), 165–186,

MR 1370501.

All discussion content relevant to the gate

(d) The live thread contains the following seven non-deleted comments,

plus one deleted-post placeholder:

1. Terence Tao (18 January 2026; moved from problem 486) says Gérald

Tenenbaum is interested and would exchange ideas.

2. Przemek Chojecki (19 March 2026) asks to learn and test Tenenbaum's ideas.

3. Tao links Tenenbaum's contact page.

4. Chojecki links a 13-page note and says it contains two unconditional

special cases plus a quotient-sieve strategy with obstacles.

5. Nat Sothanaphan says a “standard check” finds one minor issue and points

to the second-to-last message of a linked shared conversation.

6. Chojecki replies “Thank you!”

7. Desmond Weisenberg observes that if $n_1=1$, then $A=\varnothing$ and

its logarithmic density is $0$.

8. One older post is displayed only as [Post deleted].

The site itself warns that comments are user-supplied and unverified. I

therefore do not use any comment as ground truth.

Primary-source and current-state audit

The verifier downloads each PDF, runs pdftotext, checks phrases supporting

the claims below, and records SHA-256 hashes.

1. (d) Erdős 1995, official journal PDF

exists and says that Davenport and Erdős proved logarithmic density for

sets of multiples, then asks the activated one-or-several-residue question

and says it seems difficult even for one residue. This verifies that the

live statement represents the cited original source.

2. (d) Araújo, arXiv:2602.24031v1

exists. Theorem 3.25 gives the activated multi-residue problem a natural

density under the light-tail condition

$\sum_i |R_i|/b_i<\infty$. The paper's general sieve framework uses

pairwise-coprime ideal supports; it does not settle the unrestricted

singleton problem.

3. (d) [Chojecki, *Truncated Congruence Sieves and Erdős Problem

25*](https://www.ulam.ai/research/erdos25.pdf), dated 19 March 2026, exists.

It proves in its text the summable and pairwise-coprime cases, gives a

conditional quotient-sieve reduction, and explicitly ends with the full

problem still open. Because the live thread also reports a minor checking

issue, I treat the note's un-reproved conditional material as (c).

4. (d) [Filaseta–Ford–Konyagin–Pomerance–Yu,

arXiv:math/0507374](https://arxiv.org/abs/math/0507374), *Sieving by large

integers and covering systems of congruences*, exists. Its finite-system

Lemma 3.1 decomposes a residue system by a fixed smooth kernel

$M$ and the quotients $n/(n,M)$. That finite decomposition is a clear

precursor to the argument below. I did not find the infinite activated

bounded-gcd theorem stated there.

5. (d) The live problem-486 proof-claims page currently lists one proposed

negative proof, submitted 16 July 2026 by Shouqiao Wang. The linked

PDF explicitly

says that it relies on grouping many residues at one modulus and **does not

settle problem 25**, the singleton case. Thus this does not trigger the

problem-25 skip rule or supply a counterexample here.

6. (d) Exact-phrase searches for problem 25, its statement, truncated

congruence sieves, bounded gcds, and the quotient

$n/(n,M)$ found the live page, the Chojecki note, Araújo's paper, and the

finite FFKPY decomposition, but no additional primary source directly

stating the theorem below. (c) This search miss is not a claim of

novelty or completeness.

The successful citation-audit hashes were:

| source | bytes | SHA-256 |

|---|---:|---|

| Er95 | 190123 | a4c59e58e15fc7fa6d84a52da523e639b81697e61fc1095294690268b15708ce |

| Chojecki note | 105740 | 678f553c52a94dca80f47c21e2a3066d44e0b9cd870c229d6b3534e4b1edbf78 |

| Araújo v1 | 649923 | ad80095c9d6dd4847c321fff069d51b407d5df67a439b5b6882c2c7bf81d80ab |

| FFKPY | 244877 | 60ee1a563d7306b14e3df04474cef4e59f1e0cec45ce9cc16bd2ec4b70e8e0c2 |

| Wang problem-486 claim | 350612 | 01ce6f1d22b0c9208cc45ecaa15039f0ee13ea75c334908ca65f371c365b9048 |

Main theorem: a finite coprime kernel

Normalize \(0\leq a_i \[ B_i=\{a_i+n_i t:t=1,2,\ldots\}. \]

Then the activated definition in the live statement is exactly

$A=\mathbb N\setminus\bigcup_i B_i$.

Theorem

(a) Suppose there is a fixed integer $M\geq1$ such that

\[ q_i:=\frac{n_i}{(n_i,M)} \]

are pairwise coprime. For $b\in\{0,\ldots,M-1\}$, define

\[ d_i=(n_i,M),\qquad I_b=\{i:a_i\equiv b\pmod {d_i}\}, \]

and interpret each infinite product as the decreasing limit of its finite

partial products. Then $A$ has natural density

\[ \boxed{\quad d(A)=\frac1M\sum_{b=0}^{M-1} \prod_{i\in I_b}\left(1-\frac1{q_i}\right). \quad} \tag{1} \]

A factor with $q_i=1$ makes its product zero.

Proof

(a), finite truncations. Let

\[ A^{(K)}=\mathbb N\setminus\bigcup_{i\leq K}B_i. \]

This differs only finitely from the set avoiding the first $K$ complete

congruence cylinders, so it has the same density.

Fix $b\pmod M$ and write $x=b+Mt$. The simultaneous congruences

\[ x\equiv b\pmod M,\qquad x\equiv a_i\pmod {n_i} \]

are incompatible unless $a_i\equiv b\pmod {d_i}$. When compatible, division

by $d_i$ gives

\[ \frac{M}{d_i}t\equiv\frac{a_i-b}{d_i}\pmod {q_i}. \]

Because $d_i=(M,n_i)$,

$(M/d_i,q_i)=1$, so this excludes exactly one residue of $t\pmod {q_i}$.

The $q_i$ are pairwise coprime, hence the Chinese remainder theorem gives

\[ d\bigl(A^{(K)}\cap(b+M\mathbb Z)\bigr) =\frac1M\prod_{\substack{i\leq K\\i\in I_b}} \left(1-\frac1{q_i}\right). \tag{2} \]

(a), passage to the activated infinite system. Denote the limit of the

product in (2) by $P_b$. Since $A\subseteq A^{(K)}$,

\[ \overline d\bigl(A\cap(b+M\mathbb Z)\bigr)\leq P_b/M. \tag{3} \]

If $P_b=0$, (3) already proves density zero in this ambient class.

Suppose $P_b>0$. There is no factor $q_i=1$, and

\[ \sum_{i\in I_b}\frac1{q_i}<\infty, \tag{4} \]

because $1/q\leq-\log(1-1/q)$ and the positive infinite product has a

finite logarithm.

The activation threshold is crucial here. For every $X$,

\[ \#(B_i\cap[1,X])\leq \frac{X}{n_i}; \tag{5} \]

there is no $+1$ endpoint loss, since the representative below $n_i$ is

precisely the point omitted by activation. Therefore

\[ \begin{aligned} \#\bigl((A^{(K)}\cap(b+M\mathbb Z))\setminus A\bigr)\cap[1,X] &\leq \sum_{\substack{i>K\\i\in I_b}}\#(B_i\cap[1,X])\\ &\leq X\sum_{\substack{i>K\\i\in I_b}}\frac1{n_i}\\ &\leq X\sum_{\substack{i>K\\i\in I_b}}\frac1{q_i}. \tag{6} \end{aligned} \]

Use (2), take the lower limit as $X\to\infty$, then let $K\to\infty$.

The tail in (6) vanishes by (4), giving the reverse inequality to (3).

Thus the density in each of the finitely many classes $b\pmod M$ is

$P_b/M$. Summing those classes proves (1).

Bounded-gcd corollary

Corollary

(a) If there is a fixed $G$ such that

\[ (n_i,n_j)\leq G\qquad(i\ne j), \]

then the theorem applies with

\[ M=\operatorname{lcm}(1,2,\ldots,G). \]

In particular, $A$ has a natural density and hence a logarithmic density.

Proof

(a) Suppose a prime $p$ divided both

$q_i=n_i/(n_i,M)$ and $q_j=n_j/(n_j,M)$. Put

$e=v_p(M)$. Then

\[ v_p(n_i)\geq e+1,\qquad v_p(n_j)\geq e+1. \]

For $M=\operatorname{lcm}(1,\ldots,G)$, $p^{e+1}>G$. It follows that

\[ (n_i,n_j)\geq p^{e+1}>G, \]

a contradiction. Thus the quotients $q_i$ are pairwise coprime, and the

theorem applies.

What this isolates

(a) Every hypothetical counterexample to problem 25 must have

\[ \sup_{i\ne j}(n_i,n_j)=\infty. \]

The linked pairwise-coprime result is the special case $G=1$. The present

argument permits arbitrary repeated small-prime structure so long as the

total shared prime-power kernel remains bounded.

Explicit nonsummable example outside the two previously listed cases

(a) Let $p$ run through the odd primes, in increasing order, and take

\[ n_p=2p,\qquad a_p=p\pmod {2p}. \]

These moduli are not pairwise coprime:

$(2p,2q)=2$ for distinct odd primes. They also lie outside the summable

case because

\[ \sum_p\frac1{n_p}=\frac12\sum_{p\text{ odd}}\frac1p=\infty. \]

For completeness, the divergence follows from the elementary Euler-product

argument: if $\sum_p1/p$ converged, then

$\prod_p(1-1/p)^{-1}$ would be bounded, whereas its partial product over

$p\leq y$ is at least $H_{\lfloor y\rfloor}$, which diverges.

The survivor set has an exact description:

\[ \boxed{\quad A=2\mathbb N\ \cup\ \{1\}\ \cup\ \{\text{odd primes}\}.\quad} \tag{7} \]

Indeed, even integers cannot be $p\pmod{2p}$; $1$ and odd primes have no

active prime divisor condition; and if $m$ is odd composite, choose

$p\mid m$. Then $m/p$ is odd and at least $3$, so

$m\geq2p$ and $m\equiv p\pmod{2p}$, which deletes $m$.

(a) The primes have natural density zero. One elementary proof is to fix

$y$, put $P_y=\prod_{p\leq y}p$, and observe that every prime above $y$

lies in one of the $\varphi(P_y)$ reduced classes modulo $P_y$. Hence its

upper density is at most

$\varphi(P_y)/P_y=\prod_{p\leq y}(1-1/p)$, which is at most $1/H_y$ by

the same finite Euler-product comparison and tends to zero.

Equation (7) therefore gives

\[ d(A)=\frac12. \]

This is a concrete infinite instance covered by the bounded-gcd theorem but

by neither the summable nor pairwise-coprime special case.

Independent finite verification

The standalone checker is

runs/erdos25_wave7a_verify.py. It uses only the Python standard library for

the mathematical checks. It performs three independent recomputations:

1. (d) For every $1\leq G\leq12$ and every

\(1\leq m

\[ \left(\frac m{(m,M)},\frac n{(n,M)}\right)=1,\qquad M=\operatorname{lcm}(1,\ldots,G). \]

All 134,876 eligible pairs passed.

2. (d) For every set of one to four distinct moduli from

$\{1,\ldots,8\}$, and every possible assignment of residues, it directly

enumerates one full lcm period and compares the survivor proportion with

formula (1). All 27,567 residue systems passed exactly as rational

numbers.

|---:|---:|---:|---:|

| 1 | 8 | 36 | 8 |

| 2 | 28 | 546 | 56 |

| 3 | 56 | 4536 | 280 |

| 4 | 70 | 22449 | 840 |

3. (d) For the explicit system $n_p=2p,a_p=p$, it independently sieves

every integer through $10^6$ using the activated progressions and checks

(7) point by point. It also checks the exact finite-period density for the

first six odd primes.

| first $k$ odd primes | exact finite density | period |

|---:|---:|---:|

| 1 | $5/6$ | 6 |

| 2 | $23/30$ | 30 |

| 3 | $51/70$ | 210 |

| 4 | $109/154$ | 2310 |

| 5 | $1385/2002$ | 30030 |

| 6 | $23161/34034$ | 510510 |

The activated counts also matched

$\#(A\cap[1,X])=\lfloor X/2\rfloor+\pi(X)$:

| $X$ | $\pi(X)$ | survivors | survivors/$X$ |

|---:|---:|---:|---:|

| 100 | 25 | 75 | 0.750000 |

| 1,000 | 168 | 668 | 0.668000 |

| 10,000 | 1,229 | 6,229 | 0.622900 |

| 100,000 | 9,592 | 59,592 | 0.595920 |

| 1,000,000 | 78,498 | 578,498 | 0.578498 |

Reproduction

python runs/erdos25_wave7a_verify.py
python runs/erdos25_wave7a_verify.py --audit-citations
python runs/erdos25_wave7a_verify.py --audit-live

The first command is an offline mathematical audit. The second re-downloads

and text-checks the five primary PDFs. The third uses Bright Data to re-check

the current problem-25 page, its comments, and the related problem-486 claim

page. All three completed successfully on this VM.

Exact remaining wall

(a) The bounded-gcd theorem removes all systems for which shared factors

can be absorbed into one fixed finite kernel. It cannot handle a sequence

with unbounded $(n_i,n_j)$, because no fixed $M$ then makes all quotient

moduli pairwise coprime.

(c) The linked Chojecki note identifies the same remaining phenomenon in

more local language: repeated prime-power towers can create first-kill sets

whose early harmonic mass is much larger than their eventual density loss.

The missing uniform statement is a quotient-sieve harmonic estimate with

global charges $\tau_i$ satisfying

\[ \sum_{n_i\leq X}\frac{\tau_i}{n_i}=o(\log X). \]

Neither the present finite-kernel decomposition nor the cited papers provide

that estimate for arbitrary unbounded common factors. A finite computation

cannot close this uniform infinite-scale gap.

PARTIAL: Proved that bounded pairwise gcds force an explicit natural density, so every counterexample must have unbounded common factors; verified 27,567 finite systems and an exact nonsummable gcd-2 example.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger