Erdős Problem #538

Erdős Problem 538 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/538.tex.

REUSED SOURCE 1

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.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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.