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

Erdős problem #859 — wave w019

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

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

extrapolation, not claimed as a theorem.

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

a direct observation from a fetched primary source. All newly computed table and residue arithmetic below is recomputed by runs/erdos859_wavew019_reverify.py.

0. Mandatory live-page and collision check

[d: live-page observation] I fetched the rendered live page through the Bright Data cloud browser on 2026-07-28, before doing any mathematics. It says OPEN.

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

Let $t\geq 1$ and let $d_t$ be the density of the set of integers $n\in\mathbb{N}$ for which $t$ can be represented as the sum of distinct divisors of $n$.
Do there exist constants $c_1,c_2>0$ such that \[ > d_t \sim \frac{c_1}{(\log t)^{c_2}} > \] as $t\to \infty$?

The page's listed known result is:

Erdős [Er70] proved that $d_t$ always exists, and that there exist some constants $c_3,c_4>0$ such that \[ > \frac{1}{(\log t)^{c_3}} < d_t < > \frac{1}{(\log t)^{c_4}}. > \]

[d: complete marker audit]

live-page field	value
status	OPEN
comments	0
claimed proofs	0
likes this problem	None
interested in collaborating	None
currently working on this problem	None
this problem looks difficult	None
this problem looks tractable	None
formalised statement?	Yes
results could be formalisable	None
working on formalising the results	None

There is therefore no claimed proof and no current worker, so the mandatory stop condition did not apply.

1. Primary-source and literature audit

The original source

[d] The cited paper exists:

P. Erdős, Some extremal problems in combinatorial number theory, in Mathematical Essays Dedicated to A. J. Macintyre, Ohio University Press (1970), 123–133, MR0276194.

On printed page 130, Erdős defines the same set $A_t$, observes that it is upward closed under divisibility, and says that every element of $A_t$ is a multiple of an element of $A_t$ not exceeding $t!$. He then proves $d_t\to0$, records power-of-log upper and lower bounds, and proposes

d_t=(1+o(1))\frac{c_3}{(\log t)^{c_4}}. \tag{1}

This scan is the source actually checked; no OCR reconstruction is being used to alter the live statement.

A relevant later theorem

[d] Andreas Weingartner, Integers with large practical component, Publicationes Mathematicae Debrecen 87 (2015), 439–447, DOI 10.5486/PMD.2015.7259 (arXiv:1411.6974), is directly useful even though it does not mention the fixed-$t$ question.

The paper defines $f(n)$ to be the largest integer such that every member of $[1,f(n)]$ is a sum of distinct divisors of $n$, and

N(x,y)=\#\{n\le x:f(n)\ge y\}.

Its Theorem 1(iv) and the display following equation (3) give

N(x,y)=x\nu_y+O(2^y),\qquad \nu_y=\frac{ce^{-\gamma}}{\log y} \left(1+O\left(\frac{\log\log y}{\log y}\right)\right), \tag{2}

where $c>0$ is the constant in the practical-number asymptotic

\#\{n\le x:n\text{ practical}\}\sim \frac{cx}{\log x}.

[d] Weingartner later proved $1.336073<c<1.336077$ in Theorem 1 of The constant factor in the asymptotic for practical numbers, arXiv:1906.07819v3 (2019). This verifies the identity and numerical scale of the constant in (2); no guessed numerical value is used below.

Search scope and miss

[d] I ran exact-statement, exact-title, citation, and terminology searches, and checked the full texts of the original paper, arXiv:1411.6974, arXiv:1405.2585 (Practical numbers and the distribution of divisors), arXiv:1906.07819, and the current nearby paper arXiv:2604.05284 (A statistical investigation of a divisor-sum function). The last paper concerns the distribution of $S_s(n)=\sum_{d\mid n}s(d)$, not the density in this problem.

[c: search miss] These searches found no later primary paper that states an asymptotic for this fixed-$t$ density, and no published exact table of the values below. This is an honest search report, not a theorem that no such paper exists.

2. An exact finite-union reduction

For $t\ge1$, let

\mathcal P_t=\left\{S\subseteq\{1,\ldots,t\}: S\ne\varnothing,\ \sum_{s\in S}s=t\right\}

and put $\ell(S)=\operatorname{lcm}(S)$. Let $\mathcal M_t$ be the divisibility-minimal members of $\{\ell(S):S\in\mathcal P_t\}$.

Lemma [a].

A_t=\{n:t\text{ is a sum of distinct divisors of }n\} =\bigcup_{m\in\mathcal M_t}m\mathbb N. \tag{3}

Proof. If $t=\sum_{s\in S}s$ with the summands distinct divisors of $n$, then $\ell(S)\mid n$. Conversely, if $\ell(S)\mid n$, every member of $S$ divides $n$, so their sum represents $t$. Removing an LCM divisible by another LCM does not change the union of multiples.

