Erdős Problem #312

Erdős Problem #312 (Round 2)

1) ROUND-2 OBJECTIVE

Path A (prove the original statement, or at least obtain a rigorous general quantitative bound).

Round 1 only gave an obstruction family and a lower bound inside that family. The most promising Round-2 direction is therefore to prove a universal theorem applying to every multiset $A$ with large reciprocal sum. I do not reach the conjectured exponential bound, but I do obtain a fully self-contained general estimate \[ \varepsilon(A)\le \frac{1}{K+\log K+O(1)}, \] valid for every finite multiset with total reciprocal sum $>K$.

2) Round-1 FOUNDATION USED

I use the following Round-1 result.

• The prime-multiplicity obstruction family \[ A_N:=\bigsqcup_{p\le N}\{\underbrace{p,\ldots,p}_{p-1\text{ copies}}\} \] contains no submultiset summing exactly to $1$, and for this family one has \[ \varepsilon(A_N)\ge \frac{1}{N^\#}, \qquad N^\#:=\prod_{p\le N}p. \]

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a very simple "maximal subset below $1$" argument.

If $S$ is a submultiset maximizing the reciprocal sum subject to $R(S)\le 1$, and the gap is \[ \delta:=1-R(S), \] then every omitted reciprocal must be strictly larger than $\delta$; otherwise one could add it and get closer to $1$ from below.

Combining this with the trivial observation that $n$ copies of $1/n$ would already give an exact sum $1$, one gets a global counting bound in terms of \[ \sum_{n\le M}\frac{n-1}{n}=M-H_M, \qquad H_M:=1+\frac12+\cdots+\frac1M. \]

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was the absence of any self-contained upper bound for arbitrary multisets. I therefore:

1. prove a multiplicity lemma valid for every exact-$1$-free multiset;
2. combine it with the maximal-subset-below-$1$ principle;
3. deduce an explicit universal bound on the best possible gap below $1$.

This does not match the conjectured exponential scale, but it strictly strengthens Round 1 by proving a genuine theorem for all multisets.

5) WORK (ROUND-2)

For a finite multiset $A$ of positive integers write \[ R(A):=\sum_{n\in A}\frac1n, \qquad \varepsilon(A):= \min\{1-R(S): S\subseteq A,\ R(S)\le 1\}. \] Thus $\varepsilon(A)=0$ iff some submultiset sums exactly to $1$.

Lemma 5.1 (multiplicity bound). If no submultiset of $A$ has reciprocal sum exactly $1$, then for every integer $n\ge 1$ the denominator $n$ occurs in $A$ at most $n-1$ times.

Proof. If $n$ occurred at least $n$ times, then taking exactly $n$ copies of $1/n$ would give the submultiset sum \[ \frac1n+\cdots+\frac1n=1. \] This is excluded by hypothesis. $\square$

Lemma 5.2 (denominator cutoff from a maximal subset). Let $S\subseteq A$ be a submultiset for which $R(S)$ is maximal under the constraint $R(S)\le 1$, and let \[ \delta:=1-R(S). \] If $\delta>0$, then every element of $A\setminus S$ has denominator strictly smaller than $1/\delta$.

Proof. Take any $n\in A\setminus S$. If $1/n\le \delta$, then \[ R(S)+\frac1n\le 1, \] contradicting the maximality of $R(S)$. Hence $1/n>\delta$, i.e. \[ n<\frac1\delta. \] $\square$

Theorem 5.3. Let $K>1$, and let $A$ be any finite multiset of positive integers with \[ R(A)>K. \] Let $m(K)$ be the smallest positive integer satisfying \[ m(K)-H_{m(K)} > K-1. \] Then \[ \varepsilon(A)\le \frac{1}{m(K)}. \] In particular, \[ \varepsilon(A)\le \frac1K. \]

Proof. Choose $S\subseteq A$ maximizing $R(S)$ under the constraint $R(S)\le 1$, and write \[ \delta:=1-R(S)=\varepsilon(A). \] If $\delta=0$, there is nothing to prove. So assume $\delta>0$.

Then no submultiset of $A$ sums exactly to $1$, so Lemma 5.1 applies. Also, by Lemma 5.2, every denominator appearing in $A\setminus S$ is at most \[ M:=\left\lfloor \frac1\delta\right\rfloor. \] Therefore the total reciprocal sum of all omitted elements is at most \[ \sum_{n=2}^{M}\frac{n-1}{n}=M-H_M. \] On the other hand, \[ R(A\setminus S)=R(A)-R(S)>K-(1-\delta)=K-1+\delta>K-1. \] Hence \[ M-H_M > K-1. \] By the minimality of $m(K)$ we get $M\ge m(K)$, and therefore \[ \delta\le \frac1M\le \frac{1}{m(K)}. \] This proves the main claim.

For the simpler bound, note that $m(K)>K-1$, so $m(K)\ge K$ (because $m(K)$ is an integer). Hence \[ \varepsilon(A)=\delta\le \frac{1}{m(K)}\le \frac1K. \] $\square$

Corollary 5.4. One has \[ m(K)=K+\log K+O(1), \] and therefore \[ \varepsilon(A)\le \frac{1}{K+\log K+O(1)}. \]

Proof. This is immediate from the standard asymptotic \[ H_m=\log m+\gamma+O(1/m). \] Then \[ m-H_m = m-\log m-\gamma+O(1/m), \] and solving the inequality $m-H_m>K-1$ gives \[ m=K+\log K+O(1). \] Substituting into Theorem 5.3 completes the argument. $\square$

Remark. Theorem 5.3 is weaker than the already-known Erdős--Graham type bound $\varepsilon(A)\ll 1/K^2$ quoted on the current problem page, but it is a fully self-contained theorem proved here. It also removes the vague phrase "sufficiently large" entirely: for this weaker bound, no size hypothesis on $A$ is needed.

6) ADVERSARIAL VERIFICATION

