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.

Workspace

Opens this exact Problem and source revision in Workbench. Nothing is cloned, uploaded, or executed.

How a contribution reaches this record

Seven steps, in four places.

  1. Read the sources and their formal declarations.

    Public
  2. Work on it, wherever you work.

    Your machine
  3. Keep an Approach and its Attempts here.

    Needs an account
  4. Attach evidence by its content root.

    Needs an account
  5. Prepare an unsigned Submission draft.

    Needs an account
  6. Sign it with your own key.

    Your machine
  7. The Repository decides.

    The Repository

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