I was somewhat recently introduced to the Matula-Goebel bijection between rooted trees and natural numbers. (nicely illustrated here http://keithbriggs.info/matula.html) Looking through them, I noticed that smaller integers were repeated as 'terminal subtrees' more often, which led me to wonder whether the MG numbering actually provided a perfect index of how frequently a given rooted tree would appear as such in the set of ALL rooted trees. I already knew that Schenk's Theorem implied that any (rooted) subtree would eventually occur in almost all (rooted) trees, and thus have asymptotic density of 1, but perhaps some subtrees raced to that density reliably faster than others?

To find the set of trees containing our subtree of interest, we start with a set containing only the integer representing that subtree.

  1. for every n in the set, find the nth prime.
  2. add all multiples of this prime to the set.
  3. goto 1

It seems entirely believable that the asymptotic density of all such sets must be 1 regardless of the starting integer...but larger starting n consistently have larger gaps in the final sequence. For two sets starting from different n, clearly there were at most a finite number of x for which the member counts of each set

Great! ...except there are infinitely many other bijections which construct a contradictory ordering.

Nowhere in the definition of the MG bijection is addition used, only multiplication and ordinal comparison on the set of primes...so taking a page from Beurling's generalized integers, there's no reason we can't use a different list of primes when building the tree bijection, provided they still produce unique factorizations. Let's keep things simple and just remove 2, so we can easily map the resulting odd integers back to (x+1)/2. (unsurprisingly I wasn't the first to think of this, see OEIS A048673)

so instead of 1,p1,p2,p1^2,p3,p1p2,p4,p1^3,p2^2,p1p3,p5...

we now have 1,p1,p2,p3,p1^2,p4,p5,p1p2,p6,p7,p1p3,p8,p2^2,p1^3...

which will clearly put the trees in a different ordering. But even using a different list of primes (and being careful how to interpret 'multiiples'), following the same reasoning would seem to require that this new ordering would also yield strictly decreasing 'densities' in the resulting sets. The pairs reversed by this permutation of the trees cannot both exceed the other's frequency, so I'm guessing I proverbially divided by zero somewhere above.

To further deepen the confusion, or perhaps provide a direction toward resolution, a closer reading of Schenk (or at least people quoting him on this side of the paywall) seems to indicate that the number of trees containing a particular 'limb' depends only on the limb's size, not its internal structure, which would seem to make any such ordering within a given tree size dubious, and orderings placing larger trees before smaller (ie 18<19) doubly so.

So, to bring that all into a proper question or two:

  1. Is there an intrinsic meaning to the MG ordering applicable in the domain of rooted trees without reference to the multiplicative structure of the integers? (or perhaps some other well-ordering of them is more useful/meaningful?)

  2. I understand that bijections between infinite sets can yield rampant paradoxes if not handled with sufficient care...is this just another one, or have I committed a serious logical error in the above?

Thanks in advance...



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.