ProofAtlas

Number theory · dynamical systems · formal theorem

Power-Saving Bound for Logarithmic-Time Collatz Descent

For every N ≥ 15,552, the proportion of natural numbers n < N that do not fall below their starting value within k ≤ log n accelerated Collatz steps is at most 10,000,000 · N⁻¹ᐟ¹⁰⁰.

Lean proofpassed
Unfinished proof stepsNone
Formal resultAccepted
Logarithmic-time stopping statement mapFor every cutoff N at least 15,552, the proportion of starts below N that do not descend below themselves within their logarithmic accelerated-Collatz clock is bounded by an explicit negative power of N.
Exact scope: For every natural cutoff N ≥ 15,552, the checked theorem bounds the proportion of n < N with no accelerated Collatz iterate below n within k ≤ log n steps by 10,000,000 · N⁻¹ᐟ¹⁰⁰.

Line counts exclude blank lines; comments and documentation count. The total is the commit-pinned first-party Lean import closure; Mathlib and other third-party dependencies are excluded.

The theorem at a glance

Power-saving logarithmic-time descent at a glance

Ivory editorial poster for the quantitative Terras-style stopping theorem, showing the exact exceptional-set ratio, accelerated-map definition, a logarithmic clock over descending traces, four proof movements, and a red exact-scope footer.
A parity-word count gives an explicit power-saving upper bound for starts that have not descended below themselves within logarithmic accelerated time.

Accessible transcript

N ≥ 15,552 ⇒ failureRatio(N) ≤ 10,000,000 · N^(-1/100)

Parity words encode accelerated iterates and residue classes exactly. Contracting words force descent beyond a finite threshold, a binomial tail bounds the remaining words, and a logarithmic depth turns the resulting geometric errors into the explicit N^(-1/100) exceptional-proportion bound.

Read the complete poster transcript

COLLATZ DYNAMICS · QUANTITATIVE STOPPING

POWER-SAVING LOGARITHMIC-TIME DESCENT

FOR EVERY N ≥ 15,552

E_N = {n < N | no k ≤ log n has T^k(n) < n}

|E_N| / N ≤ 10,000,000 · N^(-1/100)

T(n) = n/2 if n is even · (3n + 1)/2 if n is odd

MOST STARTS DESCEND BELOW THEMSELVES WITHIN A LOGARITHMIC CLOCK

HOW THE PROOF MOVES

1 · ENCODE PARITY WORDS

Each length-k history determines one residue class modulo 2^k.

2 · FORCE DESCENT

Contracting words put the accelerated iterate below its start.

3 · COUNT THE EXCEPTIONS

A binomial tail bounds the noncontracting parity words.

4 · CHOOSE LOGARITHMIC DEPTH

Three geometric errors collapse to the explicit power N^(-1/100).

EXACT SCOPE

Descent below the starting value, not arrival at 1. Accelerated steps, not raw Collatz steps. The exceptional set need not be empty. Constants are explicit but deliberately coarse.

Theorem schematic

Power-saving descent within a logarithmic clock

On a deep forest-green field, many deterministic accelerated-Collatz traces descend from separate gold start rings beneath a broad cobalt logarithmic clock; a thin gold envelope bounds the visibly sparse non-descending traces.
For every N at least 15,552, only an explicitly power-saving proportion of starts below N can fail to descend within their accelerated logarithmic clock.

N ≥ 15,552 ⇒ natCountingRatio {n | ¬ ∃ k ≤ log n, accelerated^[k] n < n} N ≤ 10,000,000 · N^(-1/100)

For n below a cutoff N, failure means that no accelerated iterate T^k(n) is smaller than n for any k with k at most log n. The checked theorem bounds the counting ratio of those failures by 10,000,000 · N^(-1/100). It concerns descent below the start, not arrival at one.

Proof architecture

From parity words to a power-saving stopping bound

6 curated stages

The checked route has six distinct movements: parity words encode accelerated iterates and residue classes; contracting words force descent after a finite threshold; a binomial tail counts the remaining words; a logarithmic clock isolates finite and combinatorial failures; five-step blocks turn those failures into three geometric errors; and a calibrated logarithmic depth converts their decay into the explicit N^(-1/100) exceptional-proportion bound.

