A negative answer to Erdős Problem #786
Shisheng Li
math.NT
Sep 28, 2026 · v1
TL;DR
Formalizes in Lean 4 with Mathlib the main theorem giving negative answers to Erdős Problem #786, verified against Formal Conjectures project statements.
Abstract
Call a set $A$ of positive integers admissible if, whenever $a_1\cdots a_r=b_1\cdots b_s$ with $a_1,\dots,a_r$ distinct elements of $A$ and $b_1,\dots,b_s$ distinct elements of $A$, necessarily $r=s$. Erdős asked whether admissible sets can have density $1-\varepsilon$ for every $\varepsilon>0$, and whether $\{1,\dots,N\}$ always contains an admissible subset of size $(1-o(1))N$. For the variant in which repetitions are allowed both questions were answered negatively by Erdős, Ruzsa and Sárközy and by Granville and Soundararajan; for products of distinct elements, the first question was answered only recently (with density bound $7/8$), and the second has remained open. We show that every admissible $A\subseteq\{1,\dots,N\}$ satisfies $\sum_{a\in A}1/a\le\tfrac12\log N+(\log\log N+2)^2$, and that there is an absolute constant $η>0$ such that every admissible $A\subseteq\{1,\dots,N\}$ has $|A|<(1-η)N$ for all large $N$. Both questions therefore have negative answers. The proofs are elementary; the second rests on a coupling that replaces the largest divisor of an integer composed of small primes, which avoids the divisor-function losses inherent in counting quotients along a multiplication table. Both negative answers are formally verified in Lean 4 against the statements of the Formal Conjectures project.
Problem
Erdős asked whether sets of positive integers in which equal products of distinct elements force equal numbers of factors can have density arbitrarily close to 1. He also asked whether {1,...,N} always contains such a subset of size (1-o(1))N. The second question was open.
Approach
Elementary proofs give a harmonic-sum bound of ½ log N + (log log N + 2)^2 for admissible sets. They also give a deficit bound |A| < (1-η)N, obtained through a coupling that replaces the largest divisor of a smooth integer, which avoids divisor-function losses. The second result and both parts of the Formal Conjectures statement are formalized in Lean 4 on Mathlib, reusing explicit Mertens estimates from PrimeNumberTheoremAnd.
Results
Both of Erdős's questions have negative answers. The Lean development proves erdos_786.parts.i and parts.ii using only the standard axioms. Theorem 1, the harmonic-sum bound, is not formalized.