Collatz conjecture
Does the 3n + 1 process always reach 1, whatever number it starts from?
Summary
AI-assisted claims
Positive density of Collatz convergence at every rate above 3/log(4/3)
“We prove that a positive proportion of positive integers reach 1 within c log x ordinary Collatz steps for every fixed c > 3/log(4/3), with one positive lower natural-density bound independent of c.”
- By
- Idris Ali Shaik
- AI involvement
- Text declaration: A mix of human-written and AI-generated. Human-understanding declaration: All parts of this contribution have been checked and understood by a human. Additional provenance: AI-assisted tools were used in manuscript preparation, Lean proof development, code preparation, and editorial revision.
- Where
- Hexagon
- Formal proof
- Lean, published by the source
- Repository
- shaikidris/CollatzConvergencePositiveDensity at f805c8c · read 21 Nov 2026
- Palomar
- PALOMAR-2026-09-23-000002 v1
- Source last read
- 27 Oct 2026
Checks
1 Palomar entry
- 23 Sep 2026 · In Palomar · Palomar: Palomar entry PALOMAR-2026-09-23-000002 v1: shaikidris/CollatzConvergencePositiveDensity at commit f0fda88, theorems CollatzWordCert.collatz_convergence_positive_lower_density, CollatzWordCert.collatz_convergence_depth_eleven_density_bound, CollatzWordCert.collatz_logarithmic_threshold_lt_10431_div_1000 and 15 more. Source
Explicit positive lower density for the Collatz Conjecture
“For every N, at least ⌊N/2^(2^(2^163))⌋ odd positive integers n < N reach 1 within 10.46 log n ordinary steps and 3.4881 log n accelerated steps.”
- By
- Kenny Lau
- AI involvement
- Text declaration: A mix of human-written and AI-generated. Human-understanding declaration: Some parts of this contribution, but not all, have been checked and understood by a human. Additional provenance: This project was born out of our goal to formalize Mazur's paper, with the intent of improving the estimates. With this stated goal, AxiomProver autonomously produced the mathematics in this paper and formalized it in Lean.
- Model
- AxiomProver, as stated
- Where
- Hexagon
- Formal proof
- Lean, published by the source
- Repository
- AxiomMath/CollatzPositiveDensity at c2e1f71 · read 21 Nov 2026
- Palomar
- PALOMAR-2026-10-15-000013 v1
- Source last read
- 27 Oct 2026
Checks
1 Palomar entry
- 15 Oct 2026 · In Palomar · Palomar: Palomar entry PALOMAR-2026-10-15-000013 v1: AxiomMath/CollatzPositiveDensity at commit 3a38bfb, theorems positive_density_collatz_reaches_one, positive_density_collatz_and_collatzAccel_reaches_one, positive_density_collatz_and_collatzAccel_reaches_of_coprime_six and 1 more. Source
Polylogarithmic Descent for Almost All Collatz Orbits in Natural Density
“We obtain polylogarithmic descent in ordinary natural density within logarithmically many steps, with bounds on the preceding orbit values.”
- By
- Idris Ali Shaik
- AI involvement
- Text declaration: A mix of human-written and AI-generated. Human-understanding declaration: All parts of this contribution have been checked and understood by a human. Additional provenance: OpenAI Codex assisted with mathematical exploration, Lean formalization, and manuscript preparation. The author reviewed the AI-assisted material and takes full responsibility for the manuscript.
- Model
- OpenAI Codex, as stated
- Where
- Hexagon
- Formal proof
- Lean, published by the source
- Repository
- shaikidris/FirstPassageLinearTransport-Palomar at dcd32c0 · read 21 Nov 2026
- Palomar
- PALOMAR-2026-08-26-000005 v4
- Source last read
- 27 Oct 2026
Checks
1 Palomar entry
- 06 Sep 2026 · In Palomar · Palomar: Palomar entry PALOMAR-2026-08-26-000005 v4: shaikidris/FirstPassageLinearTransport-Palomar at commit 39a6ba1, theorems CollatzFirstPassage.critical_polylogarithmic_descent_with_arbitrary_multipliers, CollatzFirstPassage.fixed_polylogarithmic_common_landing_centered_clocks_exact_rate, CollatzFirstPassage.eventually_fixedJointPolylogHeightFailureCount_ge_log_order and 1 more. Source
Claims as their sources state them. Listing a claim is not a check by Papex; the status stays the source’s.
Why it is open
Under this rule the sequence starting from a number n, called its orbit, can do one of three things: reach 1 and then repeat 4, 2, 1; enter some other cycle; or grow without bound [2]. The conjecture says that only the first ever happens [2, 5]. A resolution is a proof that covers every starting number, or a single counterexample: a number whose orbit cycles elsewhere or diverges. Since 2021 the company Bakuage has offered 120 million yen for a resolution, under its own rules (see Prize); earlier prizes include $500 offered by Paul Erdős [2].
The problem is traditionally credited to Lothar Collatz, who became interested in number-theoretic functions and their iterates as a student in the 1930s; it then circulated by word of mouth under names such as the Syracuse problem, Kakutani's problem and Ulam's problem [2]. Erdős commented: "Mathematics is not yet ready for such problems" [2].
Jeffrey Lagarias, in his 1985 survey, connects the difficulty to the fact that the rule is "a deterministic process that simulates 'random' behavior": the structure that allows analysis seems to be what prevents a proof that the process behaves randomly, and to the extent that it is random there is nothing to analyse [2]. Generalisations show how much such simple rules can encode [2, 4]. John Conway showed in 1972 that for an explicitly constructed rule of the same piecewise-linear kind, no algorithm can decide for every starting number whether its orbit reaches a power of 2 [2]. Stuart Kurtz and Janos Simon proved in 2007 that, given an arbitrary rule of this kind, it is undecidable whether every starting number reaches 1, and offer this as a heuristic explanation of the problem's difficulty [4]. These results concern families of rules, not the 3n + 1 rule itself [4].
What is known
Heuristics. If the odd numbers in an orbit behaved like randomly chosen odd numbers, the orbit would shrink on average by a factor of about 3/4 from one odd number to the next, so divergent orbits should not exist [2, 5]. Lagarias locates the central difficulty in proving the "mixing" properties that this argument assumes [2].
Almost all numbers (1976–2022). Riho Terras proved in 1976, and C. J. Everett independently in 1977, that almost every starting number eventually drops below itself, in the sense of natural density [1, 5]. Later work showed that almost every orbit drops below N^θ, where N is the starting number; in 1994 I. Korec obtained this for every θ > log 3/log 4 ≈ 0.7924 [5]. Terence Tao proved (preprint 2019, published 2022) that for any function f(N) tending to infinity, however slowly, almost every orbit drops below f(N); here "almost every" is in the sense of logarithmic density [5]. For example, almost every orbit drops below log log log log N [5].
Numbers that reach 1. Ilia Krasikov and Jeffrey Lagarias proved in 2003, with a computer-aided proof, that at least x^0.84 of the integers below x reach 1, for all large x [3].
Computer checks. In 2025 David Barina reported that every starting number up to 2^71, about 2.4·10^21, reaches 1; the computation ran on graphics processors and several European supercomputers [8].
Cycles. Allowing negative numbers, other cycles do exist, starting for example from −1, −5 and −17 [2]. For positive numbers, R. P. Steiner showed in 1977 that the only "circuit", a cycle of a particular simple form, is the trivial one [2]. Counting the local minima of a cycle, Christian Hercher proved in 2023 that a non-trivial cycle would need at least 92, improving a bound of 76 by John Simons and Benne de Weger; a corrigendum of June 2026 repairs one step of the proof [7]. Kevin Knight showed in 2026 that the opposite extreme to circuits, which he calls high cycles, does not occur among positive integers either [9].
Recent claims. On 25 July 2026 Ramana Kumar published a GitHub repository, CollatzLean, containing a Lean formalisation whose stated result is the negation of the conjecture: an orbit that never reaches 1, shown to exist without naming a starting number [10]. Lean's kernel and the independent checker nanoda accepted it [11, 12]. Leonardo de Moura, chief architect of the Lean FRO, wrote that the repository was "produced with AI assistance" and "is not a valid proof because it exploits a bug in the kernel's handling of nested inductive types"; the bug was reported and fixed in the week of 27 July, and nanoda had a separate bug that let the same proof through [11]. Lawrence Paulson wrote: "Unfortunately, the proof is wrong. It exploited a bug in the Lean kernel" [12]. In a guest post on Terence Tao's blog, Thomas Hales called it "an illicit disproof of the Collatz conjecture" and credited Kumar with finding the bug [13]. On 14 October 2026 the Wikipedia list of unsolved problems in mathematics, the catalogue's status source, still gave the conjecture as open [14].
Main approaches
Density and probability. Treat orbits statistically and prove that typical ones drop [1, 5]. Strongest evidence: Tao's theorem that almost all orbits attain almost bounded values [5]. Main difficulty: "almost all" leaves room for exceptional orbits, and Tao writes that bounding almost all orbits by a fixed constant is "likely to be almost as hard to settle as the full Collatz conjecture" [5].
Counting with inequalities. Systems of difference inequalities give lower bounds for how many numbers reach 1 [3]. Strongest evidence: the bound x^0.84 [3]. Main difficulty: this is far from all numbers, and the authors write that their improvement apparently extracts full information from these inequalities, so going further needs new ones [3].
Cycles and Diophantine equations. A cycle must satisfy an exponential Diophantine equation in powers of 2 and 3, so results on such equations and on rational approximation can rule cycles out [2]. Strongest evidence: the exclusion of circuits [2], of cycles with fewer than 92 local minima [7] and of high cycles [9]. Main difficulty: each result excludes one class of cycles, some depend on how far computer checks reach [7], and none addresses orbits that grow without bound [2].
Computation. Check every starting number up to a bound [8]. Strongest evidence: the check up to 2^71 [8]. Main difficulty: a check cannot exclude a counterexample beyond its range, although it feeds the cycle bounds [7].
Automated reasoning. Emre Yolcu, Scott Aaronson and Marijn Heule built a string-rewriting system whose termination is equivalent to the conjecture, and found automated proofs of nontrivial weakenings of it [6]. Strongest evidence: those automated proofs [6]. Main difficulty: the conjecture itself was not proved [6], and the 2026 episode above shows that a machine-checked proof depends on bug-free proof checkers [11].
Open sub-questions
- Natural density. Can Tao's theorem be proved with natural density in place of logarithmic density, as he considers plausible [5]?
- A positive share. Can an explicit version of Tao's argument, combined with the check up to 2^71, prove the conjecture for a set of starting numbers of positive logarithmic density, as Tao notes is possible in principle [5, 8]?
- Beyond x^0.84. Which new inequalities could raise the exponent 0.84 in the Krasikov–Lagarias bound [3]?
- Larger cycles. Hercher showed that checking all starting numbers up to 3·2^69 would suffice to show that a non-trivial cycle has at least 1.375·10^11 odd members [7]; with the check now at 2^71 [8], what bounds on cycles follow, and can the minimum of 92 local minima be raised [7]?
- Between circuits and high cycles. Can the methods that exclude circuits and high cycles be extended to the cycle types between them [2, 9]?
- Divergent orbits. If an orbit grows without bound, what limits are there on how its members grow? Lagarias lists this as a place to begin research [2].
- Machine proofs. Can termination provers prove stronger weakenings of the rewriting system of Yolcu, Aaronson and Heule [6]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It does not check a proof, and it is not a submission for the Bakuage prize.
Key references
- Terras, R. (1976). A stopping time problem on the positive integers. Acta Arithmetica 30(3), 241–252. 10.4064/aa-30-3-241-252 · Checked 14 Oct 2026
- Lagarias, J. C. (1985). The 3x + 1 problem and its generalizations. The American Mathematical Monthly 92(1), 3–23. 10.1080/00029890.1985.11971528 · Checked 14 Oct 2026
- Krasikov, I. & Lagarias, J. C. (2003). Bounds for the 3x+1 problem using difference inequalities. Acta Arithmetica 109(3), 237–258. 10.4064/aa109-3-4 · Checked 14 Oct 2026
- Kurtz, S. A. & Simon, J. (2007). The undecidability of the generalized Collatz problem. In Theory and Applications of Models of Computation (TAMC 2007), Lecture Notes in Computer Science, Springer, 542–553. 10.1007/978-3-540-72504-6_49 · Checked 14 Oct 2026
- Tao, T. (2022). Almost all orbits of the Collatz map attain almost bounded values. Forum of Mathematics, Pi 10, e12 (published online 20 May 2022). 10.1017/fmp.2022.8 · Checked 14 Oct 2026
- Yolcu, E., Aaronson, S. & Heule, M. J. H. (2023). An automated approach to the Collatz conjecture. Journal of Automated Reasoning 67(2), 15. 10.1007/s10817-022-09658-8 · Checked 14 Oct 2026
- Hercher, C. (2023). There are no Collatz m-cycles with m ≤ 91. Journal of Integer Sequences 26(3), Article 23.3.5; corrigendum dated 14 June 2026. Source · Checked 14 Oct 2026
- Barina, D. (2025). Improved verification limit for the convergence of the Collatz conjecture. The Journal of Supercomputing 81(7), 810 (published online 2 May 2025). 10.1007/s11227-025-07337-0 · Checked 14 Oct 2026
- Knight, K. (2026). Collatz high cycles do not exist. Discrete Mathematics 349(3), 114812. 10.1016/j.disc.2025.114812 · Checked 14 Oct 2026
- Kumar, R. (2026). CollatzLean: "Collatz conjecture in Lean". GitHub repository; commit "Finish disproof", 25 July 2026. Source · Checked 14 Oct 2026
- de Moura, L. (2026). Postmortem for kernel soundness bug #14576. Blog post, 1 August 2026. Source · Checked 14 Oct 2026
- Paulson, L. C. (2026). Why is it all in the kernel? Machine Logic (blog), 30 July 2026. Source · Checked 14 Oct 2026
- Hales, T. (2026). What mathematicians should know about the Lean Theorem Prover: questions of reliability and AI. Guest post on Terence Tao's blog What's new, 9 October 2026. Source · Checked 14 Oct 2026
- Wikipedia. List of unsolved problems in mathematics, revision 1379514120 of 10 October 2026. Source · Checked 14 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 29 Sep 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Prize
Bakuage · ¥120,000,000
Only Bakuage awards this prize, under its own rules. Your Papex record is separate: a signed, dated record of your work, not a prize entry.
Records on this problem
No public record addresses this problem yet.