A problem of Erd\H{o}s and Sur\'{a}nyi \cite{ErSu59}, who proved that $g(n) \geq (2-o(1))n$, and that $g(3)=4$. Their lower bound construction takes $A$ as the set of $p_ip_j$ for $i\neq j$, where $p_1<\cdots <p_\ell$ is some set of primes such that $2p_1^2>p_\ell^2$.

Gallai was the first to consider problems of this type, and observed that $g(2)=2$ and $g(3)\geq 4$.

In \cite{Er92c} Erd\H{o}s offers '100 dollars or 1000 rupees', whichever is more, for a proof or disproof. (In 1992 1000 rupees was worth approximately \$38.60.)

Erd\H{o}s and Sur\'{a}nyi similarly asked what is the smallest $c_n\geq 1$ such that in any interval $I\subset [0,\infty)$ of length $c_n\max(A)$ there exists some $B\subseteq I\cap \mathbb{N}$ with $\lvert B\rvert=n$ such that\[\prod_{a\in A} a \mid \prod_{b\in B}b.\]They prove $c_2=1$ and $c_3=\sqrt{2}$, but have no good upper or lower bounds in general.


See also [709].


References


[Er92c] Erd\"{o}s, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50.

[ErSu59] Erd\H{o}s, P\'{a}l and Sur\'{a}nyi, J\'{a}nos, Bemerkungen zu einer Aufgabe eines mathematischen
{W}ettbewerbs. Mat. Lapok (1959), 39-48.