This site is supported by donations to The OEIS Foundation.
Forest Primeval
From OeisWiki
This is the latest Author: Jon Awbrey
Contents
Forest Primeval • Correspondence
Jon Awbrey to Martin Gardner • 76.08.16
page 1, typewritten
760816
Mr. Martin Gardner
Scientific American
Dear Sir:
On the following sheet find the beginnings of a correspondence
between integers and petrified trees, those so rooted and embedded
in their strata as to have a fixed order of limbs at each node.
Read blank areas as nodes, the outside being counted first, and
enclosure relations as branches. The 0 is merely an orthographic
variant for a final parenthesis, reading inward.
If this is not old news to you, maybe you would enjoy taking
it as a problem to uncover the motivation of this arrangement.
If not the time, there is a brief explanation under the stapled section
below.
Jon Awbrey
404 Michigan Ave.
East Lansing, Michigan 48823
This arrangement of trees I have dubbed "the forest primeval".
It is developed by expressing each integer in its prime factorization,
and then carrying this process to its extremes, factoring each
exponent into powers of primes, and each of these powers in turn,
quitting only when zero (or empty sets of) exponents are reached,
and given the convention that unit exponents be expressed as 2⁰.
This suggests a system of numerals with the primes in order as
place values, the place-holders being exponents instead of multipliers,
the held values being multiplied instead of added together, and with
the same multitude of place-values implied in each place.
o
/
o o o
\ / /
o o
\ /
@
|
I have therefore sometimes thought of this as a notation in which
numerals are wholly expressed by means of place-value, there being
but one symbol, whose only office is to reserve a place; but I'm
not sure how much this means, since as much might be said of simple
tally marks, with alot less complexity taken for granted.
page 2, hand written
|
|
Jon Awbrey to Martin Gardner • 78.08.04
page 1, typewritten
August 4, 1978
Martin Gardner
Scientific American
415 Madison Avenue
New York, New York
Dear Sir:
The attached short essay will update my letter of August 16, 1976
on the "forest primeval" or "petrified trees", which were just planted
plane trees with the planter omitted.
The natural correspondence of integers to trees came about
as an accidental hybrid of Gödel numbers with Zermelo's integers.
The problem of getting a one-to-one correspondence was suggested by
the various binary encodings of trees in your column of June 1976, and
was worked out later that year while reading Frazer's 'Golden Bough'.
However, the time since then has brought forth no obvious use for this
correspondence, i.e. no theorems of graph theory seem transferable to
number theory (or vice versa) by virtue of it.
As a note of possible interest connecting two of your recent columns,
Charles Peirce used Bell numbers to count the different forms of n-place
relations, giving a complicated expression and a triangular array for
calculating them; but I don't know how original these may have been
with him. See his 'Collected Papers': 3.229.
As a last incidental, Peirce's logical graphs have received
a modern echo in George Spencer-Brown's 'Laws of Form', which
accents what Peirce called the entitative interpretation of the
graphs. Spencer-Brown derives from the algebra of graphs its
arithmetic of truth values; and just as Mandelbrot is led to
fractional dimensions by a consideration of self-similar curves,
Spencer-Brown finds imaginary truth-values useful in evaluating
infinitely self-similar graphs.
Yours Truly,
Jon Awbrey
404 Michigan Ave.
East Lansing, Michigan 48823
page 2, typewritten
The forest primeval: a correspondence between natural numbers and planted plane trees.
Consider the primes factorization of a number and represent it as the sequence of its
exponents separated by parentheses, thus, N = (n_1) (n_2) (n_3) ... (n_m), ignoring
for now the all-zero exponents after some point m.
e.g.: 1 = 2^0 = (), 2 = 2^2^0 = (()), 3 = 2^0 3^2^0 = ()(())
Repeat this process with each exponent in the factorization and with each further
exponent in 'its' factorization and so on, until zero exponents are reached along
every path of development. A zero exponent, having no representation in primes,
may simply be omitted on the next pass. For example:
360 = (3)(2)(1) = ((0)(1)) ((1)) ((0)) = (()((0))) (((0))) (())
= (()(())) ((())) (())
= 2^(2^0 3^2^0) 3^2^2^0 5^2^0
Thus, parentheses suffice to represent this "involved factorization" of a number.
But they also represent planted plane trees, if we interpret the exterior space
as the planter, parenthetical containments as further edges, and contained
spaces as nodes, e.g.:
o o
| |
o o o o
\| | |
o o o
\ | /
\|/
o
|
360 = @
In this way, every number may be assigned a unique minimal tree, but
many trees will share the same number when the "insignificant digits" of
a factorization are taken into account. E.g., trees of the following form,
where an ellipsis represents an arbitrary number of terminal edges, all have
the number 360:
o … o …
|/ |/
o o … o … o …
\|/ |/ |/
o o o
\ | /
\ | /
\|/
o---…
|
@
= 2^(2^0 3^(2^0 3^0 …) 5^0 …) 3^(2^(2^0 3^0 …) 3^0 …) 5^(2^0 …) 7^0 …
The correspondence becomes one-to-one by the following transformation.
To the rightmost "offspring", when not the only offspring, of any node
of a given planted plane tree, assign an extra unit of significance:
such that, if terminal, that node represents a unit exponent; if it
is not terminal, the unit may be "inherited", but only by a singleton
offspring of that node, with a like condition entailing any further
inheritance, until a terminal node reached; otherwise, the significance
is lost. E.g., 360 is now uniquely represented by the following tree,
where primed nodes count for unit exponents under the above rule:
o
|
o o' o
\| |
o o o'
\ | /
\|/
o
|
360 = @
e.g., we now have:
o o o
| \ /
o o o
| | |
@ = () = 1, @ = (()) = 2, @ = ()() = 3
page 2, reformatted
The Forest Primeval • A Correspondence Between Natural Numbers And Planted Plane Trees
Consider the primes factorization of a positive integer and represent it as the sequence of its exponents separated by parentheses, thus, ignoring for now the all-zero exponents after some point
For example:
Repeat this process with each exponent in the factorization and with each further exponent in its factorization and so on, until zero exponents are reached along every path of development. A zero exponent, having no representation in primes, may simply be omitted on the next pass.
For example:
|
|
![{\displaystyle {\begin{array}{lll}360&=&(3)(2)(1)~=~((0)(1))~((1))~((0))~=~(()((0)))~(((0)))~(())\\[6pt]&=&(()(()))~((()))~(())\\[6pt]&=&2^{2^{0}3^{2^{0}}}3^{2^{2^{0}}}5^{2^{0}}\end{array}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b61c689a9c32bbba76a3c03e43c257678cc4f4fd)
Thus, parentheses suffice to represent this “involved factorization” of a number. But they also represent planted plane trees, if we interpret the exterior space as the planter, parenthetical containments as further edges, and contained spaces as nodes.
For example,
o o
| |
o o o o
\| | |
o o o
\ | /
\|/
o
|
360 = @
|
In this way, every number may be assigned a unique minimal tree, but many trees will share the same number when the “insignificant digits” of a factorization are taken into account.
For example, trees of the following form, where an ellipsis represents an arbitrary number of terminal edges, all have the number 360:
o … o …
|/ |/
o o … o … o …
\|/ |/ |/
o o o
\ | /
\ | /
\|/
o---…
|
@
| |
The correspondence becomes one-to-one by the following transformation. To the rightmost “offspring”, when not the only offspring, of any node of a given planted plane tree, assign an extra unit of significance: such that, if terminal, that node represents a unit exponent; if it is not terminal, the unit may be “inherited”, but only by a singleton offspring of that node, with a like condition entailing any further inheritance, until a terminal node is reached; otherwise, the significance is lost.
For example, 360 is now uniquely represented by the following tree, where primed nodes count for unit exponents under the above rule:
o
|
o o' o
\| |
o o o'
\ | /
\|/
o
|
360 = @
|
In this way, we now have:
o o o
| \ /
o o o
| | |
@ = () = 1, @ = (()) = 2, @ = ()() = 3
|
Jon Awbrey to N.J.A. Sloane • 80.08.04 {?}
hand written, 2 pages, reformatted here
|
N.J.A. Sloane Dear Mr. Sloane, I don't know of any published references to the sequence 1, 2, 6, 20, 73, 281, 1124, 4488*, … or to anything resembling riffs, but there are a few items of context I can supply. Unfortunately, I have just gone through a change of address and can't find notes or exact references on anything. I haven't worked out the sequence any further, but am returning to the problem with some fancier methods and will let you know if I have any luck. The rest of this is less immediate. Riffs came out of an investigation with several heads: either ‘number-theoretic codings of graphs’, or ‘graph-theoretic models of the integers’, or ‘measures of complexity on the integers’. From a musing together of Gödel numberings and the Zermelo–Von Neumann construction of integers, I was led to the following map of integers into planted plane trees, based on the multiplicative sequence: |
o | @ | ||||||
o | o | @ | ||||||
o
|
o o
\ /
o
|
@
| ||||||
o | o | o | @ | ||||||
o
|
o o o
\|/
o
|
@
| ||||||
o o | | o o \ / o | @ |
|
By a proper consideration of rightmost paths out of each node, this map can be changed into a one-one correspondence; but of course counting planted plane trees does not a new sequence make. I have since found that one Albert A. Mullin had already analyzed integers this way, getting patterns of primes like that he called ‘mosaics’; and in one place he mentions a graphical correspondence but gives no example. Articles of his that I can find are in Zeitschr. f. math. Logik und Grundlagen d. Mathk. Bd. 10 p. 159 and p. 199 (1964) and Notre Dame J. of Form. Logic VIII #4 p. 353 (Oct 1967). You may want to check with him to see if he knows this sequence or has got something similar to riffs. The latest address I've seen is in AMS Notices 26 #2 p. A195 (Feb 1979). Using the numbers of points in the graph of an integer as a measure of its complexity is a study related to the measures of ‘roundness’ discussed in Hardy & Wright. By way of the Zermelo–Von Neumann construction of integers (as etc.), riffs are also a multiplicative analog of Conway's surreal numbers and game trees. (It would be nice if we could add these representations as easily as Conway multiplies his.) There we have a class of games recursively defined as ordered pairs of sets of and a specials subclass of ‘numbers’ with nothing on the left anything on the right. Here we have a class of ‘forts’ (forests of oriented rooted trees) defined as sets of ordered pairs of and a special class of ‘riffs’ (rooted index-functional forests) in which the riffs above lines into a point are all distinct. Another class of graphs in this correspondence, with the same counting sequence, and somewhat easier to draw, are called ‘rotes’ (rooted odd trees with only exponent symmetries), which are a subset of rooted trees formed from |
|
||||||
|
|
|||||
|
|
|||||
|
|
|||||
|
|
|||||
|
|
|||||
|
|
|||||
|
Note that if looked at as a set of ordered pairs, where then which can be filled in recursively to get the parenthetical form of the corresponding rote. Also note that rotes are free of any plane embedding as long as the root stays marked; for each point immediately above the root there is a unique line leading to an odd tree, and this is the exponent. Yours truly, Jon Awbrey 521 Sunrise Court |
Jon Awbrey to H.W. Gould • 81.12.03
page 1, hand written
81/12/03
H.W. Gould
Dept. of Mathematics
West Virginia University
Morgantown, W. Virginia 26506
Dear Sir:
I thought you might be interested in this one-one correspondence
between natural numbers and planted plane trees, which I worked out
after reading Martin Gardner's June 1976 column on Catalan numbers.
I have left its description in the somewhat whimsical form which
his article originally induced.
It seems that A.A. Mullin had suggested the idea of such
continued factorizations of exponents as far back as 1954. He called
the resulting expressions 'mosaics'. His several articles can be traced
through Math Reviews.
Recently, F. Göbel has given a 1-1 correspondence between natural
numbers and rooted (free) trees, based on continued factorization of the
ordinal indices of the primes in a factorization; see Discrete Math, Aug 1980.
I have also enumerated (generating function and first few terms only)
the expressions resulting from continued factorization of both exponents
and indices. These 'riffs' have 1-1 correspondences with special subsets
of forests of oriented rooted trees and rooted odd trees.
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|||
# of Riffs (by # of p's) = # of Rotes (by # of Γ's) = 1, 1, 2, 6, 20, 73, 281, 1124, 4488[*]
Yours truly,
Jon Awbrey
521 Sunrise, E. Lansing, Mich. 48823
[*] Correct value is 4618. See A061396.
Forest Primeval • Old Notes
Note 1
Subj: Riffs & Rotes & A061396 Date: Fri, 22 Jun 2001 08:42:01 -0400 From: Jon Awbrey <jawbrey@oakland.edu> To: SeqFan <seqfan@ext.jussieu.fr> I would like to step back a bit from my retrospective and try to make some connections with my present work, specifically for the reason that I think that this is where some new enumerative problems might be found to arise, all of which I no longer have the proper tools to tackle, but I think that some of this community is almost bound to. During the 80's my work shifted its focus from the enumerative to the computational. Yes, there was a distinction then, strange to say, and yet what I meant was more toward theorem-proving programs. All along I had been keeping an eye out for relations among arithmetic (number theory) and algebra (groups), geometry (graphs), and logic -- the "lambda point" as one of my professors (Davis) called it then, counting the first two as one. So the little bit of graph and group theory that I picked up was already ready to be converted into data-structures and algorithms able to take advantage of their symmetries, all in support of the new logical mission. But I had to let go of what I earnestly would have kept, all the joys of counting. From my present perspective, what all of these graphs and other sorts of structures have in common is their so-called "reflective" or "self-documenting" property. The archetype of these "reflective or auto-documental" data structures is, of course, the usual construction of natural numbers as sets -- {}, {{}}, {{}{{}}}, ... -- which builds its own distinctive character by keeping a record of its history as it goes. In a similar way, I recall that I first began to think of riffs and all their kin by asking myself a question about molecular tagging: What would be the limit of a tagging tactic? For now, I do not think that I can explain myself any better, but I hope the sense of it will clear in time. Enough flash-forward -- back to the story ... The earliest indication of this line of thinking, that I can find at present among my personal records, is contained in the following letter to Martin Gardner: | 1976-08-16 | | Mr. Martin Gardner | Scientific American | | Dear Sir: | | On the following sheet find the beginnings of a correspondence | between integers and petrified trees, those so rooted and embedded | in their strata as to have a fixed order of limbs at each node. | Read blank areas as nodes, the outside being counted first, and | enclosure relations as branches. The 0 is merely an orthographic | variant for a final parenthesis, reading inward. | | ... | | This arrangement of trees I have dubbed "the forest primeval". | It is developed by expressing each integer in its prime factorization, | and then carrying this process to its extremes, factoring each exponent | into powers of primes, and each of these powers in turn, quitting only | when zero (or empty sets of) exponents are reached, and given the convention | that unit exponents be expressed as 2^0. This suggests a system of numerals | with primes in order as place values, the place-holders being exponents instead | of multipliers, the held values being multiplied instead of added together, | and with the same multitude of place-values implied in each place. | | o | / | o o o | \ / / | o o | \ / | Example: 24 = 2^3 3^1 = 2^(2^0 3^(2^0)) 3^(2^0) = (()(()))(()) = @ | | I have therefore sometimes thought of this as a notation in which numerals are | wholly expressed by means of place-value, there being but one symbol, whose only | office is to reserve a place; but I'm not sure how much this means, since as much | might be said of simple tally marks, with alot less complexity taken for granted. | | [Enclosure:] | | 1 0 | 2 (0) | 3 0(0) | 4 ((0)) | 5 00(0) | 6 (0)(0) | 7 000(0) | 8 (0(0)) | 9 0((0)) | 10 (0)0(0) | 11 0000(0) | 12 ((0))(0) | 13 00000(0) | 14 (0)00(0) | 15 0(0)(0) | 16 (((0))) | | ... ... Continuing apologies for dragging you through my memoirs this way, but there are just too many important details and incidental sidelights that I will otherwise forget.
Note 2
Subj: Topic Maps As A Fool For Inquiry
Date: Mon, 02 Jul 2001 14:34:18 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: Arisbe <arisbe@stderr.org>,
SemioCom <semiocom@listbot.com>,
Standardize Unto Others <standard-upper-ontology@ieee.org>
Paul Prueitt wrote:
>
> Please look at :
>
> http://www.ontologystream.com/IRRTest/Evaluation/ARLReport.htm
>
> and make a comment to me, if you wish.
Paul,
Initial Impression: Very Interesting!
Here are some links to my own musements:
The Forest Primeval:
http://www.research.att.com/~njas/sequences/a061396.txt
http://www.research.att.com/~njas/sequences/a061396a.txt
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A061396
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A062504
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A062537
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A062860
Inquiry Driven Systems:
http://www.chss.montclair.edu/inquiry/fall95/awbrey.html
http://www.door.net/arisbe/menu/library/aboutcsp/awbrey/integrat.htm
http://www.door.net/arisbe/menu/library/aboutcsp/awbrey/inquiry.htm
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
> > -----Original Message-----
> > From: Jon Awbrey [mailto:jawbrey@oakland.edu]
> > Sent: Sunday, July 01, 2001 12:30 AM
> > To: topicmapmail@infoloom.com
> > Cc: W.M. Jaworski; Paul Prueitt; Steve Pepper
> > Subj: [topicmapmail] Topic Maps As A KM Fool
> >
> >
> > ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
> >
> > W.M. Jaworski wrote:
> > >
> > > [Paul Prueitt]
> > > Steve,
> > > Might someone take a part of
> > > http://www.antarcti.ca
> > > say:
> > > http://maps.map.net/cat/Games/Roleplaying?ms=10;ap=0
> > > and write this out as a Topic Map, i.e. as a special XML document?
> > >
> > > [WMJ]
> > > I did try to generate a context map (aka 'topic map') for the
> > > WebPage but our harvester is not processing special scripts.
> > > Of course the conversion can be done manually, but why move
> > > to a foreign context of
> > >
> > > http://maps.map.net/cat/Games/Roleplaying?ms=10;ap=0
> > ?
> > > My desire to enrich receiver context (aka deliver knowledge)
> > > and my "human action perception cycle" is responsible for
> > > suggesting a similar (better?) task namely 're-writing'
> > >
> > > http://www.ontologystream.com (or http://www.ontopia.net )
> > >
> > > website into a kind of 'topic map'. Do we know what value-added should
> > > the 'topic map' deliver? What new views provided by 'topic map' of the
> > > website content are expected or required by 'owners' or 'navigators'?
> > > Are the websites good content sources for the 'topic maps'?
> >
> > Hi Folks,
> >
> > Something in this note led me to wonder what
> > the 'Machines And People' (MAP's) under the
> > influence of a Topical Aesthetic would do
> > with a large database site like NJA Sloane's
> > "Encyclopedia of Integer Sequences" (EIS):
> >
> > http://www.research.att.com/~njas/sequences/Seis.html
> >
> > I ask this merely as a way of introducing myself to your aims and means
> > in the medium of a concrete example.
> >
> > Thanks In Prospect,
> >
> > Jon Awbrey
Note 3
Subj: This Is The Forest Primeval ...
Date: Wed, 04 Jul 2001 07:40:06 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: Topic Map Mail <topicmapmail@infoloom.com>
CC: Arisbe <arisbe@stderr.org>
Here is another Epistle to the SeqFanFolders that may
serve as a bit of background to my revival of my work
on 'graph theoretical data structures' (GTDS) -- I am
fond of acronyms, but not those that lack the vowels
to be vocalizable, so I will just refer to all these
structures as "gits" -- with e-special reference to
ilks of 'reflective or auto-documental' (ROAD) gits.
¤~~~~~~~~~¤~~~~~~~~~¤~MEMOIR~¤~~~~~~~~~¤~~~~~~~~~¤
SeqFanTasians,
I would like to step back a bit from my retrospective
and try to make some connections with my present work,
specifically for the reason that I think that this is
where some new enumerative problems might be found to
arise, all of which I no longer have the proper tools
to tackle, but I think that some of this community is
almost bound to. During the 80's my work shifted its
focus from the enumerative to the computational. Yes,
there was a distinction then, strange to say, and yet
what I meant was more toward theorem-proving programs.
All along I had been keeping an eye out for relations
among arithmetic (number theory) and algebra (groups),
geometry (graphs), and logic -- the "lambda point" as
one of my professors (Davis) called it then, counting
the first two as one. So the little bit of graph and
group theory that I picked up was already ready to be
converted into data-structures and algorithms able to
take advantage of their symmetries, all in support of
the new logical mission. But I had to let go of what
I earnestly would have kept, all the joys of counting.
From my present perspective, what all of these graphs
and other sorts of structures have in common is their
so-called "reflective" or "self-documenting" property.
The archetype of these "reflective or auto-documental"
data structures is, of course, the usual construction
of natural numbers as sets -- {}, {{}}, {{}{{}}}, ... --
which builds its own distinctive character by keeping
a record of its history as it goes. In a similar way,
I recall that I first began to think of riffs and all
their kin by asking myself a question about molecular
tagging: What would be the limit of a tagging tactic?
For now, I do not think that I can explain myself any
better, but I hope the sense of it will clear in time.
Enough flash-forward -- back to the story ...
The earliest indication of this line of thinking,
that I can find at present among my personal records,
is contained in the following letter to Martin Gardner:
| 1976-08-16
|
| Mr. Martin Gardner
| Scientific American
|
| Dear Sir:
|
| On the following sheet find the beginnings of a correspondence
| between integers and petrified trees, those so rooted and embedded
| in their strata as to have a fixed order of limbs at each node.
| Read blank areas as nodes, the outside being counted first, and
| enclosure relations as branches. The 0 is merely an orthographic
| variant for a final parenthesis, reading inward.
|
| ...
|
| This arrangement of trees I have dubbed "the forest primeval".
| It is developed by expressing each integer in its prime factorization,
| and then carrying this process to its extremes, factoring each exponent
| into powers of primes, and each of these powers in turn, quitting only
| when zero (or empty sets of) exponents are reached, and given the convention
| that unit exponents be expressed as 2^0. This suggests a system of numerals
| with primes in order as place values, the place-holders being exponents instead
| of multipliers, the held values being multiplied instead of added together,
| and with the same multitude of place-values implied in each place.
|
| o
| /
| o o o
| \ / /
| o o
| \ /
| Example: 24 = 2^3 3^1 = 2^(2^0 3^(2^0)) 3^(2^0) = (()(()))(()) = @
|
| I have therefore sometimes thought of this as a notation in which numerals are
| wholly expressed by means of place-value, there being but one symbol, whose only
| office is to reserve a place; but I'm not sure how much this means, since as much
| might be said of simple tally marks, with alot less complexity taken for granted.
|
| [Enclosure:]
|
| 1 0
| 2 (0)
| 3 0(0)
| 4 ((0))
| 5 00(0)
| 6 (0)(0)
| 7 000(0)
| 8 (0(0))
| 9 0((0))
| 10 (0)0(0)
| 11 0000(0)
| 12 ((0))(0)
| 13 00000(0)
| 14 (0)00(0)
| 15 0(0)(0)
| 16 (((0)))
|
| ... ...
Continuing apologies for dragging you through my memoirs
this way, but there are just too many important details
and incidental sidelights that I will otherwise forget.
Note 4
Subj: This Is The Forest Primeval ...
Date: Thu, 05 Jul 2001 10:00:01 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: SemioCom <semiocom@listbot.com>,
Standardize Unto Others <standard-upper-ontology@ieee.org>
Here is another Epistle to the SeqFanFolders that may
serve as a bit of background to my revival of my work
on 'graph theoretical data structures' (GTDS) -- I am
fond of acronyms, but not those that lack the vowels
to be vocalizable, so I will just refer to all these
structures as "gits" -- with e-special reference to
ilks of 'reflective or auto-documental' (ROAD) gits.
¤~~~~~~~~~¤~~~~~~~~~¤~MEMOIR~¤~~~~~~~~~¤~~~~~~~~~¤
SeqFanTasians,
I would like to step back a bit from my retrospective
and try to make some connections with my present work,
specifically for the reason that I think that this is
where some new enumerative problems might be found to
arise, all of which I no longer have the proper tools
to tackle, but I think that some of this community is
almost bound to. During the 80's my work shifted its
focus from the enumerative to the computational. Yes,
there was a distinction then, strange to say, and yet
what I meant was more toward theorem-proving programs.
All along I had been keeping an eye out for relations
among arithmetic (number theory) and algebra (groups),
geometry (graphs), and logic -- the "lambda point" as
one of my professors (Davis) called it then, counting
the first two as one. So the little bit of graph and
group theory that I picked up was already ready to be
converted into data-structures and algorithms able to
take advantage of their symmetries, all in support of
the new logical mission. But I had to let go of what
I earnestly would have kept, all the joys of counting.
>From my present perspective, what all of these graphs
and other sorts of structures have in common is their
so-called "reflective" or "self-documenting" property.
The archetype of these "reflective or auto-documental"
data structures is, of course, the usual construction
of natural numbers as sets -- {}, {{}}, {{}{{}}}, ... --
which builds its own distinctive character by keeping
a record of its history as it goes. In a similar way,
I recall that I first began to think of riffs and all
their kin by asking myself a question about molecular
tagging: What would be the limit of a tagging tactic?
For now, I do not think that I can explain myself any
better, but I hope the sense of it will clear in time.
Enough flash-forward -- back to the story ...
The earliest indication of this line of thinking,
that I can find at present among my personal records,
is contained in the following letter to Martin Gardner:
| 1976-08-16
|
| Mr. Martin Gardner
| Scientific American
|
| Dear Sir:
|
| On the following sheet find the beginnings of a correspondence
| between integers and petrified trees, those so rooted and embedded
| in their strata as to have a fixed order of limbs at each node.
| Read blank areas as nodes, the outside being counted first, and
| enclosure relations as branches. The 0 is merely an orthographic
| variant for a final parenthesis, reading inward.
|
| ...
|
| This arrangement of trees I have dubbed "the forest primeval".
| It is developed by expressing each integer in its prime factorization,
| and then carrying this process to its extremes, factoring each exponent
| into powers of primes, and each of these powers in turn, quitting only
| when zero (or empty sets of) exponents are reached, and given the convention
| that unit exponents be expressed as 2^0. This suggests a system of numerals
| with primes in order as place values, the place-holders being exponents instead
| of multipliers, the held values being multiplied instead of added together,
| and with the same multitude of place-values implied in each place.
|
| o
| /
| o o o
| \ / /
| o o
| \ /
| Example: 24 = 2^3 3^1 = 2^(2^0 3^(2^0)) 3^(2^0) = (()(()))(()) = @
|
| I have therefore sometimes thought of this as a notation in which numerals are
| wholly expressed by means of place-value, there being but one symbol, whose only
| office is to reserve a place; but I'm not sure how much this means, since as much
| might be said of simple tally marks, with alot less complexity taken for granted.
|
| [Enclosure:]
|
| 1 0
| 2 (0)
| 3 0(0)
| 4 ((0))
| 5 00(0)
| 6 (0)(0)
| 7 000(0)
| 8 (0(0))
| 9 0((0))
| 10 (0)0(0)
| 11 0000(0)
| 12 ((0))(0)
| 13 00000(0)
| 14 (0)00(0)
| 15 0(0)(0)
| 16 (((0)))
|
| ... ...
Continuing apologies for dragging you through my memoirs
this way, but there are just too many important details
and incidental sidelights that I will otherwise forget.
Note 5
Subj: Gits & Gambits
Date: Thu, 05 Jul 2001 12:34:01 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: Arisbe <arisbe@stderr.org>,
SemioCom <semiocom@listbot.com>,
Standardize Unto Others <standard-upper-ontology@ieee.org>,
Topic Map Mail <topicmapmail@infoloom.com>
I would that I could not be held responsible for the
hasty way that I will have to be pudding this today,
but, of course, nobody ever escapes responsibility
for anything, and especially the half-baked loaves.
I have been trying to rely as much as I can on my 'archives',
as I was so much sharper then than I'll ever be again, but
I do not see how I can avoid treading on the haziness of
trying to force a fresh thought on this point or edge.
Aside to Graham: I do not see much chance that I can do anything
about most of the annoyances and irritations that you mention, as
they are parts of what I need to keep even this barest semblance
of organization, myself, but I do see that a continuing fraction
of the discontinuity you experienced is due to the circumstance
that I have always been disposed to think and to work in what
one might call "overlapping neighborhoods of thought" (ONOT's),
as a consequence of which I'll often be trying to make some
contributary to one "watershed of thinking" (WOT) when out
of the blue it will appear to me that some of it might be
pertinet to some other group that is weighing on my mind --
I am often disieved by my illusions of pertinets, sure,
but the raveling of that is always a post hoc matter --
anyway, with that pre-rumble, here is the message that
preceded the one you seized up on -- oh, wait, it will
probably be less distracting to e-mit it separately:
| Cf: "This Is The Forest Primeval ..."
| Now Serving At Two Locations, No Waiting:
|
| http://stderr.org/pipermail/arisbe/2001-July/000690.html
| http://www.infoloom.com/pipermail/topicmapmail/2001q3/001161.html
To continue, I want now to introduce the family
of 'graph-theoretical data structures' ("gits")
that I know as "gambits", for reasons that will
soon be manifest. Structures like these always
come in two forms, the text and the graph forms,
like the phenotypic 'alternation of generations'
that I remember from a biology course lang syne.
I will present the two variations on this theme
in the parallel paradigmatics that follows here.
Nota Bene. The at-sign "@" denotes a root node.
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
| Definition |
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
| | |
| Blank " " is a gambit. | @ is a gambit. |
| | |
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
| | |
| If i is a gambit and | If i is a gambit and |
| if j is a gambit, | if j is a gambit, |
| | |
| | i j |
| then ij is one too. | then @ is one too. |
| | |
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
| | |
| If i is a gambit and | If i is a gambit and |
| if j is a gambit, | if j is a gambit, |
| | |
| | i j |
| | o---o |
| | | |
| then (i(j)) is one too. | then @ is one too. |
| | |
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
In Step 1 of this recursive scheme, the
notation "ij" denotes the concatenation
of i and j, id est, just the writing of
string i and string j one after another.
The associated graphical notation means
that one joins tree i and tree j at the
root in order to construct the new tree.
In Step 2 of this scheme, i is called the "index"
and j is called the "exponent" of the gambit that
is constructed there. The notation "(i(j))" says
to place the strings for i and j in the indicated
places of the frame "(_(_))". The parallel graph
notation enjoins one to graft the tree i and then
to graft the tree j at the pair of sites that are
severally indicated, merging their roots with the
nodes that are currently sited in the underlying
gambit, in passing erasing their status as roots.
The glyphing of that basic constructor, the rooted path of length 2,
in the form of a 'gamma' is the source of the family name, but that
is little more than a conventional way of scribing it that is often
convenient. In actuality, except for their roots, gambits are free
trees, not embedded in the plane or unnaturally crooked or anything.
That is the basic construction of gambits,
contingent on my remembering it all right.
Note 6
Subj: Gits & Gambits
Date: Thu, 05 Jul 2001 12:48:16 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: SeqFan <seqfan@ext.jussieu.fr>
I would that I could not be held responsible for the
hasty way that I will have to be pudding this today,
but, of course, nobody ever escapes responsibility
for anything, and especially the half-baked loaves.
I have been trying to rely as much as I can on my 'archives',
as I was so much sharper then than I'll ever be again, but
I do not see how I can avoid treading on the haziness of
trying to force a fresh thought on this point or edge.
Aside to Graham: I do not see much chance that I can do anything
about most of the annoyances and irritations that you mention, as
they are parts of what I need to keep even this barest semblance
of organization, myself, but I do see that a continuing fraction
of the discontinuity you experienced is due to the circumstance
that I have always been disposed to think and to work in what
one might call "overlapping neighborhoods of thought" (ONOT's),
as a consequence of which I'll often be trying to make some
contributary to one "watershed of thinking" (WOT) when out
of the blue it will appear to me that some of it might be
pertinet to some other group that is weighing on my mind --
I am often disieved by my illusions of pertinets, sure,
but the raveling of that is always a post hoc matter --
anyway, with that pre-rumble, here is the message that
preceded the one you seized up on -- oh, wait, it will
probably be less distracting to e-mit it separately:
| Cf: "This Is The Forest Primeval ..."
| Now Serving At Two Locations, No Waiting:
|
| http://stderr.org/pipermail/arisbe/2001-July/000690.html
| http://www.infoloom.com/pipermail/topicmapmail/2001q3/001161.html
To continue, I want now to introduce the family
of 'graph-theoretical data structures' ("gits")
that I know as "gambits", for reasons that will
soon be manifest. Structures like these always
come in two forms, the text and the graph forms,
like the phenotypic 'alternation of generations'
that I remember from a biology course lang syne.
I will present the two variations on this theme
in the parallel paradigmatics that follows here.
Nota Bene. The at-sign "@" denotes a root node.
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
| Definition |
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
| | |
| Blank " " is a gambit. | @ is a gambit. |
| | |
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
| | |
| If i is a gambit and | If i is a gambit and |
| if j is a gambit, | if j is a gambit, |
| | |
| | i j |
| then ij is one too. | then @ is one too. |
| | |
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
| | |
| If i is a gambit and | If i is a gambit and |
| if j is a gambit, | if j is a gambit, |
| | |
| | i j |
| | o---o |
| | | |
| then (i(j)) is one too. | then @ is one too. |
| | |
¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~¤
In Step 1 of this recursive scheme, the
notation "ij" denotes the concatenation
of i and j, id est, just the writing of
string i and string j one after another.
The associated graphical notation means
that one joins tree i and tree j at the
root in order to construct the new tree.
In Step 2 of this scheme, i is called the "index"
and j is called the "exponent" of the gambit that
is constructed there. The notation "(i(j))" says
to place the strings for i and j in the indicated
places of the frame "(_(_))". The parallel graph
notation enjoins one to graft the tree i and then
to graft the tree j at the pair of sites that are
severally indicated, merging their roots with the
nodes that are currently sited in the underlying
gambit, in passing erasing their status as roots.
The glyphing of that basic constructor, the rooted path of length 2,
in the form of a 'gamma' is the source of the family name, but that
is little more than a conventional way of scribing it that is often
convenient. In actuality, except for their roots, gambits are free
trees, not embedded in the plane or unnaturally crooked or anything.
That is the basic construction of gambits,
contingent on my remembering it all right.
Note 7
Subj: Göbel = Matula Numbering. (Neé: Riffs & Rotes & A061396) Date: Fri, 06 Sep 2002 00:30:42 -0400 From: Jon Awbrey <jawbrey@oakland.edu> To: Antti Karttunen <karttu@megabaud.fi> SeqFan <seqfan@ext.jussieu.fr> 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. 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: is there a "purely combinatorical" reason that (p_2)^1 < (p_1)^2? viewed as rotes: o---o o---o | | o---o o---o | | @ <?< @ (p_2)^1 <?< (p_1)^2 fun & games ... links here to dana scott's d_infinity and similar constructions. Antti Karttunen wrote: > > Jon Awbrey wrote Fri, 22 Jun 2001 14:36:26: > > > > ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤ > > > > F. Göbel, > > On a 1-1-Correspondence between Rooted Trees and Natural Numbers, > > Journal of Combinatorial Theory, B29 (1980), pages 141-143. > > > > This correspondence is associated in one way or another > > with the following sequences in the EIS online database: > > > > A005517, A005518, A007097, A057452. > > > > 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 > > > > 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. > > > > 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. > > > > 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 ... > > | > > ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤ > > 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. > > 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. > > ......... > > 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 > > 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. > > > 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. > 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?) > > 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) > where X means multiplication of Z2[x] polynomials, > so it is a homomorphism between these semigroups. > > 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. > (How does it map the corresponding multiplication > tables A004247 and A048720 to each other?) > > 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. > > Terveisin, > > Antti Karttunen
Note 8
Subj: Göbel = Matula Numbering. (Neé: Riffs & Rotes & A061396) Date: Tue, 10 Sep 2002 09:16:23 -0400 From: Jon Awbrey <jawbrey@oakland.edu> To: Antti Karttunen <karttu@megabaud.fi>, SeqFan <seqfan@ext.jussieu.fr> AK = Antti Karttunen JA = Jon Awbrey 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? JA: | Göbel, F., |"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.
Note 9
Subj: Riffs & Rotes & A061396 Date: Wed, 18 Sep 2002 08:32:31 -0400 From: Jon Awbrey <jawbrey@oakland.edu> To: SeqFan <seqfan@ext.jussieu.fr> memories like strawberries ... grow fuzzy with time ... i remember now that it was bonnie stewart who first told me about mullin's work, only he said "mulligan", so that threw me off the trail for a while, and it was only later when r.w. robinson gave me the correct name that i was able to find his work on "mosaics". here are the references that i can find at present: | mullin, a.a., |'zeitschrift f. math. logik und grundlagen d. mathk.', | bd. 10, p.159 & p.199, 1964. | mullin, a.a., |'notre dame j. of formal logic', | vol. 8, no. 4, p. 353, oct. 1967. a basic reference on dana scott's "d_infinity" (model of lambda calculus) is this: | stoy, j.e., |'denotational semantics: the scott-strachey approach to programming language theory', | mit press, cambridge, ma, 1977.
Note 10
Subj: Gödel, Göbel, Matula, Mullin, ...
Date: Wed, 18 Sep 2002 10:14:25 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: SeqFan <seqfan@ext.jussieu.fr>
AK = Antti Karttunen
JA = Jon Awbrey
catching up on old correspondence,
so this may be a bit out of order.
will try to pare the redundancies.
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.
AK: Look at A075166, giving a bijection between
rooted plane trees and natural numbers > 0.
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=075166
| The rooted plane trees encoded here are:
| .....................o...............o.........o...o..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......9.....
AK: was it that what you had in mind then?
oh, strictly speaking, we should be calling these "planted plane trees",
as otherwise you can rotate the branches around the root and transform,
for example, 6 into 9.
i found the two letters that i wrote to martin gardner in 76 & 78,
and will try to extract the gist of them later, but here is a bit:
| The forest primeval: a correspondence between natural numbers and planted plane trees.
|
| Consider the primes factorization of a number and represent it as the sequence of its
| exponents separated by parentheses, thus, N = (n_1) (n_2) (n_3) ... (n_m), ignoring
| for now the all-zero exponents after some point m.
|
| e.g.: 1 = 2^0 = (), 2 = 2^2^0 = (()), 3 = 2^0 3^2^0 = ()(())
|
| Repeat this process with each exponent in the factorization and with each further
| exponent in 'its' factorization and so on, until zero exponents are reached along
| every path of development. A zero exponent, having no representation in primes,
| may simply be omitted on the next pass. For example:
|
| 360 = (3)(2)(1) = ((0)(1)) ((1)) ((0)) = (()((0))) (((0))) (())
|
| = (()(())) ((())) (())
|
| = 2^(2^0 3^2^0) 3^2^2^0 5^2^0
|
| Thus, parentheses suffice to represent this "involved factorization" of a number.
| But they also represent planted plane trees, if we interpret the exterior space
| as the planter, parenthetical containments as further edges, and contained
| spaces as nodes, e.g.:
|
| o o
| | |
| o o o o
| \| | |
| o o o
| \ | /
| \|/
| o
| |
| 360 = @
|
| In this way, every number may be assigned a unique minimal tree, but
| many trees will share the same number when the "insignificant digits" of
| a factorization are taken into account. E.g., trees of the following form,
| where an ellipsis represents an arbitrary number of terminal edges, all have
| the number 360:
|
| o … o …
| |/ |/
| o o … o … o …
| \|/ |/ |/
| o o o
| \ | /
| \ | /
| \|/
| o---…
| |
| @
|
| = 2^(2^0 3^(2^0 3^0 …) 5^0 …) 3^(2^(2^0 3^0 …) 3^0 …) 5^(2^0 …) 7^0 …
Note 11
Subj: Tree Terminology, Terminable & Interminable
Date: Thu, 19 Sep 2002 13:48:55 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: SeqFan <seqfan@ext.jussieu.fr>
oh, i understand that dialects in graph theory differ,
especially when you have to interface with computer sci,
i am merely going by the particular usage that i learned
long ago, and there's always a way of finding the proper
translations between different terminologies.
"planted plane tree" was a classical usage for the trees
that are counted by catalans. different folks would use
different strokes like these to indicate a "planter":
o OR o OR o
^ | |
- @
and sometimes they would count the root and sometimes not.
the point here is to prevent the rotations around the root
within the plane, not to block the reflections, which are
not allowed anyway.
e.g. "the five planted plane trees of order 5"
o
|
o o o o o
| \ / | |
o o o o o o o o o
| | \ / \ / \|/
o o o o o
| | | | |
@ @ @ @ @
p.67 in Harary & Palmer, 'Graphical Enumeration', 1973.
i was in the middle of writing another note slightly related to this,
but i think that all of this fuss about the planters may have been
one of the reasons why i eventually shifted to cacti, which are
much happier without the planters, the desert sand being far
too forbidding of these underground rotations in any case.
AK: | The rooted plane trees encoded here are:
| .....................o...............o.........o...o..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......9.....
JA: oh, strictly speaking, we should be calling these "planted plane trees"
as otherwise you can rotate the branches around the root and transform,
for example, 6 into 9.
what i meant is that we have to add a planter to the above trees
in order to get a correspondence with parenthetical expressions.
AK: I'm following Stanley's usage in his
"Exercises on Catalan and Related Numbers"
http://www-math.mit.edu/~rstan/ec/catalan.pdf
AK: that is, the above trees belong to his manifestation 19 (e)
"plane trees with n + 1 vertices" while the next manifestation (f)
is given as "planted (i.e., root has degree one) trivalent plane trees
with 2n + 2 vertices"
AK: so I have thought that the term "planted" means exactly that,
that the tree (whether binary (= trivalent) or general),
is "planted" on a top of the single "stem" | _not_ that
it cannot be reflected as a whole, as you indicate.
(Because being "planar", it is already forbidden).
AK: And also, I assume the terms "plane", "planar", and
"oriented" (cf. A000108) are synonyms, as well as their
antonyms "non-planar" and "non-oriented" (cf. A000081).
AK: Am I correct?
AK: I guess we could create a "tree matrix", where we have all
the combinations of labeled/unlabeled, rooted/non-rooted,
planar/non-planar, binary/general trees, with each entry
pointing to the corresponding enumerating EIS-sequence.
(will do that, when I have spare time ...)
Note 12
Subj: The Forest Primeval Date: Thu, 19 Sep 2002 14:16:32 -0400 From: Jon Awbrey <jawbrey@oakland.edu> To: SeqFan <seqfan@ext.jussieu.fr> Here is what the initial mapping of numbers into parenthetical expressions looked like: 1 2^0 o () 2 2^2^0 (o) (()) 3 2^0 3^2^0 o(o) ()(()) 4 2^2^2^0 ((o)) ((())) 5 2^0 3^0 5^2^0 oo(o) ()()(()) 6 2^2^0 3^2^0 (o)(o) (())(()) 7 2^0 3^0 5^0 7^2^0 ooo(o) ()()()(()) 8 2^[2^0 3^2^0] (o(o)) (()(())) 9 2^0 3^2^2^0 o((o)) ()((())) 10 2^2^0 3^0 5^2^0 (o)o(o) (())()(()) 11 2^0 3^0 5^0 7^0 11^2^0 oooo(o) ()()()()(()) 12 2^2^2^0 3^2^0 ((o))(o) ((()))(()) 13 2^0 3^0 5^0 7^0 11^0 13^0 ooooo(o) ()()()()()(()) 14 2^2^0 3^0 5^0 7^2^0 (o)oo(o) (())()()(()) 15 2^0 3^2^0 5^2^0 o(o)(o) ()(())(()) 16 2^2^2^2^0 (((o))) (((()))) The "o" is just an easier to read variant for an empty pair of terminal parentheses. Here is the second half of that note I wrote, where I "supposedly" got a 1-1 correspondence: | The correspondence becomes one-to-one by the following transformation. | To the rightmost "offspring", when not the only offspring, of any node | of a given planted plane tree, assign an extra unit of significance: | such that, if terminal, that node represents a unit exponent; if it | is not terminal, the unit may be "inherited", but only by a singleton | offspring of that node, with a like condition entailing any further | inheritance, until a terminal node reached; otherwise, the significance | is lost. E.g., 360 is now uniquely represented by the following tree, | where primed nodes count for unit exponents under the above rule: | | o | | | o o' o | \| | | o o o' | \ | / | \|/ | o | | | 360 = @ Subsequently, I wrote this marginal note: | e.g., now: | | o o o | | \ / | o o o | | | | | @ = () = 1, @ = (()) = 2, @ = ()() = 3 Well, that is what I wrote, but to be honest it looks wrong somehow. Maybe I muffed up the initial conditions in my later note. Or maybe it can be fixed by deleting the "when not the only offspring" clause in the token-passing transformation. Let me give it another try ... What we are really interested in are sequences of exponents, that we turn into sequences of trees, and we use the gimmick of a graph-theoretical "planter" to convert the sequences of trees into planted plane trees. In the general setting, the planter look like this: ^ ^ ^ \|/ o | @ But it's a quirky property of this set-up that the empty sequence and the singleton sequences require planters that appear to be excessively large: Empty sequence <>: o | @ Singleton sequence <k>: k | o | @ So maybe I should have written: | o' o o' | | \ / | o o o | | | | | @ = _ = 1, @ = () = 2, @ = ()() = 3 So far this seems to suggest that the buck-passing rule should apply to every node but the root, but now I will have to rethink the whole thing. Maybe I'll just leave this one to the current inhabitants of Fair Catalania, and return to the Realm Of Rote Arithmetic.
Note 13
Subj: The Lambda Point
Date: Thu, 19 Sep 2002 15:14:15 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: SeqFan <seqfan@ext.jussieu.fr>
AK = Antti Karttunen
AK: So far I haven't found/constructed any ranking scheme
which would be practical to implement as a computer
algorithm, in a sense that the sequence {max integer
mapped to the size n tree} wouldn't grow too steeply.
I reckon this is also the problem with Matula/Göbel
encoding of rooted unoriented trees.
Ok, there are lots and lots of mappings between any two countable sets,
so I guess that the "interesting" ones are relative to one's interest,
one's end-in-view, and most likely one's personal sense of aesthetics.
I was initially interested in the correspondences that might serve as
mathematical "labor-saving devices", allowing us to transfer theorems,
what we know and can prove, among different domains, especially among
algebra, geometry, and logic -- what one of my teachers used to call
the "lambda point", after the critical triple point of transitions
among gas, liquid, and solid phases.
From this perspective, it's not a problem, may even be a feature,
that some relatively big numbers have some interesting aspects
of their structure captured by some relatively small graphs.
I haven't said anything about the logical side of this yet,
but remember that it was folks like Gödel, not to mention
Peirce, who lobbed us into this particular briar patch.
Note 14
Residual Questions ...
Here is how I last defined rotes:
JA: | @ 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.
Strictly speaking, I probably should have stipulated that
each f is a "finite partial function" from rotes to rotes,
but since the set of rotes is infinite the partiality of f
might be taken as implicit in the fact of its being finite.
Let $N$ ("Script N") be the set of rotes.
Let (X -> Y) be the set of functions from X to Y.
Let [X -> Y] be the set of finite partial functions from X to Y.
Then we have the isomorphism $N$ ~=~ [$N$ -> $N$],
that is, every rote k : $N$ is uniquely analyzed
as a finite partial function k : $N$ -> $N$, and
every such function gets a unique gödel number
in $N$. Notice the polymorphism of types.
1 = {} = the empty function
2 = (p_1)^1 = {<1, 1>}
3 = (p_2)^1 = {<2, 1>}
4 = (p_1)^2 = {<1, 2>}
5 = (p_3)^1 = {<3, 1>}
6 = (p_1)^1 (p_2)^1 = {<1, 1>, <2, 1>}
As rooted trees, these look like this:
o--o
|
o--o o--o o--o o-o
| | | /
o--o o--o o--o o--o o-o o-o
| | | | \ /
@ @ @ @ @ @
1 2 3 4 5 6
Anyway, I think this is right, but I've learned not
to trust stuff like this until several other people
have a chance to go over it.
Note 15
More Residual Questions ...
JA: 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?
AK: I delve into this later in autumn, after I have read more
about posets and lattices, and also when I have grokked
your rotes & riffs (has to find the folder where I put
all your mails I printed out then ...)
AK: Anyways, I doubt in the following:
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:
is there a "purely combinatorical" reason that (p_2)^1 < (p_1)^2?
AK: that you could find with such methods a total order that would correspond
with our usual linear order 1 < 2 < 3 < 4 < 5 < 6 < ... because it's based
on the additive property of integers, and these N <-> various trees schemes
are based on the multiplicative properties (more or even less). (And I'm
afraid that the connection with primes and such is just a red herring ...)
