Problem 1217

Let $A=\{a_1<a_2<\cdots\}$ be an infinite sequence of positive integers with positive lower logarithmic density.

Must there exist a sequence $n_1<\cdots$ such that

a_{n_i}\mid a_{n_{i+1}}

for all $i\geq 1$ and

\limsup_{x\to \infty}\frac{1}{\log\log x}\sum_{a_{n_i}<x}1 \geq \limsup_{x\to \infty} \frac{1}{\log\log x}\sum_{a_n<x}\frac{1}{a_n\log a_n}?

Source: erdosproblems.com/1217

Number theory
Divisors
Primitive sets

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site labels the problem PROVED (page last edited 12 May 2026) and credits Theorem 1.6 of Alexeev, Barreto, Li, Lichtman, Price, Shah, Tang and Tao (arXiv, 1 May 2026), recorded on its claim page (Alexeev Barreto Li Lichtman Price Shah Tang Tao, 2026); the theorem needs only that the weighted sum $\sum_{a_n<x}1/(a_n\log a_n)$ has a positive upper growth rate against $\log\log x$ , that is, a positive $\limsup$ of the quotient, which positive lower logarithmic density implies, so the density hypothesis is not needed. The result is an arXiv preprint accepted by the site's curator, with no journal record and no Lean proof. The standing in the frontmatter derives from the claim pages.

ABLLPSTT26: B. Alexeev, K. Barreto, Y. Li, J. D. Lichtman, L. Price, J. I. Shah, Q. Tang, and T. Tao, Primitive sets and von Mangoldt chains: Erdős Problem #1196 and beyond. arXiv:2605.00301v1 (2026). Library home: Alexeev 2026.
DaEr51: Davenport, H. and Erdős, P., On sequences of positive integers. J. Indian Math. Soc. (N.S.) (1951), 19-24. The site's commentary credits the divisibility-chain theorem to this key, but the 1951 note proves only that a set of multiples has lower and logarithmic density $A$ and contains no chain theorem. The chain theorem is Theorem 2 (§3, p. 150) of Davenport and Erdős, On sequences of positive integers, Acta Arith. 2 (1936), 147--151, proved under positive upper logarithmic density, which [ESS66] cites as its reference [1]: Theorem 2 (Davenport and Erdős 1936).
ESS66: Erdős, P. and Sárközi, A. and Szemerédi, E., On divisibility properties of sequences of integers. Studia Sci. Math. Hungar. 1 (1966), 431-435. Library home: Erdős, Sárközi and Szemerédi 1966.

Problem 1217

Status

Proof claims

Discussion