gpt pro 5.2 attempt on Math-5572
mathematicsErdős problemscontributionManuscript
Contents
Erdős Problem #311
FORMAL RESTATEMENT
For each $N\in\mathbb N$, define \[ \delta(N):=\min\left\{\left|1-\sum_{n\in A}\frac1n\right|:\; A\subseteq\{1,2,\dots,N\},\; \forall S\subseteq A,\ \sum_{n\in S}\frac1n\neq 1 \right\}. \] Equivalently, we look for a subset $A$ whose reciprocal sum is as close as possible to $1$, subject to the constraint that no subsubset $S\subseteq A$ has reciprocal sum exactly $1$.The question asks for the asymptotic behavior of $\delta(N)$ as $N\to\infty$; in particular, whether \[ \delta(N)=e^{-(c+o(1))N} \quad\text{for some constant }c\in(0,1). \]
Stress points / ambiguity checks.
- The constraint is on all subsubsets $S\subseteq A$, including $S=A$; thus any $A$ with $\sum_{n\in A}1/n=1$ is forbidden.
- Without the constraint, the minimal nonzero distance to $1$ is at least $1/\mathrm{lcm}(1,\dots,N)$ by a denominator argument (proved below).
- The statement "$\delta(N)=e^{-(c+o(1))N}$" should be read as a conjectural asymptotic, not as already-established.
QUICK LITERATURE/CONTEXT CHECK
A quick web check indicates this problem is currently listed as open; known general bounds include the trivial lower bound $1/\mathrm{lcm}(1,\dots,N)\approx e^{-N}$ and a much weaker (larger) upper bound of the form $\exp\!\big(-cN/(\log N\,\log\log N)^3\big)$ due to work of Tang (as described on the Erdős Problems site). (See sources cited in the accompanying chat message.)ATTACK PLAN
- Prove unconditional basic bounds: a clean arithmetic lower bound on $\delta(N)$.
- Compute small $N$ exactly to calibrate growth and to test whether minimizers violate the "no subsubset sums to $1$" constraint.
- (Unfinished) Seek constructions giving exponentially small $\delta(N)$, or obstructions showing $\delta(N)$ cannot be that small.
WORK
Lemma 1 (Denominator lower bound). Let $L_N:=\mathrm{lcm}(1,2,\dots,N)$. For every subset $A\subseteq\{1,\dots,N\}$ we have \[ \sum_{n\in A}\frac1n = \frac{m}{L_N} \] for some integer $m$. Consequently, for any $A$ with $\sum_{n\in A}\frac1n\neq 1$, \[ \left|1-\sum_{n\in A}\frac1n\right|\ge \frac{1}{L_N}, \] and hence \[ \delta(N)\ge \frac{1}{L_N}. \]Proof. Each $1/n$ equals $(L_N/n)/L_N$ with $L_N/n\in\mathbb Z$. Summing over $n\in A$ gives an integer numerator over $L_N$. If the sum is not exactly $1=L_N/L_N$, then the numerator differs from $L_N$ by a nonzero integer, hence by at least $1$ in absolute value. Dividing by $L_N$ yields the bound. $\square$
Remark. Since $\log L_N = (1+o(1))N$ (a classical estimate equivalent to the prime number theorem), Lemma 1 gives $\delta(N)\ge \exp(-(1+o(1))N)$.
Small-$N$ computation. Using an exact meet-in-the-middle search on the subset sums of $\{1,2,\dots,N\}$ (scaled by $L_N$), one finds the following values of $\delta(N)$ for $1\le N\le 25$, together with one witness set $A$. All the listed witnesses $A$ are "$1$-avoiding" in the required sense (no subsubset sums to $1$).
| $N$ | $\delta(N)$ | one witness $A\subseteq\{1,\dots,N\}$ |
| 1 | $1$ | $\{\}$ |
| 2 | $\frac{1}{2}$ | $\{2\}$ |
| 3 | $\frac{1}{6}$ | $\{2, 3\}$ |
| 4 | $\frac{1}{12}$ | $\{2, 3, 4\}$ |
| 5 | $\frac{1}{30}$ | $\{2, 3, 5\}$ |
| 6 | $\frac{1}{30}$ | $\{2, 3, 5\}$ |
| 7 | $\frac{1}{105}$ | $\{2, 5, 6, 7\}$ |
| 8 | $\frac{1}{120}$ | $\{2, 5, 6, 8\}$ |
| 9 | $\frac{1}{252}$ | $\{2, 4, 7, 9\}$ |
| 10 | $\frac{1}{360}$ | $\{2, 6, 8, 9, 10\}$ |
| 11 | $\frac{1}{2310}$ | $\{2, 6, 7, 10, 11\}$ |
| 12 | $\frac{1}{2310}$ | $\{3, 4, 7, 10, 11, 12\}$ |
| 13 | $\frac{1}{2310}$ | $\{3, 4, 7, 10, 11, 12\}$ |
| 14 | $\frac{1}{2772}$ | $\{2, 7, 9, 11, 12, 14\}$ |
| 15 | $\frac{1}{2772}$ | $\{2, 7, 9, 11, 12, 14\}$ |
| 16 | $\frac{1}{6160}$ | $\{2, 8, 11, 12, 14, 15, 16\}$ |
| 17 | $\frac{1}{30940}$ | $\{2, 7, 12, 13, 14, 15, 17\}$ |
| 18 | $\frac{1}{30940}$ | $\{2, 7, 12, 13, 14, 15, 17\}$ |
| 19 | $\frac{5}{298452}$ | $\{2, 7, 11, 12, 14, 17, 19\}$ |
| 20 | $\frac{5}{298452}$ | $\{2, 7, 11, 12, 14, 17, 19\}$ |
| 21 | $\frac{11}{1244880}$ | $\{2, 12, 13, 14, 16, 18, 19, 20, 21\}$ |
| 22 | $\frac{23}{17907120}$ | $\{4, 7, 9, 11, 14, 15, 16, 17, 19, 21, 22\}$ |
| 23 | $\frac{1}{1105104}$ | $\{2, 7, 11, 12, 13, 16, 23\}$ |
| 24 | $\frac{1}{1105104}$ | $\{3, 4, 7, 11, 13, 16, 23\}$ |
| 25 | $\frac{1}{1593900}$ | $\{2, 9, 11, 14, 20, 21, 22, 23, 25\}$ |
These values match the list recorded in the problem discussion thread (at least up to $N=25$), and illustrate that $\delta(N)$ can be much smaller than $1/N$ even for modest $N$.
VERIFICATION (adversarial proof check; stress-test edge cases)
- Lemma 1 is purely arithmetic and exact: the key point is that every reciprocal sum over $\{1,\dots,N\}$ is a rational with denominator dividing $L_N$.
- The computational table: meet-in-the-middle is exact because it operates on integers $L_N/n$ and checks exact equality/inequality to $L_N$; no floating point is needed.
- The "$1$-avoiding" condition for each witness was additionally checked by a second meet-in-the-middle subset-sum test within $A$.
FINAL
UNRESOLVED.- What is proved here. The clean unconditional lower bound $\delta(N)\ge 1/\mathrm{lcm}(1,\dots,N)=\exp(-(1+o(1))N)$, and exact values for $N\le 25$.
- Key obstacle. No argument here gives a matching exponential upper bound $\delta(N)\le \exp(-(c+o(1))N)$, nor a disproof of such an upper bound.
- Most promising next step. Develop explicit constructions of $1$-avoiding sets $A$ with reciprocal sum extremely close to $1$ (e.g. via structured Egyptian-fraction approximations), or prove anti-concentration results preventing too-close approximation under the $1$-avoiding constraint.
- Deliverables if continuing. Either (i) a construction giving $\delta(N)\le e^{-(c+o(1))N}$, or (ii) a lower bound $\delta(N)\ge e^{-o(N)}$ (or similar) ruling out the conjectured exponential scale.