Erdős Problem #319

Round 2 continuation for Erdős problems #319, #359, #361

This file is written as a continuation of the Round-1 write-up. I explicitly indicate below whenever I use a Round-1 result as a black box.

---

Problem #319

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. Round 1 gave the lower bound \[ F(N)\ge \left(1-\frac1e+o(1)\right)N \] by using a singleton-sign construction \[ A=\{1\}\cup B,\qquad \sum_{b\in B}\frac1b=1. \] The most promising Round-2 step is therefore to determine whether this entire strategy can ever do better. I will prove that it cannot: within the class of solutions in which one sign class has size $1$, the constant $1-\frac1e$ is asymptotically best possible. Hence any future improvement for the full problem must use genuinely two-sided cancellation with at least two positive and two negative terms.

2) ROUND-1 FOUNDATION USED

I use the following Round-1 fact without re-proving it.

• Round 1 showed, using Croot's short-interval Egyptian-fraction theorem, that there exists \[ B\subseteq \left[\left(\frac1e-o(1)\right)N,N\right] \] with $\sum_{b\in B}1/b=1$, and hence \[ F(N)\ge \left(1-\frac1e+o(1)\right)N \] via the admissible set $A=\{1\}\cup B$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is a sharp extremal principle for reciprocal sums:

Maximal-cardinality reciprocal-sum principle. For fixed $r>0$, among all $m$-element subsets of $\{1,\dots,N\}$, the reciprocal sum \[ \sum_{n\in B}\frac1n \] is minimized by the terminal interval \[ \{N-m+1,\dots,N\}. \]

This immediately turns the problem of maximizing $|B|$ subject to $\sum_{b\in B}1/b=r$ into a harmonic-tail calculation, and it gives a matching upper bound to the Round-1 lower-bound strategy.

4) ATTACK PLAN (ROUND-2)

The exact gap left by Round 1 was this: the construction \[ A=\{1\}\cup B,\qquad \sum_{b\in B}\frac1b=1 \] gave a lower bound, but there was no proof that this particular type of construction was already optimal.

So I will now prove two precise claims.

• (i) For every fixed rational $r>0$, if \[ M_r(N):=\max\left\{|B|:\ B\subseteq \{1,\dots,N\},\ \sum_{b\in B}\frac1b=r\right\}, \] then \[ M_r(N)=\left(1-e^{-r}+o(1)\right)N. \]
• (ii) Consequently, if an admissible solution to Problem #319 has one sign class of size $1$, then its total size is at most \[ \left(1-\frac1e+o(1)\right)N. \]

This closes the entire Round-1 "singleton-sign" avenue.

5) WORK (ROUND-2)

Proposition 319.1.

Fix a rational number $r>0$. Let \[ M_r(N):=\max\left\{|B|:\ B\subseteq \{1,\dots,N\},\ \sum_{b\in B}\frac1b=r\right\}. \] Then \[ M_r(N)=\left(1-e^{-r}+o(1)\right)N \qquad (N\to\infty). \]

Proof.

I first prove the upper bound.

Suppose $B\subseteq \{1,\dots,N\}$ has cardinality $m$ and \[ \sum_{b\in B}\frac1b=r. \] Since the function $n\mapsto 1/n$ is strictly decreasing, the reciprocal sum of an $m$-element subset is minimized by choosing the $m$ largest available integers. Therefore \[ r=\sum_{b\in B}\frac1b \ge \sum_{n=N-m+1}^{N}\frac1n = H_N-H_{N-m}, \] where $H_t$ denotes the $t$th harmonic number.

Using $H_t=\log t+\gamma+o(1)$ uniformly for $t\to\infty$, we get \[ r\ge \log\!\left(\frac{N}{N-m}\right)+o(1). \] Exponentiating, \[ \frac{N}{N-m}\le e^{\,r+o(1)}, \] so \[ 1-\frac{m}{N}\ge e^{-r+o(1)}=e^{-r}+o(1). \] Hence \[ m\le \left(1-e^{-r}+o(1)\right)N. \] This proves \[ M_r(N)\le \left(1-e^{-r}+o(1)\right)N. \]

For the lower bound I use Croot's theorem, exactly as in Round 1 but with $1$ replaced by $r$. Croot proved that for every fixed rational $r>0$ there are, for all sufficiently large $X$, distinct integers \[ X<n_1<\cdots<n_k<(e^r+o_r(1))X \] such that \[ \sum_{i=1}^k \frac1{n_i}=r. \] Choose $X=X(N)$ so that \[ (e^r+o_r(1))X\le N. \] Then there is a set \[ B\subseteq \left[(e^{-r}-o(1))N,\ N\right] \] with \[ \sum_{b\in B}\frac1b=r. \]

