Recognition: unknown
Primitive sets and von Mangoldt chains: ErdH{o}s Problem #1196 and beyond
Pith reviewed 2026-05-09 19:30 UTC · model grok-4.3
The pith
The von Mangoldt-weighted Markov chain method proves Erdős conjectures on primitive sets
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central discovery is that a Markov chain equipped with von Mangoldt weights can be constructed to yield upper bounds on the Erdős sums for primitive sets, and these bounds are strong enough to confirm the conjectures on primitive sets consisting of large integers, on chains under divisibility, the original Erdős conjecture on the sum being less than e^gamma, and the revised Banks-Martin conjecture.
What carries the argument
The von Mangoldt-weighted Markov chain, which generates a probability distribution over the integers that respects the primitive set condition to derive sum bounds.
Load-bearing premise
The Markov chain with von Mangoldt weights produces valid upper bounds on the Erdős sums for primitive sets without hidden restrictions or unaccounted error terms that would affect the applications.
What would settle it
A specific primitive set whose Erdős sum exceeds the upper bound obtained from the von Mangoldt Markov chain construction, or a computation for small cases showing the bound is violated.
Figures
read the original abstract
A set of integers is primitive if no number in the set divides another. We introduce a new method for bounding Erd\H{o}s sums of primitive sets, suggested from output of GPT-5.4 Pro, based on Markov chains with von Mangoldt weights. The method leads to a host of applications, yet seems to have been overlooked by the prior literature since Erd\H{o}s's seminal 1935 paper. As applications, we prove two 1966 conjectures of Erd\H{o}s-S\'ark\"ozy-Szemer\'edi, on primitive sets of large numbers (#1196) and on divisibility chains (#1217). The method also provides a short proof of the Erd\H{o}s Primitive Set Conjecture (#164), as well as the related claim that 2 is an ''Erd\H{o}s-strong'' prime. Moreover, the method resolves a revised form of the Banks-Martin conjecture, which has long been viewed as a unifying `master theorem' for the area.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a Markov chain construction with transition probabilities weighted by the von Mangoldt function Λ(n) to obtain upper bounds on Erdős sums over primitive sets. It applies this method to prove the Erdős-Sárközy-Szemerédi conjectures #1196 (on primitive sets consisting of large numbers) and #1217 (on divisibility chains), gives a short proof of the Erdős Primitive Set Conjecture #164, establishes that 2 is an Erdős-strong prime, and resolves a revised form of the Banks-Martin conjecture.
Significance. If the von Mangoldt-weighted Markov chain is shown to deliver valid, restriction-free upper bounds that hold for arbitrary primitive sets and survive iteration over divisibility chains, the work would constitute a significant contribution by resolving multiple longstanding open problems in a unified way. The approach appears novel in this context and could provide a new analytic tool for studying sums over sets with divisibility constraints.
major comments (2)
- [§3] §3 (Markov chain construction and stationary measure): The derivation of the upper bound on the Erdős sum must explicitly verify that the inequality holds without additional decay assumptions on the primitive set or unstated error terms; otherwise the applications to infinite divisibility chains in #1217 and the exact statements of #1196 and #164 are not justified.
- [§4] §4 (Application to conjecture #1196): The claim that the bound is strong enough to imply the conjecture on primitive sets of large numbers requires a direct check that the chain remains irreducible and the bound is uniform over all primitive sets, as any hidden restriction would undermine the resolution.
minor comments (2)
- [§1] The introduction could include a brief comparison table of the new bounds versus previously known estimates for the Erdős sums to clarify the improvement.
- Notation for the stationary distribution and the precise form of the Erdős sum should be fixed consistently across sections to avoid minor confusion for readers.
Simulated Author's Rebuttal
We thank the referee for the careful reading of our manuscript and for highlighting these points regarding explicit verification and uniformity. We address each major comment below and will incorporate the suggested clarifications in the revised version.
read point-by-point responses
-
Referee: [§3] §3 (Markov chain construction and stationary measure): The derivation of the upper bound on the Erdős sum must explicitly verify that the inequality holds without additional decay assumptions on the primitive set or unstated error terms; otherwise the applications to infinite divisibility chains in #1217 and the exact statements of #1196 and #164 are not justified.
Authors: The upper bound in §3 is obtained directly from the stationary distribution of the von Mangoldt-weighted Markov chain, with transition probabilities defined solely in terms of Λ(n) and the primitivity condition. No decay assumptions on the set or error terms appear in the derivation, and the resulting inequality applies uniformly to arbitrary primitive sets, including those supporting infinite divisibility chains. To address the request for explicit verification, we will insert a short clarifying paragraph in the revised §3 that restates the construction and confirms the absence of hidden restrictions. revision: yes
-
Referee: [§4] §4 (Application to conjecture #1196): The claim that the bound is strong enough to imply the conjecture on primitive sets of large numbers requires a direct check that the chain remains irreducible and the bound is uniform over all primitive sets, as any hidden restriction would undermine the resolution.
Authors: The application in §4 uses the same Markov chain whose transition matrix is independent of any particular primitive set beyond the primitivity constraint itself; irreducibility on the state space of integers >1 follows from the positive density of primes and the von Mangoldt weights. The bound is therefore uniform by construction. We will add an explicit paragraph in the revised §4 that verifies irreducibility and uniformity over all primitive sets, thereby confirming that no hidden restrictions affect the resolution of #1196. revision: yes
Circularity Check
No circularity: novel Markov chain construction yields independent bounds
full rationale
The paper introduces a Markov chain with von Mangoldt weights as a new bounding technique for Erdős sums on primitive sets. The abstract and description present this as an original method that produces upper bounds, then applies those bounds to resolve the listed conjectures. No quoted equations or steps reduce a claimed prediction or theorem to a fitted parameter, self-definition, or load-bearing self-citation whose validity depends on the target result. The derivation chain is therefore self-contained against external benchmarks and does not exhibit any of the enumerated circular patterns.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Standard properties of the von Mangoldt function and its Dirichlet series
- domain assumption Existence and uniqueness properties of stationary distributions for the defined Markov chains
Reference graph
Works this paper leans on
-
[1]
J. A. Adell and A. Lekuona,Dirichlet’s eta and beta functions: Concavity and fast computation of their derivatives, J. Number Theory157(2015), 215–222
2015
-
[2]
Alexeev,A Lean formalization of ErdősProblem 164, Lean 4 formalization, Mathlib v4.29.0 and Lean v4.29.0, commit a9d31bcdffd1a68544b4e9214b867b2b34912fd2, 2026
B. Alexeev,A Lean formalization of ErdősProblem 164, Lean 4 formalization, Mathlib v4.29.0 and Lean v4.29.0, commit a9d31bcdffd1a68544b4e9214b867b2b34912fd2, 2026. Available at https://github.com/plby/lean-proofs/blob/a9d31bcdffd1a68544b4e9214b867b2b34912fd2/ ErdosProblems/Erdos164.md
2026
-
[3]
Number Theory151(2015), 172–196
H.AlzerandM.K.Kwong,On the concavity of Dirichlet’s eta function and related functional inequalities, J. Number Theory151(2015), 172–196
2015
-
[4]
Ahlswede, L
R. Ahlswede, L. Khachatrian, and A. Sárközy,On the density of primitive sets, J. Number Theory108 (2004), 319–361
2004
-
[5]
W. D. Banks and G. Martin,Optimal primitive sets with restricted primes, Integers13(2013), Paper No. A69, 10 pp
2013
-
[6]
Behrend,On sequences of numbers not divisible one by another, J
F. Behrend,On sequences of numbers not divisible one by another, J. London Math. Soc.10(1935), 42–44
1935
-
[7]
T. F. Bloom,Erdős problems,https://www.erdosproblems.com/
-
[8]
Cohen, Number Theory, Volume II: Analytic and Modern Tools, GTM Vol
H. Cohen, Number Theory, Volume II: Analytic and Modern Tools, GTM Vol. 240, Springer, 2007
2007
-
[9]
Davenport and P
H. Davenport and P. Erdős,On sequences of positive integers, Acta Arith.2(1936), 147–151
1936
-
[10]
Erdős,Note on sequences of integers no one of which is divisible by any other, J
P. Erdős,Note on sequences of integers no one of which is divisible by any other, J. London Math. Soc. 10(1935), 126–128
1935
-
[11]
Erdős,Some unsolved problems, Magyar Tud
P. Erdős,Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221–254
1961
-
[12]
Erdős,Some extremal problems in combinatorial number theory, Mathematical Essays Dedicated to A
P. Erdős,Some extremal problems in combinatorial number theory, Mathematical Essays Dedicated to A. J. Macintyre (1970), 123–133
1970
-
[13]
Erdős,Problems and results on combinatorial number theory, A survey of combinatorial theory (Proc
P. Erdős,Problems and results on combinatorial number theory, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117–138
1971
-
[14]
Erdős, Conjecture 2.1,Problems and results on combinatorial number theory
P. Erdős, Conjecture 2.1,Problems and results on combinatorial number theory. II, J. Indian Math. Soc. (N.S.) (1976), 285–298
1976
-
[15]
Erdős,Problems and results on combinatorial number theory
P. Erdős,Problems and results on combinatorial number theory. III, Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43–72
1976
-
[16]
Erdős,A survey of problems in combinatorial number theory, Ann
P. Erdős,A survey of problems in combinatorial number theory, Ann. Discrete Math. (1980), 89–115
1980
-
[17]
Erdős,Problémes et résultats en théorie des nombres, Conférence de Paul Erdősá l’Université de Limoges le 21 Octobre 1986, rédigé par François Morain
P. Erdős,Problémes et résultats en théorie des nombres, Conférence de Paul Erdősá l’Université de Limoges le 21 Octobre 1986, rédigé par François Morain
1986
-
[18]
Erdős,Some of my forgotten problems in number theory, Hardy-Ramanujan J
P. Erdős,Some of my forgotten problems in number theory, Hardy-Ramanujan J. (1992), 34–50
1992
-
[19]
Erdős,Some of my favorite problems and results, The mathematics of Paul Erdős, I (1997), 47–67
P. Erdős,Some of my favorite problems and results, The mathematics of Paul Erdős, I (1997), 47–67
1997
-
[20]
Erdős, A
P. Erdős, A. Sárközy, and E. Szemerédi,On divisibility properties of sequences of integers, Studia Sci. Math. Hungar.1(1966), 431–435
1966
-
[21]
Erdős, A
P. Erdős, A. Sárközy, and E. Szemerédi,On an extremal problem concerning primitive sequences, J. London Math. Soc.42(1967), 484–488
1967
-
[22]
Erdős, A
P. Erdős, A. Sárközy, and E. Szemerédi,On divisibility properties of sequences of integers, Colloq. Math. Soc. János Bolyai2(1970), 35–49. 33
1970
-
[23]
Erdős, Z
P. Erdős, Z. Zhang,Upper bound ofP 1/(ai loga i)for primitive sequences, Proc. Amer. Math. Soc., 117(1993), 891–895
1993
-
[24]
Gorodetsky, J
O. Gorodetsky, J. D. Lichtman, and M. D. Wong,On Erdős sums of almost primes, Comptes Rendus. Mathématique362(2024), no. G12, 1571–1596
2024
-
[25]
Halberstam, K
H. Halberstam, K. F. Roth,Sequences, Oxford University Press, Oxford (1966)
1966
-
[26]
R. R. Hall,Sets of multiples, Cambridge Tracts in Mathematics,118, Cambridge University Press, Cambridge (1996)
1996
-
[27]
Kamihigashi,A generalization of Fatou’s lemma for extended real-valued functions onσ-finite measure spaces: With an application to infinite-horizon optimization in discrete time, J
T. Kamihigashi,A generalization of Fatou’s lemma for extended real-valued functions onσ-finite measure spaces: With an application to infinite-horizon optimization in discrete time, J. Inequal. Appl.2017 (2017), Paper No. 24, 15 pp
2017
-
[28]
D. Koukoulopoulos, Y. Lamzouri, and J. D. Lichtman,Erdős’s integer dilation approximation problem and GCD graphs, arXiv:2502.09539
- [29]
- [30]
-
[31]
J. D. Lichtman and C. Pomerance,The Erdős conjecture for primitive sets, Proc. Amer. Math. Soc. Ser. B6(2019), 1–14
2019
-
[32]
Lubell,A short proof of Sperner’s lemma, Journal of Combinatorial Theory1(1966), 299
D. Lubell,A short proof of Sperner’s lemma, Journal of Combinatorial Theory1(1966), 299
1966
-
[33]
Available athttps://github.com/math-inc/ Erdos1196/tree/02fba13be7487cc51315f68d8fa7ef277633d3c8
Math Inc.,Primitive Sets Abovexin Lean, Lean 4 formalization, Lean v4.30.0-rc1, com- mit 02fba13be7487cc51315f68d8fa7ef277633d3c8, 2026. Available athttps://github.com/math-inc/ Erdos1196/tree/02fba13be7487cc51315f68d8fa7ef277633d3c8
2026
-
[34]
L. D. Meshalkin,Generalization of Sperner’s theorem on the number of subsets of a finite set, Theory of Probability and Its Applications,8(1963), 203–204
1963
-
[35]
H. L. Montgomery and R. C. Vaughan,Multiplicative Number Theory I: Classical Theory, Cambridge Studies in Advanced Mathematics, vol. 97, Cambridge University Press, 2007
2007
-
[36]
V. V. Petrov, Sums of Independent Random Variables, Springer, 1975
1975
-
[37]
Sárközy,On divisibility properties of sequences of integers, 241–250, in The Mathematics of Paul Erdős I, R
A. Sárközy,On divisibility properties of sequences of integers, 241–250, in The Mathematics of Paul Erdős I, R. L. Graham, J. Nesetril (eds.), Springer-Verlag Berlin Heidelberg (1997)
1997
-
[38]
Sárközy,On divisibility properties of sequences of integers, 221–232, in The Mathematics of Paul Erdős I (2nd edition) R
A. Sárközy,On divisibility properties of sequences of integers, 221–232, in The Mathematics of Paul Erdős I (2nd edition) R. L. Graham, J. Nesetril (eds.), Springer-Verlag Berlin Heidelberg (2013)
2013
-
[39]
Sperner,Ein Satz über Untermengen einer endlichen Menge, Mathematische Zeitschrift27(1928), 544–548
E. Sperner,Ein Satz über Untermengen einer endlichen Menge, Mathematische Zeitschrift27(1928), 544–548
1928
-
[40]
Stanley,Two poset polytopes, Discrete Comput
R. Stanley,Two poset polytopes, Discrete Comput. Geom. 1 (1986), no. 1, 9–23
1986
-
[41]
Tenenbaum,Introduction to Analytic and Probabilistic Number Theory, Graduate Studies in Mathe- matics, vol
G. Tenenbaum,Introduction to Analytic and Probabilistic Number Theory, Graduate Studies in Mathe- matics, vol. 163, American Mathematical Society, Providence, RI, 2015
2015
-
[42]
van de Lune,Some inequalities involving Riemann’s zeta-function, CWI Report ZW 50/75, Centrum Wiskunde & Informatica, Amsterdam, 1975
J. van de Lune,Some inequalities involving Riemann’s zeta-function, CWI Report ZW 50/75, Centrum Wiskunde & Informatica, Amsterdam, 1975
1975
-
[43]
Paul Erdős and his mathematics,
Various,Some of Paul’s favorite problems, booklet produced for the conference “Paul Erdős and his mathematics,” Budapest, July 1999
1999
-
[44]
K. C. Wang,The logarithmic concavity of(1−21−r)ζ(r), J. Changsha Comm. Univ.14(1998), 1–5. In Chinese
1998
-
[45]
Yamamoto,Logarithmic order of free distributive lattice, Journal of the Mathematical Society of Japan6(1954), 343–353
K. Yamamoto,Logarithmic order of free distributive lattice, Journal of the Mathematical Society of Japan6(1954), 343–353
1954
-
[46]
Zhang,On a conjecture of Erdős on the sumP p≤n 1/(plogp), J
Z. Zhang,On a conjecture of Erdős on the sumP p≤n 1/(plogp), J. Number Theory39(1991), 14–17
1991
-
[47]
Zhang,On a problem of Erdős concerning primitive sequences, Math
Z. Zhang,On a problem of Erdős concerning primitive sequences, Math. Comp.60(1993), 827–834. 34 OpenAI, San Francisco, CA 94158 Email address:boris.alexeev@gmail.com Queens’ College, University of Cambridge, Cambridge, CB3 9ET, United Kingdom Email address:kb799@cam.ac.uk School of Mathematics, Southeast University, Nanjing 211189, P. R. China Email addre...
1993
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.