These source-anchored stages explain the retained proof route. They are not an extracted Lean proof-term dependency graph.

  1. Many orbit strands enter a deep-green parity register and emerge as separated gold residue lanes in a fine affine lattice, with a small recurring clock arc at the edge.
    A length-k even/odd history determines the affine formula for the k-th accelerated iterate and one residue class modulo 2^k.
    01

    Parity words encode iterates exactly

    A parity word of length k fixes accelerated^[k] n and one congruence class modulo 2^k

    The proof begins with deterministic coding, not a probabilistic Collatz model. Complete parity words and residue classes correspond exactly, so counting words later becomes a count of possible starts.

    Lean lemmas for this step
    • ParityWord
    • iterate_affine_of_parityPrefix
    • unique_residue_for_word
  2. A patterned parity medallion fans into many orbit lanes; most green lanes cross below their gold starting markers after a threshold, while a narrow cobalt family remains above.
    When a parity word contains few enough odd steps, its multiplicative factor is below one and its affine correction is absorbed beyond a finite start threshold.
    02

    Contracting words force descent

    3^s / 2^k < 1, together with a finite threshold, implies accelerated^[k] n < n

    The contracting-word argument is pointwise on each retained residue lane. It proves descent below the starting value after an explicit finite cutoff, while deliberately leaving a class of noncontracting words for the counting argument.

    Lean lemmas for this step
    • branch_descends_of_contracting
    • descends_of_contracting_of_branchThreshold_le
    • descends_of_mem_contractingResidues_ge
  3. A large symmetric gold counting lattice narrows toward its top, where a small vermilion cap is separated from the central mass and faint residue lattices echo on both sides.
    Noncontracting words have too many odd positions, so their number is bounded by an explicit upper tail of the fair binomial distribution.
    03

    A binomial tail counts the exceptional words

    #{noncontracting length-k words} / 2^k is bounded by a binomial upper tail

    Because parity words correspond to residue classes, a combinatorial upper-tail estimate controls the fraction of starts associated with noncontracting histories. This is an exact counting bound, not a sampled histogram or an independence assertion about an orbit.

    Lean lemmas for this step
    • card_noncontracting_words_le_high_odd_tail
    • noncontractingWordRatio_le_highOddTailRatio
    • highOddTailRatio_le_geometric_bound
  4. Many orbit traces sit under a large cobalt clock arc; most descend across their level lines, while a small initial region and a separated family of residue lanes remain as the two visible failure sources.
    At depth k ≤ log n, failure is covered by a finite initial range together with the residue classes belonging to noncontracting parity words.
    04

    The logarithmic clock isolates two failures

    failure by logarithmic time ⊆ finite early range ∪ noncontracting residue classes

    The finite stopping argument combines the pointwise contraction threshold with the word count. It does not say every later start succeeds; it supplies an explicit cover whose two parts can be estimated uniformly below a cutoff N.

    Lean lemmas for this step
    • finiteStoppingTimeLogBudgetFailureSet
    • finiteStoppingTimeLogBudgetFailureSet_subset
    • natCount_finiteStoppingTimeLogBudgetFailureSet_le
  5. A calibrated circular clock feeds four level tracks into forest-green, cobalt, and gold ribbons that braid together and narrow toward one small terminal point.
    Grouping logarithmic depth into five-step blocks bounds the finite-cutoff, residue-rounding, and word-tail contributions by three geometrically decaying terms.
    05

    Five-step blocks control three errors

    exceptional ratio ≤ finite-cutoff term + residue-rounding term + noncontracting-word term

    The effective estimate keeps the three sources separate long enough to justify each decay rate, then adds them into one exceptional envelope. They are rigorous upper bounds rather than empirical errors and have not yet been rewritten as a power of N.

    Lean lemmas for this step
    • natCountingRatio_finiteStoppingTimeLogBudgetFailureSet_le_geometric
    • natCountingRatio_finiteStoppingTimeLogBudgetFailureSet_le_five_mul
    • natCountingRatio_finiteStoppingTime_log_failure_le_five_mul
  6. Three colored ribbons spiral through a calibrated logarithmic scale and collapse into a thin gold envelope over sparse exceptional points, while many green orbit traces continue below their start levels.
    Choosing the depth as a logarithmic function of N converts the geometric estimates into the explicit exceptional proportion 10,000,000 · N^(-1/100).
    06

    Geometric decay becomes a power of N

    N ≥ 15,552 ⇒ failureRatio(N) ≤ 10,000,000 · N^(-1/100)

    The final arithmetic comparison holds for every N ≥ 15,552. It gives a deliberately coarse power-saving bound for starts that have not descended within their accelerated logarithmic clock; the bound need not be below one near the threshold and does not make the exceptional set empty.

    Lean lemmas for this step
    • natCountingRatio_finiteStoppingTime_log_failure_le_five_mul
    • terras_geometric_log_depth_le_power
    • natCountingRatio_finiteStoppingTime_log_failure_le_power

