Largest subset of {1,...,N} with all pairwise products distinct: pin the constant in $F(N)$ (Erdős #425)
Statement
Let $F(N)$ denote the maximum possible size of a subset $A\subseteq\{1,\ldots,N\}$ such that all pairwise products $ab$ with $a<b$ (equivalently, all products of two distinct elements of $A$) are distinct — a multiplicative Sidon set. Erdős asked whether there is a constant $c$ with $$F(N)=\pi(N)+(c+o(1))N^{3/4}(\log N)^{-3/2},$$ where $\pi$ is the prime-counting function. More generally, for an integer $r\geq 2$, if $A\subseteq\{1,\ldots,N\}$ is such that all products $a_1\cdots a_r$ with $a_1<\cdots<a_r$ (over $r$-element subsets) are distinct, is it true that $$\lvert A\rvert\leq \pi(N)+O\!\left(N^{\frac{r+1}{2r}}\right)?$$
Acceptance. FULLY RESOLVES (proof-shaped): a complete proof that determines the constant — establishing $F(N)=\pi(N)+(c+o(1))N^{3/4}(\log N)^{-3/2}$ with an explicit value of $c$ (in particular that the limit defining $c$ exists), or proving no such single constant exists; and/or a proof of the $r$-fold upper bound $\lvert A\rvert\leq\pi(N)+O(N^{(r+1)/(2r)})$. A machine-checkable proof (Lean/Coq) is preferred, otherwise a complete rigorous written proof; a numerical computation alone cannot close this. ADVANCES (each independently checkable): (a) replace the background's mere existence of $0<c_1\leq c_2$ by explicit numerical constants, or narrow the ratio $c_2/c_1$, with proof; (b) prove the $r$-fold bound for a specific value of $r$ where it was not previously known; (c) compute exact values of $F(N)$ over a stated range of $N$ with a reproducible search program and an exhaustiveness certificate, extending the known tabulated values and giving data-driven estimates of $c$. Deliver the proof, or the search code plus the certified table of $F(N)$ values.
Background
The quantity $F(N)$ was studied by Erdős across a long series of papers [Er69, Er70b, Er73, Er77, Er77c, Er80] and by Erdős and Graham [ErGr80]. Erdős [Er38] proved the lower bound, and Erdős [Er68] established that there are constants $0<c_1\leq c_2$ with $$\pi(N)+c_1 N^{3/4}(\log N)^{-3/2}\leq F(N)\leq \pi(N)+c_2 N^{3/4}(\log N)^{-3/2};$$ thus the order of the second-order term is settled, and only its constant $c$ (and whether the limit even exists) is open. Erdős also posed a real-variable form: how large can $A\subset[1,x]$ be if $\lvert ab-cd\rvert\geq 1$ for all distinct $a,b,c,d\in A$? He conjectured $\lvert A\rvert=o(x)$ [Er73, Er77c], but Alexander disproved this — a construction reported by Erdős and Graham [ErGr80] and given in [Er80] takes a Sidon set $B\subseteq[1,X^2]$ of size $\gg X$ and forms $A=\{Xe^{b/X^2}:b\in B\}$, achieving $\lvert A\rvert\gg x$. A complex-number analogue appears in [Er77c]. There is no Erdős prize attached. Listed as open on erdosproblems.com/425 (fetched 2026-07-21, status 'open'); see also the related erdosproblems.com/490, erdosproblems.com/793, and erdosproblems.com/796. Attacker's tool: compute $F(N)$ exactly for a range of $N$ by treating it as a maximum subset with no repeated product (maximum independent set / ILP / SAT on the 'shared-product' conflict graph), tabulating values to estimate $c$; combined with analytic control of the multiplicative structure (products of two primes) to determine the constant and to attack the $r$-fold exponent.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #425 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.