🔢 mathematics

Recurrence Structures, Finite State Decomposition, and Statistical Bias in Collatz Path Sequences

This paper reduces the Collatz conjecture to the convergence of integers congruent to $3 \pmod{4}$ by classifying them into six recurrent residue classes modulo 9, modeling their dynamics via a finite state machine, and revealing a striking statistical bias where the form $9n+8$ accounts for approximately 97.6% of terminating paths.

Original authors: Sawon Pratiher

Published 2026-03-31

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sawon Pratiher

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, tangled knot of string. This knot represents the Collatz Conjecture, a famous math puzzle that has stumped geniuses for nearly 90 years.

The rules of the game are simple:

Pick any whole number.
If it's even, cut it in half.
If it's odd, triple it and add one.
Repeat.

The big question is: Will you always eventually reach the number 1? (Once you hit 1, the loop becomes 4 → 2 → 1 → 4... and you stay there).

Most people have tried to prove this by looking at the numbers one by one. This paper, by Sawon Pratiher, takes a different approach. Instead of looking at the individual threads, the author builds a map and a traffic control system to see how the numbers move as a group.

Here is the paper explained in simple terms, using analogies.

1. The "Easy" vs. "Hard" Neighborhoods

The author first divides all numbers into four neighborhoods based on what happens when you divide them by 4 (like sorting mail by zip code).

Neighborhoods A, B, and D: These are the "Easy" neighborhoods. If you start here, the rules of the game force you to immediately shrink down to a smaller number. It's like walking down a slide; you can't get stuck here.
Neighborhood C: This is the "Hard" neighborhood (numbers like 3, 7, 11, 15...). If you start here, the rules might actually make the number bigger before it gets smaller.

The Big Insight: The author proves that if you can solve the puzzle for the "Hard" neighborhood (C), you have solved it for everyone. The other neighborhoods just funnel you into this one tricky area. So, we can ignore the easy stuff and focus entirely on Neighborhood C.

2. The Six "Rest Stops" (Recurrent Forms)

Once you are in the Hard Neighborhood, the numbers don't just wander randomly. They get funneled into one of six specific "Rest Stops."

Imagine a highway where every car, no matter how fast or slow it's going, eventually has to stop at one of six specific gas stations. These stations are defined by the remainder you get when you divide the number by 9.

The author calls these stations a, b, c, d, e, and f.
Every time a number follows the Collatz rules, it hops from one station to another.
The "Power of 2" Goal: The goal of the game is to reach a "Power of 2" (like 2, 4, 8, 16, 32...). The author proves that every single Power of 2 belongs to exactly one of these six stations. If you can prove that every car eventually reaches a gas station that is a Power of 2, you win.

3. The Traffic Light System (Finite State Machine)

To track how numbers move between these six stations, the author builds a Traffic Light System (called a Finite State Machine).

Think of it like a board game:

You are a piece on the board.
Your current position is one of the six stations (a–f).
The "dice roll" is whether your number is Even or Odd.
The rules tell you exactly which station you move to next.

For example:

If you are at Station a and your number is Even, you move to Station b.
If you are at Station a and your number is Odd, you stay at Station a (but your number changes).

This turns the chaotic, infinite math problem into a structured, predictable flow chart. The author writes down the exact "traffic laws" (equations) for every possible move.

4. The Shocking Discovery: The "97.6%" Bias

Here is where the paper gets really interesting. The author ran a computer simulation on the first 100 million numbers to see which station they ended up at when they finally reached a Power of 2.

If the Collatz game were purely random (like flipping a coin), you would expect the numbers to finish at each of the six stations roughly 1/6th of the time (about 16.6% each).

But that's not what happened.

Station "a" (Form 9n + 8): This station swallowed 97.6% of all the numbers!
Station "c": Got about 2.4%.
Stations b, d, e, f: These were almost empty. They got so few numbers that they are practically invisible in the data.

