The Real deal, too

To clarify…

Just to make sure it is clear, let me say that the main point of the first “Real deal” is this: the discrete derivative is about transforming the entire standard Binary tree by “twisting” every other pair of branches across every row in the tree….it is about transforming the tree, about an automorphism of the tree. I say automorphism because the transformation does not result from removing branches. It results from a “twist” and as such cannot and does not result in eliminating any element from the set of resulting codes, both vertices and “leaves”. They are only reordered.

While I started the “Real deal” blog entry with a presentation of the transformation of an individual binary string, that is just the fine detail of the picture. The discrete derivative is defined by the transformation of the standard Binary tree. That transformation is effected in every row by simply reversing the order of every other pair of branches. In each row of the DD tree the first branching is always 0-1 and the last is always 1-0. After all, there is an even number of vertices in each row after the [e]. The transformation is by construction not by “logic”. The logic of the tree is IN its structure. In a very real sense Aristotelian logic is nothing more paths in a binary coded tree.

The rows in the Binary tree read”01-01-01-01-…” The branches in the DD tree read “01-10 | 01-10 | 01-10 |…” By “twisting” the branches of every other pair, row after row, the whole tree is transformed …and every binary string of 0’s and 1’s that comes from it.

By following a given path: LLRLRRLRLRRRRL… (including the infinite strings) in the Binary tree along that path we get an output string 00101101011110… (since L->0 and R->1). In the DD tree that same sequence of Left and Right moves yields a different binary string: 0 1 1 1 0 1 1 1 1 0 0 0 1…, namely the discrete derivative of the original string. Nevertheless, the focus here is on the transformation of the whole Binary tree into a whole new tree: the DD tree.

The result across a row of transforming the Binary tree into the DD tree (by construction) is a reordering of the codes across a row, and therefore a reordering of the codes associated with every vertex in the tree. But by reordering the “parents” in a row n we get a necessary reordering of their children in row n+1. The codes associated with vertices across a row in the DD tree are Gray’s coded: they differ from their neighbor on either side by exactly one bit change. Also the first and last in a row differ by exactly one bit change. This makes the whole row into a cycle of single bit changes. That structure is replicated row after row.

Now let’s apply some reasoning

Let’s examine the structure of the DD tree. Given that a row is ordered as stated above, what do we get in row n+1 from the branches of a pair of neighbors that differ by one bit change in row n? In that the branches of such a pair are either ordered 01-10 or 10-01 and those branchings append a digit at the end of the string, the “children” of that pair will be arranged in a sequence of four that differ at most by a single bit change.

If the new neighbors (in the next row) are children of the same parent they differ from each other at most by 1 bit change (they come from either a 0->1 branching or 1->0 branching). If the new neighbors (in the next row) are children of neighbors above, then because the branchings between neighbors is always 01-10 or 10-01 they will have the same binary digit appended and hence will also differ by at most one bit change just like their parents. So in one case neighbors differ in their “prefix” and in the other in their “tail”. What we get is a cross referencing of strings: first by their prefix and then by their tails. Either way the structure set by the row of two bit strings that reads 00-01-11-10 is replicated down the tree for all rows. That single alteration telescopes through the whole tree even to the “infinite” strings it defines.

Given the above observation, it is the case that even as we move on to “infinite” strings we can see that the branching of the DD tree produces an ordering that is guaranteed to have neighbors in a linear order differing by exactly one bit change.

Now consider what that means for the whole tree

For an infinite string to differ from a “neighbor” by exactly one bit change must mean that their “prefixes” are different and their “tails” are identical or that their “prefixes” are identical and their “tails” differ. Identical prefixes are the equivalence classes where the corresponding infinite continued fraction form of the numbers they correspond to coincide after a finite number of steps. Given that such prefixes correspond to rationals and can extend as far as we like (to any n’th digit), the change must occur in some n’th digit. It must occur in the “prefix” of a given infinite string. Yet the infinite strings can be gathered into equivalence classes that contain every possible finite “prefix” and the same “tail”. These equivalence classes must be arranged such that complements are on opposite sides of the tree (since that structure is set in the first 0 -1 row which is not changed by the DD restructuring) yet every class has every possible initial string in it…therefore the complementary relationship is forced into the tails. But the tails must be exactly one bit change differentiating step beyond finite, beyond what ever occurs as a finite string, beyond Q because of the parent/child connection described above. Therefore the prefix and tails (the strings) must break down into just two classes: a class associated with 0 and a class associated with 1. We get exactly two equivalence classes….equivalence classes determined by the infinitesimals a=[[00][10]] and b=[[01][00]]. They structure the whole dyadic monoid through their action as L=I+a=[[10][11]] and R=I+b=[[11][01]] where I=[[10][01]]. The fact that for any given digit half the tree must match it and the other half must have its complement while differing in only one digit (extended by the parent/child structure to the tails) extends the cyclic linear order to the infinite strings in the DD tree. That parent/child relationship is the link. Thus in the DD tree we get paths in a cyclic linear order with countability. All of the claimed complexity of the Cantor set (the “leaves” of the tree) collapses under the influence of the transformation effected by the 00,01,11,10 structure (the logic) of the DD tree. The logic inherent in the “twist” does it.

What exactly the anti-DD tree does is the focus of the next post. It too is a tree transformation, an automorphism of the Binary tree. It too has an internal “logic”, a logic given by its structure, its construction.

The 00000…string (the infinite string of 0’s) is the fixed point of the DD and anti-DD trees. It runs down the left side of all the jsatrees and is never “relocated”.