Problem 795

Let $g(n)$ be the maximal size of $A\subseteq \{1,\ldots,n\}$ such that the products $\prod_{n\in S}n$ are distinct for all $S\subseteq A$ . Is it true that

g(n) \leq \pi(n)+\pi(n^{1/2})+o\left(\frac{x^{1/2}}{\log n}\right)?

Source: erdosproblems.com/795

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. Raghavan's Theorem 1.3 (Acta Math. Hungar. 177 (2025), no. 2, 363--377; refereed; arXiv:2501.02695) gives $g(n)=\pi(n)+\pi(n^{1/2})+O(n^{5/12})$ , an error term smaller than the $o(n^{1/2}/\log n)$ asked for, so the answer is yes; his Theorem 1.4 gives $g(n)\ge\pi(n)+\pi(n^{1/2})+\tfrac13\pi(n^{1/3})-O(1)$ , which disproves Erdős's 1980 expansion. The copy read is arXiv v2, of which no file is held; the journal text was not compared. Claim page: Raghavan 2025 (accepted: refereed, and credited by the site's curator, Thomas Bloom).

Ra25: Raghavan, R., Sharp bounds for sets with distinct subset products. Acta Math. Hungar. 177 (2025), no. 2, 363--377, doi:10.1007/s10474-025-01578-4 (published online 25 December 2025; Crossref record read); arXiv:2501.02695v1 (6 January 2025), v2 (26 February 2026, 13 pp., the copy read; not held). Theorems 1.3--1.6, pp. 1--2. Library home: Raghavan 2025.
Er66: Erdős, Pál, Remarks on number theory, V. Extremal problems in number theory, II (in Hungarian). Mat. Lapok 17 (1966), 135--155; Section I.11, printed pp. 138--141 (PDF pp. 4--7 of the Rényi archive's scan). Library home: Erdős 1966; result page Section I.11.
Er69: Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Kalamazoo 1968), Springer (1969), 77--82; displays (6) and (7), printed p. 79. Library home: Erdős 1969; result pages inequality (6) and display (7).
Er70b: Erdős, P., Some applications of graph theory to number theory. Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (1970), 136--145; displays (5) and (6), printed pp. 136--137. Library home: Erdős 1970; result pages display (5) and display (6).
Er65: Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math., Vol. VIII (1965), 181--189; display (3), printed p. 182. Library home: Erdos 1965; result page display (3).
Er80: Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89--115; printed pp. 102--103. Library home: Erdos 1980.
Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory, North-Holland (1973), 117--138; printed p. 131 states the upper bound of [Er70b]'s (5), as $\max k\le\pi(x)+cx^{1/2}/\log x$ without the lower bound, and its conjecture (6), introduced by "perhaps"; not a site key for this problem. Library home: Erdos 1973 (the card carries the passage as its row for this problem).

Problem 795

Status

Proof claims

Discussion