[last update 2000-2-6]




n-stage trees, n-fibonacci numbers, and the cohomology of k(a,n)




define the "complexity" of an n-stage tree [1] to be the total number
of globes in it's "globular realization".  thus for example the
complexity of the 2-stage tree

/\
 /\

is 9, because it's globular realization has 3 0-globes + 4 1-globes +
2 2-globes.

the complexity of an n-stage tree is always an odd number >= 1.  the
"rank" of an n-stage tree t is defined to be (complexity(t)-1)/2.
alternatively, the rank of t is simply the number of "edges" in the
tree picture of t.  the main aim of this note is to explain the
significance of the rank of an n-stage tree in homotopy theory and
higher-dimensional category theory.


define an n-stage tree t to be "non-degenerate" if n = 0 or if t
(thought of as a list of [n-1]-stage trees) is non-empty.  recursively
define t to be "hereditarily non-degenerate" if t is non-degenerate
and all of the [n-1]-stage trees in t are hereditarily non-degenerate.
thus for example

/\
 /\

isn't hereditarily non-degenerate but

 /\
| /\

is.


lemma 1: the number of hereditarily non-degenerate n-stage trees of
rank r is the rth so-called "n-fibonnaci number" [2].


proof of lemma 1:

we can enumerate the hereditarily non-degenerate n-stage trees as the
nodes in the complete n-ary tree (hereafter referred to as "the big
tree" to distinguish it from the n-stage trees) of infinite depth.
for example when n = 2:

                                  [[*]]

            [[**]]                                 [[*][*]]

    [[***]]        [[**][*]]             [[*][**]]         [[*][*][*]]

  [4]  [3,1]    [2,2]  [2,1,1]        [1,3]  [1,2,1]    [1,1,2]  [1,1,1,1]

...


the organizing principle here is that the left branch emerging from a
node in the big binary tree corresponds to incrementing the last list
in the list of lists, while the right branch corresponds to
incrementing the list of lists itself.  (similarly in the big ternary
tree of hereditarily non-degenerate 3-stage trees, the 3 branches
emerging from a node correspond respectively to incrementing the last
list in the last list of lists in the list of lists of lists,
incrementing the last list of lists in the list of lists of lists, and
incrementing the list of lists of lists itself; and similarly too for
the higher cases.)

note that the horizontal levels in the big n-ary tree as drawn above
for the case n = 2 are not the lines of constant rank.  rather, depth
in the tree measures a different kind of "complexity", namely the
number of n-globes in the globular realization of the n-stage tree.
we can fix this deficiency by re-drawing the big tree with the n
branches emerging from each node drawn with characteristically
differing vertical displacements to account for the differing effects
of the corresponding incrementation processes on rank.  for example,
again in the case n = 2:

                                  [[*]]

            [[**]]

    [[***]]                                        [[*][*]]

  [4]              [[**][*]]             [[*][**]]

       [3,1]    [2,2]                 [1,3]                [[*][*][*]]

                       [2,1,1]               [1,2,1]    [1,1,2]

                                                                 [1,1,1,1]

...


now the horizontal levels are the lines of constant rank, and when the
big tree is completed the number of n-stage trees on the rth level is
the rth n-fibonnaci number.  (since the smallest rank of any
hereditarily non-degenerate n-stage tree is n, we think of there as
also being unoccupied levels numbered from 1 to n-1 before the
appearance of the first occupied level numbered n in the big tree.)

[end of proof of lemma 1]


why is all this interesting?  because the hereditarily non-degenerate
n-stage trees of rank r correspond to pieces of data which together
constitute an r-cocycle valued in an abelian group b on the
eilenberg-maclane space k(a,n) of an abelian group a.  of course by
the yoga of categorification and de-categorification that means that
they can also be seen as coherence laws obeyed by an [r-1]-cocycle on
k(a,n).

here is a heuristic explanation:


[warning: begin even-less-rigorous-than-usual section]

we know, particularly from experience with the postnikov cocycles of
homotopy types involving just two non-trivial homotopy groups, that
r-cocycles on k(a,n) can sometimes be analyzed into more basic
"ingredients".  for example, the postnikov 4-cocycle of a homotopy
type with just pi_2 and pi_3 non-trivial can be analyzed into an
"associator" part and a "braiding" part.  we want to understand this
analysis process in general.

let's consider as an example the rth cohomology group of k(a,2) with
coefficients in b.  it's elements are the homotopy classes of maps
from k(a,2) to k(b,r).  roughly, that's the same as the homotopy
classes of "group homomorphisms up to homotopy" from the loop space
k(a,1) of k(a,2) to the loop space k(b,r-1) of k(b,r).  so, we need to
understand the ingredients of such a
group-homomorphism-up-to-homotopy.

first, we need the underlying map k(a,1) -> k(b,r-1) of the
group-homomorphism-up-to-homotopy.  then we need the homotopy up to
which the underlying map preserves multiplication.  by a gross
over-simplification, that homotopy can be construed as a map
k(a,1)Xk(a,1) -> k(b,r-2).  but then we also need the
homotopy-homotopy up to which the underlying map preserves associator
homotopies, which by the same kind of gross over-simplification can be
construed as a map k(a,1)Xk(a,1)Xk(a,1) -> k(b,r-3), and so on.  thus
we've analyzed the map k(a,2) -> k(b,r) into a sequence of ingredients
labeled roughly as:

k(a,1) -> k(b,r-1)

k(a,1)Xk(a,1) -> k(b,r-2)

k(a,1)Xk(a,1)Xk(a,1) -> k(b,r-3)

...


the items in the sequence, however, can be further analyzed into
smaller ingredients by applying the formula that says that the jth
(reduced) cohomology with coefficients in b of a cartesian product x_1
X ... X x_k is the sum over [all k-tuples (t_1,...,t_k) of positive
integers with t_1+...+t_k = j] of [the t_1^th cohomology of x_1 with
coefficients in [...[the t_k^th cohomology of x_k with coefficients in
b]...]].  a simple combinatorial analysis then shows that, taking (for
each k) j = r-k, the number of such k-tuples, summed over all k, is
the rth fibonacci number.

a similar but more involved analysis in the case of the cohomology of
k(a,n) leads to the rth n-fibonacci number.


[end of even-less-rigorous-than-usual section]


thus an r-cocycle on k(a,n) can be analyzed into the rth n-fibonacci
number of ingredients.  thus it's reasonable to guess that the
ingredients of an r-cocycle on k(a,n) systematicly correspond to the
n-stage trees of rank r, both being counted by the rth n-fibonacci
number.  there are clear indications that such a systematic
correspondence in fact exists, and it's easy to make all sorts of
interesting guesses about why this is so.  (note for example the case
r = 4, n = 2, already alluded to, where the two 2-stage trees of rank
4, [[***]] and [[*][*]], clearly correspond to "associator" and
"braiding", respectively.)  i hope to work out the details of all of
this, as well as the big picture of how it relates to
higher-dimensional category theory in general.







[1] michael batanin, monoidal globular categories as a natural
environment for the theory of weak n-categories, allegedly available
at http://www-math.mpce.mq.edu.au/~mbatanin/papers.html

[2] sloane's on-line encyclopedia of integer sequences, at
http://www.research.att.com/~njas/sequences/
(click on "find word" and try "tribonacci" or "tetranacci".)