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

Erdős problem #839 — wave w017

Date: 2026-07-28 UTC

Claim labels

[a] elementary-rigorous: proved here without an external theorem.
[b] rigorous-modulo-named-theorem: a rigorous consequence of the

explicitly named published result.

[c] plausible/structural-unverified: a heuristic, search miss, or

extrapolation, not claimed as a theorem.

[d] computational-only/source-verified: an exact finite computation or a

direct observation from a fetched source. The finite claims are recomputed by runs/erdos839_wavew017_reverify.py.

0. Mandatory live-page and collision check

[d: live-page observation] I fetched <https://www.erdosproblems.com/839> and its discussion thread through the Bright Data cloud browser on 2026-07-28. The rendered page says OPEN.

The current statement, copied verbatim from the page's LaTeX view, is:

Let $1\leq a_1<a_2<\cdots$ be a sequence of integers such that no $a_i$ is the sum of consecutive $a_j$ for $j<i$. Is it true that\[\limsup \frac{a_n}{n}=\infty?\]Or even\[\lim \frac{1}{\log x}\sum_{a_n<x}\frac{1}{a_n}=0?\]

[d: page-listed context] The page says that Erdős observed all of the following:

it is possible to have finite $\liminf a_n/n$;
one can have

$\sum_{a_n<x}1/a_n\gg\log\log x$;

upper density $1/2$ is possible;
Erdős guessed that upper density greater than $1/2$ was impossible, but

Freud constructed an infinite sequence of upper density $19/36$.

It links the original references [Er78f] and [Er92c], Freud [Fr93], and related problems #359 and #867.

[d: complete marker audit]

| live-page field | value | |---|---:| | status | OPEN | | comments | 2 | | claimed proofs | 0 | | interested in collaborating | None | | currently working on this problem | None | | formalised statement? | No |

The two comments were also read:

[d] FlaredRain, 20:36 on 11 May 2026, gives the elementary

two-term-sum argument \[ A(x)\leq \frac23x+O(\log x),\qquad \sum_{a_n<x}\frac1{a_n}\leq\frac23\log x+O(1), \] then offers a heuristic based on the forbidden sums of all block lengths. The comment explicitly says the analysis and heuristic were developed with AI assistance and says the full limits remain open. Section 3 below audits the rigorous part from scratch and identifies the gap in the heuristic.

[d] BorisAlexeev, 17:18 on 2 September 2025, points out Freud's

construction with upper density greater than $1/2$ and refers to #867. The page says it was updated in response.

The site labels comments as unverified user content. There is no claimed proof and no current worker, so the mandatory stop condition did not apply.

1. Equivalent density formulation

For an infinite valid sequence $A=\{a_1<a_2<\cdots\}$, put

A(x)=|\{n:a_n<x\}|.

Lemma [a].

\limsup_{n\to\infty}\frac{a_n}{n}=\infty \quad\Longleftrightarrow\quad \liminf_{x\to\infty}\frac{A(x)}x=0.

Proof. If $a_{n_r}/n_r\to\infty$, then

\frac{A(a_{n_r})}{a_{n_r}} =\frac{n_r-1}{a_{n_r}}\longrightarrow0.

Conversely, take $x_r\to\infty$ with $A(x_r)/x_r\to0$ and put $m_r=A(x_r)$. Since the sequence is infinite, $a_{m_r+1}\geq x_r$, and hence

\frac{a_{m_r+1}}{m_r+1} \geq\frac{x_r}{A(x_r)+1}\longrightarrow\infty.

$\square$

Thus the first question asks whether every infinite valid path has lower asymptotic density zero. The second asks for the stronger vanishing of its logarithmic density.

2. Primary-source and literature audit

Sources actually checked

[d] The official Hardy–Ramanujan Journal page and PDF for P. Erdős,

Some of my forgotten problems in number theory, Hardy–Ramanujan Journal 15 (1992), 34–50, DOI 10.46298/hrj.1992.125, exist. On journal pages 42–43 Erdős states this problem in terms of lower and logarithmic density, records the $\gg\log\log x$ construction, and discusses the then-conjectured $1/2$ finite/upper-density boundary.

[d] The live bibliography identifies [Er78f] as P. Erdős,