• Lemma 5.1 only uses one denominator at a time, so there is no hidden interaction issue.
• In Lemma 5.2 the maximality is with respect to all submultisets $S$ satisfying $R(S)\le 1$, not a greedy or ordered construction. That is enough.
• The proof of Theorem 5.3 uses $\delta>0$ only to ensure there is no exact-$1$ submultiset and to define $M=\lfloor 1/\delta\rfloor$.
• The omitted-sum upper bound \[ R(A\setminus S)\le \sum_{n=2}^M \frac{n-1}{n} \] is valid because each denominator $n\le M$ can occur at most $n-1$ times in all of $A$, hence certainly in $A\setminus S$.
• The argument is uniform in non-integer $K$ as well, because $m(K)$ is defined by an inequality, not by divisibility.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advance over Round 1 is a genuine universal theorem: for every finite multiset $A$ with reciprocal sum $>K$, \[ \varepsilon(A)\le \frac{1}{m(K)}=\frac{1}{K+\log K+O(1)}\le \frac1K. \]

This is still far weaker than the conjectured exponential bound \[ \varepsilon(A)\le e^{-cK}, \] and it is also weaker than the already-known $O(1/K^2)$ bound cited in the literature context. But it is a rigorous theorem proved in full detail here, and it converts Round 1 from "context plus an obstruction family" into an actual general quantitative result.

8) COMPLETION ESTIMATE

COMPLETION: 66%

9) REFERENCES

1. P. Erdős and R. Graham, Old and New Problems and Results in Combinatorial Number Theory, problem source for #312.
2. T. F. Bloom, Erdős Problem #312, Erdős Problems website, accessed 2026-03-07.
3. T. F. Bloom, Erdős Problem #312 -- Discussion thread, Erdős Problems website, accessed 2026-03-07.

10) OUTPUT FORMAT

This file is already in drop-in LaTeX format with no preamble.

Erdős Problem #312: independent continuation

Date: 23 September 2026. Source versions read in full: 312.tex in gpt_pro_5.4.

1) OBJECTIVE AND SOURCE AUDIT

The target is exponential closeness to one from below when a multiset has reciprocal mass greater than $K$. The source's maximal-subset argument gives only inverse-linear closeness. I improve its elementary counting constant using dyadic chains; this still does not match even the known inverse-square bound, let alone the conjectured exponential rate.

2) WORK: A CHAIN HAS TOTAL MASS LESS THAN ONE

If a multiset contains denominators only of the form $m2^j$ for a fixed odd $m$, and has total reciprocal mass at least one, it has a submultiset of mass exactly one. To see this, choose the largest exponent $J$ present and scale by $m2^J$. The weights are powers of two at most $2^J$, and the target is the multiple $m2^J$. Repeatedly combine pairs of equal smaller weights until every smaller denomination has at most one copy. Those residual weights total less than $2^J$. If total mass is at least $m2^J$, at least $m$ bundles of weight $2^J$ must have been formed. Taking $m$ of those disjoint bundles proves the claim.