$\square$

This gives a completely explicit rational formula. Write

Q_t=\operatorname{lcm}\{m:m\in\mathcal M_t\}.

Corollary [a].

d_t=\frac1{Q_t}\#\{1\le r\le Q_t:\exists m\in\mathcal M_t,\ m\mid r\} \tag{4}

and, equivalently,

d_t=\sum_{\varnothing\ne J\subseteq\mathcal M_t} \frac{(-1)^{|J|+1}}{\operatorname{lcm}(J)}. \tag{5}

Proof. The indicator in (3) is periodic modulo $Q_t$, proving (4). Finite inclusion–exclusion gives (5). $\square$

Thus existence and exact computability of each individual $d_t$ require no limiting argument. Formula (3) also identifies the precise finite object whose behavior must be controlled uniformly as $t$ grows: a correlated union of divisibility events indexed by LCMs of distinct-part partitions.

3. A sharper analytic lower bound

Let

B_t=\{n:f(n)\ge t\}.

Every $n\in B_t$ represents $t$, so $B_t\subseteq A_t$.

Proposition [b: Weingartner 2015, Theorem 1].

d_t\ge \frac{ce^{-\gamma}}{\log t} \left(1+O\left(\frac{\log\log t}{\log t}\right)\right). \tag{6}

In particular,

\liminf_{t\to\infty}d_t\log t\ge ce^{-\gamma}>0. \tag{7}

Proof. For fixed $t$, (2) shows that $B_t$ has density $\nu_t$. The containment $B_t\subseteq A_t$ gives $d_t\ge\nu_t$, and the second part of (2) gives (6) and (7). $\square$

Consequence [b]. If the answer to the live question is affirmative, its exponent must satisfy $c_2\le1$. If $c_2=1$, its leading constant must satisfy $c_1\ge ce^{-\gamma}$. Indeed, $c_2>1$ would make $d_t\log t\to0$, contradicting (7).

This does not settle the problem: (6) controls only integers for which every integer up to $t$ is representable, while $A_t$ asks only for the single target $t$.

4. Exact isolation of the unresolved contribution

Define

R_t=A_t\setminus B_t,\qquad r_t=\operatorname{dens}(R_t).

Both densities exist, and $B_t\subseteq A_t$.

Reduction [a+b].

d_t=\nu_t+r_t =\frac{ce^{-\gamma}}{\log t} \left(1+O\left(\frac{\log\log t}{\log t}\right)\right)+r_t. \tag{8}

Here $R_t$ consists exactly of the integers which represent $t$ but have at least one gap below $t$ in their divisor subset sums. Consequently:

[a+b] proving $r_t=o(1/\log t)$ would settle the problem with

$c_2=1$ and $c_1=ce^{-\gamma}$;

[a] if $r_t$ is larger, then its asymptotic—not the practical

component—must supply the leading term;

[d] the residual is genuinely nonempty. The complete-period check gives

\[ \nu_t= \begin{cases} 1,&t=1,\\ 1/2,&2\le t\le3,\\ 1/3,&4\le t\le7,\\ 29/105,&8\le t\le12,\\ 3667/15015,&13\le t\le15. \end{cases} \] For example, \[ r_{15}=d_{15}-\nu_{15} =\frac{1739}{15015}\approx0.1158175158. \]

Small $t$ cannot predict the limiting size of $r_t$, but this decomposition pinpoints the exact missing analytic term.

5. Exact computation for $1\le t\le50$

Algorithms

[a] The antichains $\mathcal M_t$ are generated by a subset-sum dynamic program. After processing the possible part $a$, the state for a sum $s$ keeps only divisibility-minimal attainable LCMs. If $u\mid v$, then for every future set of parts $F$,

\operatorname{lcm}(u,F)\mid\operatorname{lcm}(v,F),

so discarding $v$ is rigorous.

The central update in the checker is:

states[0].add(1)
for part in range(1, limit + 1):
    for total in range(limit, part - 1, -1):
        for old in tuple(states[total - part]):
            insert_minimal(states[total], lcm(old, part))

[a] Density is evaluated in two independent exact ways.

Compressed inclusion–exclusion stores the coefficient of each resulting

LCM:

   for modulus in moduli:
       old_terms = tuple(coefficients.items())
       coefficients[modulus] = coefficients.get(modulus, 0) + 1
       for old_modulus, coefficient in old_terms:
           joint = lcm(old_modulus, modulus)
           coefficients[joint] = coefficients.get(joint, 0) - coefficient
   density = sum(Fraction(c, m) for m, c in coefficients.items())

A prime-valuation decision diagram uses