On some unusual nonconventional problems in additive number theory, Matematikai Lapok 30 (1978/82), 9–14, MR 734602. The Rényi publication catalogue corroborates that bibliographic entry, but its PDF link is misassigned to Erdős's different paper on prime factors of binomial coefficients. I therefore did not use an unverified reconstruction of the Hungarian article's contents.

[d] The complete scan of R. Freud,

Adding numbers—on a problem of P. Erdős, James Cook Mathematical Notes 6 (1993), 6199–6202, is present in issue 60. The article gives:

a finite family with $76y-7$ terms below $144y-12$;
the limiting proportion $19/36$;
a block-splicing argument producing an infinite sequence with

$\limsup A(x)/x=19/36$;

an early report of improvements by Coppersmith and Phillips.

The standalone checker independently reconstructs the finite family for $1\leq y\leq20$; see Section 5.

[d] Don Coppersmith and Steven Phillips,

On a Question of Erdös on Subsequence Sums, SIAM Journal on Discrete Mathematics 9 (1996), 173–177, DOI 10.1137/S0895480193244139, exists. Its publisher abstract defines exactly the finite problem and states a construction of size $13N/24-O(1)$ and an upper bound with $\epsilon=1/512$. The related live page #867 gives the current finite bounds as \[ \frac{13}{24}N-O(1) \leq f(N) \leq \left(\frac23-\frac1{512}\right)N+\log N. \] Freud's 1993 note had reported the weaker prepublication saving $1/3584$; the published abstract says $1/512$.

[b: Coppersmith–Phillips 1996] These are uniform bounds for the finite extremal function $f(N)$. They do not prove that one nested infinite sequence has lower density zero, nor does the finite $13/24$ construction automatically splice into an infinite sequence with that upper density.

Search miss

[c] Exact-title, exact-phrase, DOI-citation, and statement searches found the two original Erdős records, Freud 1993, Coppersmith–Phillips 1996, and Guy's later problem-book citation. They found no later primary paper directly improving the infinite lower-density or logarithmic-density questions. This is an honest search report, not a claim that no such paper exists. No arXiv identifier is asserted for Freud or Coppersmith–Phillips.

3. Audit of the $2/3$ argument

Let $A$ be any finite or infinite valid sequence, with the same counting function $A(x)$.

Lemma [a]. For every integer $y\geq1$,

A(4y)-A(y)\leq 2y+1.

Proof. List the $k=A(2y)-A(y)$ elements of $A\cap[y,2y)$ as $b_1<\cdots<b_k$. Consecutive elements in this list are also consecutive in the full sequence. Thus, when $k\geq2$, the $k-1$ integers

b_1+b_2<b_2+b_3<\cdots<b_{k-1}+b_k

are distinct, lie in $[2y,4y)$, and are forbidden from $A$. The latter interval contains exactly $2y$ integers, so

A(4y)-A(2y)\leq 2y-(k-1).

Adding $k$ proves the claim. The cases $k=0,1$ satisfy the same bound directly. $\square$

Corollary [a].

A(x)\leq\frac23x+O(\log x).

Proof. The preceding proof works for real $y$ with an absolute $O(1)$ endpoint error. Apply it successively at $y=x/4,x/16,\ldots$, down to $y<1$. The left sides telescope, while

2\left(\frac{x}{4}+\frac{x}{16}+\cdots\right)=\frac23x

and the endpoint errors contribute $O(\log x)$. $\square$

Corollary [a].

\sum_{a_n<x}\frac1{a_n} \leq\frac23\log x+O(1).

Proof. Partial summation gives

\sum_{a_n<x}\frac1{a_n} =\frac{A(x)}x+\int_1^x\frac{A(t)}{t^2}\,dt+O(1/x).

Insert the preceding bound; the error integrates absolutely because $\int_1^\infty(\log t)t^{-2}\,dt<\infty$. $\square$

Diagnosis [a]. This argument is correct, but it gives only a fixed constant: even the stronger Coppersmith–Phillips finite bound would imply at most a fixed lower bound on $\limsup a_n/n$. Neither estimate can make that limsup infinite or make the normalized harmonic sum tend to zero.

Exact gap in the comment's heuristic [c]. For each block length $r\geq2$, the sums

