Erdős #1135 — the Collatz (3x+1) conjecture

Statement

Define $f:\mathbb{N}\to \mathbb{N}$ by $f(n)=n/2$ if $n$ is even and $f(n)=\frac{3n+1}{2}$ if $n$ is odd. Given any integer $m\geq 1$, does there exist $k\geq 1$ such that $f^{(k)}(m)=1$? (erdosproblems.com/1135, statement verified verbatim against the live page.) This is the Collatz / $3x+1$ / Syracuse / Ulam / Kakutani / Hasse conjecture, in the "shortcut" (odd-step-halved) form.

Facts

- Prize $500; status open, explicitly flagged "This is open, and cannot be resolved with a finite computation" (erdosproblems.com/1135, site-owner belief; last edited 12 Jan 2026; 3 comments, none claiming progress). - Falsifiable: no in the strict sense the site means — a single counterexample orbit that provably never reaches 1 would refute it, but no finite computation can certify non-termination/divergence, so the problem "cannot be resolved with a finite computation" (only a proof, or a proof that a specific $m$'s orbit is unbounded/cyclic, would settle it). - Origin: not actually an Erdős problem — first devised by Lothar Collatz before 1952. Erdős referred to it repeatedly as "hopeless" and, per Lagarias [La16], the closest Erdős himself came to working on this class of problem is the theorem discussed in the remarks to erdos/1134. The much-repeated "\$500 Erdős prize" claim originates in Lagarias's 1985 survey [La85]; Lagarias later reported (personal communication, recorded on the page) that this figure came from a ~1983 conversation with Erdős and Graham where Graham asked Erdős to estimate what he'd rate the problem on his prize scale, and Erdős said \$500 — i.e. never a formally *offered* prize, just an estimate. It is Problem E16 in Guy's collection [Gu04], where Guy quotes Erdős: "Mathematics may not be ready for such problems." Also stated by Erdős in [Er97e, p.537]. - Known results / best bounds (all read directly from primary sources): - Almost-all results (density, not full resolution). Terras (1976, Acta Arith. 30) and, independently, Everett (1977, Adv. Math. 25) proved $\mathrm{Col}_{\min}(N) < N$ for almost all $N$ (natural density) — confirmed via Tao's intro, arxiv.org/pdf/1909.03562. Korec (1994, Math. Slovaca 44) improved this to: for any $\theta>\log 3/\log 4\approx0.7924$, $\mathrm{Col}_{\min}(N)\le N^\theta$ for almost all $N$ (natural density) — abstract of arXiv:1909.03562. Terence Tao, "Almost all orbits of the Collatz map attain almost bounded values" (arXiv:1909.03562, 2019, published Ann. of Math. Studies vol. for a 2020 conference volume): for *any* function $f:\mathbb N\to\mathbb R$ with $f(N)\to\infty$, $\mathrm{Col}_{\min}(N)\le f(N)$ for almost all $N$ in the sense of *logarithmic* density — the strongest known partial result, via a stabilisation/first-passage argument for a skew random walk on $\mathbb Z/3^n\mathbb Z$ (3-adic characteristic-function estimates). Tao's own paper states plainly that "the full resolution of Conjecture 1.1 remains well beyond reach of current methods." - Density lower bound. Krasikov & Lagarias, "Bounds for the 3x+1 Problem using Difference Inequalities" (arXiv:math/0205002, Acta Arith. 109 (2003), 237–258): computer-assisted proof that $\#\{N\le x:\mathrm{Col}_{\min}(N)=1\}\gg x^{0.84}$. - No small nontrivial cycles. Steiner (1977) proved no nontrivial 1-cycle; Simons (2005) extended Steiner's method to rule out 2-cycles; Simons & de Weger, "Theoretical and computational bounds for m-cycles of the 3n+1-problem" (Acta Arith. 117 (2005), DOI 10.4064/aa117-1-3, confirmed via Crossref) extended this to rule out all $k$-cycles for $k\le68$; Hercher later extended the method to $k\le91$ (en.wikipedia.org/wiki/Collatz_conjecture, "Cycle length"/"k-cycles" sections). Eliahou (1993) showed any nontrivial cycle's period $p$ must have the form $p=301994a+17087915b+85137581c$ ($a,b,c\ge0$, $b\ge1$, $ac=0$), derived from the simple continued-fraction expansion of $\ln3/\ln2$ (same Wikipedia sections) — this is the technique most likely to generalize (Diophantine/continued-fraction obstruction on cycle shapes). - Computational verification (not a proof; explicitly excluded by the site's "not finite" flag). Oliveira e Silva verified up to $\approx5.78\times10^{18}$; Roosendaal to $10^{20}$; David Barina, "Convergence verification of the Collatz problem" (J. Supercomputing, 2020) to $2^{68}\approx2.95\times10^{20}$; and most recently Barina, "Improved verification limit for the convergence of the Collatz conjecture" (J. Supercomputing, 2025, DOI 10.1007/s11227-025-07337-0, abstract read via Crossref) pushed this to $2^{71}$, using a $1335\times$ CPU→GPU speedup distributed across several European supercomputers, and additionally found four new path-length records. - 2026 negative/obstruction result (unrefereed, single-author, flag credibility). Edward Y. Chang, "Exploring Collatz Dynamics with Human-LLM Collaboration" (arXiv:2603.11066, v6, 233 pages, math.DS/cs.AI/cs.HC, submitted 10 Mar 2026, still being revised as of Jun 2026): a ~1014-experiment, 29-mathematical-paradigm survey (transfer-operator spectral theory, S-unit equations, $p$-adic interpolation, martingale methods, modular sieving, formal language theory, discrete-log obstruction, Diophantine approximation, etc.) claiming a "Paradigm Exhaustion Theorem" — that every currently known framework for promoting *distributional* convergence (Tao's "almost all orbits" style result) to *pointwise* convergence (every orbit) hits an irreducible structural obstruction on the Syracuse map. Explicitly states "The present work is not a proof of the Collatz conjecture; it characterizes why the conjecture resists proof." This is a preprint (not peer-reviewed, single author, explicitly AI-assisted per its own §12) and should be read as a survey/negative-result claim, not an established theorem — but it is directly on point for "what would crack this," see Attack surface below. Same author's companion arXiv:2603.25753 reduces the conjecture, on the compressed odd-to-odd Syracuse map, to a "one-bit orbit mixing" balance question at low depths ($K=3,4,5$), again unproven. - Related problems: erdos/1134 — explicitly cross-referenced in the site's own remarks as "the closest Erdős ever came to working on problems of this nature" (Lagarias [La16]); a *different* Erdős-original problem (density of the set generated by $x\mapsto2x+1,3x+1,6x+1$ from $\{1\}$) that was resolved (disproved, Lean-verified), giving a concrete worked example of the exact style of growth-exponent argument ($\sigma$ with $\sum m_i^{-\sigma}=1$, refined by Crampin–Hilton to $\tau\approx0.900626$) that is structurally analogous to (but strictly easier than) what would be needed here.

Literature state

Not resolved anywhere found — still fully open as of this writing (2026-07-02). Every source checked (erdosproblems.com/1135 itself, 3 non-substantive comments, still marked "open"; Lagarias's own annotated bibliographies arXiv:math/0309224 and its sequel arXiv:math/0608208; Tao's 2019/2022 paper's own framing "well beyond reach of current methods"; every 2026 arXiv preprint scanned) agrees the conjecture is open. The Collatz conjecture is among the most famous problems in mathematics precisely *because* elementary-looking density/verification/cycle-exclusion results keep accumulating (Terras 1976, Everett 1977, Korec 1994, Krasikov–Lagarias 2003, Tao 2019, Barina 2020/2025) without ever closing the gap between "almost all" (density, even logarithmic-density-1) and "all" (every single positive integer) — Tao's paper is explicit that his own theorem, though it gets $\mathrm{Col}_{\min}(N)$ below *any* diverging function for almost all $N$, still does not touch a single exceptional orbit, let alone rule out unbounded/divergent or cyclic orbits outright.

The most interesting recent literature signal is Edward Y. Chang's 2026 "Paradigm Exhaustion Theorem" preprint (arXiv:2603.11066), which — while itself unrefereed and single-author — is a serious, dated (submitted March 2026, still being revised through at least v6) argument that *no currently known technique* (not just Tao's, but 29 distinct paradigms spanning spectral transfer-operator theory, $p$-adic methods, martingales, S-unit equations, formal-language theory, Diophantine approximation) can be pushed from distributional to pointwise convergence on the Syracuse map, without a genuinely new idea. Whether or not its specific technical claims hold up under review, it is directly useful as a map of "what has already been tried and why it plausibly can't work," produced with explicit LLM collaboration.

No AI system (GPT/DeepMind/Aristotle/AlphaProof/AlphaEvolve) is recorded on erdosproblems.com or the GitHub teorth/erdosproblems project as having touched #1135 specifically (unlike, e.g., erdos/229 in the same "iterated functions" tag, solved and Lean-formalized by Barth–Schneider with AlphaProof/DeepMind assistance noted on that page). The problem *is* formalised on the site ("Formalised statement? Yes"), meaning the statement itself has a machine-checkable Lean encoding, but that says nothing about a proof existing.

Attack surface

- Mode: literature-resolution confirms open; the only viable modes going forward are derivation+formalization (a genuinely new proof technique — see the "Paradigm Exhaustion" negative result above, which argues incremental refinement of any of the 29 known paradigms is unlikely to suffice) or finite-search restricted to narrow sub-questions that *are* finitely decidable (extending the no-small-cycles bound past $k=91$, or the verification bound past $2^{71}$) — neither of which resolves the conjecture itself, only chips at its edges, consistent with the site's own "not finite" flag on the top-level question. - Concrete first experiment (narrow, in-reach, NOT a resolution): reproduce Simons–de Weger / Hercher's continued-fraction-driven no-$k$-cycle argument (built on Eliahou's 1993 period-form constraint $p=301994a+17087915b+85137581c$) and push the exhaustive computer search past $k=91$ to the next tractable bound — this is a genuinely finite, mechanically verifiable computation in the *cycle-exclusion* sub-problem (distinct from the "not finite" top-level conjecture, since ruling out cycles of bounded "descent count" $k$ is a finite search per $k$). - Oracle: none for the conjecture itself (not finite, per the site). For the narrow sub-experiment: mechanical — a candidate $k$-cycle is verified/refuted by direct simulation of the orbit and checking periodicity against the Eliahou period-form constraint; a claimed proof that no $k$-cycle exists for $k\le K$ is checked by reproducing the finite search underlying Simons–de Weger/Hercher's argument. - Feasibility: honest read — this is one of the hardest and most famous open problems in mathematics, explicitly called "hopeless" by Erdős himself and, per the 2026 "Paradigm Exhaustion" preprint, actively argued to resist all 29 currently known attack paradigms. Not remotely in reach for a full resolution. The only realistically useful contributions are (a) incremental verification-record or cycle-exclusion-bound pushes (mechanical, well-trodden, low research value), or (b) synthesizing/auditing the "why every known paradigm fails" literature (Chang 2026) into a sharper, credibly-refereed obstruction result — itself a nontrivial research contribution but not a resolution.

Related

- erdos/1134 — explicitly cross-referenced on the erdosproblems.com page as the closest Erdős himself came to this problem class; a *different*, Erdős-original problem (density of the smallest set containing 1 closed under $x\mapsto2x+1,3x+1,6x+1$) that was disproved and Lean-verified, via a growth-exponent bound ($\sum m_i^{-\sigma}=1$, sharpened by Crampin–Hilton to $\tau\approx0.900626$) — the nearest fully-solved analog in the Erdős-problems corpus, though its counting-argument technique does not obviously transfer to the full Collatz map (the three affine maps there are non-conflicting/injective-image partitions, unlike the even/odd branching here). - erdos/408 — same "iterated functions" tag; distribution of the iterated-Euler-totient stopping time $f(n)=\min\{k:\phi_k(n)=1\}$, structurally the same "how many iteration steps until absorption at a fixed point" question as Collatz's stopping time, with a body of results (Pillai 1929 bounds, Erdős–Granville–Pomerance–Spiro conditional distribution result) that is a natural place to look for stopping-time-distribution technique transfer. - Logarithmic density: the $1/n$-weighted density that survives when natural density doesn't — the density notion (as opposed to natural density) that lets Tao's theorem be unconditional for *any* diverging bound function; central technical device of arXiv:1909.03562. - concept/3-adic-skew-random-walk — Tao's core technique: recasting the Collatz/Syracuse map's parity sequence as a skew random walk on cyclic groups $\mathbb Z/3^n\mathbb Z$ and estimating its characteristic function at high frequencies via a 2D renewal-process argument. - concept/transfer-operator-spectral-gap — the Sinai/Kontorovich–Sinai "statistical 3x+1" framework and its 2026 use (arXiv:2603.11066) proving a uniform spectral gap for the Syracuse transfer operator, implying equidistribution mod any power of 2 — one of the 29 paradigms surveyed as insufficient alone for pointwise convergence. - concept/continued-fraction-cycle-obstruction — Eliahou's 1993 technique: any nontrivial cycle's period is constrained to a specific numerical semigroup derived from the continued-fraction expansion of $\ln3/\ln2$; the backbone of every no-small-cycle result since (Steiner, Simons, Simons–de Weger, Hercher). - concept/paradigm-exhaustion-survey — the 2026 human-LLM-collaboration methodology (arXiv:2603.11066) of systematically running ~1000+ computational experiments across dozens of named mathematical paradigms to map which known techniques provably cannot close a stubborn distributional-to-pointwise gap; a reusable meta-technique for triaging "is this open problem in reach with known tools" independent of Collatz specifically. - concept/gpu-distributed-exhaustive-verification — Barina's 2020→2025 pipeline (CPU→GPU, $1335\times$ speedup, distributed across European supercomputers) pushing brute-force convergence verification from $2^{68}$ to $2^{71}$; the state of the art for the finite-search sub-mode.