[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".)