Ken Conrow Home Page

Collatz 3n+1 Problem Structure

Mathematicians who refer to the problem as the 3x+1 problem were never brainwashed by FORTRAN (as I was)  into the belief that n,  not x,  stands for an integer.

This work has been ongoing for several years, and fragments of earlier approaches appear on these pages. An attempt has been made to label these fragments, and they are referenced among the later entries of the table of contents, below.

Currently, I've obtained a detailed mapping of the residue sets which constitute the abstract Collatz predecessor tree.  Systematic features of this structure permit development of formulas whose infinite summation indicates the presence of all the odd positive integers therein.  The recursive program which develops details of this structure starting from the root node {5[8]} is effectively an inductive/constructive proof of the Collatz conjecture.  An image of a paper representing this approach to a proof is available.

I hope someone who can formalize mathematical proofs will see the potential here and take the appropriate set of ideas and sketch or complete a formal proof of the conjecture using them.

You may communicate with me by e-mail at kconrow@ksu.edu.  Reports of errors and constructive comments will be particularly welcome.

Ideas Basic to the Structural View of the Collatz Graph

3n+1 Problem Statement and References
3n+1 Predecessor Tree,  Three Views
        The notion of a predecessor tree and details of the general,  binary,  and abstract versions of the predecessor tree are presented.
Glossary of Terms Used

Numerical Elaboration of the Trees

Development of Contents of Left Descent Nodes
        Hand-made examples show the method of developing successive predecessor sets during elaboration of the abstract predecessor tree.

Maple Programs

Descriptions and References
               A brief guide to Maple programs which support the abstract predecessor tree gestalt.
               The following items are repeated therein with a little more description.
        Program Treegrow -- Tracing the Left Descent Assemblies in the Abstract Tree
               Treegrow produces every element of every left descent assembly up to a user specified limit.
        Program Rsetprog -- Construction of the Abstract Predecessor Tree
                Rsetprog, similar to treegrow, but using residue sets, informs proof of the Collatz conjecture.
        Program Nbigpath -- Generating the General Predecessor Tree
                Excepting time and space imitations, Nbigpath generates the entire infinite predecessor tree as a general tree.
        Algorithm Idit -- Locating an Arbitrary Integer in the Abstract Predecessor Tree
                An algorithm is presented for identifying the l.d.a. which contains an arbitrary odd integer
        Program IDtheLDA -- Characterization of the l.d.a. for an Arbitrary Integer
                IDtheLDA calculates the l.d.a.(and its instance) an arbitrary odd integer appears in. .
        Program Fullmap -- Mapping the trajectory from any Arbitrary Odd Integer to 1:
                Fullmap traces the detailed path from an arbitrary odd integer to 1 through its series of l.d.a.s

Big Programs Yielding Big Results or Big Fun

Producing "Designer" Path Segments
        Less ambitious than nbigpath, two programs work together to accept a specification of an arbitrary left descent assembly and produce, then plot, the Collatz trajectory embodying the requested path.
Some of the Plots of "Designer" Paths are "Works of Art"
        Though not useful in pursuit of a proof, there is clearly an open field here for producing computer art.

Pages Concerned with Proof Elements

Positive Features of this Work
        What insights/viewpoints distinguish this work from others?
Brief Overview of Logical Connections in this Web Site and Proof
Proof Develops from the Abstract Predecessor Tree Properties
        A relatively brief overview is given of the proof to be presented in these pages.
Comparison of Binary Tree Requirements with the Graph-Forming Capabilities of L.d.a.s for the (3n+1)/2i Iteration
        It is argued from a table of properties that the individual nodes within the binary predecessor tree are incapable of forming any graph other than a binary tree.
Argument via Construction of a Binary Tree
        The individual nodes in the binary predecessor tree have properties which can produce only a binary tree.
Concise Statement of Arguments Leading to a Proof.
        This repeats four major components of the previous 10 pages selected because they seem most cogent to a proof of the Collatz conjecture.  Readers who already know nearly everything are advised to start here.
Set Densities From Finite Left Descent Assembly Element Sets
        The proposition that the sets being summed in the cardinality table represent sums determined from densities measured in finite sets is explored thoroughly.
Behavior of Powers of 2 and 3 in (2a*3b*n+c)/2i in Extended Paths
        This gives a numeric argument for the directed nature of the Collatz graph.
Mapping the Odd Integers>1,  the Trees,  and the List of Left Descent Assemblies Into One Another
        Only mapping the members of a set of  left descent assemblies from the abstract predecessor tree into their respective positions in the binary predecessor tree is lacking.
