MathDB

Erdős Problem #1217 — Divisibility chains in logarithmically dense sets

About 60 years old · traced to

Let A={a1<a2<⋯ }A=\{a_1<a_2<\cdots\} have positive lower logarithmic density. Must AA contain a chain an1∣an2∣⋯a_{n_1}\mid a_{n_2}\mid\cdots such that

lim sup⁡y→∞#{i:ani<y}log⁡log⁡y=lim sup⁡x→∞1log⁡log⁡x∑ai<x1ailog⁡ai?\limsup_{y\to\infty}\frac{\#\{i:a_{n_i}<y\}}{\log\log y}=\limsup_{x\to\infty}\frac1{\log\log x}\sum_{a_i<x}\frac1{a_i\log a_i}?
References

Primary source

P. Erdős, A. Sárközi, and E. Szemerédi, On divisibility properties of sequences of integers, Studia Scientiarum Mathematicarum Hungarica 1 (1966), 431–435.

Additional references

P. Erdős, A. Sárközi, and E. Szemerédi, On divisibility properties of sequences of integers, Studia Scientiarum Mathematicarum Hungarica 1 (1966), 431–435.

divisorsnumber-theoryprimitive-sets
InErdős Problems
Posted

Progress summary

Refreshed
Claimed solved

A 2026 paper proves the conjecture, and in fact establishes it under a weaker density assumption than originally required.

This is the Erdős–Sárközy–Szemerédi problem from 1966: sufficiently dense sets of positive integers should contain a divisibility chain meeting the stated quantitative bound.

Known results

  • Davenport and Erdős proved that positive lower logarithmic density gives an infinite divisibility chain.
  • Erdős, Sárközy, and Szemerédi proved that positive normalized limsup of the reciprocal sum yields a chain with a positive normalized limsup, without the full quantitative bound.

May 2026 affirmative proof

Alexeev, Barreto, Li, Lichtman, Price, Shah, Tang, and Tao proved the quantitative statement as Theorem 6, in a form using positive upper doubly logarithmic density; this implies the original formulation and removes its lower-density hypothesis. Similar proofs were independently found by GPT 5.4 Pro.

Current status (as of May 2026): The problem is resolved by the affirmative theorem in arXiv:2605.00301; the original implication and a stronger version under weaker density assumptions are settled.

Sources

Solutions 0

No solutions have been posted yet.