gpt pro 5.2 attempt on Math-759

Erdős problem 320

1) FORMAL RESTATEMENT

For $N\in\mathbb{N}$ define \[ S(N):=\left|\left\{\sum_{n\in A}\frac{1}{n}\ :\ A\subseteq \{1,2,\dots,N\}\right\}\right|, \] the number of distinct subset sums of the reciprocals $1,1/2,\dots,1/N$. Estimate $S(N)$ as $N\to\infty$.

2) QUICK LITERATURE/CONTEXT CHECK

Problem text records Bleicher--Erdős bounds: \[ \log S(N)\ge \frac{N}{\log N}\log_2\log N(1-o(1)), \quad \log S(N)\le \frac{N}{\log N}(\log_2\log N)^2(1+o(1)), \] with later improvements (Losonczy). I do not reproduce these proofs here.

3) ATTACK PLAN

Prove two clean self-contained lemmas: $1$ subset sums over reciprocals of distinct primes are unique $\Rightarrow$ explicit lower bound in terms of $\pi(N)$, $2$ every subset sum has denominator dividing $\mathrm{lcm}(1,\dots,N)$ $\Rightarrow$ simple upper bound $S(N)\le \mathrm{lcm}(1,\dots,N)\cdot H_N+1$. Also compute exact $S(N)$ for small $N$.

4) WORK

Lemma 4.1 (Prime-reciprocal subset sums are distinct).

Let $P$ be any finite set of distinct primes. Then the sums $\sum_{p\in A}1/p$ are all distinct as $A$ ranges over subsets of $P$. Proof. Suppose $\sum_{p\in A}1/p=\sum_{p\in B}1/p$. Let $C=A\triangle B$ be the symmetric difference, and cancel common terms to obtain \[ \sum_{p\in C_+}\frac1p=\sum_{p\in C_-}\frac1p \] with $C_+\cup C_-=C$ disjoint. Multiply by $Q=\prod_{p\in C} p$ to get an integer equality \[ \sum_{p\in C_+} \frac{Q}{p}=\sum_{p\in C_-}\frac{Q}{p}. \] Let $\ell$ be the largest prime in $C$. Then $Q/\ell$ is not divisible by $\ell$, whereas for $p\ne \ell$, $Q/p$ is divisible by $\ell$. Reducing mod $\ell$ forces the side containing $Q/\ell$ to be nonzero and the other side $0$, contradiction. Hence $C=\emptyset$ and $A=B$. $\square$

Corollary 4.2.

For every $N$, $S(N)\ge 2^{\pi(N)}$, where $\pi(N)$ is the number of primes $\le N$. Proof. Take $P=\{p\le N:\ p\text{ prime}\}$ and restrict subset sums to primes only; by Lemma 4.1 they are all distinct. $\square$

Lemma 4.3 (LCM upper bound).

Let $L_N=\mathrm{lcm}(1,2,\dots,N)$ and $H_N=\sum_{n=1}^N 1/n$. Then \[ S(N)\le L_N\cdot H_N+1. \] Proof. Every subset sum $s=\sum_{n\in A}1/n$ is a rational number whose denominator (in lowest terms) divides $L_N$ because each $1/n$ has denominator dividing $L_N$. Hence $s=m/L_N$ for some integer $m\ge 0$. Also $0\le s\le H_N$, so $0\le m\le L_N H_N$. Thus there are at most $L_NH_N+1$ possibilities. $\square$

FAST REALITY CHECK (computed exact values)

Brute enumeration (exact rational arithmetic) gives: \[ \begin{array}{c|cccccccccccc} N&1&2&3&4&5&6&7&8&9&10&11&12\\\hline S(N)&2&4&8&16&32&52&104&208&416&832&1664&1856 \end{array} \] and continuing: $S(13)=3712$, $S(14)=7424$, $S(15)=9664$, $S(16)=19328$, $S(18)=59264$, $S(20)=126976$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial results: $S(N)\ge 2^{\pi(N)}$ (Lemma 4.1/Cor. 4.2) and $S(N)\le L_NH_N+1$ (Lemma 4.3).

(ii) First gap: bridge the large gap between these elementary bounds and the refined asymptotics stated in the problem text (of order $\exp((N/\log N)\,\text{polylog}\log N)$).

(iii) Top 3 next moves: 1. Strengthen lower bound by selecting structured denominators (smooth numbers / prime products) with uniqueness mod a large prime factor. 2. Improve upper bound by bounding collisions via additive relations among reciprocals (Egyptian fraction structure). 3. Compute $S(N)$ for larger $N$ and analyze collision patterns to guide theory.

(iv) Minimal counterexample structure (to very large growth): many distinct subsets producing identical rational sums; minimal collisions likely arise from small-denominator identities (e.g. Egyptian fraction decompositions) propagating multiplicatively.