Erdős Problem #859

Erdős Problem 859 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/859.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT.

Fix $t\in\mathbb N$ with $t\ge 1$. For each $n\in\mathbb N$, let $\mathcal D(n)$ be the set of positive divisors of $n$. Say that $n$ is $t$-representable if there exists a finite subset $S\subseteq \mathcal D(n)$ of distinct divisors such that \[ \sum_{d\in S} d = t. \] Let \[ S_t := \{n\in\mathbb N : n\text{ is $t$-representable}\}. \] If the natural density \[ d_t := \lim_{X\to\infty} \frac{|S_t\cap\{1,2,\dots,X\}|}{X} \] exists, the problem asks whether there are constants $c_1,c_2>0$ such that \[ d_t \sim \frac{c_1}{(\log t)^{c_2}} \qquad (t\to\infty). \]

QUICK LITERATURE/CONTEXT CHECK.

The problem statement records that Erdős proved $d_t$ exists and that there are positive constants $c_3,c_4$ with \[ (\log t)^{-c_3} < d_t < (\log t)^{-c_4}. \] We do not assume any more literature.

ATTACK PLAN.

We prove two unconditional structural facts:

$1$ For each fixed $t$, the membership of $n$ in $S_t$ depends only on divisibility of $n$ by integers $\le t$, hence is periodic modulo $\mathrm{lcm}(1,2,\dots,t)$. This immediately implies $d_t$ exists (and is rational).

$2$ Provide elementary lower bounds on $d_t$ (e.g. $d_t\ge 1/t$ via multiples of $t$).

We then compute $d_t$ exactly for small $t$ as a sanity check.

WORK.

Lemma 859.1 (Periodicity and existence of $d_t$).

