Erdős Problem #858

Erdős Problem 858

Statement and result.

Let $M(N)$ be the maximum of $\sum_{a\in A}1/a$ over $A\subseteq\{1,\ldots,N\}$ having no pair $a,b$ with $b=at$, $t>1$, and least prime factor $P^-(t)>a$. We reconstruct the known asymptotic solution \[ M(N)=(c+o(1))\log N,\qquad c=0.6187712111\ldots, \] with an integral definition of $c$ below. The restriction $t>1$ excludes the meaningless self-pair. The argument follows the note linked by the problem page and credited there to Przemysław Chojecki and GPT-5.4 Pro.

The divisibility tree.

Write $a\prec b$ when $b=at$, $t>1$, and every prime divisor of $t$ exceeds $a$. This relation is transitive: in a product of two successive quotients, the primes of the first exceed $a$, and those of the second exceed the intermediate integer and hence $a$.

Factor $n=p_1\cdots p_s$ with $p_1\leq\cdots\leq p_s$, and let $P_j=p_1\cdots p_j$, $P_0=1$. The proper ancestors of $n$ are exactly those $P_j$, $j<s$, for which $p_{j+1}>P_j$. Indeed, if $a\prec n$, every prime factor of $n$ at most $a$, with its full multiplicity in $n$, belongs to $a$. All prime factors of $a$ are at most $a$, so $a$ is precisely an initial prefix product. The converse is immediate.

These ancestors form a chain. Let $\pi(n)$ be the largest proper ancestor of $n>1$; every such $n$ has ancestor 1. Joining $n$ to $\pi(n)$ gives a rooted tree on $\{1,\ldots,N\}$, and the admissible sets in the question are exactly its antichains.

Let $F_N(a)$ be the maximum reciprocal weight of an antichain in the subtree rooted at $a$. Distinct child subtrees are incomparable, so \[ F_N(a)=\max\left\{\frac1a,\ \sum_{\pi(b)=a}F_N(b)\right\}, \qquad B_N(a)=a\sum_{\pi(b)=a}F_N(b). \tag{1} \] In particular $M(N)=F_N(1)$. At $a$, continuing to the children is optimal exactly when $B_N(a)\geq1$, with continuation chosen at a tie.

A threshold is eventually optimal.

Every $ap\leq N$ with prime $p>a$ is a child of $a$: the prefix characterization leaves no ancestor strictly between them. Define \[ P_N(a)=\sum_{a<p\leq N/a}\frac1p, \qquad Q_N(a)=\sum_{\substack{a<p\leq q\\p,q\text{ prime}\\apq\leq N}}\frac1{pq}. \] Let $L=\lfloor N^{1/4}\rfloor$. For $a\leq L$, $1$ and the prime children give \[ B_N(a)\geq P_N(a)\geq P_N(L)=\log3+o(1)>1, \tag{2} \] by Mertens' estimate for reciprocal primes.

If $a>L$, then $a>N^{1/4}$. For any child $n=at$, the quotient $t\leq N/a<a^3$ has every prime factor above $a$, so it is either a prime or a product of two primes, with repetition allowed. Conversely every $apq\leq N$ with $a<p\leq q$ is a child. Its only possible intermediate ancestor is $ap$, but $ap>a^2>\sqrt N$ and $q\leq N/(ap)<\sqrt N<ap$, which rules that out. All these children exceed $a^2>\sqrt N$ and are leaves: any proper descendant of $b$ exceeds $b^2$. Hence \[ B_N(a)=P_N(a)+Q_N(a)\qquad(a>L). \tag{3} \] The right-hand side is nonincreasing in the integer $a$, because both summation domains shrink, and is zero for $a\geq\sqrt N$. Equations $2$--$3$ imply that, for all sufficiently large $N$, there is an integer $K_N\geq L$ for which \[ B_N(a)\geq1\ (a\leq K_N),\qquad B_N(a)<1\ (a>K_N). \] Thus the optimal policy continues below this threshold and stops above it. In particular, with $\pi(1)=0$, the frontier \[ A_N(K)=\{n\leq N:\pi(n)\leq K<n\} \] has maximum weight when $K=K_N$. This establishes eventual exact frontier optimality; it does not assert an exact frontier theorem for every small $N$.

