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

Erdős problem #468 — wave 9l

Date of live check and computation: 2026-07-28 (UTC).

0. Mandatory live-page audit

I fetched the rendered public page through the Bright Data browser path: problem #468, its discussion thread, its LaTeX view, and its revision history. (The first request to the www host returned a Cloudflare 504; the non-www host then loaded successfully.)

Live status:

status: OPEN;
comments: 1;
claimed proofs: 0;
“Currently working on this problem”: None;
“Interested in collaborating”: None;
“This problem looks difficult”: None;
“This problem looks tractable”: None;
“The results on this problem could be formalisable”: None;
“I am working on formalising the results on this problem”: None;
likes: antonshakov, Vjeko_Kovac;
related OEIS entries: A167485, A387502, A387503.

Thus none of the requested stop conditions is present on page #468.

Verbatim current statement

For any $n$ let $D_n$ be the set of sums of the shape $d_1,d_1+d_2,d_1+d_2+d_3,\ldots$ where $1<d_1<d_2<\cdots$ are the divisors of $n$.
What is the size of $D_n\backslash \cup_{m<n}D_m$?
If $f(N)$ is the minimal $n$ such that $N\in D_n$ then is it true that $f(N)=o(N)$? Perhaps just for almost all $N$?

The page cites [ErGr80]: P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique 28 (1980), MR 0592420. I also inspected the scan of the original source; the question occurs on printed p. 93 and agrees with the live formulation.

The one live comment

The sole comment is by Vjeko Kovač, posted 2025-09-14. It is explicitly covered by the site's “comments are not verified” disclaimer. Its relevant claims/leads are:

It defines

