Skip to content

Erdős problem 535

Let r≥3r \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/log⁡log⁡Nf_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 r≥3r \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.log ↑N))
OpenStatement only, no proof

Reported activity

Reported by these sources. 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