Problem 425

../

---

Statement. Let $F(n)$ be the maximum possible size of a subset $A\subseteq\{1,\ldots,N\}$ such that the products $ab$ are distinct for all $a<b$. Is there a constant $c$ such that

$$F(n)=\pi(n)+(c+o(1))n^{3/4}(\log n)^{-3/2}?$$

If $A\subseteq \{1,\ldots,n\}$ is such that all products $a_1\cdots a_r$ are distinct for $a_1<\cdots <a_r$ then is it true that

$$\lvert A\rvert \leq \pi(n)+O(n^{\frac{r+1}{2r}})?$$

Status. Open.

Source. erdosproblems.com/425, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #425, https://www.erdosproblems.com/425.

References.

• [Er38] P. Erdős, On sequences of integers no one of which divides the product of two others and on related problems. Tomsk. Gos. Univ. Ucen Zap. (1938), 74-82.
• [Er68] Erdős, P., On some applications of graph theory to number theoretic problems. Publ. Ramanujan Inst. (1968/69), 131-136.
• [Er69] 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. Library home: erdos_1969_applications_graph_theory_number_theory.
• [Er70b] Erdős, P., Some applications of graph theory to number theory. Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970) (1970), 136-145.
• [Er73] Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138.
• [Er77] Erdős, P., Problems in number theory and combinatorics. Proceedings of the Sixth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1976) (1977), 35-58.
• [Er77c] Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72.
• [Er80] Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.
• [ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• erdos_1968_applications_graph_theory_number_theoretic_problems
• erdos_1968_applications_graph_theory_number_theoretic_problems / inequality_4
• erdos_1968_applications_graph_theory_number_theoretic_problems / theorem
• erdos_1938_sequences_integers_no_one_which_divides
• erdos_1969_applications_graph_theory_number_theory