gpt pro 5.2 attempt on Math-844

FORMAL RESTATEMENT. Fix an integer $r\ge 2$ and $N\ge 2$. Let $A\subseteq\{1,2,\dots,N\}$ satisfy the multiplicity condition: for every integer $m$, the number of pairs $(p,a)$ with $p$ prime, $a\in A$, and $m=p a$ is at most $r$. Equivalently, \[ \forall m\in\mathbb N:\quad \left|\{p\text{ prime}: p\mid m\ \text{and}\ m/p\in A\}\right|\le r. \] Determine the best possible upper bound (in terms of $r$ and $N$) for \[ \sum_{n\in A}\frac1n. \]

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself includes Erdős's double-counting argument yielding $\sum_{n\in A} \frac{1}{n} \ll r \frac{\log N}{\log\log N}$. I re-derive the exact inequality behind that bound. I do not claim optimality.

ATTACK PLAN. 1) Re-derive Erdős's inequality carefully and isolate the clean, unconditional form. 2) Produce explicit constructions of sets $A$ satisfying the multiplicity condition to get nontrivial lower bounds on the extremal harmonic sum. 3) Brute force for small $N$ to see what extremizers look like and what growth to expect.

WORK. Fast reality check (small $N$ brute force). For $N\le 18$ I brute-forced all subsets $A\subseteq\{1,\dots,N\}$ and computed the maximum possible value of $\sum_{n\in A}1/n$ subject to the multiplicity condition, for $r=1$ and $r=2$. The maximizing sets and values found (rounded) were: \[ \begin{array}{c|l|l} N & r=1\text{ best }\sum 1/n & r=2\text{ best }\sum 1/n\\\hline 8 & 1.875\ \ (A=\{1,2,4,8\}) & 2.717857\ \ (A=\{1,\dots,8\})\\ 12 & 1.986111\ (A=\{1,2,4,8,9\}) & 3.103211\ (A=\{1,\dots,12\})\\ 15 & 1.986111\ (A=\{1,2,4,8,9\}) & 3.251562\ (A=\{1,\dots,14\})\\ 18 & 1.986111\ (A=\{1,2,4,8,9\}) & 3.428441\ (A=\{1,\dots,14,16,17,18\}) \end{array} \] (These are exact for the searched range; they are not claimed to represent the asymptotic optimum.)

Lemma 538.1 (Erdős double counting inequality). Let $A\subseteq\{1,\dots,N\}$ satisfy the multiplicity condition with parameter $r$. Let $\mathcal P=\{p\text{ prime}: p\le N\}$. Then \[ \left(\sum_{a\in A}\frac{1}{a}\right)\left(\sum_{p\in\mathcal P}\frac{1}{p}\right) \le r\sum_{m\le N^2}\frac{1}{m}. \] In particular, \[ \sum_{a\in A}\frac{1}{a}\le r\,\frac{\sum_{m\le N^2}\frac{1}{m}}{\sum_{p\le N}\frac{1}{p}}. \]