Two Paradoxes Encountered
       One paradox notes different estimates of the odd/even ratio of the integers in the Collatz predecessor tree. The other notes that left descent assemblies should lead to higher numbers on average, contrary to fact.  Actually,  neither is a paradox;  both are explained in detail.
Metrics of Infinity
        Can it be that using densities as a metric and recognizing that the Collatz itineraries involve only integers avoids many traps otherwise encountered when considering infinite sets?
Approaches to Dealing with the Infinity Problem in the 3n+1 Conjecture
    Here's a listing of various approaches to solving the infinity problem with references to other sections of this work and some discussion.
Several Arguments Toward a Proof
       Several arguments are presented side by side for easy comparison.
Why an Arithmetic Argument Fails; Why Twins (etc.) Arise
        Subsets of integers arising in the stepwise development of the abstract tree have overlapping magnitudes. The proof that these subsets are all disjoint requires a more sophisticated argument.

Alternative Proof Involving A State Transition Diagram

An example of the trajectory of a long left descent assembly as seen using the state transition diagram is provided.
State Transition Diagram for Steps Within One Left Descent Assembly
        The allowed transitions within left descents are detailed in support of the elaboration of the abstract predecessor tree and the consequent left descent assemblies.
Details of the Path Within State Transition Diagram for Left Descent to 27
        An transition diagram is provided.
State Transition Diagram for Multiple Chained Left Descent Assemblies
        An attempt is made to show how sequential transitions from left descent assembly to extension to l.d.a to extension .... are supported by the allowed individual transitions.
Early Proof Attempt Based on State Diagrams
       This early proof attempt depends only on the state transition diagram and the graph forming properties of the l.d.a. graphical elements. Much of the content is repetitious to the current work.
Observational Development of Integer Sieve for 3n+1 Conjecture
        Computer runs give results suggesting that the left descent assemblies constitute a sieve which covers the odd positive integers.
A Priori Sieve for the Odd Integers >1 Using the 3n+1 World View
        A method for using the predecessor tree's structural features (left descent assemblies and extensions) to generate a sieve for the odd integers is described.

All Left Descent Subset Formulas Represent Disjoint Sets
        It is pointed out that the method of construction of formulas of left descent assembly set members results entirely in disjoint subsets.
Proofs of Some Little Pieces of the Structure
       A very few oddments,   here and there,   are given proofs.

Minor Points not in Direct Line to the Structure of the Collatz Graph

Ancillary Related Topics

Infinite Sums over the Abstract Predecessor Tree and the Table of Cardinalities
        Summation of the densities of the sets of integers identified in all the left descent assemblies provides for the totality of the integers.
Finite Sums in the Cardinality Table
        The sums of the densities of the sets of integers represented in larger and larger samples of left descent assemblies approaches the totality of the integers more and more closely.
Limits to Conclusions Drawn from the State Transition Diagram
        It has been suggested that the state transition diagram is less than omnipotent in its support of left descent assemblies and the abstract predecessor tree.
What is Dull (Interesting?) About the Extensions?
        The extension sets are tightly interleaving progressions to infinity such that every odd integer can at length be found among them.

A Few Numeric Observations: Some Useful; Some Historic

Synopsis/Abstract as of ca. 2005
Maple Provides the Clue in the Left Descent to 27     
This was the discovery event (AHAH!) for this whole work.
Numeric Residue Set Values for the Descent from 445 to 27
     Detailed exposition of the residue set descent to 27; offers a contrast to the immediately preceding index entry.
Showing Complete Paths and the Huge Scatter in the Instances of a Given Left Descent Assembly
    A single example of complete paths developed from a single terminating left descent assembly.
Shortcut to Numeric Values of the Coefficients in the dn+c Formulas
        It is just a matter of knowing the number of steps in the left descent assembly and the sum of the i's in the successive (3n+1)/2^i steps.
Picture of Integer Filling Through 3 Generations of Left Descent Assemblies
        Also referred to as the bedroom wallpaper picture.
Extensions Do Pass Some (Limited) Control
        A first hint arose here that certain patterns of development of the predecessor tree are propagated through iteration sequences which include extensions.

Feinstein's Proof that Collatz's Conjecture Can't be Proven

Representation of Trajectories
       Using the symbols {s,b,e} to denote fragments of the paths in the binary predecessor tree and encoding those as {'10','11','0'} achieves a shorter bit string representation of a path than the parity bit string.   Naively, at least, this undercuts the thesis of Feinstein's proof.
Infinite Steps or Infinite Sums -- Which Is More Convincing?
        The various threads of the arguments introduced in the above pages are pulled together not only to argue that Feinstein's proof of the unprovability of the Collatz conjecture is incorrect, but also that this work provides such a proof.

