Estimate $f_r(N)$: largest subset of $\{1,\ldots,N\}$ with no $r$ elements sharing one pairwise gcd (Erdős #535)
Statement
Let $r\geq 3$, and for $N\geq 1$ let $f_r(N)$ denote the size of the largest subset $A\subseteq\{1,\ldots,N\}$ with the following property: no $r$ elements of $A$ all share the same pairwise greatest common divisor. That is, there is no $r$-element subset $\{a_1,\ldots,a_r\}\subseteq A$ for which $\gcd(a_i,a_j)$ takes one common value $d$ over every pair $i\neq j$. Estimate the growth of $f_r(N)$ as $N\to\infty$.
Acceptance. FULLY RESOLVES: determine the asymptotic order of $f_r(N)$ — a proof (machine-checkable in Lean/Coq preferred, otherwise a complete written proof) that pins the growth, for example establishing matching upper and lower bounds of the form $N^{(c+o(1))/\log\log N}$ (confirming Erdős's conjectured shape) or refuting it. ADVANCES: strictly improve either side of the current frontier stated in the background — an upper bound provably smaller than the ALWZ-sunflower bound $N^{(C_r\log\log\log N)/\log\log N}$, or a lower bound provably larger than $N^{c_r/\log\log N}$ — with a full proof; or, for a fixed small $r$, compute $f_r(N)$ exactly over an extended range of $N$ with a reproducible search and an exhaustiveness certificate, documenting the extremal configurations. Deliver the proof, the improved-bound argument, or the search code plus certified data. State in words the bound you improve on.
Background
Posed by Erdős across [Er69], [Er70], and [Er73]; listed as open on erdosproblems.com/535 (fetched 2026-07-21, status 'open'). Erdős [Er64] first proved the upper bound $f_r(N)\leq N^{3/4+o(1)}$, and Abbott and Hanson [AbHa70] lowered the exponent to $1/2$, giving $f_r(N)\leq N^{1/2+o(1)}$; an alternative account of these bounds is in Abbott and Hanson [AbHa67]. In the other direction Erdős [Er64] proved that for every $r\geq 3$ there is a constant $c_r>0$ with $f_r(N)>N^{c_r/\log\log N}$, and conjectured that this doubly-logarithmic shape is also the truth for the upper bound. The problem is intimately tied to the sunflower problem, Erdős #20 (erdosproblems.com/20, also on this venue): Erdős noted that a positive solution to the sunflower conjecture would force $f_r(N)\leq N^{C_r/\log\log N}$ for some $C_r>0$. Feeding in the breakthrough sunflower bounds of Alweiss, Lovett, Wu and Zhang [ALWZ20] already yields $f_r(N)\leq N^{C_r\log\log\log N/\log\log N}$, and in particular $f_r(N)\leq N^{o(1)}$. So the current frontier is a lower bound $N^{c_r/\log\log N}$ against an upper bound $N^{(C_r\log\log\log N)/\log\log N}$, with the exact order left open. A formalised statement is available in DeepMind's formal-conjectures library. The attacker's tool: extremal/analytic combinatorics sharpening the sunflower-to-gcd reduction, together with computer search for the largest gcd-uniform-free sets at small $r$ and $N$ to test whether the lower-bound construction is essentially optimal.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #535 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #535 (formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.