Erdős Problem #796

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

Representations of a product are unordered pairs of distinct factors, written $a_1<a_2$. Fewer than $k$ means at most $k-1$, so the highlighted case allows two representations. The proposed constant is independent of $n$. [S1] [S2]

Statement recorded in the supplied source.

Let $k\geq 2$ and let $g_k(n)$ be the largest possible size of $A\subseteq \{1,\ldots,n\}$ such that every $m$ has $<k$ solutions to $m=a_1a_2$ with $a_1<a_2\in A$. Is it true that $ g_3(n)=\frac{\log\log n}{\log n}n+(c+o(1))\frac{n}{\log n} $ for some constant $c$? [S1]

Residual task reported by the archive.

The embedded review (2026-08-17) records: Prove existence and value of the normalized second-order limit. [S1]

Short English statement

Does the largest integer set allowing at most two distinct-factor representations of each product have the proposed two-term asymptotic formula?

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 2311 (EP-796), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 T. F. Bloom, Erdős Problems, Problem 796, https://www.erdosproblems.com/796. Reference from the supplied record; the live problem page was not independently checked for this compilation.

• S3 P. Erdős, On the multiplicative representation of integers. Israel Journal of Mathematics (1964). Bibliographic information from the supplied record.

• S4 Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) (1969), 77-82. Bibliographic information from the supplied record.

• S5 Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) (1969), 27-35. Bibliographic information from the supplied record.