Göbel = Matula Numbering. (Neé: Riffs & Rotes & A061396)

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

some incidental remarks on riffs & rotes,
from the standpoint of ordered domains.

suppose that we don't know anything at all about the number theory connection,
but are simply given a species of trees defined by the following recursion:

| @ is a rote.
|
| if f is a finite function from rotes to rotes,
| say, f : index_j ~> exponent_j for j = 1 to k,
| where the "indices" and "exponents" are rotes,
| then the following tree is a rote:
|
|  i_1  e_1  i_k  e_k
|   o----o    o----o
|    \  ...  /
|     \  |  /
|      \ | /
|       \|/
|        @
|
| where the rotes for the "indices" (source elements) i_j
| and the "exponents" (target elemnts) e_j are attached
| at the places indicated.

so the question is, what is a natural way of partial ordering this species?
then, can we specify enough information to make it a total linear ordering?

jon awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

AK = Antti Karttunen
JA = Jon Awbrey

JA: | F. Göbel,
    | "On a 1-1-Correspondence between Rooted Trees and Natural Numbers",
    | 'Journal of Combinatorial Theory', B29 (1980), pages 141-143.

JA: This correspondence is associated in one way or another
    with the following sequences in the EIS online database:

    A005517, A005518, A007097, A057452.

JA: In 1980, we find the above paper published,
    giving a correspondence between rooted trees
    and natural numbers that is dual, in a sense,
    to the one that I gave between natural numbers
    and planted plane trees.  In summary, we have:

    1.  Recur on Index : N <-> Rooted Trees
    2.  Recur on Power : N <-  Planted Plane Trees
    3.  Recur on Both  : N  -> Riffs <-> Rotes

JA: As given, the 2nd mapping is many-to-one and onto
    from planted plane trees to natural numbers, but
    there is a way to make the 2nd mapping injective,
    at least, I have an old note that claims this,
    but I will need to read it over again first,
    as I'm not as sure as I used to be about it.

JA: I also notice that Göbel's paper is
    given as "Received June 26, 1978",
    so I begin to suspect that there
    must have been something in the
    air (or the water) that year.

JA: Here is a cartoon synopsis of how Göbel's numbering goes:

    ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
    |
    |   1     blank               blank
    |   2     p_1                 ()
    |   3     p_(p_1)             (())
    |   4     p_1^2               ()()
    |   5     p_(p_(p_1))         ((()))
    |   6     p_1 p_(p_1)         ()(())
    |   7     p_(p_1^2)           (()())
    |   8     p_1^3               ()()()
    |   9     p_(p_1)^2           (())(())
    |  10     p_1 p_(p_(p_1))     ()((()))
    |
    | ...
    |
    ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
    |
    |                          o
    |                          |
    |              o           o       o o   o
    |              |           |       |  \ /
    |        o     o   o   o   o   o   o   o   o o o
    |        |     |    \ /    |    \ /    |    \|/
    |  @     @     @     @     @     @     @     @
    |
    |  1     2     3     4     5     6     7     8   ...
    |
    ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

AK: Something in the air ten years earlier ?

    | D.W. Matula, Washington University, St. Louis, Missouri.
    | A Natural Rooted Tree Enumeration by Prime Factorization.
    | SIAM Rev. 10 (1968), p. 273.
    |
    | A one-to-one correspondence between the space of rooted
    | trees and the positive integers is given by the following
    | recursive procedure. Let the positive integer n correspond
    | to the root node of a tree, the prime factors of n
    | (each occurring as often as its multiplicity) correspond
    | to the edges incident to the root node, and for each such
    | edge incident to the root which corresponds to the prime p
    | let the branch of the tree incident to that edge be the
    | rooted tree corresponding to the number pi(p) (the prime
    | number function pi). The terminal condition of this
    | recursion arises quite naturally as unity (which has no
    | prime factors) is thus associated with each pendent vertex.
    | On the other hand, the number associated with a given
    | rooted tree may be recursively determined as follows:
    | If the numbers associated with the branches of a rooted
    | tree T are n1, n2, ..., nm, then the unique number
    | associated with T is the product p(n1) x p(n2) x ... x p(nm),
    | where p(ni) is the ni:th prime. Certain interesting
    | relationships between the theories of primes and trees
    | will be developed utilizing this "natural" correspondence.