Sweeping the frontier.

Set $A_N(0)=\{1\}$, $S_N(K)=\sum_{n\in A_N(K)}1/n$, and $C_N(a)=\sum_{\pi(b)=a}1/b$. Passing from $K-1$ to $K$ removes $K$ and inserts its children, so \[ S_N(K)-S_N(K-1)=C_N(K)-1/K. \] Every $n>1$ is exactly one child, whence $\sum_a C_N(a)=H_N-1$. Also $C_N(a)=0$ for $a\geq\sqrt N$. Writing $J=\lfloor\sqrt N\rfloor$, we obtain, for $L\leq K\leq J$, \[ S_N(K)=H_N-H_J+ \sum_{K<a\leq J}\frac{1-P_N(a)-Q_N(a)}a. \tag{4} \] Here $a>K\geq L$, so $3$ applies.

Uniform asymptotics above the quarter-power layer.

For $u\in[1/4,1/2]$, define \[ \Phi(u)=\log\frac{1-u}{u}+ \begin{cases} \displaystyle\int_u^{(1-u)/2}\frac1v \log\frac{1-u-v}{v}\,dv,&u<1/3,\\[4pt] 0,&u\geq1/3. \end{cases} \tag{5} \] Uniformly for integers $a\in(N^{1/4},\sqrt N]$, with $u=\log a/\log N$, Mertens' estimate gives \[ P_N(a)=\log\frac{1-u}{u}+o(1),\qquad P_N(a)+Q_N(a)=\Phi(u)+o(1). \tag{6} \] For clarity, the second estimate follows by summing first over the smaller prime $p$, with $v=\log p/\log N$. The inner prime sum is \[ \sum_{p\leq q\leq N/(ap)}\frac1q =\log\frac{1-u-v}{v}+o(1), \qquad u<v\leq(1-u)/2. \] The lower-endpoint correction $1/p$ tends uniformly to zero. Mertens' formula and partial summation convert the outer reciprocal-prime sum to the integral in $5$. Uniformity follows because all logarithmic coordinates lie in the compact interval $[1/4,1/2]$, the integrand and its first derivatives are bounded there on the stated domain, and the total outer reciprocal-prime weight is bounded. If $u\geq1/3$, no such semiprime quotient exists and $Q_N(a)=0$.

The function $\Phi$ is continuous and strictly decreasing. Its first term is strictly decreasing; on the integral's domain its positive integrand decreases as $u$ increases, while the integration interval shrinks. Moreover \[ \Phi(1/4)\geq\log3>1,\qquad \Phi(1/3)=\log2<1. \] There is therefore a unique $\alpha\in(1/4,1/3)$ with $\Phi(\alpha)=1$. Equation $6$, the threshold property, and strict monotonicity imply \[ \frac{\log K_N}{\log N}\longrightarrow\alpha. \] Indeed, at exponents at least a fixed distance below or above $\alpha$, $6$ puts $B_N$ uniformly above or below 1.

The extremal constant.

Insert $K=K_N$ into $4$. The uniform error in $6$, summed against $1/a$, is $o(\log N)$. Since $H_N-H_J=\tfrac12\log N+O(1)$, the remaining harmonic Riemann sum gives \[ \boxed{\quad M(N)=(c+o(1))\log N,\qquad c=\frac12+\int_\alpha^{1/2}(1-\Phi(u))\,du, \quad\Phi(\alpha)=1.\quad} \] Numerical quadrature yields $\alpha\approx0.28043830989$ and $c\approx0.6187712111$. These decimal values are illustrative; the integral and unique-root characterization define the constant rigorously.

Attribution and assessment.