\[ D'_n=D_n\setminus\bigcup_{m<n}D_m \] and points to OEIS A387502 for $|D'_n|$ and A387503 for the partial union sizes.

It reports many empty $D'_n$, and gives the conditional example that

infinitely many primes $r=pq+p+q$, with $p<q$ prime, would give $D'_r=\varnothing$. This is conditional on a special case of Schinzel's hypothesis, not a theorem.

Its reported strict-record indices are

\[ 2,12,36,144,336,1320,1980,5040,8400,25200,75600, \] ending with $|D'_{75600}|=24$; it suggests that large $\sigma(n)$ should correlate with large debut sets.

It reports cumulative counts $924,8697,83490$ through

$10^3,10^4,10^5$, respectively, i.e. means $0.924,0.8697,0.8349$.

It explains the shift to the including-1 function in Guy/OEIS A167485,

notes that the excluding-1 $f$ is undefined at $1,4$, and says suitable stronger Goldbach/Vinogradov statements would imply well-definedness elsewhere.

Its explicit experimental evidence says that 31.279% of

$N\le100000$ have $f(N)>100000$, and, for $5\le N\le10000$, fewer than 36%, 27%, and 6% of the ratios $f(N)/N$ are at most $1,0.9,0.5$, respectively. It also records the elementary $\liminf f(N)/N=0$ consequence obtained by taking $N=\sigma(n)-1$.

An edit says that Tao disproved the second part under problem #1054 and

that there were later quantitative upgrades. This lead is verified below; it is not being counted as a claimed proof on page #468.

1. Source/literature audit

I searched the exact wording, “initial subsequence(s) of the divisors,” “debut sums,” A387502, A387503, and the two problem numbers. The problem-specific sources found were:

the original Erdős–Graham source above;
A387502 and

A387503, both contributed in 2025 and with b-files through $n=10000$;

A167485, for the version which includes the

divisor 1;

Tao's 2025-11-01 proof sketch, now located in the

#1054 discussion;

Vjekoslav Kovač,

An improved bound in Erdős problem #1054, dated 2026-05-17.

The exact-phrase searches found no journal paper or arXiv preprint devoted to the first quantity $|D'_n|$. This is a search miss, not a proof that none exists.

For the including-1 function $g$, Kovač proves, building on Tao, that for some $c>0$, all sufficiently small $\delta>0$, and every $X\ge1$,

\#\{M\le X:g(M)\le\delta M\} \ll \exp\!\left(-\exp((1/\delta)^c)\right)X. \tag{1}

This is a source-verified result, not a new result of this run. Page #1054 is itself still marked OPEN and currently lists workers; I did not attempt its remaining questions.

The shift between the two conventions is exact:

f_{468}(N)=g(N+1). \tag{2}

Indeed, adding the initial divisor 1 adds exactly 1 to every nontrivial prefix sum. The verifier checks this set identity for every $m\le250$. Consequently (1) disproves both the pointwise and “almost all” versions of $f_{468}(N)=o(N)$, up to the harmless shift. Classification: (b) rigorous modulo the cited Tao–Kovač theorem.

The rest of this report addresses the first, still-open question.

2. Notation

Put

a(n)=\left|D_n\setminus\bigcup_{m<n}D_m\right|, \qquad U(x)=\left|\bigcup_{m\le x}D_m\right|.

The debut sets are disjoint, so

U(x)=\sum_{n\le x}a(n). \tag{3}

For an integer $m$, write its positive divisors as

1=r_1<r_2<\cdots<r_t=m

and let $\sigma_j(m)$ be the sum left after deleting the $j$ largest divisors. Thus $0\le j\le t-1$ below. Every $N\in D_m$ has the form

N=\sigma_j(m)-1 \quad\text{for some }0\le j\le t-2. \tag{4}

3. Elementary first-part bound obtained in this run

Theorem

For all integers $x\ge1$ and all real $y>0$,

\#\left\{N\in\bigcup_{m\le x}D_m:N>y\right\} \le \frac{\pi^2x^2}{3y}. \tag{5}

Consequently,

U(x)\le y+\frac{\pi^2x^2}{3y}, \qquad U(x)\le\frac{2\pi}{\sqrt3}\,x =3.6275987284\ldots\,x. \tag{6}

In particular,

\frac1x\sum_{n\le x}a(n)\le\frac{2\pi}{\sqrt3}, \tag{7}

so $a(n)$ is bounded on average by an absolute explicit constant. Moreover, for every $K>0$,

\#\{n\le x:a(n)\ge K\}\le\frac{2\pi}{K\sqrt3}\,x. \tag{8}

All of (5)–(8) are classification (a), elementary-rigorous.

Proof

Reflecting the divisor list via $r_i r_{t+1-i}=m$ gives

\frac{\sigma_j(m)}m=\sum_{i=j+1}^{t}\frac1{r_i}.

Therefore

\sum_{j=0}^{t-1}\frac{\sigma_j(m)}m =\sum_{i=1}^{t}\frac{i}{r_i}. \tag{9}

The index $i$ is exactly the number of divisors $d\mid m$ with $d\le r_i$. Summing (9) over $m\le x$, then interchanging the finite sums, gives the exact identity

\begin{aligned} S(x) &:=\sum_{m\le x}\sum_{j=0}^{\tau(m)-1}\frac{\sigma_j(m)}m\\ &=\sum_{1\le d\le r}\frac1r \left\lfloor\frac{x}{[d,r]}\right\rfloor. \tag{10} \end{aligned}

Here $[d,r]$ is the least common multiple.

The corresponding infinite coefficient sum is explicitly evaluable:

\begin{aligned} C &:=\sum_{1\le d\le r}\frac1{r[d,r]}\\ &=\sum_{\substack{g\ge1,\ a\le b\\(a,b)=1}} \frac1{g^2ab^2}\\ &=\zeta(2) \sum_{\substack{a\le b\\(a,b)=1}}\frac1{ab^2}. \tag{11} \end{aligned}

Möbius inversion and absolute convergence show

\begin{aligned} \sum_{\substack{a\le b\\(a,b)=1}}\frac1{ab^2} &=\sum_{q\ge1}\frac{\mu(q)}{q^3} \sum_{a\le b}\frac1{ab^2}\\ &=\frac1{\zeta(3)}\sum_{b\ge1}\frac{H_b}{b^2}=2. \tag{12} \end{aligned}

For completeness, the last Euler sum is $\sum_{b\ge1}H_b/b^2=2\zeta(3)$. One direct proof writes

\sum_{b\ge1}\frac{H_b}{b^2} =\int_0^1\frac{\zeta(2)-\operatorname{Li}_2(x)}{1-x}\,dx

and uses $\zeta(2)-\operatorname{Li}_2(x) =\operatorname{Li}_2(1-x)+\log x\log(1-x)$; the two resulting integrals both equal $\zeta(3)$, by termwise integration of absolutely convergent series.

It follows from (11)–(12) that

C=2\zeta(2)=\frac{\pi^2}{3}. \tag{13}

Equation (10) and $\lfloor x/[d,r]\rfloor\le x/[d,r]$ now give the finite, uniform estimate

S(x)\le\frac{\pi^2}{3}x. \tag{14}

In fact, dominated convergence in (10) also gives the exact auxiliary asymptotic $S(x)\sim(\pi^2/3)x$.

For each distinct $N\in\bigcup_{m\le x}D_m$ with $N>y$, choose one representing pair $(m,j)$ from (4). Then $\sigma_j(m)=N+1>y$, and since $m\le x$,

1<\frac{x}{y}\frac{\sigma_j(m)}m.

Thus the number of selected pairs, and hence of such $N$, is at most

\frac{x}{y}S(x)\le\frac{\pi^2x^2}{3y},

which proves (5). There are at most $\lfloor y\rfloor\le y$ positive integers $N\le y$, proving the first inequality in (6). Taking $y=\pi x/\sqrt3$ proves the second. Equations (7) and (8) follow from (3) and Markov's inequality. $\square$

What this does and does not settle

The theorem gives a uniform $O(1)$ Cesàro bound for the quantity Erdős and Graham asked about. It does not prove that $a(n)$ is pointwise bounded, that it is unbounded, that $U(x)/x$ has a limit, or that a positive density of the $a(n)$ vanish. Those remain open here.

The exact obstacle is collision/minimality: (10) controls the weighted number of all representations, whereas $a(n)$ asks which prefix sums first occur at exactly $n$. An asymptotic for $U(x)$, or a pointwise description of $a(n)$, needs a lemma controlling collisions among $\sigma_j(m)$ with different $(m,j)$. Neither the first-moment argument above nor the higher-moment Tao–Kovač machinery supplies that lower-bound/minimality information.

4. Exact computation through $10^6$

Classification of every statement in this section: (d), computational-only, despite exhaustive exact arithmetic in the stated finite range.

The standalone verifier runs/erdos468_wave9l_verify.py uses two independent standard-library algorithms.

Factor-stream algorithm. It builds a smallest-prime-factor table,

factors each $n$, generates and sorts its divisors, and inserts its prefix sums into a set while processing $n=1,2,\ldots$. A sum is a debut exactly when the set has not seen it.

Global divisor sweep. It never factors individual integers.

Sweeping $d=2,3,\ldots,x$ over all multiples generates the divisors of every $n$ in increasing order. For every generated prefix $s$, it stores the least $n$ producing $s$, and recovers $a(n)$ by counting those least indices.

The two arrays $a(1),\ldots,a(10^6)$ agree term by term. They also agree with the complete A387502 b-file through $10^4$, and with the live comment's cumulative counts through $10^5$.

Checkpoints

The zero count includes the vacuous $a(1)=0$.

| $x$ | $U(x)=\sum_{n\le x}a(n)$ | number of $a(n)=0$ | $\max_{n\le x}a(n)$ | |---:|---:|---:|---:| | 10 | 9 | 1 | 1 | | 100 | 102 | 33 | 4 | | 1,000 | 924 | 439 | 7 | | 10,000 | 8,697 | 4,959 | 16 | | 100,000 | 83,490 | 51,760 | 24 | | 1,000,000 | 811,945 | 532,169 | 32 |

Thus the measured mean at $10^6$ is $0.811945$, and 532,168 of the 999,999 indices $2\le n\le10^6$ have $a(n)=0$.

Strict records

| $n$ | $a(n)$ | |---:|---:| | 2 | 1 | | 12 | 3 | | 36 | 4 | | 144 | 6 | | 336 | 7 | | 1,320 | 8 | | 1,980 | 10 | | 5,040 | 12 | | 8,400 | 16 | | 25,200 | 22 | | 75,600 | 24 | | 240,240 | 25 | | 277,200 | 29 | | 942,480 | 32 |

The last three extend the record list in the live comment. Their explicit debut certificates are:

n=240240 (25):
56254, 61624, 73687, 106742, 117922, 123928, 144232, 170060,
180070, 190990, 202430, 214442, 229457, 245473, 262633, 281113,
301133, 322973, 346997, 451387, 499435, 559495, 639575, 759695,
999935

n=277200 (29):
74034, 130889, 142824, 155724, 162654, 178274, 186674, 205814,
216902, 228452, 241052, 254252, 268112, 283512, 300837, 319317,
339117, 362217, 387417, 415137, 445937, 480587, 520187, 566387,
621827, 691127, 783527, 922127, 1199327

n=942480 (32):
350105, 375435, 519788, 540732, 562152, 584592, 608154, 661262,
688982, 748958, 782618, 821888, 864728, 909608, 956732, 1009092,
1064532, 1123437, 1186269, 1253589, 1332129, 1417809, 1512057,
1616777, 1734587, 1869227, 2026307, 2214803, 2450423, 2764583,
3235823, 4178303

For every listed value, both algorithms independently verify (i) that it is a prefix sum for the displayed $n$ and (ii) that no smaller positive integer produces it.

Complete finite certificate summary

The histogram a(n) -> number of indices, for $1\le n\le10^6$, is

0:532169, 1:292433, 2:101609, 3:34193, 4:17816, 5:9473,
6:5031, 7:2739, 8:1594, 9:963, 10:641, 11:402, 12:273,
13:216, 14:133, 15:85, 16:64, 17:53, 18:29, 19:21,
20:19, 21:12, 22:10, 23:7, 24:5, 25:2, 26:2, 27:1,
28:1, 29:3, 32:1.

The largest prefix sum generated by an $n\le10^6$ is 4,390,847. The canonical SHA-256 of the one-byte sequence a(1),...,a(1000000) is

d23bc50738ae2066183f9c8e99fe2cfcf4c3d89896575df7858be491242d7169

5. Reproduction

From the repository root:

python3 runs/erdos468_wave9l_verify.py

The script uses no network and no nonstandard packages. On the final run on this VM it took 13.8 seconds. Besides recomputing the million terms twice, it:

compares every term between the two algorithms;
compares the first 100 terms to the embedded current OEIS data;
compares every record's actual debut set between the algorithms;
checks the checkpoint table, histogram, record list, maximum prefix,

and SHA-256 certificate;

exactly checks (9) and (10), using rational arithmetic, through $x=250$;
exactly checks finite truncations of the Möbius and gcd/lcm

decompositions in (11)–(12);

checks the convention shift (2) at the set level through $m=250$.

The observed terminal line was PASS.

6. Claim ledger

(a) Elementary-rigorous: identities (3)–(14), the tail bound (5),

the mean bound $2\pi/\sqrt3$, and its Markov consequence.

(b) Rigorous modulo named/source-checked theorem: the Tao–Kovač

disproof and quantitative strengthening for the second question, transferred by the exact shift (2).

(c) Plausible/structural-unverified: the live comment's Schinzel

heuristic for infinitely many empty debut sets, any limiting density suggested by the finite data, and unboundedness of $a(n)$.

(d) Computational-only: all claims restricted to $n\le10^6$,

including the three new record indices and explicit debut lists.

No uniformity or infinitude claim has been inferred from the finite table, and the open first question is not claimed solved.

PARTIAL: proved the elementary uniform mean bound $\sum_{n\le x}|D'_n|\le(2\pi/\sqrt3)x$ and independently certified all values through $10^6$, finding new records 25, 29, and 32 at $240240,277200,942480$.

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