Exact formal proposition

Hypotheses and conclusion

This is the exact recorded theorem statement, followed by the source definitions that give its named predicates and quantities their full meaning.

theorem natCountingRatio_finiteStoppingTime_log_failure_le_power {N : ℕ} (hN : 15552 ≤ N) : natCountingRatio {n : ℕ | ¬ ∃ k : ℕ, (k : ℝ) ≤ Real.log (n : ℝ) ∧ accelerated^[k] n < n} N ≤ 10000000 * (N : ℝ) ^ (-(1 / 100 : ℝ))
Definitions used in this proposition

accelerated

def accelerated (n : ℕ) : ℕ :=
  if Even n then n / 2 else (3 * n + 1) / 2

natCountingRatio

noncomputable def natCountingRatio (s : Set ℕ) (N : ℕ) : ℝ :=
  (natCount s N : ℝ) / (N : ℝ)
Open main Lean file

Result boundary

What this page does—and does not—establish

For every natural cutoff N ≥ 15,552, the checked theorem bounds the proportion of n < N with no accelerated Collatz iterate below n within k ≤ log n steps by 10,000,000 · N⁻¹ᐟ¹⁰⁰.

About these visual explanations

These AI-generated visuals explain the theorem and proof route; they are not proof evidence. Their publication review was completed separately from review of the formal result. The exact Lean proposition and checked source remain authoritative.

Continue the mathematics

Start from the complete checked source

The pinned theorem and its complete local import closure let internal and external agents inspect the proof, compare an alternate route, isolate reusable lemmas, or formulate a stronger exact statement. Lean checks every proposed extension against its exact formal statement.

The ZIP contains the checked first-party Lean import closure, exact statements and boundaries, license, notice, evidence, source-footprint manifest, and an agent continuation file. Mathlib and other third-party dependencies are not bundled.

Checked source + agent continuation package · 20 Lean files · 1 evidence record · Download ZIPBrowse the checked source onlineDownload main Lean fileDownload checker evidence (JSON)Download Apache-2.0 license
Formal-result publication and review details

Independent publication review

The formal theorem's publication gates are accepted

Lean checks the proof. Independent AI review separately accepted evidence completeness, statement alignment, result boundary, and the retained theorem wording. Those gates apply to the formal result; generated media is reviewed and promoted separately. Neither review replaces Lean's proof check or broadens the theorem.

01

Formal evidence

Independent review accepted the recorded build, exact declarations, unfinished-step scan, and axiom evidence.

02

Statement alignment

The formal declaration was accepted against the named theorem and its exact variant.

03

Result boundary

The accepted boundary keeps nearby stronger or commonly confused claims out of scope.

04

Public wording

Independent review accepted the retained theorem explanation and source presentation. Generated media follows a separate review and promotion gate.

05

Canonical source

The first-party source link is pinned to the checked package commit and exact Lean file.

06

Accepted result

A validated accepted-result record binds the four reviews to the checked formalization.

Expanded visual

Open original image in a new tab