Various Analogs, (an+b)/2^i, to the Collatz trajectories

Scaling in the Collatz Itineraries
        E-Mail from Oleg developing scaling transformations to form a more general (3n+3k)/2i family of analogs.
Converging Sequences:(3n+3j)/2i
        Some quick diagnostic tests,  state transition diagrams,  and samples of  the predecessor trees for these analogs are presented.
Comparison of Behaviors of Members of the (3n+3j/2i Family
        A table detailing the differences in features of the analogous (3n+3j)/2i family members as j is varied is provided.
Observations within the (3n+3j)/2i Family
        The retention of powers of  3 in segments of the itineraries and the appearance of   left descent assemblies among these trees is noted.
Analogs of Collatz Sequences which Fail to Converge to an Integer
        We look at cases of (ax+b)/2^i where a is not 3 and/or b is not 1).
Diverging Trajectories from (5n+1)/2i
        This is the case which made everyone apprehensive that the Collatz trajectories might include one or more divergent ones.

>Justification of Viewpoints

        In communication with several interested investigators, situations have arisen in which we have had difficulty exchanging ideas because of different basic assumptions made early in our independent investigations.  These differences are discussed and mutually justified.

Junk(?) or Outdated(?)

Slide Show
If you want a quick trip through my work,  look at a somewhat outdated (from 2005 or so) 24 slide show,  either serially or through an index,  which contains a few pointers to illustrative material.  Always use your browser's back button to return to the slide show if you look at this auxiliary material.

Now in May/June, 2006, I'm trying to streamline, condense, improve the organization of the components, etc.  I'll try to do so without worsening the already dense and sometimes confused presentation.  I've made a new attempt to produce a very concise presentation of the main arguments I believe will produce a proof of the Collatz conjecture.
A draft paper (in February 2007) giving the abstract predecessor structure but prior to recognition of the duplication of integers among the resdiue sets. A more recent (after the duplication of integers in resitue sets was realized) simplified version of the proof is also provided. This contains many detailes elided from the current paper.

Pictures, Diagrams, Tables

Most of these are referenced somewhere from the text.
(3n+1)/2^i Predecessor Tree as a General Tree
(3n+1)/2^i Predecessor Tree as a Binary Tree
Collatz Graph Nodes and Edges in Isolation
Collatz Graph nodes and Edges in Binary Predecessor Tree Context
Abstract (3n+1)/2^i Predecessor Tree Defined Iteratively
State Transition Diagram within Left Descent Assemblies
State Transition Diagram for Multiple Chained Left Descent Assemblies
State Transition Table for the (5n+1)/2i Case Analog
State Transition Diagram for Predecessors in the (5n+1)/2i Case Analog
State Transition Diagram for the (3n+3)/2i Case Analog
Binary Predecessor Tree for the (3n+3)/2i Case Analog
State transition diagram for Successors in the (5n+1)/2i Case Analog
State Transition Diagram for the (3n+3^j)/2i Analog
Predecessor Tree (as a General Tree) for (3*n+3j)/2i (with j=12)
Abstract Predecessor Tree,  3 Levels,  With Set Names
Abstract Tree for Paths
Stepwise Downward Development of Set Contents in Abstract Predecessor Tree
Stepwise Upward Development of Subset Contents in Abstract Predecessor Tree
Subsets Nested to Show Progressive Diminution of Unresolved Extension Elements
Table of Cardinalities of Subsets Sharing {a,b} in Abstract Predecessor Tree
Cumulative Filling of the Integers, Fibonacci-Wise
Location of  Left Descent Assemblies of Zero to Three Steps in the Cardinality Table
Location of Two Lengthy Left Descent Assemblies, and Scope of  Left Descent Assemblies of Those Lengths in the Cardinality Table
Diagram of Integer Coverage by Growth of the Abstract Predecessor Tree
Diagram of Integer Coverage by Growth in the Cardinality Table
Relationship of Pascal Triangle to Fibonacci Numbers
Sample Characterization of Arbitrary Integer in Abstract Predecessor Tree
Listing of Extensions for Left Descent Assemblies<=100061
Several Examples of Complete Left Descent Assemblies
Predecessor Tree for (3n+36)/2i

I will modify or add to these pages from time to time as I get feedback from readers or make new discoveries myself.

Let me emphasize that I know no proof with adequate mathematical rigor exists here.  That is why I've put these pages up.  I hope I'm writing this well enough both to attract other amateurs to the problem and to attract one or more professional mathematicians to the problem of developing a formal proof on the basis of some or all of the structure presented here.  At least it should encourage some fresh thinking.


KSU Home Page       Index to Terms Used