This reconstructs the Bellman-recursion and quarter-power-layer proof in The asymptotic constant in Erdős problem #858, https://www.ulam.ai/research/erdos858-asymptotic.pdf, linked and credited on https://www.erdosproblems.com/858, checked 24 September 2026. Mertens' reciprocal-prime estimate is the standard external analytic input; the tree structure, threshold argument, frontier identity, and deduction of the asymptotic are supplied above. No novelty or local Lean verification is claimed.

Completion rate estimate: 100%.

FORMAL RESTATEMENT.

Fix an integer $N\ge 2$. Let $A\subseteq \{1,2,\dots,N\}$. For an integer $t\ge 2$, write $\operatorname{spf}(t)$ for the smallest prime divisor of $t$.

Assume $A$ satisfies:

There do not exist $a,b\in A$ and an integer $t\ge 2$ such that $b=a t$ and $\operatorname{spf}(t)>a$.

Define \[ F(N):= \max_{A\subseteq [N]\ \text{satisfying the condition}} \frac{1}{\log N}\sum_{n\in A}\frac{1}{n}. \] The problem asks to estimate $F(N)$ as $N\to\infty$.

Ambiguity/misstated-context note. The statement in the problem file asserts that Alexander and Erdős--Sárközy--Szemerédi proved that this maximum is $o(1)$. Under the literal finite-$N$ definition above, we give an explicit family with $F(N)\ge \tfrac12+o(1)$, so $F(N)$ cannot be $o(1)$. This suggests the cited $o(1)$ result concerns a different "maximum" (e.g. for a fixed infinite set $A$ and $\limsup_{N\to\infty}$), or the condition is different in the original source.

QUICK LITERATURE/CONTEXT CHECK.

The problem file itself cites Alexander and Erdős--Sárközy--Szemerédi as proving an $o(1)$ bound for the stated maximum, and provides an $N$-dependent example set $A$. We do not assume any additional literature beyond what is in the problem file.

ATTACK PLAN.

First, sanity-check the condition: when $a$ is large (e.g. $a\ge \sqrt N$), the constraint "$\operatorname{spf}(t)>a$" becomes impossible for any multiple $b\le N$, making the condition vacuous. This immediately yields a lower bound $F(N)\ge 1/2+o(1)$.

We then brute-force optimise $F(N)$ for small $N$ to see what the true finite-$N$ behaviour looks like.

WORK.

Lemma 858.1 (The constraint is vacuous for $a\ge \sqrt N$).

Lemma. Let $N\ge 2$. Suppose $a,b\in\{1,\dots,N\}$ and $t\ge 2$ satisfy $b=a t$. If $a\ge \sqrt N$, then $\operatorname{spf}(t)\le a$. In particular, no triple $(a,b,t)$ with $a\ge \sqrt N$ can violate the condition $\operatorname{spf}(t)>a$.

Proof. From $b=a t\le N$ we get $t\le N/a$. If $a\ge \sqrt N$ then $N/a\le \sqrt N\le a$, hence $t\le a$. For $t\ge 2$ we have $\operatorname{spf}(t)\le t$ (because the smallest prime factor cannot exceed the number itself). Therefore $\operatorname{spf}(t)\le t\le a$. $\square$

Lemma 858.2 (A concrete family gives $F(N)\ge 1/2+o(1)$).

Lemma. Let $A_N:=\{\lceil \sqrt N\rceil,\lceil \sqrt N\rceil+1,\dots,N\}$. Then $A_N$ satisfies the condition, and \[ \frac{1}{\log N}\sum_{n\in A_N}\frac{1}{n} = \frac{H_N-H_{\lceil\sqrt N\rceil-1}}{\log N} = \frac12 + o(1) \quad\text{as }N\to\infty, \] where $H_m=\sum_{j=1}^m \frac{1}{j}$.

Proof. By Lemma 858.1, any $a\in A_N$ satisfies $a\ge \sqrt N$, so no equation $b=a t$ with $b\le N$ can have $\operatorname{spf}(t)>a$. Hence $A_N$ satisfies the defining condition.

