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.
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