Erdős Problem #425
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, sidon sets.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A set of positive integers is multiplicatively Sidon in the sense of Erdős Problem 425 if every product of two different elements has a unique representation as such a product. More precisely, for a finite set \(A\), whenever \(a<b\) and \(c<d\) are pairs drawn from \(A\), equality \(ab=cd\) must imply that the pairs are identical. The order within a pair does not count as a new representation.
Let \(F(n)\) be the largest possible number of elements in such a set \(A\subseteq\{1,\dots,n\}\). Write \(\pi(n)\) for the number of primes not exceeding \(n\). Erdős asks for a sharp asymptotic formula for the excess \(F(n)-\pi(n)\):
with some fixed constant \(c\). A separate, harder-looking extension imposes uniqueness of products of \(r\) distinct selected elements and asks for a corresponding upper bound. The questions concern infinite growth rates, not merely constructing one large finite set.
A small example
A set consisting of \(1\) and all primes up to \(n\) satisfies the pair-product condition by unique prime factorization. Two different primes multiply to a number with a unique pair of prime factors; multiplying \(1\) by a prime instead produces that prime, which cannot equal a product of two distinct primes. Thus \(F(n)\geq\pi(n)+1\) for sufficiently large \(n\). Erdős's historical work establishes a substantially stronger lower bound.
At a small scale, consider
There are \(\binom62=15\) unordered pairs of different elements. Direct exact-integer multiplication shows their fifteen products are all distinct. Exhaustively inspecting every one of the \(2^8=256\) subsets of \(\{1,\dots,8\}\), and rejecting any subset with a repeated unordered-pair product, gives \(F(8)=6\). A similar complete search of the \(2^{10}=1024\) subsets of \(\{1,\dots,10\}\) gives \(F(10)=7\). These are independently calculated finite certificates, not evidence for a particular constant \(c\).
The predicate for the finite search is transparent: map each two-element subset \(\{a,b\}\) to its integer product \(ab\), and test whether that map is injective. If two different unordered pairs share a product, the set fails. This definition must be kept separate from variants that allow repeated factors \(a=a\) or compare ordered products, because those variants have different trivialities and different possible extremal sizes.
What is known
The problem has a long history in additive and multiplicative number theory, including Erdős's work in 1938 and 1968, and the account in P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 84 of the historical monograph.
The maintained Erdős Problems #425 page records a powerful result attributed to Erdős: there are positive constants \(c_1\leq c_2\) such that
for sufficiently large \(n\). The earlier 1938 work supplied the lower-bound direction. These inequalities determine the order of magnitude of the excess, but they do not prove that the normalized excess converges to any single constant. That remaining limiting-coefficient question is why the main problem is still listed OPEN.
A further question considers sets for which all products of \(r\) distinct members are different, and asks whether their size is bounded by
This extension is not obtained merely by substituting an integer \(r\) into the pairwise bound. It changes the uniqueness hypothesis and the extremal problem.
There is also a related problem for real numbers. Erdős once conjectured that a large set of real numbers in an interval with all products of four distinct factors separated by at least one must have size \(o(x)\). Alexander's construction, described in later sources, disproved that assertion by producing sets of size comparable to \(x\). It is a different real-number question and should not be treated as a resolution of the integer \(F(n)\) asymptotic.
GCL's current state
The original source issue #1695 pins the catalogue at teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records open status as of August 2025. The maintained page, last edited June 21, 2026, also regards the sharp coefficient and the product extension as open.
The source issue records no Problem 425 statement file in the admitted FormalConjectures provider revision 85f863718beeec7b58a3a1926ee92e3472bc2020. This is a source-lock fact, not a judgment that a formal statement cannot be created. No external Lean development was built or certified for this article.
The authenticated audit is original issue #1695, RESULT/1 comment #6157273563. It captures sources and finite checks. The separate V2 editorial ledger, not this article, governs accepted Compendium coverage.
What remains
A useful bounded task is to compute \(F(n)\) exactly for \(1\leq n\leq15\) by two independent implementations. The first enumerates all subsets as bitmasks and checks unordered-pair products. The second performs backtracking, maintaining the set of products already used. For each \(n\), record the maximum cardinality, one lexicographically specified maximizing set and the number of maximizing sets. The two implementations must agree, including the known fixtures \(F(8)=6\) and \(F(10)=7\).
The source-concordance component should inspect the 1938 and 1968 primary results and verify the precise hypotheses and constants behind the two-sided asymptotic bounds. It must also keep the \(r\) fold extension and Alexander's real-number construction distinct. Acceptance requires exact finite agreement and a theorem-by-theorem source table. Falsification includes an unreported product collision, wrong repeated-factor convention, or inventing a limiting constant from coarse order bounds. The task stops at finite certificates and source normalization; the asymptotic problem remains for mathematical research.
Sources and claim boundaries
Primary historical sources: Erdős (1938, 1968) and Erdős–Graham (1980), p. 84. Current mathematical statement, related real construction and two-sided bounds: Erdős Problem #425. Original GCL issue: #1695. Source lock: teorth catalogue. Authenticated audit: issue comment #6157273563.
The small extremal values are reproducible exhaustive finite calculations. The historical two-sided estimates are attributed to external mathematical publications rather than independently reconstructed here. No limiting coefficient, new theorem, Lean proof or protected editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1695 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.