Proof. Compute \[ \left(\sum_{a\in A}\frac{1}{a}\right)\left(\sum_{p\le N}\frac{1}{p}\right) =\sum_{a\in A}\sum_{p\le N}\frac{1}{ap}. \] For each ordered pair $(a,p)$, set $m=ap$. Since $a\le N$ and $p\le N$, we have $m\le N^2$. Regrouping the double sum by the value of $m$ gives \[ \sum_{a\in A}\sum_{p\le N}\frac{1}{ap} =\sum_{m\le N^2}\frac{1}{m}\cdot \#\{(p,a): p\le N\text{ prime},\ a\in A,\ ap=m\}. \] By the hypothesis, for every $m$ the multiplicity term is at most $r$. Therefore the whole sum is at most $\sum_{m\le N^2} (1/m)\cdot r$, proving the stated inequality. Dividing by $\sum_{p\le N}1/p$ yields the second display. $\square$

Lemma 538.2 (a family of admissible examples from $P$-smooth numbers). Let $P$ be any set of primes with $|P|=r$. Define \[ A_P:=\{a\in\{1,\dots,N\}: \text{every prime divisor of $a$ lies in $P$}\}. \] Then $A_P$ satisfies the multiplicity condition with parameter $r$. Moreover, \[ \sum_{a\in A_P}\frac1a \ge \prod_{p\in P}\frac{1}{1-1/p}\ -\ \text{(a nonnegative truncation error)}. \] In particular, for fixed $r$, the supremum of $\sum_{a\in A}1/a$ over admissible $A$ is at least a positive constant depending on $r$.

Proof (multiplicity). Fix $m\in\mathbb N$. If $m=pa$ with $a\in A_P$, then all prime divisors of $a$ lie in $P$, hence all prime divisors of $m$ other than $p$ lie in $P$. If $p\notin P$, then $m$ can have no other prime divisor outside $P$ (otherwise $a=m/p$ would inherit it and fail to lie in $A_P$), so $p$ is uniquely determined as the unique prime divisor of $m$ outside $P$ (if it exists). If $p\in P$, then different solutions correspond to different primes $p\in P$ dividing $m$ such that $m/p\le N$; there are at most $|P|=r$ such primes. Thus for every $m$ the number of solutions is $\le r$.

Proof (harmonic sum lower bound). The set of all positive integers with prime factors contained in $P$ has Euler product $ \sum_{a: \operatorname{supp}(a)\subseteq P} 1/a = \prod_{p\in P} (1+1/p+1/p^2+\cdots)=\prod_{p\in P} (1-1/p)^{-1}. $ The truncated set $A_P$ only omits terms with $a>N$, so its partial sum is at least the full Euler product minus a nonnegative tail. $\square$

VERIFICATION. Check Lemma 538.2 on a concrete collision. If $P=\{2,3\}$ and $A_P$ are the $\{2,3\}$-smooth numbers $\le N$, then for $m=2\cdot 3^t$ we have representations with $p=2$ and with $p=3$ (if $m/3\in A_P$), giving at most $2$ solutions, consistent with $r=2$.

FINAL.\;UNRESOLVED.

• (i) Strongest proved partial result. For every admissible $A$, \[ \sum_{a\in A}\frac{1}{a}\le r\,\frac{\sum_{m\le N^2} \frac{1}{m}}{\sum_{p\le N}\frac{1}{p}} \le r\,\frac{2\log N+1}{\sum_{p\le N}\frac{1}{p}}, \] where the second inequality uses the elementary bound $\sum_{m\le N^2}1/m\le 1+\int_1^{N^2} dx/x = 1+2\log N$. Also, the explicit admissible family $A_P$ of $P$-smooth numbers (Lemma 538.2) gives nontrivial lower bounds depending on $r$.
• (ii) First gap (crisp statement). Determine the true asymptotic order (in $N$) of $\sup\{\sum_{a\in A} 1/a : A\subseteq[1,N]\text{ admissible for }(r,N)\}$ for fixed $r$ (or describe the dependence when $r=r(N)$ grows).
• (iii) Top 3 next moves.
  • Try to show a stronger upper bound by exploiting the restriction on how many quotients $m/p$ can lie in $A$ for an $m$ with many prime factors, perhaps via a weighted sieve/entropy argument.
  • Search for better constructions than $P$-smooth numbers that make $\sum_{a\in A}1/a$ grow with $N$ while keeping the multiplicity $\le r$.
  • Computationally: implement integer programming/heuristic search for $N$ up to $50$ or $100$ to guess the growth rate and typical extremal structure.
• (iv) Minimal counterexample structure to look for. Any construction approaching the Erdős upper bound would need many relatively small elements (to make the harmonic sum large) while ensuring that for each $m$ the set $\{m/p: p\mid m\}$ intersects $A$ in size $\le r$; in particular it must avoid including too many of the prime-divisor quotients of integers with many distinct prime factors.