CollatzLIS

Longest increasing subsequences of Collatz trajectories: a null model decomposition.

We study the LIS of Collatz trajectories as a quantitative probe of pseudorandomness. The mean ratio LIS/2sqrt(k) is 0.567 at N=10^6, significantly below the 0.812 random baseline. A hierarchy of null models decomposes the deviation: the 31.6% up-step fraction and the long descending suffix account for most of the gap, with a residual of ~0.05 beyond matched stochastic models.

Key results

Prerequisites

• Python 3.11+
• No external dependencies (standard library only)

Run

# Main experiment suite (scaling, parameter sensitivity, structural analysis)
python src/collatz_lis.py

# Validation suite (correctness, null models, trajectory correlation, convergence)
python src/validate.py

The main experiment runs scaling from N=1,000 to N=1,000,000 and takes several minutes at the largest scale. The validation suite runs five independent checks and takes approximately 5-10 minutes.

Project structure

src/
  collatz_lis.py      # Main experiment suite (5 experiments)
                      #   1. Scaling (N=1k to 1M)
                      #   2. Parameter sensitivity (3n+b family)
                      #   3. Bootstrap statistics
                      #   4. Structural analysis (directionality, peak, runs)
                      #   5. Random baseline control
  validate.py         # Validation suite (5 validations)
                      #   V1. LIS algorithm correctness (brute-force check)
                      #   V2. Null model comparison (5 models)
                      #   V3. Trajectory correlation (suffix sharing)
                      #   V4. Convergence modeling (3 functional forms)
                      #   V5. Autocorrelation analysis (Bernoulli/Markov)

data/
  experiment_results.md     # Detailed findings from experiment suite
  validation_results.md     # Validation findings with corrections

paper/
  paper.tex                 # Manuscript (LaTeX, article class)

The null model hierarchy

The central methodological contribution is a hierarchy of stochastic models, each capturing one additional structural property of Collatz trajectories:

Null model comparisons at N=50,000. Scaling experiments (Table 1 in the paper) extend to N=10^6.

Validated claims

Known limitations

• Trajectory correlation: 97.4% shared suffixes reduce effective sample size to ~500, widening bootstrap CIs by ~6x
• Convergence not settled: models disagree on asymptotic limit (0.47 to 0.57); N>10^8 needed
• No analytical derivation: all results are empirical
• Prefix-only ratio is near-normal (0.853): the low full ratio is primarily a suffix effect

References

• Baik, Deift, Johansson (1999). On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12, 1119-1178.
• Lagarias (1985). The 3x+1 problem and its generalizations. Amer. Math. Monthly 92, 3-23.
• Tao (2022). Almost all orbits of the Collatz map attain almost bounded values. Forum of Mathematics, Pi 10, e12.
• Aldous, Diaconis (1999). Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. 36, 413-432.

License

MIT