Let \[ I_N:=\left\{\left\lceil (e^{-r}-o(1))N\right\rceil,\dots,N\right\}. \] The reciprocal sum of the full interval is \[ \sum_{n\in I_N}\frac1n = \log(e^r)+o(1)=r+o(1). \] Since $B\subseteq I_N$ and $\sum_{b\in B}1/b=r$, it follows that \[ \sum_{n\in I_N\setminus B}\frac1n=o(1). \] Every omitted element of $I_N$ is at most $N$, so each contributes at least $1/N$. Hence \[ \frac{|I_N\setminus B|}{N}\le \sum_{n\in I_N\setminus B}\frac1n=o(1), \] that is, \[ |I_N\setminus B|=o(N). \] Therefore \[ |B|=|I_N|-o(N)=\left(1-e^{-r}+o(1)\right)N. \] So \[ M_r(N)\ge \left(1-e^{-r}+o(1)\right)N. \] Together with the upper bound, this proves the proposition. $\square$

Corollary 319.2 (singleton-sign solutions are completely understood).

Let $A\subseteq \{1,\dots,N\}$ be admissible for Problem #319, and write \[ A=P\sqcup Q,\qquad \sum_{p\in P}\frac1p=\sum_{q\in Q}\frac1q. \] If $\min\{|P|,|Q|\}=1$, then \[ |A|\le \left(1-\frac1e+o(1)\right)N. \]

Proof.

By symmetry it suffices to consider the case $P=\{p\}$ for some $p\in\{1,\dots,N\}$. Then \[ \sum_{q\in Q}\frac1q=\frac1p. \] Applying Proposition 319.1 with $r=1/p$ gives \[ |Q|\le \left(1-e^{-1/p}+o(1)\right)N. \] Since the function $p\mapsto 1-e^{-1/p}$ is decreasing for $p\ge 1$, its maximum occurs at $p=1$, giving \[ |Q|\le \left(1-\frac1e+o(1)\right)N. \] Hence \[ |A|=|Q|+1\le \left(1-\frac1e+o(1)\right)N. \] $\square$

Corollary 319.3 (exact asymptotic for the Round-1 class).

Let $F_{\mathrm{sing}}(N)$ be the maximum size of an admissible set in Problem #319 for which one sign class has size $1$. Then \[ F_{\mathrm{sing}}(N)=\left(1-\frac1e+o(1)\right)N. \]

Proof.

The upper bound is Corollary 319.2. The matching lower bound is exactly the Round-1 construction $A=\{1\}\cup B$ with $\sum_{b\in B}1/b=1$ and \[ |B|=\left(1-\frac1e+o(1)\right)N. \] $\square$

6) ADVERSARIAL VERIFICATION

I check the new argument against the obvious failure modes.

• Did I accidentally use minimality where only equality was needed? No. Proposition 319.1 is purely about subsets $B$ with a fixed reciprocal sum, and Corollary 319.2 uses only the equality \[ \sum_{p\in P}\frac1p=\sum_{q\in Q}\frac1q. \] So the upper bound for singleton-sign solutions is valid a fortiori.

• Could a non-terminal set of the same size have smaller reciprocal sum than the terminal interval? No. Replacing any denominator by a larger one strictly decreases its reciprocal. Repeating this replacement process pushes every $m$-element set to the terminal interval and can only decrease the reciprocal sum.

• Does the lower bound really give almost all elements of the interval? Yes. The missing reciprocal mass is $o(1)$, and every omitted denominator contributes at least $1/N$, so the number of omitted denominators is $o(N)$.

• Does the corollary really rule out every singleton-sign strategy, not just $P=\{1\}$? Yes. The proof treats an arbitrary singleton $\{p\}$ and shows that the constant is maximized at $p=1$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 proves a genuine obstruction that was absent in Round 1:

• the entire singleton-sign class is now solved asymptotically, and
• the Round-1 constant $1-\frac1e$ is exactly the best possible constant obtainable from any construction with one positive term or, more generally, with one sign class of size $1$.

So any future improvement for the full problem must use at least two positive and two negative denominators. In other words, the Round-1 mechanism has now been exhausted, not merely exhibited.

8) COMPLETION ESTIMATE

COMPLETION: 60%

9) REFERENCES

• E. S. Croot III, On unit fractions with denominators in short intervals, Acta Arithmetica 99 $2001$, 99--114.
• T. F. Bloom, Erdős Problem #319, erdosproblems.com/319 (checked in this round).

---

Erdős Problem #319: independent continuation

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

1) OBJECTIVE AND SOURCE AUDIT

