Two Counter-Example Graphs

This first communicaton was received in early June 2005 from a correspondent who wishes to remain anonymous.  I post it essentially verbatim with his permission.  I am indebted to him for identifying a major omission in the original version of this essential piece of my proof.


"On page http://www-personal.ksu.edu/~kconrow/august.html it says:

   Proposed Th.:Given a collection of labelled nodes of degree 3 with directed edges and
      (1) one outgoing edge and two incoming edges for every node, and
      (2) every node uniquely labelled with an odd positive integer, and
      (3) one unique node whose outgoing edge loops back to itself, and
      (4) no restrictions arise to limit the growth of the graph,
   then the only graph which can be formed is a directed binary tree.

"This proposed theorem is incorrect.  The following picture gives a counter example:

"In this graph, all four conditions hold,  yet the graph is not a single binary tree.  This shows that those four conditions are not sufficient to ensure the graph is a binary tree.  So the proposed theorem is not true.

"Notice that if you start at 1 or somewhere in the red tree,  you'll eventually reach 1.  But if you start anywhere else in the graph,  then you'll eventually reach a yellow node,  and will then move forever to the right,  and will never reach 1.

"The numbers in the graph are as follows.  The yellow nodes are labelled with 2n-1 for all positive n.  The red nodes are 4n+1.  The green are 8n+3.   The blue are 16n+7.  The magenta are 32n+15.  The gray are 64n+31.  The brown are 128n+63.  This pattern continues forever to the right,  with the mth tree having all possible labels of the form 2m+1n+2m-1.

"There are simpler counter examples which have cycles,  but it's perhaps more interesting to see this acyclic counter example."



My response to the above communication was to add two additional conditions to the proposed theorem to tie the Collatz tree structure more closely to the statement of the theorem in order to exclude constructed counter examples like that above.


The same correspondent in early June 2007 provided this second example in reference to section 1.3 of The Structure of the Collatz Trajectories....

"Imagine that I've created an infinite tree with different odd integers at each node.  The tree is made up of an infinite number of pieces.  The first piece has nodes whose numbers are the set 5[6].  The next piece has the nodes with numbers {7,13,15}[18].   The first 6 pieces of the tree are these sets:

{5}[6]     density=2*1/6
{7,13,15}[18]     density=2*3/18
{19,21,37,39,45}[54]     density=2*5/54
{55,57,63,109,111,117,135}[162]     density=2*7/162
{163,165,171,189,325,327,333,351,405}[486]     density=2*9/486
{487,489,495,513,567,973,975,981,999,1053,1215}[1458]     density=2*11/1458
...

"This continues forever.   So the tree is made up of an infinite number of sets,  each of which contains an infinite number of odd numbers.   We're constructing this tree by starting with a boneyard universe of all the odd numbers,  and then we keep whacking at it without loss.   We might expect that it would include all the odd numbers.

"For each set above,  the modulus [d] is 3 times the modulus of the line before it.   The numbers in braces are chosen such that the set will include all the odd numbers possible that haven't been included by any set above it,  and which don't include any power of 3.  In other words, none of the sets will ever include any of the numbers {1, 3, 9, 27, 81, 3^5, 3^6, 3^7, ...}.

"The density of each set is a fraction,  where the denominator is the previous denominator times 3,  and the numerator is the previous numerator plus 4.

"In other words,  the density of the nth set is (4*n-2)/(2*3^n).  If you take the sum of that fraction as n goes from 1 to infinity,  the densities add up to 1.   Not just close to 1.  Exactly 1.   Mathematica found that result using symbolic math,  so there's no possibility of roundoff error.

"So these are disjoint sets of odd numbers whose densities add up to 1.   But they don't include any powers of 3.  Even though their densities add up to 1,  there are still infinitely many odd numbers that are hiding in a rat hole outside the tree.   The numbers in the rat hole are {1,3,9,27,81,...}.  Yet the densities in the tree sum to 1.

"How is that possible?   It's possible because the numbers in the rat hole have a density of  0.  Just because they have a density of zero, doesn't mean they don't exist!

"That's the problem.   If the sum of the densities is 1,  that doesn't guarantee that the rat hole is empty.  It just guarantees that the rat hole has a density of   0.  But it can still contain an infinite number of "left out" odd numbers.   Even infinite sets can have a density of  0.

"For infinite sets of sets,  we can never use arguments based on densities to prove that we've caught all the odd numbers.   It's mathematically impossible."


My response to this second communication was to elaborate the point that the abstract predecessor tree starts out containing all the odd positive integers {union({1[8]}, 3{[8]}, {5[8]}, and {[8]})} and that its elaboration does not permit the loss  (or insertion, either)  of any integers from that original comprehensive set.  Ths change appears near the end of section 1.2 of The Structure of the Collatz Trajectories....

It is interesting that the counter-example constructed by this correspondent was chosen as if the set of powers of 3 were omitted from the otherwise complete infinite set of odd integers.  But all the integers in {0[3]} are specifically included in the Collatz predecessor tree as leaf nodes in the left descent assemblies.   No more unfortunate choice of properties for a zero density set could have been chosen.   But,  since the entire set of odd positive integers is included in the abstract tree,  there is no set of properties which can be selected which represents integers from which to construct this sort of counter example. The counter example is instructive,  but not applicable to the Collatz predecessor tree.

I appreciate the help of this correspondent in increasing the precision of my presentation.