Problem #535: Let $r\geq 3$, and let $f_r(N)$ denote the size of the...

---

Progress

Erdős [Er64] proved that\[f_r(N) \leq N^{\frac{3}{4}+o(1)},\]and Abbott and Hanson [AbHa70] improved this exponent to $1/2$. Erdős [Er64] proved the lower bound\[f_3(N) > N^{\frac{c}{\log\log N}}\]for some constant $c>0$, and conjectured this should also be an upper bound.

Erdős writes this is 'intimately connected' with the sunflower problem [20]. Indeed, the conjectured upper bound would follow from the following stronger version of the sunflower problem: estimate the size of the largest set of integers $A$ such that $\omega(n)=k$ for all $n\in A$ and there does not exist $a_1,\ldots,a_r\in A$ and an integer $d$ such that $(a_i,a_j)=d$ for all $i\neq j$ and $(a_i/d,d)=1$ for all $i$. The conjectured upper bound for $f_r(N)$ would follow if the size of such an $A$ must be at most $c_r^k$. The original sunflower proof of Erdős and Rado gives the upper bound $c_r^kk!$.

See also [536].