The problem maximizes the size of a minimal signed vanishing reciprocal sum, with no proper nonempty zero-sum subcollection. The source settles the asymptotic density of the singleton-sign construction. Its proof applies a fixed-$r$ asymptotic with $r=1/p$, although $p$ can depend on $N$. The following finite inequality fixes that uniformity issue and extends the obstruction to every bounded size of the smaller sign class.

2) WORK: BOUNDED SIGN CLASSES CANNOT APPROACH DENSITY ONE

Write $A=P\sqcup Q$ and suppose the two reciprocal sums agree. Put $h=\min(|P|,|Q|)$ and, by exchanging signs, assume $|P|=h$, $|Q|=m$. Since the largest possible reciprocal mass of $h$ distinct positive integers is $H_h$, while the smallest mass of $m$ members of $[1,N]$ is a terminal harmonic sum, \[ H_h\ge\sum_{p\in P}1/p=\sum_{q\in Q}1/q \ge H_N-H_{N-m} \ge\log\frac{N+1}{N-m+1}. \] The last inequality follows by integrating $1/t$ over $[N-m+1,N+1]$. Hence the uniform finite bound is \[ |A|=h+m\le h+(N+1)(1-e^{-H_h}). \tag{1} \] For $h=1$ this recovers the source's upper density $1-e^{-1}$ without any parameter-dependent error term. For each fixed $h$, it gives the upper density $1-e^{-H_h}<1$. Thus a sequence of admissible sets with $|A|/N\to1$ must have both sign-class sizes tending to infinity.

More quantitatively, using $H_h\le1+\log h$ in $1$, \[ N-|A|\ge\frac{N+1}{eh}-h-1. \] This is nontrivial, for example, when $h=o(\sqrt N)$. It isolates a necessary growth requirement on the number of positive and negative terms for any construction improving strongly on the singleton mechanism.

3) ADVERSARIAL VERIFICATION

The inequality needs only equality of the two masses, so it applies in particular to minimal signed zero sums. It does not prove minimality for a proposed new construction. Combining two existing signed relations would generally violate minimality by retaining a proper vanishing subset. No matching construction for the fixed-$h$ bound is asserted.

7) FINAL AND REFERENCE

UNRESOLVED. A uniform finite bound and a larger family of structural obstructions are proved, but the maximal size of a minimal relation remains undetermined. The minimality condition was checked in the indexed primary statement: https://www.erdosproblems.com/319.

8) COMPLETION ESTIMATE

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

Problem #319

1) FORMAL RESTATEMENT

For each integer $N\ge 1$, let $F(N)$ be the maximum cardinality of a set $A\subseteq \{1,2,\dots,N\}$ for which there exists a sign function \[ \delta:A\to\{-1,+1\},\qquad n\mapsto \delta_n, \] such that \[ \sum_{n\in A}\frac{\delta_n}{n}=0, \] and moreover \[ \sum_{n\in A'}\frac{\delta_n}{n}\neq 0 \quad\text{for every nonempty proper subset } \varnothing\neq A'\subsetneq A. \] The problem asks for good bounds/asymptotics for $F(N)$ as $N\to\infty$.

2) CONTEXT AND DEFINITIONS

Writing $A=P\sqcup Q$ where $P=\{n\in A:\delta_n=+1\}$ and $Q=\{n\in A:\delta_n=-1\}$, the condition is equivalent to \[ \sum_{p\in P}\frac1p=\sum_{q\in Q}\frac1q, \] together with a minimality condition: there do not exist nonempty proper subcollections $P'\subseteq P$, $Q'\subseteq Q$ with $\sum_{p\in P'}\frac1p=\sum_{q\in Q'}\frac1q$.

A particularly simple way to guarantee minimality is to take $P=\{1\}$ and $Q=B$ for some $B\subseteq\{2,\dots,N\}$ with $\sum_{b\in B}\frac1b=1$. Then any proper sub-sum over $B$ is $<1$.

3) QUICK LITERATURE/CONTEXT CHECK

The Erdős Problems page for #319 records an observation of Adenwalla that a linear-size lower bound follows from a theorem of Croot on Egyptian fractions in short intervals: there exists $B\subset [(\frac1e-o(1))N,N]$ with $\sum_{b\in B}1/b=1$, which yields $|A|\ge (1-\frac1e+o(1))N$ by taking $A=B\cup\{1\}$ with signs $+1$ on $1$ and $-1$ on $B$.

4) ATTACK PLAN

I will (i) state the needed consequence of Croot's theorem precisely; (ii) give a complete proof that it implies \[ F(N)\ge \left(1-\frac1e+o(1)\right)N; \] and (iii) check the "no proper subset sums to $0$" condition carefully.

This does not resolve the full asymptotic for $F(N)$, but it does give a fully rigorous linear lower bound of the claimed constant.