\[ \operatorname{dens}\{n:v_p(n)=e\}=\frac{p-1}{p^{e+1}}, \qquad \operatorname{dens}\{n:v_p(n)\ge E\}=\frac1{p^E}, \] with independence across the finitely many primes supplied by the Chinese remainder theorem.

[d: independent verification] The standalone checker performs all of the following:

compares the dynamic program with a separate recursive enumeration of

every distinct-part partition for all $t\le50$;

compares compressed inclusion–exclusion with the prime-valuation decision

diagram for all $t\le50$;

scans all $360360=\operatorname{lcm}(1,\ldots,15)$ residue classes and

directly performs divisor subset sums, without using partitions or LCM witnesses, for all $t\le15$;

checks every rational in the following table and the sharp finite-range

minimum.

Run it with:

python runs/erdos859_wavew019_reverify.py

Verified table

[d] Here $|\mathcal M_t|$ is the size of the minimal LCM antichain.

$t$	$\|\mathcal M_t\|$	exact $d_t$	$t$	$\|\mathcal M_t\|$	exact $d_t$
1	1	1	26	29	5418551/16900975
2	1	1/2	27	33	415249/1322685
3	2	2/3	28	31	183314459/557732175
4	2	1/2	29	33	150916721/462120945
5	3	7/15	30	40	15890417/48474225
6	3	7/15	31	39	11339754563/33426748355
7	4	16/35	32	44	14555971/46881835
8	5	3/7	33	42	152652759197/501401225325
9	6	17/45	34	39	319916351/1055581527
10	6	2/5	35	42	4250880551/14325749295
11	6	13/33	36	45	31781797673/100280245065
12	7	43/99	37	53	398932881967/1236789689135
13	9	6151/15015	38	54	1850717401899/6183948445675
14	10	1087/3003	39	51	74910018269/240933056325
15	9	1802/5005	40	53	3356447249/10393190665
16	12	5197/15015	41	62	48271207496597/152125131763605
17	13	555/1547	42	61	1337262602471/4346432336103
18	14	89239/255255	43	70	93979988434347/311494317420715
19	18	78121/230945	44	77	11191733479327/37987111880575
20	20	552611/1616615	45	77	121471016290297/436092044389001
21	18	1620859/4849845	46	78	9806892672341/34980645271845
22	17	523443/1616615	47	83	1327729725833653/4455723062235445
23	20	280229/780045	48	86	583986472831913/1909595598100905
24	22	3779353/10140585	49	95	3098849400971709691/10760571195298599675
25	26	228311/676039	50	103	993258048983311/3533849325221215

[d: sharp concrete bound]

\min_{1\le t\le50}d_t =d_{45} =\frac{121471016290297}{436092044389001} \approx0.278544444580,

and $t=45$ is the unique minimizer in this range.

[d] The full verification run completed successfully in about 42 seconds of one CPU core with peak resident memory about 198 MB. At $t=50$, the two exact evaluators respectively used 139700 coalesced inclusion–exclusion LCM terms and 774920 prime-valuation decision-diagram states.

6. Precise wall

[a+b] Equations (3) and (8) isolate the unresolved issue exactly: determine the density $r_t$ of integers having a gapped divisor subset-sum set which nevertheless contains $t$. The named practical-component theorem controls $\nu_t$, but says nothing asymptotic about this gapped residual.

[a] Pointwise exact computation does not provide the required uniformity. The clauses in (3) are highly correlated through shared prime powers, and the number and arithmetic shape of the minimal LCM clauses both change with $t$. A finite table—even a much larger one—cannot prove that $r_t$ is negligible or that it has a power-log main term.

[c: computational cost estimate] From $t=40$ to $t=50$, the valuation diagram grew from 59700 to 774920 states. A naive continuation by another ten values would plausibly require on the order of $10^7$ states, several GB of memory, and roughly $0.1$–$0.3$ core-hours for the same dual exact checks. This extrapolation is not a theorem and was not run. More importantly, values even near $t=100$ would still not supply the missing uniform analytic estimate.

[a] A sufficient missing lemma with a clean payoff is

\operatorname{dens}\{n:t\text{ is representable but }f(n)<t\} =o(1/\log t). \tag{9}

It would prove the conjectured form with exponent $1$ and leading constant $ce^{-\gamma}$. No checked source proves (9), and the exact data do not justify assuming it.

PARTIAL: proved the exact finite-union/LCM reduction, derived the rigorous lower bound $\liminf d_t\log t\ge ce^{-\gamma}$ from Weingartner's theorem (forcing any asymptotic exponent $c_2\le1$), and independently verified the full rational table through $t=50$; the precise remaining term is the density $r_t$ of gapped representations.

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