Lemma. Fix $t\ge 1$ and let $L:=\mathrm{lcm}(1,2,\dots,t)$. Then $S_t$ is a union of residue classes modulo $L$. In particular, the natural density $d_t$ exists and equals \[ d_t = \frac{1}{L}\,\#\{0\le r<L : r\in S_t\}. \]

Proof. Let $n\in\mathbb N$. If $n$ is $t$-representable, then there exists a subset $S\subseteq\mathcal D(n)$ with $\sum_{d\in S} d=t$. Every $d\in S$ satisfies $d\le t$ because all summands are positive. Thus the condition "$n$ is $t$-representable" depends only on which integers $d\in\{1,2,\dots,t\}$ divide $n$.

For each $d\le t$, the predicate "$d\mid n$" depends only on the residue class of $n$ modulo $d$, hence only on $n\bmod L$ because $d\mid L$. Therefore the set of residues $r\bmod L$ for which the collection of divisors $\{d\le t: d\mid r\}$ admits a subset summing to $t$ is well-defined; call this set $R\subseteq\{0,1,\dots,L-1\}$. Then $n\in S_t$ if and only if $n\bmod L\in R$, i.e. $S_t$ is a union of residue classes mod $L$.

Any union of residue classes modulo $L$ has natural density $|R|/L$ by periodicity: among $1,2,\dots,X$ each residue appears $\lfloor X/L\rfloor$ or $\lceil X/L\rceil$ times, and the proportion tends to $|R|/L$ as $X\to\infty$. Thus $d_t$ exists and equals $|R|/L$. $\square$

Lemma 859.2 (A trivial universal lower bound).

Lemma. For every $t\ge 1$, we have $d_t\ge 1/t$.

Proof. If $n$ is a multiple of $t$, then $t\in\mathcal D(n)$, and we can represent $t$ as the sum of the single divisor $t$. Hence every multiple of $t$ lies in $S_t$. The set of multiples of $t$ has natural density $1/t$. Therefore $d_t\ge 1/t$. $\square$

Lemma 859.3 (A union-bound upper estimate in terms of distinct partitions).

Lemma. Let $\mathcal P_t$ be the set of all finite subsets $S\subseteq\{1,2,\dots,t\}$ with $\sum_{d\in S} d=t$, and for $S\in\mathcal P_t$ let $m(S):=\mathrm{lcm}(S)$. Then \[ d_t \le \sum_{S\in\mathcal P_t} \frac{1}{m(S)}. \]

Proof. If $n\in S_t$, then there exists $S\in\mathcal P_t$ such that every $d\in S$ divides $n$, hence $m(S)=\mathrm{lcm}(S)$ divides $n$. Therefore \[ S_t \subseteq \bigcup_{S\in\mathcal P_t} \{n: m(S)\mid n\}. \] Taking natural densities and using the union bound for densities of sets, \[ d_t \le \sum_{S\in\mathcal P_t} \mathrm{dens}(\{n: m(S)\mid n\}) = \sum_{S\in\mathcal P_t} \frac{1}{m(S)}. \] $\square$

Fast reality check (exact values for small $t$).

Using Lemma 859.1 (period $L=\mathrm{lcm}(1,\dots,t)$) and a direct computation for $t\le 10$, we obtain the exact values: \[ \begin{array}{c|c|c} t & d_t & \text{decimal}\\\hline 1 & 1 & 1.0000\\ 2 & 1/2 & 0.5000\\ 3 & 2/3 & 0.6667\\ 4 & 1/2 & 0.5000\\ 5 & 7/15 & 0.4667\\ 6 & 7/15 & 0.4667\\ 7 & 16/35 & 0.4571\\ 8 & 3/7 & 0.4286\\ 9 & 119/315 & 0.3778\\ 10 & 2/5 & 0.4000 \end{array} \]

VERIFICATION.

• Lemma 859.1: the key point is that any divisor used in a sum to $t$ is automatically $\le t$, ensuring finiteness and periodicity modulo $\mathrm{lcm}(1,\dots,t)$.
• Lemma 859.2 is valid because using the single divisor $t$ is allowed ("distinct divisors").
• The computed small values agree with obvious checks: $d_1=1$ and $d_2=1/2$ (only even $n$ have divisor $2$).

FINAL. UNRESOLVED.

(i) Strongest proved partial results. We proved that for every fixed $t$, the set $S_t$ is periodic modulo $\mathrm{lcm}(1,\dots,t)$, hence $d_t$ exists and is rational. We also proved the universal lower bound $d_t\ge 1/t$ and an explicit union-bound upper estimate in Lemma 859.3. Exact values for $t\le 10$ were computed.

(ii) First gap. Determine the true asymptotic behaviour of $d_t$ as $t\to\infty$; in particular, prove or disprove the existence of $c_1,c_2>0$ with $d_t\sim c_1/(\log t)^{c_2}$.

(iii) Top 3 next moves. $1$ Analyse which subsets $S\subseteq\{1,\dots,t\}$ with sum $t$ give the smallest $\mathrm{lcm}(S)$; these dominate the union-bound in Lemma 859.3. $2$ Develop a lower-bound construction beyond $1/t$ by forcing a "binary" divisor structure (e.g. many powers of two) with reasonably high density. $3$ Compute $d_t$ for larger $t$ (say $t=20,30,40$) using periodicity but avoiding enumerating all residues by instead enumerating the moduli $m(S)$ and using inclusion--exclusion on their lcms.

(iv) What a minimal counterexample would look like. If $d_t$ fails to be a power of $\log t$, then either (a) $d_t$ is much larger, requiring unexpectedly many small-lcm partitions of $t$ into distinct parts, or (b) $d_t$ is much smaller, meaning that every representation of $t$ as a sum of distinct integers forces an lcm so large that the union of multiples has unusually small density.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT.

Fix $t\in\mathbb N$ with $t\ge 1$. For each $n\in\mathbb N$, let $\mathcal D(n)$ be the set of positive divisors of $n$. Say that $n$ is $t$-representable if there exists a finite subset $S\subseteq \mathcal D(n)$ of distinct divisors such that \[ \sum_{d\in S} d = t. \] Let \[ S_t := \{n\in\mathbb N : n\text{ is $t$-representable}\}. \] If the natural density \[ d_t := \lim_{X\to\infty} \frac{|S_t\cap\{1,2,\dots,X\}|}{X} \] exists, the problem asks whether there are constants $c_1,c_2>0$ such that \[ d_t \sim \frac{c_1}{(\log t)^{c_2}} \qquad (t\to\infty). \]

QUICK LITERATURE/CONTEXT CHECK.

The problem statement records that Erdős proved $d_t$ exists and that there are positive constants $c_3,c_4$ with \[ (\log t)^{-c_3} < d_t < (\log t)^{-c_4}. \] We do not assume any more literature.

ATTACK PLAN.

We prove two unconditional structural facts:

$1$ For each fixed $t$, the membership of $n$ in $S_t$ depends only on divisibility of $n$ by integers $\le t$, hence is periodic modulo $\mathrm{lcm}(1,2,\dots,t)$. This immediately implies $d_t$ exists (and is rational).

$2$ Provide elementary lower bounds on $d_t$ (e.g. $d_t\ge 1/t$ via multiples of $t$).

We then compute $d_t$ exactly for small $t$ as a sanity check.

WORK.

Lemma 859.1 (Periodicity and existence of $d_t$).

Lemma. Fix $t\ge 1$ and let $L:=\mathrm{lcm}(1,2,\dots,t)$. Then $S_t$ is a union of residue classes modulo $L$. In particular, the natural density $d_t$ exists and equals \[ d_t = \frac{1}{L}\,\#\{0\le r<L : r\in S_t\}. \]

Proof. Let $n\in\mathbb N$. If $n$ is $t$-representable, then there exists a subset $S\subseteq\mathcal D(n)$ with $\sum_{d\in S} d=t$. Every $d\in S$ satisfies $d\le t$ because all summands are positive. Thus the condition "$n$ is $t$-representable" depends only on which integers $d\in\{1,2,\dots,t\}$ divide $n$.

For each $d\le t$, the predicate "$d\mid n$" depends only on the residue class of $n$ modulo $d$, hence only on $n\bmod L$ because $d\mid L$. Therefore the set of residues $r\bmod L$ for which the collection of divisors $\{d\le t: d\mid r\}$ admits a subset summing to $t$ is well-defined; call this set $R\subseteq\{0,1,\dots,L-1\}$. Then $n\in S_t$ if and only if $n\bmod L\in R$, i.e. $S_t$ is a union of residue classes mod $L$.

Any union of residue classes modulo $L$ has natural density $|R|/L$ by periodicity: among $1,2,\dots,X$ each residue appears $\lfloor X/L\rfloor$ or $\lceil X/L\rceil$ times, and the proportion tends to $|R|/L$ as $X\to\infty$. Thus $d_t$ exists and equals $|R|/L$. $\square$

Lemma 859.2 (A trivial universal lower bound).

Lemma. For every $t\ge 1$, we have $d_t\ge 1/t$.

Proof. If $n$ is a multiple of $t$, then $t\in\mathcal D(n)$, and we can represent $t$ as the sum of the single divisor $t$. Hence every multiple of $t$ lies in $S_t$. The set of multiples of $t$ has natural density $1/t$. Therefore $d_t\ge 1/t$. $\square$

Lemma 859.3 (A union-bound upper estimate in terms of distinct partitions).

Lemma. Let $\mathcal P_t$ be the set of all finite subsets $S\subseteq\{1,2,\dots,t\}$ with $\sum_{d\in S} d=t$, and for $S\in\mathcal P_t$ let $m(S):=\mathrm{lcm}(S)$. Then \[ d_t \le \sum_{S\in\mathcal P_t} \frac{1}{m(S)}. \]

Proof. If $n\in S_t$, then there exists $S\in\mathcal P_t$ such that every $d\in S$ divides $n$, hence $m(S)=\mathrm{lcm}(S)$ divides $n$. Therefore \[ S_t \subseteq \bigcup_{S\in\mathcal P_t} \{n: m(S)\mid n\}. \] Taking natural densities and using the union bound for densities of sets, \[ d_t \le \sum_{S\in\mathcal P_t} \mathrm{dens}(\{n: m(S)\mid n\}) = \sum_{S\in\mathcal P_t} \frac{1}{m(S)}. \] $\square$

Fast reality check (exact values for small $t$).

Using Lemma 859.1 (period $L=\mathrm{lcm}(1,\dots,t)$) and a direct computation for $t\le 10$, we obtain the exact values: \[ \begin{array}{c|c|c} t & d_t & \text{decimal}\\\hline 1 & 1 & 1.0000\\ 2 & 1/2 & 0.5000\\ 3 & 2/3 & 0.6667\\ 4 & 1/2 & 0.5000\\ 5 & 7/15 & 0.4667\\ 6 & 7/15 & 0.4667\\ 7 & 16/35 & 0.4571\\ 8 & 3/7 & 0.4286\\ 9 & 119/315 & 0.3778\\ 10 & 2/5 & 0.4000 \end{array} \]

VERIFICATION.

• Lemma 859.1: the key point is that any divisor used in a sum to $t$ is automatically $\le t$, ensuring finiteness and periodicity modulo $\mathrm{lcm}(1,\dots,t)$.
• Lemma 859.2 is valid because using the single divisor $t$ is allowed ("distinct divisors").
• The computed small values agree with obvious checks: $d_1=1$ and $d_2=1/2$ (only even $n$ have divisor $2$).

FINAL. UNRESOLVED.

(i) Strongest proved partial results. We proved that for every fixed $t$, the set $S_t$ is periodic modulo $\mathrm{lcm}(1,\dots,t)$, hence $d_t$ exists and is rational. We also proved the universal lower bound $d_t\ge 1/t$ and an explicit union-bound upper estimate in Lemma 859.3. Exact values for $t\le 10$ were computed.

(ii) First gap. Determine the true asymptotic behaviour of $d_t$ as $t\to\infty$; in particular, prove or disprove the existence of $c_1,c_2>0$ with $d_t\sim c_1/(\log t)^{c_2}$.

(iii) Top 3 next moves. $1$ Analyse which subsets $S\subseteq\{1,\dots,t\}$ with sum $t$ give the smallest $\mathrm{lcm}(S)$; these dominate the union-bound in Lemma 859.3. $2$ Develop a lower-bound construction beyond $1/t$ by forcing a "binary" divisor structure (e.g. many powers of two) with reasonably high density. $3$ Compute $d_t$ for larger $t$ (say $t=20,30,40$) using periodicity but avoiding enumerating all residues by instead enumerating the moduli $m(S)$ and using inclusion--exclusion on their lcms.

(iv) What a minimal counterexample would look like. If $d_t$ fails to be a power of $\log t$, then either (a) $d_t$ is much larger, requiring unexpectedly many small-lcm partitions of $t$ into distinct parts, or (b) $d_t$ is much smaller, meaning that every representation of $t$ as a sum of distinct integers forces an lcm so large that the union of multiples has unusually small density.