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:

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

Tenenbaum is interested and would exchange ideas.

Przemek Chojecki (19 March 2026) asks to learn and test Tenenbaum's ideas.
Tao links Tenenbaum's contact page.
Chojecki links a 13-page note and says it contains two unconditional

special cases plus a quotient-sieve strategy with obstacles.

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

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

Chojecki replies “Thank you!”
Desmond Weisenberg observes that if $n_1=1$, then $A=\varnothing$ and

its logarithmic density is $0$.

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.

(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.

(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.

(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).

(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.

(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.

(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<n_i$, and put

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:

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

$1\leq m<n\leq160$ with $(m,n)\leq G$, it checks directly that \[ \left(\frac m{(m,M)},\frac n{(n,M)}\right)=1,\qquad M=\operatorname{lcm}(1,\ldots,G). \] All 134,876 eligible pairs passed.

(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.

number of moduli	modulus sets	residue assignments	largest enumerated period
1	8	36	8
2	28	546	56
3	56	4536	280
4	70	22449	840

(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

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