Now choose a submultiset $S$ with maximal mass $1-\delta\le1$. If $\delta>0$, there is no exact-one submultiset anywhere. Every omitted denominator is less than $1/\delta$, by maximality. Put $M=\lceil1/\delta\rceil-1$. Partition the omitted denominators according to their odd parts. There are at most $\lceil M/2\rceil$ chains, and each has mass strictly less than one by the preceding lemma. Therefore \[ K-1+\delta<R(A\setminus S)<\lceil M/2\rceil \le(M+1)/2<(1/\delta+1)/2. \] After rearrangement this gives \[ 2\delta^2+(2K-3)\delta<1, \qquad \delta<\frac{\sqrt{(2K-3)^2+8}-(2K-3)}4. \] For large $K$ the right side is $(1+o(1))/(2K)$, improving the source's elementary leading constant by a factor of two.

3) ADVERSARIAL VERIFICATION

Binary carrying retains disjoint groups of original occurrences, so it does not create unauthorized multiplicities. Different odd-part chains need not be independent; only the necessary bound on each chain is used. The result is deliberately compared with the source's elementary bound, not claimed to improve the literature. A comment on the official discussion announces still stronger progress; it is not an input to this proof.

7) FINAL AND REFERENCE

UNRESOLVED. The exponential target remains out of reach. The proof gives a modest self-contained refinement and identifies where the linear loss survives: summing over all odd parts separately. Exact target checked at https://www.erdosproblems.com/312.

8) COMPLETION ESTIMATE

COMPLETION: 8% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Erdős Problem #312

FORMAL RESTATEMENT

Let $A$ be a finite multiset of (typically positive) integers, and write \[ R(A):=\sum_{n\in A}\frac1n. \] For a submultiset $S\subseteq A$ write $R(S)=\sum_{n\in S}1/n$. Define the "gap below $1$" as \[ \varepsilon(A):=\min\{\,1-R(S):\ S\subseteq A,\ R(S)\le 1\,\}. \] (Thus $0\le \varepsilon(A)\le 1$, and $\varepsilon(A)=0$ iff some submultiset sums to $1$ exactly.)

The question asks whether there exists an absolute constant $c>0$ such that for all $K>1$, whenever $A$ is a sufficiently large finite multiset with $R(A)>K$, one has \[ \varepsilon(A)\le e^{-cK}, \] equivalently: there exists $S\subseteq A$ with \[ 1-e^{-cK}<R(S)\le 1. \]

Stress points / ambiguity checks.

• If $1\in A$ then $\varepsilon(A)=0$ trivially by taking $S=\{1\}$; the interesting regime is $A\subseteq\{2,3,4,\dots\}$.
• The phrase "sufficiently large" is ambiguous in isolation (large cardinality? large elements?); I interpret it in the standard way: there exists $N_0(K)$ such that the conclusion holds whenever $|A|\ge N_0(K)$ and $R(A)>K$.
• The problem is quantitative: Erdős--Graham reportedly knew a weaker bound with $e^{-cK}$ replaced by $c/K^2$.

QUICK LITERATURE/CONTEXT CHECK

A quick web check indicates the problem is currently listed as open; the discussion notes the known weaker bound $\varepsilon(A)\ll 1/K^2$ (Erdős--Graham) and provides an example multiset built from primes which avoids subset sums equal to $1$. (See sources cited in the accompanying chat message.)

ATTACK PLAN

1. Prove at least one robust construction illustrating obstructions (no exact subset sum $1$), and quantify the minimum possible gap in that construction.
2. Examine whether generic "pigeonhole/density of subset sums" heuristics could yield an exponential gap $e^{-cK}$, and identify where positivity/submultiset constraints block a direct argument.

WORK

A modular obstruction construction (from the discussion thread). Fix $N\ge 2$ and define a multiset \[ A_N:=\bigsqcup_{p\le N}\{\underbrace{p,p,\dots,p}_{p-1\text{ copies}}\}, \] i.e. for every prime $p\le N$, include $p$ with multiplicity $p-1$.

Lemma 1. No submultiset $S\subseteq A_N$ satisfies $R(S)=1$.

