Skip to content

Erdős problem 535

Let r3r \geq 3, and let fr(N)f_r(N) denote the size of the largest subset of {1,,N}\{1,\ldots,N\} such that no subset of size rr has the same pairwise greatest common divisor between all elements. Erdős [Er64] proved that f3(N)>Nc/loglogNf_3(N) > N^{c/\log\log N} for some constant c>0c > 0, and conjectured this should also be an upper bound; here we state the conjectural upper bound for all r3r \geq 3.

No current result

No reviewed Result is current in Vela Mathematics Program. Retained source material is shown below.

Retained declaration

FormalConjectures/ErdosProblems/535.lean

Formal Conjectures

FormalConjectures/ErdosProblems/535.leanErdos535.erdos_5351 lineExact file
r ≥ 3, ∃ c > 0, ∀ᶠ (N : ℕ) in Filter.atTop, ↑(Erdos535.f r N) ≤ ↑N ^ (c / Real.log (Real.logN))
OpenStatement only, no proof

Reported activity

Work these sources record against this Problem. Source-reported attribution, not reviewed here.

  • AI collaborating with humans

    Erdős AI contributions wiki · 27 Apr, 2026

    Machine
    GPT-5.5 Thinking
    People
    Kireet Cheri, Sourish Kumrawat, Hrishi Sunder
    Open the source record

Continue

Search problems.science

Find a Problem, Result, source, or page