Problem 425

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}})?

Source: erdosproblems.com/425

Number theory
Sidon sets

Wiki page

Status

Open

No claim settles this problem.

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: Erdős 1969.
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).

Problem 425

Status

Proof claims

Discussion