S_r=\{a_i+a_{i+1}+\cdots+a_{i+r-1}:i\geq1\}

are individually increasing and avoid $A$. It is tempting to add proposed density contributions of size roughly $\delta/r$ when $A$ has lower density $\delta$. That addition is invalid without controlling overlaps $S_r\cap S_s$. The sets of sums for different lengths can overlap heavily, and no disjointness or bounded-multiplicity statement was proved in the comment.

A sufficient missing lemma would be the following kind of new forbidden mass lemma: for every $\delta>0$, a sequence satisfying $A(t)\geq\delta t$ throughout a sufficiently long scale must have, on some target interval $I$,

\left|\left(\bigcup_{2\leq r\leq R(\delta)}S_r\right)\cap I\right| > |I|-|A\cap I|.

Since the union on the left is disjoint from $A$, this would be a contradiction. Proving any uniform statement strong enough to beat the complement capacity—despite cross-length coincidences—is the exact missing step. The harmonic-density question needs a weighted/multiscale version whose gain can be made arbitrarily large, not merely one fixed saving.

4. New exact finite computation

Define

f(N)=\max\bigl\{|B|:B=\{b_1<\cdots<b_k\}\subseteq[1,N], \ b_i+\cdots+b_j\notin B\text{ for all }i<j\bigr\}.

This is the finite extremal function in #867 and Coppersmith–Phillips.

Theorem [d: exact exhaustive computation]. The exact values through $N=70$ are:

| $N$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | $f(N)$ | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 6 | | $N$ | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | | $f(N)$ | 7 | 7 | 8 | 8 | 9 | 9 | 10 | 10 | 11 | 12 | | $N$ | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | $f(N)$ | 12 | 12 | 13 | 14 | 14 | 15 | 15 | 16 | 17 | 17 | | $N$ | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | | $f(N)$ | 17 | 18 | 19 | 20 | 20 | 21 | 22 | 22 | 23 | 24 | | $N$ | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | | $f(N)$ | 25 | 25 | 25 | 26 | 27 | 27 | 28 | 28 | 29 | 30 | | $N$ | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | | $f(N)$ | 30 | 31 | 32 | 32 | 33 | 34 | 34 | 35 | 36 | 36 | | $N$ | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | | $f(N)$ | 36 | 37 | 38 | 38 | 38 | 39 | 40 | 40 | 41 | 42 |

The table's SHA-256, when encoded as comma-separated decimal entries, is ea3d59ef1fe44a72a7f8c7b1b9f229a06b464afbe0dbc6225d7542bed6fe420b.

Two lower-bound witnesses are:

\begin{aligned} N=20:\quad& (4,5,6,7,8,10,12,14,16,17,19,20),\\ N=70:\quad& (8,9,10,11,13,14,16,18,20,23,25,26,28,29,32,33,35,36,\\ &\qquad37,39,40,41,42,44,45,46,47,49,50,52,53,55,56,58,\\ &\qquad59,60,62,63,66,67,69,70). \end{aligned}

The first is the $N=20$, $k=12$ example that Freud attributes to Pomerance; the second has 42 entries. The checker tests every consecutive block in every carried witness directly.

Why the exhaustive search is exact

Lemma [a].

f(N-1)\leq f(N)\leq f(N-1)+1.

Proof. The lower inequality is immediate. For the upper one, take a valid sequence in $[1,N]$. If it omits $N$, its size is at most $f(N-1)$. If it contains $N$, delete that last entry. Removing the last entry cannot create a new adjacency among earlier entries, so the remaining sequence is valid in $[1,N-1]$. $\square$

Consequently, after $f(N-1)$ is known, only the feasibility of $f(N-1)+1$ terms in $[1,N]$ has to be decided.

State-completeness lemma [a]. Before deciding the integer $x$, it is enough to store:

the sums not exceeding $N$ of all nonempty suffixes of the selected

prefix;

a bit set $F$ of all sums not exceeding $N$ of its consecutive blocks

of length at least two.

The choice $x$ is legal exactly when $x\notin F$. If it is selected, its new suffix sums are

x,\quad x+s\quad(s\text{ an old suffix sum}),