AK: Compare with the beginning of Göbel's paper:

    | In the sequel, we suppose that p(1) = 2, p(2), p(3), ...
    | is the sequence of primes in ascending order.
    | Let T be a rooted tree, r its root. The connected components
    | of T - r are denoted by T1, ..., Tv, where v is the degree
    | of r. The graphs Tj (j = 1,...,v) obviously are trees, which
    | we transform into rooted trees by defining as the the root
    | of Tj the vertex of Tj which is adjacent to r in T. We now
    | assign a natural number phi(T) to the rooted tree T.
    |
    | Definition. If T has only one vertex, then phi(T) = 1.
    | If the number of vertices of T is greater than 1, then
    |
    | phi(T) = product_{i=1..v} p(phi(Ti)),
    |
    | where T1, ..., Tv are the rooted trees defined above.
    |
    | ...

AK: There's at least one on-line document about Matula-numbers:

    | Ivan Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers,
    | Publications de L'institut Mathématique (Beograd), Vol. 53(67), pp. 17-22 (1993).
    | URL: http://www.emis.de/journals/PIMB/067/n067p017.pdf

AK: It would be nice to compute the functions f1 - f10
    (corresponding to the properties P1 - P10) defined in that paper.
    I don't know how much you can find connections from there to the
    classical elementary number theory, but as a simple example, the
    degree of the rooted tree with Matula/Göbel number n is bigomega(n),
    (A001222), and "the primeth recurrence" A007097 gives the trees with
    just one leaf.

AK: Now, I started thinking why we must use specifically the ordinary primes.
    Why not use instead the binary encoding of irreducible Z2[x] polynomials, i.e.
    A014580 (2,3,7,11,13,19,25,31,...) instead of A000040 (2,3,5,7,11,13,17,19,23,...)
    as the function 'p' in the above definition given by Göbel?  Of course then we
    should use the carryless Z2[x] multiplication instead of the ordinary one,
    to acquire a one-to-one map.

AK: So, 5 = 101 in binary (corresponding to x^2 + 1 = x+1 * x+1 in Z2[X])
    corresponds now to the tree:

      \  /
       \/

    which in original Matula/Göbel scheme is associated with the number 9.
    (Deducing the properties of the trees using this scheme might be
    slightly easier than with the original one?)

AK: Combining the mapping N <-> rooted trees, and rooted trees <-> Z2[x] polynomials we
    obtain a map between the multiplicative semigroup (or specifically: commutative monoid)
    of natural numbers and the multiplicative semigroup found in the ring of Z2[x] polynomials.
    Let's call it khi.  Unless I'm completely zombie, it obeys

    khi(1)  = 1

    and

    khi(ab) = khi(a) X khi(b)

AK: where X means multiplication of Z2[x] polynomials,
    so it is a homomorphism between these semigroups.

AK: Using the standard binary encoding of Z2[x]
    polynomials we can represent it in OEIS as
    yet another permutation of natural numbers.
    Among other things, it maps A000040 and A014580
    term-by-term to each other.

AK: (How does it map the corresponding multiplication tables
     A004247 and A048720 to each other?)

AK: Then we can get even wilder, because any domain
    with unique factorization can be used, so why not to
    use, say Gaussian integers, or some other "double ring"?
    I remember that Marc spoke some months ago about storing
    these ones to OEIS with the "bits-interleaved" method.

JA: i will see if i can find the references later, but i remember
    neil or maybe nordhaus telling me about some similar ideas
    that a.a. mullin (?) called 'mosaics', some of which got
    published in the nat.acad.sci., and i think that there
    were related constructions going back to a goodstein
    or goldstein in the 20's, also some connections to
    mirimanoff.  all very fuzzy now.

JA: my initial interest in riffs and rotes came out of a search for
    "auto-documenting data structures" and "self-tagging molecules",
    plus links between additive and multiplicative number theory that
    i associated with the question:  "how much of the ordering of the
    integers is purely combinatorial", whatever that means.  so, yes,
    some flavor of generalized primes comes into play -- if you ask:

JA: is there a "purely combinatorical" reason that (p_2)^1 < (p_1)^2?

JA: viewed as rotes:
 
|    o---o                 o---o
|    |                     |
|    o---o             o---o
|    |                 |
|    @         <?<     @
|
|   (p_2)^1    <?<    (p_1)^2

JA: fun & games ...

JA: links here to dana scott's d_infinity and similar constructions.

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o