Erdős Problems

Tags Prizes

OPEN - $100

Let $g(n)$ be minimal such that for any $A\subseteq [2,\infty)\cap \mathbb{N}$ with $\lvert A\rvert =n$ then in any set $I$ of $\max(A)$ consecutive integers there exists some $B\subseteq I$ with $\lvert B\rvert=g(n)$ such that \[\prod_{a\in A} a \mid \prod_{b\in B}b.\] Is it true that \[g(n) \leq (2+o(1))n?\] Or perhaps even $g(n)\leq 2n$?

#708: [ErSu59][Er92c]

number theory

A problem of Erdős and Surányi [ErSu59], who proved that $g(n) \geq (2-o(1))n$, and that $g(3)=4$. Their upper bound construction took $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 [Er92c] Erdő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ős and Surá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.