The Analogy: Imagine a giant funnel with six holes at the bottom. If you pour a million marbles in, you'd expect them to split evenly. Instead, the author found that the funnel is rigged so that 97 out of 100 marbles fall into the same single hole.

This proves that the Collatz game is not random. It has a hidden, rigid structure that forces almost everything into one specific path.

5. What Does This Mean?

The paper doesn't prove the Collatz Conjecture is true (that would solve the 90-year-old mystery), but it changes how we look at the problem.

It's a Covering Problem: The author suggests that proving the conjecture is now equivalent to proving that this "Traffic Light System" covers every possible starting number. If the system works, everyone gets to the exit.
It's Deterministic: The massive bias (97.6%) shows that the numbers aren't behaving like a chaotic storm; they are behaving like a well-oiled machine with a very specific design.
New Tools: The author provides a new set of tools (the six stations and the traffic rules) for other mathematicians to use. Instead of guessing, they can now study the specific "traffic laws" of these six stations.

Summary

Sawon Pratiher took the messy, infinite Collatz problem and organized it into a neat, six-stop bus route. He showed that:

We only need to worry about one type of starting number.
All numbers eventually get sorted into one of six categories.
Almost all numbers (97.6%) end up in the same category, proving the system is highly structured and not random.

It's like realizing that while the traffic in a city looks chaotic, if you look at the right map, you see that 98% of the cars are actually taking the exact same highway to the same exit. This gives mathematicians a much clearer path to finding the solution.

1. Problem Statement

