Problem 535

Erdős Problem #535: declared status 'open'. Formalized: yes. Let $r\geq 3$, and let $f_r(N)$ denote the size of the largest subset of $\{1,\ldots,N\}$ such that no subset of size $r$ has the same pairwise greatest common divisor between all elements. Estimate $f_r(N)$. Current best: Erd\H{o}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. 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\H{o}s and Rado gives the upper bound $c_r^kk!$. Prize: no. Tags: number theory.