For the asymptotic, we use the standard integral bounds for harmonic numbers: for every integer $M\ge 1$, \[ \int_1^{M+1} \frac{dx}{x} \le H_M \le 1 + \int_1^M \frac{dx}{x}, \] which imply \[ \log(M+1) \le H_M \le 1+\log M. \] Apply this with $M=N$ and $M=\lceil\sqrt N\rceil-1$. Then \[ H_N - H_{\lceil\sqrt N\rceil-1} \ge \log(N+1) - (1+\log(\lceil\sqrt N\rceil-1)) = \tfrac12\log N + O(1), \] and similarly \[ H_N - H_{\lceil\sqrt N\rceil-1} \le (1+\log N) - \log(\lceil\sqrt N\rceil) = \tfrac12\log N + O(1). \] Dividing by $\log N$ gives the claimed limit $\tfrac12+o(1)$. $\square$

Lemma 858.3 (The element $1$ is incompatible with any other element).

Lemma. If $1\in A$ and $b\in A$ with $b\ge 2$, then $A$ violates the condition.

Proof. Take $a=1$ and $t=b$. Then $b=a t$ holds. Since $b\ge 2$, $\operatorname{spf}(t)=\operatorname{spf}(b)\ge 2>1=a$. Thus $(a,b,t)$ is a forbidden solution, contradicting the defining property. $\square$

Fast reality check (exact optimisation for small $N$).

Interpreting the problem literally as a finite-$N$ maximisation, we can brute-force compute $F(N)$ for $N\le 20$ (by enumerating all $2^N$ subsets and checking the forbidden condition). The computed maximisers for $N=20$ give \[ F(20)\approx 0.6968, \] attained for example by \[ A=\{2,3,4,5,7,8,9,11,12,13,16,17,19\}. \] In particular, for these small values the optimum is noticeably larger than the simple lower bound coming from $A_N=[\lceil\sqrt N\rceil,N]$.

VERIFICATION.

• Lemma 858.1 hinges only on the inequalities $t\le N/a$ and $\operatorname{spf}(t)\le t$; there are no hidden assumptions.
• Lemma 858.2 checks the forbidden condition by reducing to Lemma 858.1; this is valid because every $a\in A_N$ satisfies $a\ge\sqrt N$.
• The brute-force calculation for $N\le 20$ is consistent with Lemma 858.3 (all computed maximisers omit $1$).

FINAL. UNRESOLVED.

(i) Strongest proved partial results. For the literal finite-$N$ formulation, we proved the unconditional lower bound \[ F(N)\ge \frac{H_N-H_{\lceil\sqrt N\rceil-1}}{\log N} = \tfrac12+o(1), \] by exhibiting an explicit admissible set $A_N=[\lceil\sqrt N\rceil,N]$. We also proved the structural fact that any forbidden solution must have $a<\sqrt N$.

(ii) First gap. Determine the true asymptotic behaviour of the finite-$N$ maximum $F(N)$: does $F(N)$ converge, and if so to what constant? (The computation up to $N=20$ suggests values $>1/2$.)

(iii) Top 3 next moves. $1$ Reformalise the statement in the original Erdős source to resolve the apparent conflict between the literal lower bound $\ge 1/2$ and the cited "$o(1)$" claim. $2$ For the finite-$N$ version, model the condition as a maximum-weight independent set problem on the graph with vertices $\{1,\dots,N\}$ and forbidden edges $(a,at)$; use branch-and-bound/ILP to compute $F(N)$ for larger $N$ to guess a limit. $3$ Attempt a "swap"/charging argument comparing inclusion of small $a$ (large weight $1/a$) versus the forced exclusion of many multiples $a p$ with primes $p>a$.

(iv) What a minimal counterexample would look like. If the true statement is that $F(N)=o(1)$, then a counterexample to that would require an admissible family $A_N$ whose harmonic weight is a positive fraction of $\log N$ while still avoiding all forbidden multiplicative relations. The explicit family $[\lceil\sqrt N\rceil,N]$ already achieves fraction $\approx 1/2$ under the literal reading.