5) DETAILED WORK

Step 1: A usable consequence of Croot's theorem.

Croot proved (among other things) that for any fixed rational $r>0$ and sufficiently large $X$ there exist integers \[ X < n_1 < n_2 < \cdots < n_k < (e^r+o_r(1))X \] such that $\sum_{i=1}^k \frac1{n_i}=r$. Specializing to $r=1$ and choosing $X=X(N)$ with $(e+o(1))X\le N$ (e.g. $X=N/(e+\varepsilon_N)$ for any $\varepsilon_N\to 0^+$) gives:

Lemma 319.1 (existence of an interval representation of $1$). There exists a function $\alpha_N\to 1/e$ and, for all sufficiently large $N$, a finite set of integers \[ B\subseteq \{\lceil \alpha_N N\rceil,\lceil \alpha_N N\rceil+1,\dots,N\} \] such that \[ \sum_{b\in B}\frac1b = 1. \]

Step 2: This forces $B$ to have (almost) full size in the interval.

Let $I_N=\{\lceil \alpha_N N\rceil,\dots,N\}$. Using the integral test (or the asymptotic $H_n=\log n+\gamma+o(1)$), \[ \sum_{m\in I_N}\frac1m = \log\!\Big(\frac{N}{\alpha_N N}\Big) + o(1) = \log\!\Big(\frac1{\alpha_N}\Big)+o(1) = 1+o(1) \quad (N\to\infty), \] since $\alpha_N\to 1/e$.

Because $B\subseteq I_N$ and $\sum_{b\in B}\frac1b=1$, we have \[ \sum_{m\in I_N\setminus B}\frac1m = \sum_{m\in I_N}\frac1m - 1 = o(1). \] But every $m\in I_N\setminus B$ satisfies $m\le N$, hence $1/m\ge 1/N$. Therefore \[ \frac{|I_N\setminus B|}{N} \le \sum_{m\in I_N\setminus B}\frac1m = o(1), \] so $|I_N\setminus B|=o(N)$, i.e. \[ |B|=|I_N|-o(N)=\left(N-\lceil \alpha_N N\rceil +1\right)-o(N) = \left(1-\frac1e+o(1)\right)N. \]

Step 3: Build $A$ and verify minimality.

Let \[ A := B\cup\{1\}\subseteq\{1,\dots,N\}, \qquad \delta_1:=+1,\ \delta_b:=-1\ (b\in B). \] Then \[ \sum_{n\in A}\frac{\delta_n}{n} = 1-\sum_{b\in B}\frac1b = 0. \] Now let $\varnothing\neq A'\subsetneq A$.

• If $1\notin A'$, then $A'\subseteq B$ and $\sum_{n\in A'}\frac{\delta_n}{n}=-\sum_{b\in A'}\frac1b<0$, so it is nonzero.
• If $1\in A'$, write $A'=\{1\}\cup B'$ with $B'\subsetneq B$. Then \[ \sum_{n\in A'}\frac{\delta_n}{n} = 1-\sum_{b\in B'}\frac1b. \] Since $B'$ is a proper subset of $B$ and all terms are positive, $\sum_{b\in B'}\frac1b < \sum_{b\in B}\frac1b = 1$, hence the above sum is $>0$, in particular nonzero.

Thus $A$ satisfies all requirements and \[ |A|=|B|+1 \ge \left(1-\frac1e+o(1)\right)N. \]

6) VERIFICATION AND EDGE CASES

• The construction uses only positivity of the reciprocals to ensure strict inequality for proper subsets.
• For small $N$ this asymptotic statement is not informative; e.g. for $N=6$ one can take $A=\{1,2,3,6\}$ with signs $(+,-,-,-)$ since $1=\frac12+\frac13+\frac16$.

7) FINAL

UNRESOLVED.

• (i) Strongest proved partial result: $F(N)\ge (1-\frac1e+o(1))N$ via Croot's theorem and the explicit $A=B\cup\{1\}$ construction above.
• (ii) First remaining gap: obtain any nontrivial upper bound $F(N)\le (1-\varepsilon)N$ for some fixed $\varepsilon>0$, or determine the true asymptotic constant for $F(N)/N$.
• (iii) Next moves: study structure of minimal solutions of $\sum_{p\in P}1/p=\sum_{q\in Q}1/q$ with $P,Q\subseteq[1,N]$; try to rule out "too many" denominators by showing unavoidable sub-equalities among large sets of unit fractions.
• (iv) Minimal counterexample search: compute $F(N)$ for moderate $N$ by integer/rational exact search to guess the constant (if it exists), and to see whether extremals always have a "single positive term" form.

COMPLETION: 45%

---