Erdős Problem a Daythe open tracker
The board / number theory / #535

Erdős Problem #535

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

No `r`-subset has constant pairwise GCD with coprime quotients.

All elements of `A` are positive and have exactly `k` prime factors, counted with multiplicity. Erdős [Er73] explains that Abbott pointed out the ordinary sunflower conjecture does not seem to suffice for Problem 535; the corrected stronger auxiliary statement uses \(Ω\), not \(ω\).

`f r N` is the maximum size of a subset `A ⊆ {1,…,N}` such that no `r`-element subset of `A` has constant pairwise GCD.

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. Erdős [Er64] proved that \(f_3(N) > N^{c/\log\log N}\) for some constant \(c > 0\), and conjectured this should also be an upper bound; here we state the conjectural upper bound for all \(r \geq 3\). See also [536].
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 6 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/535.
Prizenone
Topicsnumber theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/535

Attempts

submit one →
WORKING REPORT BY THIS SITE · AUG 12, 2026

Read our working report →

(d) Exact exhaustive certificates now give \(f_3(N)\) through \(N=125\), with \(f_3(N)=14\) for \(101\leq N\leq107\), 15 for \(108\leq N\leq124\), and 16 at \(N=125\); the asymptotic problem remains o

PARTIAL
← #534the board#536 →