Proof. Let $S\subseteq A_N$ be any submultiset. For each prime $p\le N$, let $a_p\in\{0,1,\dots,p-1\}$ be the number of times $p$ appears in $S$. Then \[ R(S)=\sum_{p\le N}\frac{a_p}{p}. \] Let $L:=\prod_{p\le N} p$ (the primorial $N^\#$). Multiply the equation $R(S)=1$ by $L$ to get \[ \sum_{p\le N} a_p\frac{L}{p} = L. \] Now fix a prime $r\le N$ and reduce this congruence modulo $r$. For $p\neq r$, the term $(L/p)$ is divisible by $r$, so it vanishes mod $r$. Thus the congruence becomes \[ a_r\frac{L}{r}\equiv L \equiv 0 \pmod r. \] But $r\nmid (L/r)$, so $(L/r)$ is invertible modulo $r$, forcing $a_r\equiv 0\pmod r$. Since $0\le a_r\le r-1$, this implies $a_r=0$. As this holds for every prime $r\le N$, all $a_p=0$, hence $R(S)=0\neq 1$. $\square$

Lemma 2 (Gap lower bound for $A_N$). For $A_N$ as above, \[ \varepsilon(A_N)\ge \frac{1}{N^\#}=\frac{1}{\prod_{p\le N}p}. \]

Proof. Every submultiset sum $R(S)=\sum_{p\le N} a_p/p$ is a rational with denominator dividing $N^\#$ (after clearing denominators by $N^\#$). Therefore the set \[ \{\,R(S): S\subseteq A_N\,\} \] lies in $(1/N^\#)\mathbb Z$. In particular, among values $\le 1$, the distance to $1$ is an integer multiple of $1/N^\#$. By Lemma 1 the distance is never $0$, so it is at least $1/N^\#$. This is exactly $\varepsilon(A_N)\ge 1/N^\#$. $\square$

Size of $R(A_N)$. We have \[ R(A_N)=\sum_{p\le N}\frac{p-1}{p}=\sum_{p\le N}\left(1-\frac1p\right) = \pi(N)-\sum_{p\le N}\frac1p, \] so in particular $R(A_N)\ge \pi(N)-\sum_{p\le N}1/2 = \pi(N)-\pi(N)/2 = \pi(N)/2$, and in fact $R(A_N)\sim \pi(N)$ as $N\to\infty$.

Thus this construction produces families with $R(A_N)$ growing like $\pi(N)$ while guaranteeing $\varepsilon(A_N)\ge 1/N^\#$, i.e. the gap can be as small as $\exp(-(1+o(1))N)$.

VERIFICATION (adversarial proof check; stress-test edge cases)

• Lemma 1: The congruence reduction is valid because $L$ is divisible by every prime $\le N$, and for $p\neq r$, $L/p$ retains the factor $r$. The key invertibility of $L/r$ mod $r$ holds since $r\nmid (L/r)$.
• Lemma 2: The denominator argument uses that $R(S)$ has denominator dividing $N^\#$. This is true because $R(S)$ is a $\mathbb Z$-linear combination of $\{1/p\}_{p\le N}$.
• Edge case $N=2$: Then $A_2$ contains one copy of $2$; Lemma 1 says no subset sums to $1$, true. Lemma 2 gives $\varepsilon(A_2)\ge 1/2$, and indeed the best $R(S)\le 1$ is $1/2$.

FINAL

UNRESOLVED.

• What is proved here. A clean obstruction family $A_N$ with no exact subset sum $1$, together with the rigorous lower bound $\varepsilon(A_N)\ge 1/N^\#$.
• Key obstacle. This does not decide whether every multiset with $R(A)>K$ admits a submultiset sum in $(1-e^{-cK},1]$ for some absolute $c$; no proof of the desired exponential bound (or counterexample disproving it) is given.
• Most promising next step. Either: (i) attempt to prove a general exponential upper bound for $\varepsilon(A)$ by controlling the density of achievable submultiset sums near $1$; or (ii) search for constructions where $\varepsilon(A)$ is provably bounded below by a polynomial in $1/K$, which would refute the exponential claim.
• Deliverables if continuing. A complete proof of $\varepsilon(A)\le e^{-cR(A)}$ for some $c>0$, or an explicit family $A^{(K)}$ with $R(A^{(K)})\ge K$ but $\varepsilon(A^{(K)})\gg e^{-cK}$ for every $c$.

COMPLETION ESTIMATE

COMPLETION: 55%