A DIAGONAL ON THE ASSOCIAHEDRA
SAMSON SANEBLIDZE AND RONALD UMBLE1
To Jim Stasheff on the occasion of his 65th birthday
1.Introduction
An associahedral set is a combinatorial object generated by Stasheff associah*
*edra
{Kn} and equipped with appropriate face and degeneracy operators. Associahedral
sets are similar in many ways to simplicial or cubical sets. In this paper we g*
*ive a
formal definition of an associahedral set, discuss some naturally occurring exa*
*mples
and construct an explicit geometric diagonal : C*(Kn) ! C*(Kn) C*(Kn) on
the cellular chains C*(Kn) : The diagonal ; which is analogous to the Alexander
Whitney diagonal on the simplices, gives rise to a diagonal on any associahedra*
*l set
and leads immediately to an explicit diagonal on the A1 operad: As an applicat*
*ion
of this, we use the diagonal to define a tensor product in the A1 category. Th*
*is
tensor product will play a central role in our discussion of "A1 Hopf algebras*
*" to
appear in the sequel.
We mentionPthat Chapoton [1], [2] constructed a diagonalPof the form :
C*(Kn) ! i+j=nC*(Ki) C*(Kj) on the direct sum n2 C*(Kn) ; which
coincides with the diagonal of Loday and Ronco [8] in dimension zero. Whereas
Chapoton's diagonal is formally defined to be primitive on generators, our diag*
*onal
is obtained by a purely geometrical decomposition of the generators and is tota*
*lly
different from his.
The second author wishes to thank Millersville University for its generous fi*
*nan
cial support and the University of North Carolina at Chapel Hill for its hospit*
*ality
during the final stages of this project.
2.The Stasheff Associahedra
In his seminal papers of 1963, J. Stasheff [17] constructs the associahedra
{Kn+2}n0 as follows: Let K2 = *; if Kn+1 has been constructed, let
[
Ln+2 = (Kr x Ks)k
1r+s=n+3kns+3
and define Kn+2 = CLn+2; i.e., the cone on Ln+2: The associahedron Kn+2 is
an ndimensional polyhedron, which serves as a parameter space for homotopy
associativity in n + 2 variables. The top dimensional face of Kn+2 corresponds *
*to
a pair of level 1 parentheses enclosing all n + 2 indeterminants; each component
(Kn`+2xK`+1)i+1of @Kn+2 corresponds to a pair of level 2 parentheses enclosing
____________
Date: November 8, 2000.
Key words and phrases. Associahedra, A1 algebra, A1 coalgebra, tensor prod*
*uct.
1This research funded in part by a Millersville University faculty research *
*grant.
1
2 SAMSON SANEBLIDZE AND RONALD UMBLE1
` + 1 indeterminants beginning with the (i + 1)st. We denote this parenthesizat*
*ion
by
d(i;`)= (x1. .(.xi+1. .x.i+`+1).x.n.+2)
and refer to the inner and outer parentheses as the first and last pair, respec*
*tively.
Note that indices i and ` are constrained by
8 9
< 0 i n =
: 11 ` `n; n + 1  ii=;01 i; n:
Thus, there is a onetoone correspondence between (n  1)faces of Kn+2 and
parenthesizations d(i;`)of n + 2 indeterminants.
Alternatively, Kn+2 can be realized as a subdivision of the standard ncube I*
*n in
the following way: Let ffl = 0; 1: Label the endpoints of K3 = [0; 1]via ffl $ *
*d(ffl;1): For
1 i n; let en1i;ffldenote the (n  1)face (x1; : :;:xi1; ffl; xi+1; : :;:x*
*n) In and
obtain K4 from K3 x I = I2 by subdividing the edge e11;1as the union of interva*
*ls
1 x I0;1[ 1 x I1;1: Label the edges of K4 as follows: e1i;0$ d(0;i); e12;1$ d(2*
*;1);
1 x I0;1$ d(1;1); and 1 x I1;1 $ d(1;2)(see Figure 1):
d(2;1)
(0;o_____________o1)(1; 1)
 
 d(1;2)
 
d(0;1) K4 o
 
 d(1;1)
 
o_____________o
(0; 0) d(0;2) (1; 0)
Figure 1: K4 as a subdivision of K3 x I:
Now for 0 i j 1; let Ii;jdenote the subinterval 2i 1 =2i; 2j 1 =2j
I; where (21  1)=21 is defined to be 1: For n > 2; assume that Kn+1 has been
constructed and obtain Kn+2 from Kn+1 x I In by subdividing the (n  1)faces
d(i;ni)xI as unions d(i;ni)xI0;i[d(i;ni)xIi;1; 0 < i < n. Label the (n  1)*
*faces
of Kn+2 as follows:
Face_of_Kn+2__Label_______________________________

en1`;0 d(0;`); 1 ` n

en1n;1 d(n;1);

d(i;`)x I d(i;`); 1 ` < n  i; 0 < i < n  1

d(i;ni)x I0;id(i;ni); 0 < i < n

d(i;ni)x Ii;1d(i;ni+1);0 < i < n
A DIAGONAL ON THE ASSOCIAHEDRA 3
(0; 0; 1)
o___________________oo
cc cc
 c  c
 co d(3;1)  c
 c  c
  c  c
  coo___________________oc
d(1;1)  
 d(1;3) d(2;2) 
   
 o ____________________oo
 cc  
  c   
o____ ___c_o______o 
(1; 0; c0)   c 
c d(1;2) c 
c   d(2;1) c 
co  c 
c  c 
c  c 
c ____________________ooc
(0; 1; 0)
Figure 2: K5 as a subdivision of K4 x I:
In Figure 2 we have labeled the 2faces of K5 that are visible from the viewpoi*
*nt
of the diagram.
Compositions d(im ;`m.).d.(i2;`2)d(i1;`1)denote a successive insertion of m +*
* 1
pairs of parentheses into n + 2 indeterminants as follows: Given d(ir;`r).d.(.i*
*1;`1);
1 r < m; regard each pair of level 2 parentheses and its contents as a single *
*inde
terminant and apply d(ir+1;`r+1): Conclude by inserting a last pair enclosing e*
*very
thing. Note that each parenthesization can be expressed as a unique composition
d(im ;`m.).d.(i1;`1)with ir+1 ir for 1 r < m; in which case the parentheses i*
*n
serted by d(ir+1;`r+1)begin at or to the left of the pair inserted by d(ir;`r).*
* Such com
positions are said to have first fundamental form. Thus for 0 k < n; the kfac*
*es
of Kn+2 lie in onetoone correspondence with compositions d(ink;`nk).d.(.i1;*
*`1)
in first fundamental form. The two extremes with m pairs of parentheses inserted
as far to the left and right as possible, are respectively denoted by
d(0;`m.).d.(0;`1)andd(im ;im1im.).d.(i1;i0i1);
where i0 = n + 1 and ir+1 < ir; 0 r < m: In particular, the nfold compositions
d(0;1).d.(.0;1)andd(1;1).d.(.n;1)
denote the extreme full parenthesizations of n + 2 indeterminants. When m = 0;
define d(im ;`m.).d.(i1;`1)= Id.
1 2 3 . . .n + 2
@ A : : :
@ A 
@oA
N0 

Figure 3: The planar rooted tree Tn+2
Alternatively, each face of Kn+2 can be represented as a planar rooted tree (*
*PRT)
with n+2 leaves; its leaves correspond to indeterminants and its nodes correspo*
*nd to
pairs of parentheses. Let Tn+2 denote the PRT with n+2 leaves attached to the r*
*oot
4 SAMSON SANEBLIDZE AND RONALD UMBLE1
at a single node N0; called the root node (see Figure 3). The leaves correspond*
* to a
single pair of parentheses enclosing all n + 2 indeterminants. Now consider a n*
*ode
N of valence r + 1 4 in an arbitrary PRT T . Choose a neighborhood U of N that
excludes the other nodes of T and note that Tr U \T: Labeling from left to rig*
*ht,
index the leaves of Tr from 1 to r as in Figure 3. Perform an (i; `)surgery at*
* node N
in the following way: Remove leaves i+1; : :;:i+`+1 of Tr; reattach them at a n*
*ew
node N0 6= N and graft in a new branch connecting N to N0 (see Figure 4). Now
i + 1 . . . i + ` + 1
: : :
@@ AA
@ A
1 . . .i @oA i + ` + 2 . .n.+ 2
N0 
@ : :A:  : : :
@ A 
@ A 
@ A 
@ A 
@oA
N0 


Figure 4: The planar rooted tree Tn(i;`)+2
let n 1. Given a parenthesization d(i;`)of n + 2 indeterminants, obtain the PRT
Tn(i;`)+2from Tn+2 by performing an (i; `)surgery at the root node N0 as shown
in Figure 4. Inductively, given a parenthesization d(im ;`m.).d.(i1;`1)of n + *
*2 in
determinants expressed as a composition in first fundamental form, construct the
corresponding PRT Tn(i1;`1);:::;(im+;`m2)as follows: Assume that Tn(i1;`1);:::;*
*(ir;`r)+2with
nodes N0; : :;:Nr has been constructed for some 1 r < m and note that the
root node N0 has valence n + 3  `1  . ..`r: Perform an (ir+1; `r+1)surgery *
*at
N0 and obtain Tn(i1;`1);:::;(ir+1;`r+1)+2containing a new node Nr+1 and a new b*
*ranch
connecting N0 to Nr+1: Finally, define Tn(i1;`1);:::;(im+;`m2)= Tn+2 when m = 0*
* and
obtain a onetoone correspondence between kfaces of Kn+2; 0 k n and PRT's
Tn(i1;`1);:::;(ink;`nk)+2consisting of n  k + 1 nodes and n + 2 leaves. In p*
*articular,
each vertex of Kn+2 corresponds to a planar binary rooted tree Tn(i1;`1);:::;(i*
*n;`n)+2
(see Figure 5).
Now given a kface ak Kn+2; k > 0; consider the two vertices of ak at which
parentheses are shifted as far to the left and right as possible; we refer to t*
*hese
vertices as the minimal and maximal vertices of ak; and denote them by aminkand
amaxk; respectively. In particular, the minimal and maximal vertices of Kn+2 a*
*re
the origin and the vertex of In diagonally opposite to it, i.e.,
Kminn+2$ (0; 0; : :;:0)andKmaxn+2$ (1; 1; : :;:1);
the respective binary trees in Figure 5 correspond to Kmin4and Kmax4.
A DIAGONAL ON THE ASSOCIAHEDRA 5
@ @ @ @@
@o @ @ o
@o @ @ o
@o @o
 
T4(0;1);(0;1)$ T4(2;1);(1;1)$
d(0;1)d(0;1)= (((oo)o)o) d(1;1)d(2;1)= (o(o(oo)))
Figure 5: Planar binary rooted trees.
Given a representation Tn(i1;`1);:::;(ink;`nk)+2of ak, construct the minimal *
*(resp.,
maximal) tree of ak by replacing each node of valence r 4 with the planar bina*
*ry
rooted tree representing Kminr1(resp., Kmaxr1). Note that aminkand amaxkdeter*
*mine
ak since their convex hull is a diagonal of ak. But we can say more.
When a composition of face operators d(im ;`m.).d.(i1;`1)is defined we refer *
*to
the sequence of lower indices I = (i1; `1); : :;:(im ; `ma)s an admissible sequ*
*ence
of length m; if d(im ;`m.).d.(i1;`1)has first fundamental form we refer to the *
*the
sequence I as a type I sequence of length m. The set of all planar binary rooted
trees
I
Yn+2 = Tn+2 I is type I sequence of lengthn
is a poset with partial ordering defined as follows: Say that TnIp+2 TnIq+2if t*
*here
is an edgepath in Kn+2 from vertex TnIp+2to vertex TnIq+2along which parenthes*
*es
shift strictly to the right. This partial ordering can be expressed geometrical*
*ly in
terms of the following operation on tress: Let N0 denote the root node of TnI+2*
*and
let N be a node joining some left branch L and a right branch or leaf R in TnI+*
*2:
Let NL denote the node on L immediately above N. A rightshift through node N
repositions NL either at the midpoint of leaf R or midway between N and the node
immediately above it.nThenoTnIp+2 TnIq+2if there is a rightshift sequence of p*
*lanar
binary rooted trees TnIr+2 ; i.e., for each r < q; TnIr+1+2is obtained fro*
*m TnIr+2
prq
by a rightshift through some node in TnIr+2(see Figure 6).
@ @ @@ @ @ @@
@o @o o @ @ o
@o @ @ @o
@o @ o @o
  
Figure 6: A rightshift sequence of planar binary trees
Let I0 = (i01; `01); :::; (i0m; `0m) be an admissible sequence0of length m > *
*0 and
consider a node N0 distinct from the root node N0 in the PRT TnI+2: Let N denote
the node immediately below N0 and let NN00denote the branch from N to N0;
we refer to the quotient space TnI+2= TnI+2=NN0 as the (N; N0)contraction of
6 SAMSON SANEBLIDZE AND RONALD UMBLE1
TnI0+2: Now given a type I sequence J0 of length n, consider the planar binary
tree TnJ0+2and let TnJ+2be the PRT obtained from TnJ0+2by some sequence of k
successive (N; N0)contractions. The subposet YnJ+2 Yn+2 of all planar binary
rooted trees from which TnJ+2can be so obtained is exactly the poset of vertice*
*s of
the kface ak Kn+2 represented by TnJ+2: In this way, we may regard ak as the
geometric realization of YnJ+2just as we regard a kface of the standard nsimp*
*lex
as the geometric realization of a (k + 1)subset of a linearly ordered (n + 1)*
*set. In
particular, Kn+2 is the geometric realization of Yn+2.
We summarize the discussion above as a proposition:
Proposition 1. For 0 k n; there exist onetoone correspondences
ae oe
{kfaces ofKn+2} $ o(npek)foldrcompositionsaoftfaceors in first fundam*
*ental form
ae oe
$ n  Planarkrooted+trees1withnodes andn + 2 leaves
ae oeJ
$ SubposetswofhplanarebinaryrrootedetreesYn+2J is a typ*
*e I sequence of lengthn  k
3.Associahedral Sets
Definition 1.An associahedral set is a graded set
ae fi X k oe
K = Kn1;:::;nknk+3finj 0 and j=1nj = n  k + 1
n0; k1
together with face operators
n
dq(iq;`q): Kn1;:::;nknk+3! Kn1;:::;nq1;n`q1;nq`q;nq+1;:::;nkk+2
fifi o
fi1 q k; 0 iq nq; 1 `q nq; iq + `q nq + 1n0; k1
and degeneracy operators
n fi *
* o
sqj: Kn1;:::;nknk+3! Kn1;:::;nq1;nq+1;nq+1;:::;nknk+4fifi1 q k; 1 j nq *
*+ 3
n0; k1
that satisfy the following relations:
dp(ip;`p)dq(iq;`q)= dq+1(iq;`q)dp(ip;`p);p < q (1)
dq+1(iq+1;`q+1)dq(iq;`q)= dq(iqiq+1;`q)dq(iq+1;`q+1+`q);iq+1 (iq2)iq+1+ `q+1
dq+1(iq+1;`q+1)dq(iq;`q)= dq+1(iq;`q)dq(iq+1+`q;`q+1);iq < iq+1(3)
(continued)
A DIAGONAL ON THE ASSOCIAHEDRA 7
dp(i;`)sqj= sq+1jdp(i;`);p < q
dp(i;`)sqj= sqjdp(i;`);p > q
dq(i;`)sqj= sq+1j`dq(i;`);i + ` + 1 < j
dq(i;`)sqj= sqjidq(i;`1);i < j < i + ` + 2; ` > 1
dq(i;`)sqj= sq+1jdq(i1;`);i j; ` nq
dq(i;`)sqj= 1; (i; `) = (j  1; 1); 1 j < nq + 3
dq(i;`)sqj= 1; (i; `) = (j  2; 1); 1 < j nq + 3
dq(i;`)sqj= 1; (i; `) = (0; nq + 1); j = nq + 3
dq(i;`)sqj= 1; (i; `) = (1; nq + 1); j = 1
spjsqj0= sqj0spj; p 6= q
sqjsqj0= sqj0+1sqj; p = q; j j0:
Remark 1. If the compositions dp(ip;`p)dq(iq;`q): Kn1;:::;nmnm+3! Kn1;:::;nm+*
*2nm+1and
0 q0 n ;:::;n n01;:::;n0m+2
dp(ip0;`p0)d(iq0;`q0): Kn1m+3 m! Knm+1 are equal via relations (1) to (3)*
*, then
0;:::;n0
Kn1;:::;nm+2nm+1\ Kn1nm+1 m+2contains the image of these compositions. When *
*sub
0;:::;*
*n0
sequently applying face operators to an element a 2 Kn1;:::;nm+2nm+1\ Kn1nm+1*
* m+2;
where n1; : :;:nm+2 > n01; : :;:n0m+2 in the lexicographic ordering, think of *
*a 2
Kn1;:::;nm+2nm+1:
Example 1. Consider the set of all planar rooted trees
n o
K = Tn(i1;`1);:::;(im+;`m2)2 Kn1;:::;nm+1nm+2;
n0; 0mn
P m
where nq = `q  1 for 1 q m and nm+1 = n  j=1`j; and note that Knn+2=
{Tn+2} consists of a single element. When n = 2; the sets in K are pairwise
disjoint; when n = 3 however, the sets in K intersect nontrivially:
K1;0;03\ K0;1;03= {((o o o)(oo)); ((oo)(o o)o)}:
To evaluate the face operator dq(i;`)on the element Tn(i1;`1);:::;(im+;`m2); 1 *
* q m + 1;
recall that the composition dm(im ;`m.).d.1(i1;`1)is given in first fundamental*
* form.
Repeatedly apply face relations (1) to (3) to the composition dq(i;`)dm(im ;`m.*
*).d.1(i1;`1)
to obtain the composition dm+1(i0 d0m(i0 ;`0.).d.10 0in first fundamental fo*
*rm
m+1;`m+1)m m (i1;`1)
and define
i j (i0;`0);:::;(i0 ;`0 )
dq(i;`)Tn(i1;`1);:::;(im+;`m2)= Tn+11 1 m+1: m+1
Conceptually, given a parenthesization d(im ;`m.).d.(i1;`1)in first fundamental*
* form,
the face operator dq(i;`)inserts a new pair of parentheses inside the qth pair *
*while
treating the (q  1)stpair and its contents as a single indeterminant. In terms*
* of the
8 SAMSON SANEBLIDZE AND RONALD UMBLE1
tree Tn(i1;`1);:::;(im+;`m2); apply dq(i;`)by performing an (i; `)surgery at N*
*q and relabel
0;`0);:::;(i0*
* ;`0 )
the nodes as required by the first fundamental form to obtain Tn(i1+21 m*
*+1. m+1
When n = 2, the following five face operators relate T4 2 K24to the edges of *
*the
pentagon K4:
d1(0;2)(T4)7! ((o o o)o)2 K1;03
d1(1;2)(T4)7! (o (o o o))2 K1;03
d1(0;1)(T4)7! ((oo)o o) 2 K0;13
d1(1;1)(T4)7! (o (oo)o)2 K0;13
d1(2;1)(T4)7! (o o (oo))2 K0;13
There are four compositions of face operators
d1(i2;1)d1(i1;2): K24! K1;03! K0;0;02
with 0 i1; i2 1; and six compositions
d2(i2;1)d1(i1;1): K24! K0;13! K0;0;02
with 0 i1 2 and 0 i2 1; which pair off via relations (1) to (3) and relate *
*a2
to each of the five vertices of K4 as follows:
d2(0;1)d1(0;1)(T4)=d1(0;1)d1(0;2)(T4)7!(((oo)o)o)
d2(0;1)d1(1;1)(T4)=d1(1;1)d1(0;2)(T4)7!((o (oo))o)
d2(1;1)d1(1;1)(T4)=d1(0;1)d1(1;2)(T4)7!(o ((oo)o))
d2(1;1)d1(2;1)(T4)=d1(1;1)d1(1;2)(T4)7!(o (o (oo)))
d2(0;1)d1(2;1)(T4)=d2(1;1)d1(0;1)(T4)7!((oo)(oo))
These relations encode the fact that when inserting two pairs of parentheses in*
*to a
string of four variables either pair may be inserted first.
The degeneracy operator sqjacts on Kn1;:::;nknm+3by as follows: First, s1j: *
*Knn+2!
Kn+1n+3attaches a new leaf between the (j  1)stand jth, i.e.,
s1j(x1. .x.n+2)= (x1. .x.j1e xj. .x.n+2); 1 j n + 3;
where we think of e as a unit; thus for all j;
s1j(Tn+2)= Tn+3:
In general, sqjacts on Tn(i1;`1);:::;(im+;`m2)2 Kn1;:::;nknk+3by treating the *
*(q  1)stpair
of parentheses and its contents in d(im ;`m.).d.(i1;`1)as a single indeterminan*
*t and
inserting the unit e inside the qth pair between the (j  1)stand jth indetermi*
*nant.
Thus for all j;
i j
sqj Tn(i1;`1);:::;(im+;`m2)= Tn(i1;`1);:::;(iq;`q+1);:::;(im+;`m3); 1 q *
* m + 1:
It follows that K is an associahedral set.
Example 2. For n 0; let Yn+2 be the poset of all planar binary rooted trees w*
*ith
n + 2 leaves discussednabove. The set o
K = Yn(i1;`1);:::;(im+;`m2)2 Kn1;:::;nm+1nm+2;
n0; 0mn
P m
where nq = `q  1 for 1 q m and nm+1 = n  j=1`j; is an associahedral set
under face and degeneracy operators dq(i;`)and sqjdefined by formally identifyi*
*ng
A DIAGONAL ON THE ASSOCIAHEDRA 9
Yn(i1;`1);:::;(im+;`m2)with the tree Tn(i1;`1);:::;(im+;`m2)and applying the ev*
*aluation rules in
Example 1.
Example 2 is a universal example of an associahedral complex, which we now
define.
Definition 2.An associahedral complex is a poset K with distinguished finite su*
*b
posets {Kff} such that
(a) Each element of K is distinguished;
(b) For each ff; there is an ordering isomorphism
iff: Kff! Yn(i1;`1);:::;(imff;`mff)ff;
0;`0);:::;(i0 ;`0 )
(c) If Kff0 Kffand iff(Kff0)= Yn(i1ff1 mff; mffthen Kff0is distinguishe*
*d.
(d) Face and degeneracy operators on Kffare determined by the face and degen
eracy operators on iff(Kff)defined in Example 2:
Let K be an associahedral set and let b = dqm(im ;`m.).d.q2(i2;`2)dq1(i1;`1)(*
*a) for some
a 2 K: For notational simplicity, we henceforth suppress upper indices q2; : :;*
*:qm
when qj+1 = qj + 1 for all j 1; we suppress all upper indices if, in addition,
q1 = 1.
Definition 3.Let m 2: A sequence of lower indices I = (i1; `1); : :;:(im ; `mi*
*)s
admissible whenever the composition of face operators dqm(im ;`m.).d.q1(i1;`1)i*
*s defined.
The sequence I is a type I (resp. type II) sequence if I is admissible and ik *
*ik+1
(resp. ik ik+1 + `k+1) for 1 k < m. The empty sequence (m = 0) and
sequences of length 1 (m = 1) are both type I and II sequences. A composition of
face operators d(im ;`m.).d.(i2;`2)ds(i1;`1)has first (resp. second) fundamenta*
*l form
if (i1; `1); : :;:(im ; `mi)s a type I (resp. type II) sequence. When m = 0; *
*the
composition d(im ;`m.).d.(i2;`2)ds(i1;`1)is defined to be the identity. An elem*
*ent b =
dqm(im ;`m.).d.q2(i2;`2)dq1(i1;`1)(a) is expressed in first (resp. second) fun*
*damental form
as a face of a if
dqm . .d.q2dq1= (d . .d.dsm).(.d.. .d.ds2)(d . .d.ds1);
where s1 < s2 < . .<.sm and each composition d(isj;`sj).d.(.i2;`2)dsj(i1;`1)has*
* first
(resp. second) fundamental form.
Obviously, every composition of face operators can be uniquely transformed into
first or second fundamental form by successive applications of face relations (*
*1) to
(3).
Let C*(Kn+2) denote the cellular chains on Kn+2. For 0 m n; let Im =
(i1; `1); (i2; `2); : :;:(im ; `m ) be a type I sequence and let dIm = d(im ;`m*
*.).d.(i1;`1):
Then
TnIm+2= dIm(Tn+2) 2 Cnm (Kn+2)
and n o
TnIm+2Im is a type I sequence
0mn
defines a system of generators for C*(Kn+2) .
10 SAMSON SANEBLIDZE AND RONALD UMBLE1
Definition 4.For m 0; let Im = (i1; `1); (i2; `2); : :;:(im ; `m ) be a type *
*I se
quence. If 1 r m + 1; the sign of the face b = dr(i;`)(TnIm+2) 2 Cnm1 (Kn+2*
*) is
defined to be
P r1
sgn (b)=  (1)e(b); where e (b)= r + (i + 1)` + j=1`j:
Remark 2. When applying face relations (1) to (3) in Definition 1 to cellular
chains in C*(Kn+2) , only (3) requires the sign (1)(`q+1)(`q+1+1)for commuting
factors.
Example 3. The set K defined in Example 1 generates the associahedral set of
cellular chains {C*(Kn+2) }n0 . According to Definition 4, the cellular boundary
of Tn+2 2 Cn (Kn+2)is given by
X (i+1)`
@Tn+2 = (1) d(i;`)(Tn+2):
1`n
0in`+1
Example 4. Let X be a topological space. Define the singular associahedral com
plex SingK X as follows: Let
K n ;:::;n
(]Sing X)n1k+3 =k{continuous mapsKn1+2x . .x.Knk+2 ! X};
P k
where j=1nj = n  k + 1; nj 0 and Kn1+2x . .x.Knk+2 is a Cartesian product
of associahedra. Let
K
SingK X = ]SingX=~
K
denote the orbit set of the symmetric group action on ]SingX given by the permu
tation isomorphisms
oe : Kn1+2x . .x.Knk+2 ! Koe1(n1)+2x . .x.Koe1(nk)+2;
where oe 2 Sk; k 2. Let
ffiq(iq;`q): Kn1+2x . .x.Knq1+2x K`q+1x Knq`q+2x Knq+1+2x . .x.Knk+2
! Kn1+2x . .x.Knq+2x . .K.nk+2
be the inclusion and let
fiqi: Kn1+2x . .x.Knq+3x . .K.nk+2! Kn1+2x . .x.Knq+2x . .x.Knk+2
be the projection (cf. [17]). Then for f 2 (SingK X)n1;:::;nkn+2; define
dq(iq;`q): (SingK X)n1;:::;nkn+2! (SingK X)n1;:::;nq1;`q1;nq`q;nq+1;::*
*:nkn+1
and
sqi: (SingK X)n1;:::;nkn+2! (SingK X)n1;:::;nq1;nq+1;nq+1;:::nkn+3
as compositions
dq(iq;`q)(f) = f O ffiq(iq;`q)andsqi(f) = fiqiO f:
It is easy to check that (SingK X; d(iq;`q); sqi) is an associahedral set:
A DIAGONAL ON THE ASSOCIAHEDRA 11
The singular associahedral complex SingK X determines the singular (co)homo
logy of X in the following way: Form the chain complex (C*(SingK X); d) of
SingK X and consider the quotient
CN*(SingK X) = C*(SingK X)=D;
where D is the subcomplex of C*(SingK X) generated by the degenerate elements
of SingK X: The composition of canonical projections
Kn1+2x . .x.Knk+2 ! In1 x . .x.Ink = In ! n
induces a sequence of chain maps
C*(SingX) ! C*(SingIX) ! C*(SingK X) ! CN*(SingK X);
and consequently, a natural isomorphism H*(X) H*(CN*(SingK X); d): As in the
cubical setting (but unlike the simplicial setting), normalized chains are requ*
*ired
to obtain the singular homology of X. In the discussion that follows below, we
construct a diagonal on the associahedra, which is compatible under the projec
tions above with the AlexanderWhitney diagonal on the standard simplex. Thus
H*(CN (SingK X); d) determines the singular cohomology ring of X as well:
4. A Diagonal on C*(Kn)
We begin with an overview of the geometric ideas involved. Let 0 q n and
let Inq be a type I sequence. The qdimensional generator aq = TnInq+2is asso*
*ciated
with a face of Kn+2 corresponding to n + 2 indeterminants with n q + 1 pairs of
parentheses. Identify aq with its associated face of Kn+2 and consider the mini*
*mal
and maximal vertices aminqand amaxqof aq. Define the primitive terms of Tn+2 to
be
Tnmin+2 Tn+2 + Tn+2 Tnmax+2:
Let 0 < p < p + q = n and consider distinct pfaces b and b0 of Tn+2: Say that
b b0if there is a path of pfaces from b to b0along which parentheses shift st*
*rictly
to the right. Now given a qdimensional face aq of Tn+2 such that aminq6= Tnmin*
*+2;
there is a unique path of pfaces b1 b2 . . .br with minimal length such that
Tnmin+2= bmin1and aminq= bmaxr: Up to sign, we define the nonprimitive terms of
Tn+2 to be
X
bj aq:
To visualize this, consider the edge d(1;2)(T4)2 C1(K4) whose minimal vertex
is the point 1; 1_2(see Figure 7): The edges d(0;2)(T4) d(1;1)(T4)form a path *
*of
minimal length from (0; 0)to 1; 1_2. Consequently, T4 contains the nonprimiti*
*ve
terms d(0;2) d(1;1) d(1;2)(T4 T4) :
12 SAMSON SANEBLIDZE AND RONALD UMBLE1
d(2;1)(T4) T4max
o_________________NNIo
 
 
  d(1;2)(T4)
 
 
d(0;1)(T4) T4 No
  d(1;1)(T4)
 
 
o_______________I_o
T4min d(0;2)(T4)
Figure 7: Edge paths from T4minto T4max.
Precisely, for T2 2 C*(K2) define T2 = T2 T2; inductively, assume that the
map : C*(Ki+2) ! C*(Ki+2) C*(Ki+2) has been defined for all i < n: For
Tn+2 2 Cn (Kn+2)define
X ffl
Tn+2 = (1) d(i0q;`0q).d.(.i01;`01)(Tn+2) d(ip;`p).d.(.i1;`1)(Tn+2)
0pp+q=n
where
Xq Xp
ffl = i0j(`0j+ 1) + (ik + k + p + 1)`k;
j=1 k=1
and lower indices (i1; `1); : :;:(ip; `p); (i01;;`01):;:i:0q;r`0qange over all*
* solutions
of the following system of inequalities:
8 9
>>>1 ij < ij1 n + 1 (1) >>
>>> >>>
>< 1 `j n + 1  ij `(j1) (2) >>=
(4.1) n o ;
>>>0 i0k min i0r; itk `0(o0(t))(3)>>
>>> o0(tk)>>
>: >>;
1 `0k= fflk  i0k `0(k1) (4) 1jp
1kq
where
{ffl1 < . .<.fflq}= {1; : :;:n}\ {i1; : :;:ip};
ffl0 = `0 = `00= ip+1 = i0q+1= 0;
i0 = i00= fflq+1 = `(p+1)= `0(q+1)= n + 1;
P u
`(u)= j=0`j for 0 u p + 1;
P u
`0(u)= k=0`0kfor 0 u q + 1;
(4.2) tu = min r  ir + `(r) `(o(u))> fflu;> ir
o (u)= max {r  ir fflu}; and
o0(u)= max {r  fflr iu}:
A DIAGONAL ON THE ASSOCIAHEDRA 13
Extend multiplicatively to all of C*(Kn+2), using the fact that the cells of K*
*n+2
are products of cells Ki+2with i < n.
Note that righthand and lefthand factors in each component of Tn+2 are
expressed in first and second fundamental form, respectively. In particular, t*
*he
terms given by the extremes p = 0 and p = n are the primitive terms of Tn+2 :
d(0;1).d.(.0;1) 1 + 1 d(1;1).d.(.n;1)(Tn+2 Tn+2):
P ffl
The sign in Tn+2 = (1)fflb a is the product of five signs: (1) = sgn (b).
sgn (b0). sgn(b0; a1) . sgn (a1). sgn (a); where the face b0 is obtained from b*
* by
keeping "'s but all i0k= 0 (i.e., `0kis replaced by `0k+ i0k i0k1); the face *
*a1 is
obtained from a by keeping ir's but all `r = 1 and sgn(b0; a1) is the sign of t*
*he
shuffle {ip < . .<.i1; ffl1 < ffl2 < . .<.fflq}: Geometrically, b0 and a1 lie o*
*n orthogonal
faces of the cube In and are uniquely defined by the property that the canonical
cellural projection Kn+2 ! In maps b0 7! x1; :::; xffl11; 0; :::; xfflq1; 0; *
*:::; xn and
a1 7! x1; :::; xip1; 1; :::; xi11; 1; :::; xn.
Example 5. For T4 2 C2(K4) we obtain by direct calculation:
T4 = d(0;1)d(0;1) 1 + 1 d(1;1)d(2;1)+ d(0;2) d(1;1)
o
+d(0;2) d(1;2)+ d(1;1) d(1;2) d(0;1) d(2;1)(T4 T4):
A proof of our main result, stated as the following theorem, appears in the app*
*endix:
Theorem 1. For each n 0; the map : C*(Kn+2) ! C*(Kn+2) C*(Kn+2)
defined above is a chain map.
Identify the sequence of cellular chain complexes {C*(Kn)}n2 with the A1 oper*
*ad
A1 [11]. Since is extended multiplicatively on decomposable faces, we immedi
ately obtain the following interesting fact:
Corollary 1.The sequence of chain maps
{ : C*(Kn) ! C*(Kn) C*(Kn)} n2
induces a morphism of operads
A1  ! A1 A1 :
5. Tensor Products in the A1 Category
The notion of an A1 algebra also appears in Stasheff's seminal papers [17]. *
*An
A1 algebra is a dga in which the associative law holds up to homotopy, the ho
motopies between the various associations are homotopic, the homotopies between
these homotopies are homotopic, and so on. Although A1 algebras first appeared
in topology as the singular chain complex on the loop space of a connected CW 
complex, they have since assumed their rightful place as fundamental structures
in algebra [10], [15], topology [3], [7], [18], and mathematical physics [4], [*
*5], [12],
[13], [20], [21]. Furthermore, Stasheff's idea carries over to homotopy version*
*s of
14 SAMSON SANEBLIDZE AND RONALD UMBLE1
coalgebras [14], [16], [19] and Lie algebras [6], and one can deform a classica*
*l dga,
dgc or dg Lie algebra to the corresponding homotopy version in a standard way.
An Rmodule A equipped simultaneously with an A1 algebra and an A1 
coalgebra structure is an "A1 Hopf algebra" if the two A1 structures are suff*
*i
ciently compatible. Our definition of an A1 Hopf algebra, which appears in the
sequel, requires an independently interesting tensor product in the A1 categor*
*y.
In this concluding section, we apply the diagonal defined above to obtain this
tensor product in maximal generality. We note that a special case was given by
J. Smith [16] for certain objects with a richer structure than we have here. We
also mention that Lada and Markl [6] defined a A1 tensor product structure on a
construct different from the tensor product of graded Rmodules.
We adopt the following notation and conventions: The symbol R denotes a
commutative ring with unity; all Rmodules are assumed_to be Zgraded. The
reduced Rmodule V=V0 of a connected V is denoted by V . All tensor products
and Hom's are defined over R and all maps are Rmodule maps unless indicated
otherwise. The symbol 1 : V ! V denotes the identity map; the suspension
and desuspension maps, which shift dimension by +1 and 1, are denoted by "
and #, respectively.P We let V n = V . . .V with n > 0 factors and define
V 0 = R; then T V = n0 V n : If A is an Ralgebra (resp., Rcoalgebra) , then
T aA (respectively, T cA) denotes the tensor algebra (resp., the tensor coalgeb*
*ra) of
A: Given a Rmodules V1; : :;:Vn and a permutation oe 2 Sn, define the permutat*
*ion
isomorphism oe : V1 . . .Vn ! Voe1(1) . . .Voe1(n)by oe(x1. .x.n) =
xoe1(1).x.o.e1(n); where the sign is determined by the Mac Lane commutation r*
*ule
[9] to which we strictly adhere. In particular, oem : (V1 V2)m ! V1m V2m is
the permutation isomorphism induced by oem = (1 3 . . .(2m  1)2 4 . .2.m): If
f : V p ! V q is a map, we let fi;npi= 1i f 1npi : V n ! V np+q ;
where 0 i n  p: The abbreviations dgm, dga,and dgc stand for differential
graded Rmodule, dg Ralgebra and dg Rcoalgebra, respectively.
We begin with a discussion of A1 (co)algebras paying particular attention to
the signs; in structural compatibility considerations, sign issues become criti*
*cal.
Let A be a connected graded Rmodule and consider a sequence of maps {'k 2
Homk2 Ak ; A }k1 : For each k and n 1; linearly extend 'k to An via
nkX
'ki;nki: An ! Ank+1 ;
i=0
and consider the induced map of degree 1 given by
nkX __n __nk+1
" 'k #k i;nki: " A ! " A :
i=0
__
Let eBA = T c " A and define a map dBeA: eBA ! eBA of degree 1 by
X
(5.1) dBeA= " 'k #k i;nki:
1kn
0ink
A DIAGONAL ON THE ASSOCIAHEDRA 15
The identities (1)[n=2]"n #n = 1n and [n=2]+[(n + k)=2] nk +[k=2](mod 2)
imply that
X [(nk)=2]+i(k+1)
(5.2) dBeA= (1) "nk+1 'ki;nki#n :
1kn
0ink
Definition 5.(A; 'n)n1 is an A1 algebra if d2eBA= 0: The maps {'n} in an
A1 algebra are called higher homotopies.
Proposition 2. Let (A; 'n)n1 be an A1 algebra. The higher homotopies 'k
satisfy the following quadratic relations for n 1:
X `(i+1)
(5.3) (1) 'n`'`+1i;n`1i= 0:
0`n1
0in`1
Proof: For n 1;
X [(nk)=2]+i(k+1)
0 = (1) " 'nk+1 #nk+1 "nk+1 'ki;nki#n
1kn
0ink
X nk+i(k+1)
= (1) 'nk1'ki;nki
1kn
0ink
X `(i+1)
=  (1)n (1) 'n`'`+1i;n`1i:
0`n1
0in`1
It is easy to prove that
i j
Proposition 3. Given an A1 algebra (A; 'n)n1, eBA; dBeAis a dgc.
Definition 6.Leti(A; 'n)n1jbe an A1 algebra. The tilde bar construction on A
is the dgc eBA; dBeA:
Definition 7.Let A and C be A1 algebras. A chain map f = f1 : A ! C is a
map of A1 algebras if there exists a family of higher homotopies {fk 2 Homk1
Ak ; C }k2 such that
iP jn
ef= P n1 k1 " fk #k : eBA ! eBC
is a dgc map.
Dually, consider a sequence of maps { k 2 Homk2 A; Ak }k1 : For each k
and n 1; linearly extend each k to An via
n1X
ki;n1i: An ! An+k1 ;
i=0
16 SAMSON SANEBLIDZE AND RONALD UMBLE1
and consider the induced map of degree 1 given by
n1X __n __n+k1
#k k "i;n1i: # A ! # A :
i=0
__
Let eA = T a # A and define a map deA : eA ! eA of degree 1 by
X
deA = #k k "i;n1i;
n;k1
0in1
which can be rewritten as
X [n=2]+i(k+1)+k(n+1)
(5.4) deA = (1) #n+k1 ki;n1i"n :
n;k1
0in1
Definition 8.(A; n)n1 is an A1 coalgebra if d2eA= 0: The maps { n} in an
A1 coalgebra are called higher homotopies.
Proposition 4. Let (A; n)n1 be an A1 coalgebra. The higher homotopies k
satisfy the following quadratic relations for n 1:
X `(n+i+1)
(5.5) (1) `+1i;n`1i n` = 0:
0`n1
0in`1
Proof: The proof is similar to the proof of Proposition 2 and is omitted.
Again, it is easy to prove that
i j
Proposition 5. Given an A1 coalgebra (A; n)n1, eA; deA is a dga.
Definition 9.Leti(A; n)n1jbe an A1 coalgebra. The tilde cobar construction
on A is the dga eA; deA :
Definition 10.Let A and B be A1 coalgebras. A chain map g = g1 : A ! B is a
map of A1 coalgebras if there exists a family of higher homotopies gk 2 Homk1
A; Bk }k2 such that
P iP k k jn
(5.6) eg= n1 k1 # g " : eA ! eB;
is a dga map.
The essential ingredient in an A1 (co)algebra is the given family of higher *
*ho
motopies. Given such a family, one is free to independently reverse the directi*
*on
of each homotopy, i.e., its sign, and subsequently alter the signs in the quadr*
*atic
relations. Nevertheless, the signs in the relations relate directly to the init*
*ial given
family. The "simplest" signs in the quadratic relations in an A1 algebra appear
when the tilde bar differential is the sum of the given higher homotopies, i.e.*
*, the
direction of each higher homotopy is unaltered as in (5.1) above. Consequently,
the simplest signs appear in (5.3) above. On the other hand, a straightforward
A DIAGONAL ON THE ASSOCIAHEDRA 17
calculation shows that the "simplest" signs appear in the quadratic relations f*
*or an
A1 coalgebra when n is replaced by (1)[(n1)=2] n; n 1; i.e., the direction*
* of
every third and fourth homotopy is reversed. The choices one makes will depend
on the application; for us the appropriate choices are as in (5.3) and (5.5).
Let (A; 'n)n1 be an A1 algebra with structure relations as in (5.3). For each
n 2; associate Tn 2 Cn2 (Kn)with the operation 'n via
(5.7) Tn 7! (1)n'n
and d(i;`)(Tn)2 Cn3 (Kn)with the quadratic composition 'n`'`+1i;n`1i; i.e.,
(5.8) d(i;`)(Tn)7! 'n`'`+1i;n`1i:
Then (5.7) and (5.8) induce a chain map
* n
(5.9) iA : A1  ! Hom A ; A n2
representing the A1 algebra structure on A.
Dually, if (A; n)n1 is an A1 coalgebra with structure relations as in (5.5)*
*, the
associations
Tn 7! n
and
d(i;`)(Tn)7! `+1i;n`1i n`
induce a chain map
* n
(5.10) A : A1  ! Hom A; A n2
representing the A1 coalgebra structure on A:
Definition 11.Let A and B be A1 algebras with respective A1 algebra structures
iA and iB : The tensor product A B is the A1 algebra with structure
*
iAB (Tn)= (oen)(iA iB )Tn n2 ;
where (oen)*= Hom(oen; A B). Similarly, if A and B are A1 coalgebras with
respective structures A and B ; A B is the A1 coalgebra with structure
1
AB (Tn)= oen *(A B ) Tn n2 ;
where oe1n*= Hom A B; oe1n:
Proposition 6. Let A and B be A1 algebras with respective A1 algebra structur*
*es
iA and iB ; let A B be the A1 algebra with structure iAB : Then the following
diagram commutes for each n 2 :
C*(Kn) iAB! Hom((A B)n ; A B)
# " (oen)*
C*(Kn) C*(Kn) i! Hom(An ; A) Hom (Bn ; B)
Ai B
18 SAMSON SANEBLIDZE AND RONALD UMBLE1
Dually, let A and B be A1 coalgebras with respective A1 coalgebra structures A
and B ; let A B be the A1 coalgebra with structure AB : Then the following
diagram commutes for each n 2 :
C*(Kn) AB! Hom(A B; (A B)n )
# " (oe1n)*
C*(Kn) C*(Kn) ! Hom(A; An ) Hom (B; Bn )
A B
Proof: This is an immediate consequence of Definition 11 and the canonical isom*
*or
phisms Hom(An ; A) Hom (Bn ; B) Hom(An Bn ; A B) and
Hom(A; An ) Hom (B; Bn ) Hom(A B; An Bn ):
Example 6. Given an A1 coalgebra A with operations { n}n1 ; we have the fol
lowing operations on A A:
1AA = 1 1 + 1 1
2AA = oe2 2 2 ;
3AA = oe3 20 20 3 + 3 21 20;
4AA = oe4 20 20 20 4 + 4 22 21 20+ 30 20 21 30
+ 30 20 31 20+ 21 30 31 20 20 30 22 30
.. .
. ..
The stage is now set for the sequel in which we introduce the notion of an A1*
* 
Hopf algebra in full generality. We shall observe that the homology of a loop s*
*pace
and the double cobar construction admit canonical A1 Hopf algebra structures.
6.Appendix
In this appendix we prove that the diagonal defined in Section 4 above is a
chain map. We begin with some preliminaries. It will be convenient to rewrite f*
*ace
relation (3) as follows:
dq+1(iq+1;`q+1)dq(iq;`q)= dq+1(iq`q+1;`q)dq(iq+1;`q+1); iq > iq+1+ `q*
*+1: (30)
Definition 12.For 1 k m; the kth lefttransfer ok`of a composition d(im ;`m )
. .d.(i2;`2)d(i1;`1)in first fundamental form is one of the following compositi*
*ons:
(a) If ik+1 + `k+1 ik, apply face relation(2) todk+1dk and obtain
. .d.k(ikik+1;`k)dk(ik+1;`k+1+`k).;. .
then successively apply face relation (1) todj+2dj forj = k; k + 1; : :;:m*
*  2;
and obtain
ok`= dk(ikik+1;`k)dm1(im.;`m.).dk+1(ik+2;`k+2)dk(ik+1;`k+1+`k).d.1.(i*
*1;`1):
A DIAGONAL ON THE ASSOCIAHEDRA 19
(b) If ik+1+`k+1 < ik iq+1+`(q+1)`(k)for some smallest integerq > k; suc
cessively apply face relation (30) todj+1dj forj = k; k + 1; : :;:q; and o*
*btain
. .d.q+2(iq+2;`q+2)dq+1(ik+`(k)`(q+1);`k)dq(iq+1;`q+1).d.k.(ik+1;`k+1)d*
*(ik1;`k1).:. .
Apply face relation (2) todq+1dq; then successively apply face relation (1*
*) to
dj+2dj forj = q; q + 1; : :;:m  2; and obtain
ok`= dq(i;`k)dm1(im.;`m.).dk(ik+1;`k+1)d(ik1;`k1).d.(.i1;`1);
where i = ik  iq+1+ `(k) `(q):
(c) Otherwise, successively apply face relation (30)todj+1dj forj = k; k+1; : *
*:;:m
1; and obtain
ok`= dm(i;`k)dm1(im.;`m.).dk(ik+1;`k+1)d(ik1;`k1).d.(.i1;`1)
where i = ik + `(k) `(m).
Definition 13.For 1 k m; the kth righttransfer okrof a composition d(im ;`m )
. .d.(i2;`2)d(i1;`1)in first fundamental form is one of the following compositi*
*ons:
(a) If ip + `(p) ik + `(k)< ip1 + `(p1)for some greatest integer1 < p k;
successively apply face relation (30)to dj+1dj for j = p  1; : :;:2; 1; j*
* =
p; : :;:3; 2; : :;: j = k  1; k  2; : :;:k  (p  1).Then apply face re*
*lation
(2) todj+1dj forj = k  p; : :;:2; 1 and obtain
okr= d(im ;`m.).d.(ik+1;`k+1)dk(ip1`;`p1)
. .d.kp+2(i1`;`1)dkp(ik1ik;`k1).d.1.(ipik;`p)d1(i*
*k;`);
where ` = `(k) `(p1).
(b) Otherwise, successively apply face relation(2) todj+1dj forj = k  1;
k  2; : :;:2; 1; and obtain
okr= d(im ;`m.).d.(ik+1;`k+1)dk1(ik1ik;`k1).d.1.(i1ik;`1)d1(ik;`(k*
*)):
Note that if I = (i1; `1); : :;:(im ; `mi)s a type I sequence and a = dI(Tn+2*
*) 2
Cnm (Kn+2) ; then for each k; the kth right transfer okr(Tn+2)expresses a in
first fundamental form as a face of some (n  1)face b of Tn+2: The expressions
o1r(Tn+2); : :;:omr(Tn+2) determine the m distinct (n  1)faces b containing a.
There are analogous left and right transfers for compositions in second funda
mental form.
Definition 14.For 1 k m; the kth lefttransfer ok`of a composition d(im ;`m )
. .d.(i2;`2)d(i1;`1)in second fundamental form is one of the following composit*
*ions:
(a) If ik+1 ik; apply face relation(2) todk+1dk, then successively apply face
relation(1) todj+2dj forj = k; k + 1; : :;:m  2; and obtain
ok`= dk(ikik+1;`k)dm1(im.;`m.).dk+1(ik+2;`k+2)dk(ik+1;`k+1+`k).d.1.(i*
*1;`1):
20 SAMSON SANEBLIDZE AND RONALD UMBLE1
(b) If ik+1 > ik iq+1 for some smallest integerq > k; successively apply face
relation(3) todj+1dj forj = k; k + 1; : :;:q: Apply face relation(2) to
dq+1dq; then successively apply face relation(1) todj+2dj forj = q; q+1; :*
* :;:m
2; and obtain
ok`= dq(ikiq+1;`k)dm1(im.;`m.).dq+1(iq+2;`q+2)dq(iq+1;`q+1+`k)dq1(i*
*q+`k;`q)
. .d.k(ik+1+`k;`k+1)d(ik1;`k1).d.(.i1;`1):
(c) Otherwise, successively apply face relation(3)todj+1dj forj = k; k + 1;
: :;:m  1; and obtain
ok`= dm(ik;`k)dm1(im +`k;`m.).d.k+1(ik+2+`k;`k+2)dk(ik+1+`k;`k+1)d(ik1;*
*`k1).d.(.i1;`1):
Definition 15.For 1 k m; the kth righttransfer okrof a composition d(im ;`m )
. .d.(i2;`2)d(i1;`1)in second fundamental form is one of the following composit*
*ions:
(a) Ifip1 < ik ip for some greatest integer1 < p k; successively apply
face relation(3)todj+1dj for j = p  1; : :;:2; 1; j = p; : :;:3; 2; : :;*
*: j =
k  1; k  2; : :;:k  (p  1). Then apply face relation(2) todj+1dj forj*
* =
k  p; : :;:2; 1 and obtain
okr= d(im ;`m.).d.(ik+1;`k+1)dk(ip1;`p1).d.k.p+2(i1;`1)dkp(ik1i*
*k;`k1)
. .d.1(ipik;`p)d1(ik+`(p1);`(k)`(p1)):
(b) Otherwise, successively apply face relation(2) todj+1dj forj = k  1; : :*
*;:
2; 1; and obtain:
okr= d(im ;`m.).d.(ik+1;`k+1)dk(ik1ik;`k1).d.1.(i1ik;`1)d1(ik;`(k)):
Once again, if I = (i1; `1); : :;:(im ; `mi)s a type II sequence and a = dI(T*
*n+2) 2
Cnm (Kn+2) ; then for each k; the kthrighttransfer okr(Tn+2)expresses a in se*
*cond
fundamental form as a face of some (n  1)face b; the expressions o1r(Tn+2); :*
* :;:
omr(Tn+2)determine the m distinct (n  1)faces b containing a. Thus two (n  m*
*)
faces a1 and a2 expressed in first and second fundamental form, respectively, a*
*re
contained in the same (n  1)face b if and only if there exist right transfers*
* okjr
such that aj = okjr(Tn+2); j = 1; 2; and b = d(i;`)(Tn+2); where d(i;`)is the r*
*ight
most face operator common to ok1rand ok2r: We state this formally in the follow*
*ing
lemma:
Lemma 1. Let 0 m1; m2 n and assume that a1 = d(im1;`m1).d.(.i1;`1)(Tn+2)
and a2 = d(i0m2;`0m2).d.(.i01;`01)(Tn+2)are expressed in first and second funda*
*men
tal form, respectively. Then a1 and a2 are contained in the same (n  1)face
d(i;`)(Tn+2) if and only if there exist integers kj mj and greatest integers 1
pj < kj for j = 1; 2, such that
i0p2< i0k2;
ik1+ `(k1) `(p1)< ip1
A DIAGONAL ON THE ASSOCIAHEDRA 21
and
i = ik1= i0k2+ `0(p2);
` = `(k1) `(p1)= `0(k2) `0(p2):
Consider a solution ((i1; `1); : :;:(ip; `p); (i01; `01); : :;:(i0q; `0q)) of*
* system (4.1) and
its related (p; q)shuffle {ip < . .<.i1; ffl1 < ffl2 < . .<.fflq}: Given 1 k *
* q + 1;
let k1 = k  1; kj+1 = o0 tkj for j 1 and note that kj+1 < kj for all j: For
0 m < `0k; consider the following selection algorithm:
if k = 1 then z = p + 1  i01 m
else z = n + 2; j = 0
repeat
j j + 1
if i0kj< i0k+ m then iz = fflkj i0kj+ i0k+ m
if itkj `0(kj+1)= i0k+ m then z = tkj
until z < n + 2
endif
It will be clear from the proof of Lemma 2 below that the selection algorithm
eventually terminates.
Example 7. Let p = q = 4 and consider the following solution of system (4.1):
((7; 1); (6; 1); (4; 2); (2; 3); (0; 1); (1;:1); (1; 2); (0; 4))
Then t1 = 5; t2 = 4; t3 = 3; t4 = 4 and the selection algorithm produces the
following:
____________________________
_k__12_3_3_4_4_4_4_
_m_00_0_1_0_1_2_3_
_z__55_4_3_5_4_2_1_
The key to our proof that is a chain map is given by our next lemma.
Lemma 2. Given 1 k q + 1 and 0 m < `0k; let z be the integer given by the
selection algorithm.
(a) z > o(k)
(b) iz + `(z) `(o(k)) fflk:
(c) i0k+ m = iz  `0(o0(z));
(d) If o0(z) < r < k; then i0k+ m i0r;
n o
(e) If i0k+ m > min i0r; itk `0(o0(t)); then
o0(tk) iz + `(z);`(r)
22 SAMSON SANEBLIDZE AND RONALD UMBLE1
(e.3)o0(z) = maxr p + 1  ffl1 = o (1): For k > 1;
first note that itkj< fflkj< fflk io(k)for all j 1; by the definition of tkj *
*in (4.2):
So the result follows whenever iz itkjfor some j 1: If i0k1< i0k+ m; then
iz = fflk1+i0k+mi0k1< fflk1+i0k+`0ki0k1= fflk. If i0kj< i0k+m for some j *
* 2
and i0k+m i0kr itkr`0(kr+1)for all r < j; where the later follows from inequa*
*lity
(3) of system (4.1), then iz = fflkj+ i0k+ m  i0kj< fflkj+ itkj1 `0(kj) i0k*
*j= itkj1:
(b) When k = 1; indices 0 = ip+1 < ip < . .<.ip+2ffl1are consecutive; hence
ir + `(r)= ir1 + `(r1)+ `r  1 ir1 + `(r1)for p + 3  ffl1 r p + 1:
Since z p + 2  ffl1 we have iz + `(z) `(o(1)) ip+2ffl1+ `(p+2ffl1) `(p+1*
*ffl1)=
ffl11+`p+2ffl1 ffl1: So consider k > 1: If i0k1< i0k+m; then fflk1 < iz < f*
*flk < io(k)
so that fflk = iz + z  o (k) iz + `(z) `(o(k)): If i0k1 i0k+ m and z = tk1;*
* then
o (k  1) o (k)= fflk  fflk1  1 so that iz + `(z) `(o(k))= iz + `(z) `(o(*
*k1))+
`(o(k1))`(o(k))> fflk1+fflkfflk11 = fflk1 by the definition of tk1 in (*
*4.2). If
i0k2< i0k+m then fflk2< iz < itk1< fflk1so that `(z)`(tk1) ztk1= itk1iz; whe*
*re
equality holds iff `tk1+1= . .=.`z = 1; hence iz+ `(z) `(o(k))= iz+ `(z) `(tk*
*1)+
`(tk1) `(o(k)) iz+ itk1 iz+ `(tk1) `(o(k))> fflk  1 by the previous calcula*
*tion.
If i0k2 i0k+ m and z = tk2; then iz+ `(z) `(o(k1))= iz+ `(z) `(o(k2))+ `(o(k2*
*))
`(o(k1))> fflk2+ `(o(k2)) `(o(k1)) itk1+ `(tk1) `(o(k2))+ `(o(k2)) `(o(k1))>*
* fflk1
since tk1 < tk2 implies itk1+ `(tk1) `(o(k2)) fflk2 by the definition of tk2: *
*Thus
iz + `(z) `(o(k))= iz + `(z) `(o(k1))+ `(o(k1)) `(o(k))> fflk  1: Note that*
* in
general, itkj+ `(tkj) `(o(k1))> fflk1 so that itkj+ `(tkj) `(o(k)) fflk for a*
*ll j 1:
So if necessary, continue in like manner until the desired z is found at which *
*point
the result follows.
(c) This result follows immediately from the choice of z:
(d) Note that k > 1. If i0k1< i0k+ m, then o0(z)= k  1 and the case is vacuo*
*us.
So assume that i0k+ m i0k1: If either i0k+ m = itk1 `0(k2)or i0k2< i0k+ m; th*
*en
o0(z)= o0(tk1)and i0k1 i0rfor o0(z)< r < k: Otherwise, i0k+ m min i0k1; i0k2:
If either i0k+ m = itk2 `0(k3)or i0k3< i0k+ m; then o0(z)= o0(tk2)and i0k2 i0r
for o0(z)< r k2: But i0k1 i0rfor k2 = o0(tk1)< r < k; so the desiredninequalit*
*y o
holds for o0(z)< r < k: Continue in this manner until i0k+ m min i0k1; : :;:i*
*0kj
for some j; at which point the conclusion follows.
(e) If k = 1; o0(z)= 0 so that i01+m = iz and iz+`(z) ffl1: Now i01+m > it1by
assumption, hence z < t1: But t1 is the smallest integer r such that ir + `(r)>*
* ffl1;
therefore iz + `(z)= ffl1; by (b). Let k > 1 and suppose that z tk: Then iz i*
*tk;
in which case o0(z)= o0(tk): But by (c), i0k+ m = iz  `0(o0(z)) itk `0(o0(tk)*
*)and
by (d), i0k+ m i0rfor o0(tk)< r < k; contradicting the hypothesis. Hence z < t*
*k:
But tk is the smallest possible integer such that itk+ `(tk) `(o(k))> fflk; so*
* (e.1)
follows from by (b). Results (e.2) and (e.3) are obvious.
Proof_of_Theorem_1:_
A DIAGONAL ON THE ASSOCIAHEDRA 23
Let n 0: We show that if u v is a component of d2 (Tn+2) or d(Tn+2);
there is a corresponding component that cancels it, in which case (d2 d)(Tn+2)
= 0: Let a0 a be a component of Tn+2: We consider various cases.
Case_I._Consider a component dr(i;`)1 of d1; where i+` `0r; i 0; 1 ` < `0r
and 1 r q + 1: Reduce b0= dr(i;`)(a0) to an expression in second fundamental
form, i.e., if 1 r q; successively apply relation (1) to dj+1dj for j = q; ::*
*:; r + 1;
apply (2) to replace dr(i;`)dr(i0r;`0r)by dr+1(i0r;`0r`)dr(i0r+i;`); then succ*
*essively apply (3) to
dj+1dj for either j = r  1; :::; fi if i + ` < `0ror for j = q; :::; fi if r *
*= q + 1; where
fi is the greatest integer such that 1 fi r and i + ` i0fi1. Then for i + `*
* < `0r;
1 r q + 1 we have
b0= dq+1(i0q;`0q).d.r.+2(i0r+1;`0r+1)dr+1(i0r;`0r`)dr(i0r1`;`0r1)
. .d.fi+1(i0fi`;`0fi)dfi(i0r+i;`)dfi1(i0fi1;`0fi1).d.*
*1.(i01;`01)(Tn+2);
and for i + ` = `0r; 1 r q + 1 we have
b0= dq+1(i0q;`0q).d.r.+2(i0r+1;`0r+1)dr+1(i0r;`0r`)dr(i0r+i;`)dr1(i0r1;*
*`0r1).d.1.(i01;`01)(Tn+2):
Case_Ia._Let i + ` < `0rand i0r+ i + ` > i0fi1: As in the case of a0 above,
the inequalities for lower indices in an expression of b0 as a face of Tn+2 in *
*first
fundamental form are strict, but whose number now is increased by one. Obviously
we will have that
fflfi= i0r+ i + `0(fi1)+ ` = ik
for certain 1 k p: Apply the kth lefttransfer to obtain
a = ok`(Tn+2) = d"k(";"`)(b);
where "k= ff  1; "= ik  iff `(ff1) `(k); "`= `k and ff is the smallest in*
*teger
k ff p + 1 with iff+ `(ff) `(k) ik: Then b0 b is a component of Tn+2 as
well.
Case_Ib._Let i + ` < `0rand i0r+ i + ` = i0fi1: Apply the (fi  1)thlefttra*
*nsfer to
obtain
b0= ofi1`(Tn+2) = dfi1(";"`)(c0);
where "= ` and "`= `0fi1: Then c0 a is also a component of Tn+2.
Case_Ic._Let i + ` = `0r; there are two subcases:
Subcase_i._If 1 r q and i0r+ i min(itr `0(o0(tr)); i0j); o0(tr) < j < r; *
*apply
the (r + 1)thlefttransfer to obtain
b0= or+1`(Tn+2) = d"r(";"`)(c0);
where "r= ff; "= i0r i0ff; "`= `0r ` and ff is the smallest integer r ff p*
* + 1
with i0ff i0r: Although certain i0's are increased by i; while `0ris reduced by*
* i to
obtain `; it is straightforward to check that c0 a is also a component of Tn+2.
Subcase_ii._Suppose that 1 r q+1 and i0r+i > min(itr`0(o0(tr)); i0j); o0(t*
*r) <
j < r: In view of Lemma 2 (with k = r and m = i) we have
fflr = iz + `(z) `(o(r))andi0r+ i = iz  `0(o0(z));
from which we also establish the equality
`(z) `(o(r))= `0(r1)+ `  `0(o0(z)):
24 SAMSON SANEBLIDZE AND RONALD UMBLE1
The hypotheses of Lemma 1 are satisfied by setting k1 = z; p1 = o(r) and k2 =
r; p2 = o0(z). Hence, b0 a is a component of d(";"`)(Tn+2) with "= iz and
"`= `(z) `(o(r)):
Case_II._Consider a component 1 dr(i;`)of 1 d; where i + ` `r; i 0;
1 ` < `r; and 1 r p + 1: Reduce b = dr(i;`)(a) to the first fundamental form,
i.e., if 1 r p; successively apply relation (1) to dj+1dj for j = p; :::; r +*
* 1; and
apply (2) to replace dr(i;`)dr(ir;`r)by dr+1(ir;`r`)dr(ir+i;`): Then if i > 0;*
* successively
apply (3) to dj+1dj; for j = r  1; :::; fi; or if r = p + 1; successively appl*
*y (3)
to dj+1dj for j = p; :::; fi; where fi is the greatest integer with 1 fi r and
ir+ i + `r1+ ::: + `fi ifi1: Then for fi = r; we have ir+ i ir1; and for i *
*> 0;
1 r p + 1;
b= dp+1(ip;`p).d.r.+2(ir+1;`r+1)dr+1(ir;`r`)dr(ir1;`r1)
. .d.fi+1(ifi;`fi)dfi(";`)dfi1(ifi1;`fi1).d.1.(i1;`*
*1)(Tn+2);
where "= ir + i + `(r1) `(fi1); and
b = dp(ip1;`p1).d.r.+2(ir+1;`r+1)dr+1(ir;`r`)dr(ir;`)dr1(i r1;`r1).d.*
*1.(i1;`1)(Tn+2);
for i = 0; 1 r p + 1:
Case_IIa._Let i > 0 and ir+i+`(r1)`(fi1)< ifi1: Once again, the inequalit*
*ies
for the lower indices in the expression of b in first fundamental are strict in*
*equalities
as they were for a but whose number now is increased by one. Obviously we will
have that
ifi= ir + i + `(r1) `(fi1)= fflk
for certain 1 k q: Apply the kth lefttransfer to obtain
a0= ok`(Tn+2) = d"k(";"`)(b0);
where "k= ff  1; "= i0k i0ff; "`= `0kand ff is the smallest integer k ff q*
* + 1
with i0ff i0k: Then b0 b is a component of Tn+2 as well.
Case_IIb._Let i > 0 and ir + i + `(r1) `(fi1)= ifi1: Apply the (fi  1)th
lefttransfer to obtain
b = ofi1`(Tn+2) = dfi1(";"`)(c);
where "= 0 and "`= `fi1: Then a0 c is also a component of Tn+2.
Case_IIc._Let i = 0; there are two subcases:
Subcase_i._If 1 r p and no integer 1 k q exists with r = tk; then
fflk = ir + ` + `(r1) `(o(k))and i0k= ir  `0(o0(r)):
Apply the (r + 1)thlefttransfer to obtain
b = or+1`(Tn+2) = d"r(";"`)(c);
where "r= ff; "= ir  iff+ `(ff1) `(r); "`= `r  ` and ff is the smallest in*
*teger
r < ff p + 1 such that iff+ `(ff) `(r) ir; namely, ff = r + 1 or ff = to0(r):
Now the required inequality for the i0k's could conceivably be violated for k >*
* o0(r);
but this is not so since it is easy to see that: (a) if r is not realized as tk*
* for some
k > o0(r); then each z with ff < z < r is so; and (b) if r = tk for some k > o0*
*(r);
while fflk = ir+ ` + `(r1) `(o(k)); then ff (and not r) serves as tk for indi*
*ces of face
A DIAGONAL ON THE ASSOCIAHEDRA 25
operators in expressions of a and c; moreover,nfor either ff =or + 1 or ff = to*
*0(r)(in
which case i0k i0o0(r)), one has i0k min i0j; iff `0(o0(ff))so that a0 c *
*is
o0(ff)
Department of Mathematics, Millersville University of Pennsylvania, Millersvi*
*lle,
PA. 17551
Email address: Ron.Umble@Millersville.edu