Problem #534: What is the largest possible subset...

---

Progress

A problem of Erdős and Graham (in [Er73] it was stated with $(a,b)=1$ instead but this is clearly a typo). They conjecture that this maximum is either $N/p$ (where $p$ is the smallest prime factor of $N$) or it is the number of integers $\{2t: t\leq N/2\textrm{ and }(2t,N)> 1\}$.

Ahlswede and Khachatrian [AhKh96] observe that it is 'easy' to find a counterexample to this conjecture, which they informed Erdős about in 1992. Erdős then gave a refined conjecture, that if $N=q_1^{k_1}\cdots q_r^{k_r}$ (where $q_1<\cdots <q_r$ are distinct primes) then the maximum is achieved by, for some $1\leq j\leq r$, those integers in $[1,N]$ which are a multiple of at least one of\[\{2q_1,\ldots,2q_j,q_1\cdots q_j\}.\]This conjecture was proved by Ahlswede and Khachatrian [AhKh96].

See also [56].