The paper addresses the Collatz Conjecture (the $3n+1$ problem), which posits that for any positive integer $n$ , the trajectory generated by the map $C(n)$ (dividing by 2 if even, $3n+1$ if odd) eventually reaches the value 1 (or a power of 2). Despite extensive computational verification and partial theoretical results (e.g., Tao's logarithmic density result), a general proof remains elusive.

The author's approach shifts focus from direct proof to structural decomposition. The goal is to analyze the path sequences of Collatz trajectories by classifying integers into specific residue classes and modeling their evolution as a deterministic Finite State Machine (FSM).

2. Methodology

The paper employs a multi-step analytical framework:

Modular Reduction: The set of natural numbers $\mathbb{N}$ is partitioned into four residue classes modulo 4 ( $A, B, C, D$ ). The author proves that classes $A, B,$ and $D$ are "descent" classes (they map to smaller integers in a fixed number of steps), reducing the core difficulty of the conjecture entirely to Class C ( $n \equiv 3 \pmod 4$ ).
Recurrent Forms (Modulo 9): For Class C numbers, the author identifies that after a specific sequence of Collatz operations, the trajectory enters one of six "recurrent forms" defined by residues modulo 9:
- $a: 9n+8$
- $b: 9n+4$
- $c: 9n+2$
- $d: 9n+1$
- $e: 9n+5$
- $f: 9n+7$
  These forms correspond to residues coprime to 3, which is necessary for the trajectory to eventually reach a power of 2.
Finite State Machine (FSM) Construction: A deterministic FSM is constructed where the states are the six recurrent forms. The transitions between states are governed by the parity of the internal parameter $n$ and specific sequences of Collatz operations ( $E$ for even, $O$ for odd).
Functional Equations: The FSM transitions are translated into a system of coupled functional equations describing how the parameter $n$ evolves within each state.
Statistical Analysis: Numerical experiments were conducted on the first $10^8$ natural numbers to analyze the frequency with which trajectories terminate in specific forms.

3. Key Contributions and Theoretical Results

A. Reduction to Class C (Theorem 3.2)

The paper rigorously proves that the Collatz conjecture holds for all $n \in \mathbb{N}$ if and only if it holds for all $n \equiv 3 \pmod 4$ . This is achieved by showing that integers in classes $A, B,$ and $D$ strictly decrease under a fixed sequence of Collatz operations, whereas Class C numbers do not necessarily decrease immediately.

B. Completeness of Recurrent Forms (Theorem 4.3)

The author proves that the six recurrent forms partition the set of powers of 2. Specifically, powers of 2 cycle through these forms with a period of 6 based on their residue modulo 9:

$2^{6j} \to$ Form $d$ (residue 1)
$2^{6j+1} \to$ Form $c$ (residue 2)
$2^{6j+2} \to$ Form $b$ (residue 4)
$2^{6j+3} \to$ Form $a$ (residue 8)
$2^{6j+4} \to$ Form $f$ (residue 7)
$2^{6j+5} \to$ Form $e$ (residue 5)

C. FSM Dynamics and Syracuse Equivalence (Theorems 5.1, 7.1)

The paper defines explicit transition rules for the FSM. A key finding is the equivalence between the self-transition of form $a$ (when the parameter is odd) and the Syracuse map (the accelerated Collatz map). The FSM decomposes the Syracuse map into a multi-step process where the 2-adic valuation determines the path length through intermediate forms.

D. Closed-Form Characterizations (Theorem 8.1)

For three of the six forms ( $b, d, f$ ), the paper provides closed-form characterizations of the powers of 2 that terminate in these classes. These sets are shown to be sparse, consisting of specific arithmetic progressions of exponents (e.g., $2^{6j+2}$ for form $b$ ).

E. Statistical Bias (Observation 10.2 & Conjecture 10.4)

Numerical experiments reveal a massive statistical bias in the distribution of terminating forms:

Form $a$ ( $9n+8$ ) accounts for approximately 97.6% of all terminations.
Form $c$ ( $9n+2$ ) accounts for approximately 2.4%.
Forms $b, d, e, f$ have vanishing frequencies ( $O(1/N)$ or $O(\log N/N)$ ) as $N \to \infty$ .

This contradicts the hypothesis of random parity distribution (which would predict a uniform $1/6$ distribution), suggesting the Collatz dynamics possess deep deterministic structure.

4. Reformulation of the Conjecture

The paper reformulates the Collatz conjecture as a covering problem (Theorem 9.2). The conjecture is equivalent to the statement that the union of the reachability sets of the six forms covers all natural numbers:
$N_a \cup N_b \cup N_c \cup N_d \cup N_e \cup N_f = \mathbb{N}$
Furthermore, it is equivalent to proving that the system of coupled functional equations (16–21) forces the parameter sequence to eventually satisfy a condition where the current form equals a power of 2.

5. Significance and Open Questions

Significance:

Structural Insight: The paper moves beyond probabilistic arguments to provide a rigid algebraic and combinatorial framework (FSM) for the Collatz problem.
Non-Randomness: The discovery of the 97.6% bias in form $a$ challenges the "random walk" intuition often applied to the $3n+1$ problem, highlighting strong deterministic constraints.
Reduction: By isolating Class C and the six recurrent forms, the problem space is significantly narrowed and structured.

Open Questions (Section 11):
The author formulates several open problems, including:

Covering Property: Can the functional equations be proven to always reach a power-of-2 condition?
Closed Forms for $a$ and $c$ : Unlike $b, d, f$ , forms $a$ and $c$ lack simple closed-form descriptions for their termination sets.
Asymptotic Constant: Can the constant $\alpha \approx 0.9762$ be expressed analytically (e.g., involving $\log 2$ and $\log 3$ )?
Lyapunov Function: Can a strictly decreasing function be found for non-terminating trajectories?
Cycle Exclusion: Can the FSM expansion ratios be used to prove the non-existence of non-trivial cycles?

Conclusion

Sawon Pratiher's paper offers a novel decomposition of the Collatz conjecture into a finite state system governed by modular arithmetic. By proving the completeness of six recurrent forms and demonstrating a profound statistical bias toward form $a$ , the work provides a new lens through which to view the problem, suggesting that the solution lies in understanding the specific covering properties of the resulting coupled functional equations rather than treating the sequence as a stochastic process.