and the terms $x+s$ are exactly the new forbidden block sums. Thus the two branches “select $x$” and “omit $x$” enumerate every valid sequence once the harmless memo-state merging is taken into account.

Pruning lemma [a]. At any state,

\text{current size} +|\{x,\ldots,N\}\setminus F|

is an upper bound for the size of every continuation. Future selections only add forbidden values. A branch is therefore safely discarded when this bound is below the target. If the same $(x,\text{suffix sums},F)$ state is reached with no larger current size than before, it is dominated because its future transitions are identical.

[d] On the final run, the standard-library search made 9,346,949 recursive calls and retained 5,194,982 memo states, taking about 15 seconds on this VM. It then:

directly rechecked every lower-bound witness;
literally enumerated every one of the $2^N$ subsets for each

$N\leq20$ using a separate validity routine and obtained the same values;

spot-checked the decisive infeasibilities at

$N=30,35,40,45,50,55,60$ with an independently written CP-SAT model whose variables are the ordered entries and whose constraints are all consecutive-block disequalities.

The CP-SAT code is not needed for the certificate; the supplied verifier uses only Python's standard library.

5. Independent check of Freud's finite family

[d: computation of a published construction] For $1\leq y\leq20$, the checker sets $x=17y-2$ and reconstructs Freud's four components:

$4y+1$ consecutive integers centered at $2x$;
the $4y$ nonmultiples of $3$ in the indicated interval around $3x$;
$4y-1$ even integers around $4x$;
the terminal interval from $4x+4y+2$ to $8x+8y+4$.

For each $y$, it independently finds every member of the original union that is a consecutive block sum, deletes those members, and then recomputes all consecutive sums in the new sequence. In every tested case:

\begin{array}{rcl} |\text{original union}|&=&84y-5,\\ |\text{deleted set}|&=&8y+2,\\ |\text{final sequence}|&=&76y-7,\\ \max(\text{final sequence})&=&144y-12, \end{array}

all deleted values lie in the terminal component, and there is no violation after deletion. This independently confirms the arithmetic

\frac{76y-7}{144y-12}\longrightarrow\frac{19}{36}

for those cases.

[b: Freud 1993] Freud's article proves the construction uniformly in $y$ and gives the additional rapidly separated block-splicing step for an infinite sequence. The finite computation above is a check, not a replacement for the article's uniform proof.

6. What remains, and why this does not close #839

[a] An endpoint estimate $f(N)\leq cN+O(\log N)$ with any fixed $c>0$ cannot prove #839. It only gives $\limsup a_n/n\geq1/c$, a constant. Moreover, the Coppersmith–Phillips lower construction shows that $f(N)$ itself is linear, so proving $f(N)=o(N)$ is impossible.

[a] The infinite question is a nesting/uniformity problem. To contradict positive lower density, one must rule out a single infinite path whose every sufficiently late prefix has enough selected terms. Dense finite extremizers at separate horizons need not nest, and the exact values through 70 supply no uniform finite cutoff for every positive density.

[c: precise computational wall] The pure search through $N=70$ takes about 15 seconds; an exploratory extension reached $N=80$ only after about 129 seconds. The observed state growth suggests that a straightforward extension to $N=100$ would cost roughly $2$–$6$ single-core hours and several GB of memory, with substantial instance-to-instance variation. I did not run that heavier search. More importantly, any fixed $N$ remains logically incapable of supplying the uniformity needed for the infinite limit.

The actionable mathematical wall is therefore not “more finite $f(N)$ values.” It is the cross-length overlap lemma isolated in Section 3, or an alternative potential/entropy argument that forces new forbidden mass on arbitrarily many scales. For the logarithmic-density statement, that gain must be summable across scales strongly enough to replace every fixed coefficient by $o(1)$.

7. Reproduction

Run:

python runs/erdos839_wavew017_reverify.py

The script has no nonstandard dependency. It prints the exact table, its digest, state/call counts, literal-subset cross-check, Freud-family check, selected witnesses, and finally ALL CHECKS PASSED.

PARTIAL: exact standard-library search certifies the finite extremal table $f(N)$ for every $1\leq N\leq70$, audits the elementary $2/3$ bound and Freud construction, and isolates uncontrolled overlap among different block-length sumsets as the precise obstacle to either infinite limit.

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