This would be best possible, for example letting $A=[1,N/2]\cap \mathbb{N}$ and $B=\{ N/2<p\leq N: p\textrm{ prime}\}$.

This is true, and was proved by Szemerédi [Sz76].

In [Er72] Erdős goes on to ask whether\[\lim_{N\to \infty}\max_{A,B\subseteq [N]}\frac{\lvert A\rvert\lvert B\rvert\log N}{N^2}\]exists, where the maximum is over $A$ and $B$ with all the products $ab$ distinct, and to determine its value. As noted in the comments to [896] by van Doorn, if the limit exists it must be $\geq 1$.

See also [425] and [896].

View the LaTeX source

This page was last edited 28 December 2025.