close

Monthly Archive

You are currently browsing the monthly archive for May 2026.

Primitive sets and von Mangoldt chains: Erdős Problem #1196 and beyond

3 May, 2026 in math.NT, paper | Tags: , , , , , , , , , | by | 24 comments

Boris Alexeev, Kevin Barreto, Yanyang Li, Jared Duker Lichtman, Liam Price, Jibran Iqbal Shah, Quanyu Tang, and I have just uploaded to the arXiv our paper Primitive sets and von Mangoldt chains: Erdős Problem #1196 and beyond. This paper (which is a work in progress) represents our efforts to digest and document the recent flurry of developments around the following problem of Erdős, Sárközy, and Szemerédi on primitive sets:

Conjecture 1 (Erdős problem #1196) Suppose that {A \subset [x,+\infty)} is a primitive set of integers, which means that no element of {A} divides another. Then

\displaystyle \sum_{n \in A} \frac{1}{n \log n} \le 1 + o(1)

as {x \rightarrow \infty}.

One can show that the upper bound of {1 + o(1)} is best possible up to the {o(1)} error by taking {A} to be the set of products of {k} primes for some suitable parameter {k}. This was one of the most well-known open problems in the study of primitive sets, and had attracted some number of partial results (for instance, Lichtman was able to show the upper bound of {e^\gamma \frac{\pi}{4} + o(1) \approx 1.399}). It was thus notable that this problem was first solved by an autonomous AI query (by the fifth author) a few weeks ago. This solution introduced a proof technique – based on Markov chains in the divisibility poset – which in retrospect is very natural for controlling primitive sets, but which had not been explicitly used in previous literature, though in retrospect many of the arguments in that literature involved a specific Markov chain which we call the downwards Mertens chain. The proof instead revolved around a different Markov chain, which we call the downwards von Mangoldt chain, which manages to neatly avoid the “{e^\gamma}” type losses in the previous Mertens-based arguments, and resolve Conjecture 1. In this paper we develop the Markov chain approach more systematically, and show that it settles several further conjectures concerning primitive sets, and also provides simpler proofs of some previous results in the literature. More precisely, in addition to Conjecture 1, we establish the following:

Theorem 2 (Erdős primitive set conjecture, #164) For any primitive {A} consisting of numbers greater than {1},

\displaystyle \sum_{n \in A} \frac{1}{n \log n} \le \sum_p \frac{1}{p \log p}.

Theorem 3 (Odd Banks–Martin) Let {k\ge 1} and suppose {A} is a primitive set consisting of odd numbers with at most {k} prime factors. Then

\displaystyle \sum_{n \in A} \frac{1}{n \log n} \leq \sum_{n \in \mathbb N_k(\mathcal Q)} \frac{1}{n \log n},

where {\mathcal Q} denotes the primes appearing as factors of elements of {A}, and {\mathbb N_k({\mathcal Q})} is the collection of products of {k} primes from {\mathcal Q}.

Theorem 4 ({2} is Erdős-strong) If {A} is a primitive set consisting of even numbers, then

\displaystyle \sum_{n \in A} \frac{1}{n \log n} \le \frac{1}{2\log 2}.

Theorem 5 (Ahlswede–Khachatrian–Sárközy) If {A} is a primitive set, then

\displaystyle \sum_{n \in A \cap [y/x,y]} \frac{1}{n} \ll \frac{\log x}{\sqrt{\log\log x}}

whenever {3 \leq x \leq y}.

Theorem 6 (Erdős–Sárközy–Szemerédi, #1217) Let {A \subset {\bf N}} be such that the upper doubly logarithmic density

\displaystyle \Delta := \limsup_{x\rightarrow\infty}\frac{1}{\log\log x} \sum_{n \in A \cap [2,x]} \frac{1}{n \log n}

is positive. Then there exists a strictly increasing infinite divisibility chain

\displaystyle n_0 | n_1 | n_2 | \dots

in {A} such that

\displaystyle \limsup_{x\rightarrow\infty}\frac{1}{\log\log x} \# \{ i: n_i \leq x \} \geq \Delta.

Theorem 2 and Theorem 5 had been previously established by Lichtman and Ahlswede–Khachatrian–Sárközy respectively, but the Markov chain formalism gives shorter (and more unified) proofs of both. Theorems 3, 4, 6 were open conjectures that can now be settled by this method. These results were obtained with varying levels of AI involvement, ranging from completely autonomous AI queries to traditional pen-and-paper calculations, to various hybrid approaches (for instance, with humans suggesting key inequalities that could then be rapidly tested numerically or even proved by various AI tools).

Read the rest of this entry »

Archives