THE EULER CHARACTERISTIC OF THE WHITEHEAD AUTOMORPHISM GROUP OF A FREE PRODUCT 6 0 0 2 CRAIGJENSEN1,JONMCCAMMOND2,ANDJOHNMEIER3 n a Abstract. Acombinatorialsummationidentityoverthelatticeoflabelledhy- J pertreesisestablishedthatallowsonetogainconcreteinformationontheEuler 8 characteristics ofvariousautomorphismgroups offreeproducts ofgroups. In 2 particular, we establish formulae for the Euler characteristics of: the group of Whitehead automorphisms Wh(∗ni=1Gi) when the Gi are of finite homo- ] logical type; Aut(∗ni=1Gi) and Out(∗ni=1Gi) when the Gi are finite; and the R palindromicautomorphismgroupsoffiniterankfreegroups. G . h t 1. Introduction a m Let G = G ∗···∗G , where the G are non-trivial groups. There are various 1 n i [ subgroups of Aut(G) and Out(G) (such as the Whitehead automorphism group) 1 thatareonlydefinedwithrespecttoaspecifiedfreeproductdecompositionofG. In v thisarticlewecalculatetheEulercharacteristicsofseveralsuchgroups. Postponing 4 definitions for the moment, our main result is the following. 9 6 Theorem A. If G=G1∗···∗Gn is a freeproduct of groups where χ(G) is defined, 1 then the Euler characteristic of the group of outer Whitehead automorphisms is 0 χ(OWh(G))=χ(G)n−2 =[χ(G )+···+χ(G )−(n−1)]n−2 . 6 1 n 0 Asaconsequence,theEulercharacteristicofthegroupofWhiteheadautomorphisms h/ is χ(Wh(G))=χ(G)n−1. t a A natural situation to consider is when each group Gi is finite. In this case the m vcd of Aut(G) is n−1 (independently established in [KV93] and [MM96]) and : Wh(G) is a finite index subgroup of Aut(G). Theorem A thus implies: v Xi Theorem B. If G = G1∗···∗Gn is a free product of finite groups and Ω ⊂ Σn is the subgroup of the symmetric group given by permuting isomorphic groups G , i r then the Euler characteristics of the Fouxe-Rabinovitch automorphism group of G, a the full automorphism group of G and the outer automorphism group of G are: n χ(FR(G)) = χ(G)n−1 |Inn(G )| i i=1 Y n χ(Aut(G)) = χ(G)n−1|Ω|−1 |Out(G )|−1 i i=1 Yn χ(Out(G)) = χ(G)n−2|Ω|−1 |Out(G )|−1 i i=1 Y 1PartiallysupportedbyLouisianaBoardofRegents RCScontract no.LEQSF-RD-A-39 2PartiallysupportedbyNSFgrantno.DMS-0101506 3PartiallysupportedbyanAMSCentennial ResearchFellowship 1 χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 2 The automorphism groups mentioned in these theorems are defined as follows. Definition 1.1 (Groupsofautomorphisms). LetG ∗···∗G be a freeproduct of 1 n groups. As usual, we use Aut(G) to denote the full automorphism group of G and Out(G) for the group of outer automorphisms. If g ∈G \{1} let αgi denote the i i j automorphism described by g g ∈G where k 6=j αgi(g)= k . j ggi g ∈Gk where k =j (cid:26) The Fouxe-Rabinovitch group FR(G) is the subgroup of Aut(G) generated by {αgi | i 6= j}. The group of Whitehead automorphisms is generated by all the αgi j j (including the possibility that i = j). In general, the symmetric automorphisms of a free product consist of those automorphisms that send each factor group to a conjugate of a (possibly different) factor. It is well-known that the group Wh(G) is the kernel of the map f : ΣAut(G) → Out( G ) and FR(G) is the kernel i i of the map g : ΣAut(G) → Aut( G ), where ΣAut(G) denotes the group of i i Q symmetric automorphisms. Q A quick chasing of definitions shows that the images of FR(G) and Wh(G) in Out(G) are the same — OFR(G)=OWh(G) — andso OFR(G) will notappear again. (For more background on these definitions see [MM96], especially page 48.) A palindromic automorphism of a free group F =F(a ,...,a ) is an automor- n 1 n phismsendingeachgeneratora toapalindromicword. Theelementarypalindromic i automorphisms are those which send each a to a palindrome of odd length with i a as its centermost letter. Lastly, the pure palindromic automorphisms are those i whichsendeacha to anodd palindrome with either a ora−1 in the center. After i i i identifying these automorphisms of F with ones of ∗n Z , we are able to prove: n i=0 2 Theorem C. If F is a free group of rank n, then the Euler characteristics of the n elementary palindromic automorphism group of F , the pure palindromic automor- n phism group of F , and the palindromic automorphism group of F are: n n χ(EΠA(F )) = (1−n)n−1 n (1−n)n−1 χ(PΠA(F )) = n 2n (1−n)n−1 χ(ΠA(F )) = n 2n·n! Eventhoughour statedtheorems are relatedto groupcohomology,the underly- ingargumentsareprimarilycombinatorial. Inthe nextsectionwegivebackground information on polynomial identities and a particularly useful identity relating a multi-variablepolynomialwiththenumberofrootedtreesandplantedforests. Sec- tion3istheheartofthecombinatorialwork,whereweusethepolynomialidentities to establish a number of partition identities and ultimately an identity involving a summation of particular weights over the set of hypertrees (Theorem 3.11). Then in Section 4, the notion of an Euler characteristicof a groupis reviewed, the space constructed by McCullough and Miller is outlined, and an approachto calculating the Euler characteristic of OWh(G) is sketched. In Section 5, the hypertree iden- tity is used to complete the calculationandwe complete the proofs of Theorems A and B, as well as give some concrete examples. In Section 6 we turn to the group of palindromic automorphisms of F and establish Theorem C. n χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 3 Although the current ordering of the sections in the paper presents results in the order in which they are proven, an alternate — possibly more conceptual and motivated — ordering would be §1⇒§4⇒§5⇒§6⇒§3⇒§2 . Sections 4–6 show how the Euler characteristic calculations can be derived from a particularweightedsumoverhypertrees. This hypertree identity is reducedto two weighted sums over the set of partitions in §3, and finally, the necessary partition identities are established using a polynomial identity described in §2. 2. Polynomials and Trees In this section we record some well-known polynomial identities that we need later in the article. The firsttwo identities were discoveredby Niels Abel. In order to make them easier to state we introduce the following function. Definition 2.1 (An interesting basis). For each non-negative integer k let h (x) k denotethepolynomialx(x+k)k−1. Notethatwhenk =0theexpressionx(x+0)−1 isnotquitethesameastheconstantpolynomial1sinceitisundefinedatx=0,but this situation can be remedied by explicitly defining h (x) = 1. The polynomials 0 {h (x)} formabasisfortheringofpolynomialsinx,becausethedegreeofh (x) k k≥0 k isk andthus thereisexactlyonepolynomialofeachdegree. Asaconsequence,the “monomials”ofthe formh (x )·h (x )···h (x )witheachk ≥0formabasis k1 1 k2 2 kn n i for the ring of polynomials in commuting variables x ,x ,...,x . 1 2 n Lemma 2.2 (Abel’s identities). For each non-negative integer n, the two polyno- mial identities listed below are valid. n (1) (x+y+n)n = h (x)·(y+j)j i i i+j=n(cid:18) (cid:19) X n (2) h (x+y)= h (x)·h (y) n i j i i+j=n(cid:18) (cid:19) X These identities are readily established by induction (see for example [Ro84]). Thesecondidentitylistedhasanobviousmulti-variablegeneralizationusingmulti- nomial coefficients. Remark2.3. Theexponentialgeneratingfunctionforh (x)isthefunction[GKP94] n calls (E (z))x. The generating function equivalent of Lemma 2.2 is the fact that 1 (E (z))x·(E (z))y =(E (z))x+y. 1 1 1 Definition 2.4 (Trees and forests). A forest is a simplicial graph with no cycles and a tree is a connected forest. All of the trees and forests considered here have distinguishable vertices. In particular, if [n]:={1,...,n} then it is common prac- ticetoconsiderthetreesorforeststhatcanbedescribedusing[n]asthevertexset. Atreeorforestwithadistinguishedvertexselectedineachconnectedcomponentis saidto be rooted orplanted, respectively. In a plantedforestwe considereachedge asorientedawayfromthe rootinits component. Therooted degree ofa vertexi in a planted forestis the number ofedges starting at i. Notice that the rooteddegree of a vertex is one less than its valence unless that vertex happens to be a root, in which case the two numbers are equal. The degree sequence of a planted forest χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 4 on [n] is the n-tuple of rooted degrees δ (in order) for i ∈ [n], and the associated i degree sequence monomial is xδ1xδ2···xδn. See Figure 1 for an example. 1 2 n 1 2 10 3 5 4 7 6 9 8 Figure1. Thisplantedforeston[10]hasroots1,2and10. Itsde- gree sequence is (0,1,2,0,1,0,0,0,0,3)and the associated degree sequence monomial is x x2x x3 . 2 3 5 10 Theorem 2.5 (A forest identity, Theorem 5.3.4 in [St99]). Let δ = (δ ,...,δ ) ∈ 1 n Nn with δ =n−k. The number N(δ) of planted forests σ on the vertex set [n] i (necessarily with k components) with ordered degree sequence ∆(σ)=δ is given by P n−1 n−k N(δ)= . k−1 δ ,δ ,...,δ (cid:18) (cid:19)(cid:18) 1 2 n(cid:19) Equivalently, n−1 xdeg1···xdegn = (x +···+x )n−k, 1 n k−1 1 n σ (cid:18) (cid:19) X where σ ranges over all planted forests on [n] with k components. As an illustration, consider the 6 planted forests on [3]:={1,2,3} with exactly 2 components. Each such forest contains a single edge and a unique vertex with a nonzero degree so that the final sum in the theorem is 2(x +x +x ) as claimed. 1 2 3 3. Partitions and Hypertrees In this section we establish several identities involving summations over sets of partitionsandhypertrees. OurEulercharacteristiccomputationsultimatelyinvolve sumsovertheposetoflabelledhypertrees,aposetwhoseinternalstructureisquite similar to the well-studied poset of partitions. After certain polynomial identities overthe poset of partitions areestablished inthe first subsection,we convertthem into hypertree identities in the second subsection. 3.1. Partition Identities. Definition 3.1 (Partitions). Recall that a partition σ of [n] is a collection of pairwise disjoint subsets of [n] whose union is [n]. These subsets (i.e. the elements of σ) are called blocks. The collection of all partitions of [n] is denoted Π and the n subcollection of all partitions with exactly k blocks is denoted Πk. n Definition 3.2 (Partition sums). For each i∈{1,...,n}, let w be a fixed choice i of a symmetric polynomial in i variables. These functions can be used to define weights on the blocks of a partition as follows. Given a partition σ of [n] and an χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 5 elementτ inσ ofsizeiweevaluatew atthevariablesx ,j ∈τ. Thecorresponding i j partition weight function is given by taking the product over all the blocks in the partitionσ. Thepartition lattice function f(n,k)isthesumofthepartitionweight functions over all partitions of [n] with exactly k blocks. One particular symmetric polynomial occurs often enough below so as to merit a specialnotation. For any setτ ⊂[n] define s as the sumof the variablesx over τ i all i∈τ. For example, s =x +x +x . {1,2,4} 1 2 4 Example 3.3. Let n=3 and k =2. If the symmetric polynomials s are used as τ block weights, then the partition lattice function f(3,2) is x (x +x )+x (x + 1 2 3 2 1 x )+x (x +x )=2(x x +x x +x x ). 3 3 1 2 1 2 1 3 2 3 Noticethatitisclearfromthedefinitionthatf(n,k)isitselfalwaysasymmetric function on n variables, but it is not at all clear whether one should expect closed form formulae for f(n,k) for a particular choice of block weights. Using the forest identityfromthe previoussection,itisrelativelyeasytoestablishatleastonesuch summation. Lemma 3.4 (1st partition identity). The partition weight function f(n,k) that weights each block τ by (s )|τ|−1 has closed form n−1 (s )n−k. In other words, τ k−1 [n] (cid:0) (cid:1) n−1 f(n,k)= (s )|τ|−1 = (s )n−k.  τ  k−1 [n] σX∈Πkn τ∈BlYocks(σ) (cid:18) (cid:19)   Proof. Using the forest identity (Theorem 2.5), the weight on block τ is equal to a sum of degree sequence monomials for all rooted trees on the underlying set τ. Replacingeachblockweightwiththissummationoverrootedtreesrevealsthatthe left hand side is actually a sum of the degree sequence monomials over all planted forests with exactly k components. A second use of Theorem 2.5 completes the proof. (cid:3) By specializing eachvariablex to 1, we obtain the followingresult as animme- i diate corollary. Corollary3.5(2ndpartitionidentity). Thepartitionweightfunctionf(n,k)which weights each block τ by |τ||τ|−1 has closed form n−1 nn−k. In other words, k−1 (cid:0) (cid:1) n−1 f(n,k)= |τ||τ|−1 = nn−k.   k−1 σX∈Πkn τ∈BlYocks(σ) (cid:18) (cid:19)   A second corollary uses the alternative basis described in Definition 2.1. Recall that h (x) denotes the polynomial x(x + k)k−1 so that if τ = {1,2,4,5} then k h (s )=(x +x +x +x )(x +x +x +x +3)2. |τ|−1 τ 1 2 4 5 1 2 4 5 Corollary3.6(3rdpartitionidentity). Thepartition weightfunctionf(n,k)which weights each block τ by h (s ) has closed form n−1 h (s ). In other words, |τ|−1 τ k−1 n−k [n] (cid:0) (cid:1) n−1 f(n,k)= h (s ) = h (s ).  |τ|−1 τ  k−1 n−k [n] σX∈Πkn τ∈BlYocks(σ) (cid:18) (cid:19)   χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 6 Proof. Consider the linear operator T on R[x ,...,x ] (viewed as an R-vector 1 n space) that sends the monomial xδ11···xδnn to the “monomial” hδ1(x1)···hδn(xn). If both sides of the equation in the statement of Lemma 3.4 are expanded using theusualbinomialtheorem,thenthefactthatthecoefficientsofthecorresponding monomials on each side are equal is essentially the content of the first part of the forest identity from Theorem 2.5. If each monomial on each side is now replaced with the corresponding h-monomial (i.e. its image under T) — without changing thecoefficientsused—thentheh-versionofthebinomialtheorem(Lemma2.2)can be used to recombine each side so as to establish the equality claimed above. (cid:3) 3.2. Hypertree Identities. Definition 3.7 (Hypertrees and hyperforests). A hypergraph Γ is an ordered pair (V,E) where V is the set of vertices and E is a collection of subsets of V—called hyperedges—each containing at least two elements. A walk in a hypergraph Γ is a sequence v ,e ,v ,...,v ,e ,v where for all i, v ∈ V, e ∈ E and for each 0 1 1 n−1 n n i i e , {v ,v } ⊂ e . A hypergraph is connected if every pair of vertices is joined i i−1 i i by a walk. A simple cycle is a walk that contains at least two edges, all of the e are distinct and all of the v are distinct except v = v . A hypergraph with i i 0 n no simple cycles is a hyperforest and a connected hyperforest is a hypertree. Note that the no simple cycle condition implies that distinct edges in Γ have at most onevertexincommon. Allofthe hypertreesandhyperforestsconsideredhere have distinguishable vertices. In particular, it is common practice to mainly consider the hypertrees or hyperforests that can be described using [n] as the vertex set. Examples of hypertrees on [n] are shown in Figures 2 and 3, where hyperedges are indicated by polygons. Manyoftheconceptspreviouslydefinedfortreesandforestshavenaturalexten- sions to hypertrees and hyperforests. For example, a hypertree or hyperforestwith a distinguished vertex selected in each connected component is said to be rooted or planted, respectively. In a planted hyperforest it is common practice to consider each hyperedge to be “oriented” by gravity,away from the root of the component. In this case the “orientation”of a hyperedge distinguishes between the unique ver- tex closest to the root and all of the remaining vertices in the hyperedge. We say that the closest vertex is where the hyperedge starts and the others are where it ends. The rooted degree of a vertex i in a planted hyperforest is the number of hyperedges starting at i. Notice that the rooted degree of a vertex is one less than its valence (i.e. the number of hyperedges that contain i) unless that vertex hap- pens to be a root, in which case the two numbers are equal. Finally, to establish notation, let PHFk denote the set of all planted hyperforests on [n] with exactly n k components and let RHT (=PHF1) denote the set of all rooted hypertrees on n n [n]. Weestablishapairofidentitiesinvolvingsummationsofsymmetricpolynomials over planted hyperforests and (unrooted) hypertrees, respectively. We begin by defining a particular weight function for rooted hyperforests that is similar to the block weights and partition lattice functions consider above. Definition 3.8 (Weight ofa planted hyperforest). Letτ be a planted hyperforest. Define the weight of an edge inτ as(e−1)e−2 whereeis its size. Define the weight of the vertex i as xdegi where degi is its rooted degree. The weight of τ is the i χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 7 product of all of its edge and vertex weights. Thus, Weight(τ)= (e−1)e−2 · xdegi .    i  e∈EdgYeSizes(τ) i∈VerYtices(τ)     Themaincombinatorialresultinthisarticleisanassertionthatthesumoverall planted hyperforests of their weights is equal to a very simple symmetric function. This formula is the key step in establishing Theorem A. Theorem 3.9 (A hyperforest identity). When the weight of a planted hyperforest is defined as above, the sum of these weights over all planted hyperforests on [n] with exactly k components is a function of the linear symmetric function. More specifically, n−1 (3) Weight(τ)= h (s ) k−1 n−k [n] τ∈XPHFkn (cid:18) (cid:19) which specializes to (4) Weight(τ)=h (s )=s (s +n)n−1 n [n+1] [n+1] [n+1] τ∈RXHTn+1 when summing these weights over rooted hypertrees on [n+1]. Proof. The proof is by induction on the ordered pairs (n,k), ordered lexicographi- cally. Since the base case (1,1) is easily checked, suppose that the result has been established for all ordered pairs less than (n,k). The inductive step splits into two cases depending on whether k = 1 or k > 1. When k > 1, then the sum on the lefthandside canbe rearrangedaccordingto the partitionof[n] determinedby the connected components of the hyperforest under consideration. Once a partition σ inΠk hasbeenfixed,thehyperforestsassociatedtoitarefoundbypickingarooted n hypertree on each block of σ. Because these choices can be made independent of one another, and because the weight of a planted hyperforest is the product of the weights of its rooted hypertrees, the sum of the hyperforest weights over the hy- perforests associated with this particular partition is a product of sums that only focusononeblockofσ atatime. Inaddition,ifτ isablockofσ thentheinductive hypothesis can be applied to the sum of rooted hypertree weights over each all rooted hypertrees on τ since the size of τ must be strictly less than n. Thus we have Weight(µ)= h (s ) , |τ|−1 τ µ∈XPHFkn σX∈Πknτ∈BYlocksσ which is equal to n−1 h (s ) by the 3rd partition identity, Corollary 3.6. k−1 n−k [n] When k = 1, the sum on the lefthand side is only over rooted hypertrees and (cid:0) (cid:1) the approach is slightly different. In order for the algebraic manipulations to be easier to follow, we consider the case (n+1,1) rather than (n,1). If µ is a rooted hypertree on [n+1], then there is a planted hyperforest on n vertices associated withµwhichcanbefoundbyremovingitsrootandallofthehyperedgescontaining it. The resulting components are naturally rooted by selecting the unique vertex in each that was in a common hyperedge with the original root. (See Figure 2.) As in the previous case, we proceed by rearranging a sum and applying the inductive hypothesis. Consider the portion of the lefthand side of equation 3 that χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 8 12 1 5 6 8 3 7 2 10 9 11 4 Figure 2. A rooted hypertree on [12] with its associated planted hyperforest on [11]. One can pass from the hyperforest back to the hypertree using the partition of {1,3,5,6,8} indicated by the lightly colored boxes. only sums over those rooted hypertrees on [n+1] that have the vertex n+1 as their root, the root has rooted degree exactly i, and the number of connected components in the planted forest on [n] found by removing the root and all its hyperedges is exactly k. The collection of all rooted hypertrees having all three properties can be found as follows. First, pick an arbitrary planted forest µ with exactlykcomponentsonthevertexset[n]. Next,pickapartitionσofthekrootsof µthathasexactlyiblocks. Finally,foreachblockinσ,addahyperedgecontaining theappropriaterootsofµtogetherwiththevertexn+1. (Thisprocessisillustrated in Figure 2 where k = 5 and the two blocks of the partition are indicated by the lightly colored loops.) Because of the independence of the choices involved, the sum of the hypertree weights over this restricted set of rooted hypertrees can be rewritten as follows. |τ||τ|−1 Weight(µ) xi    n+1 σX∈Πikτ∈BlYocks(σ) µ∈XPHFkn    Thefirstfactoristhecontributionoftheedgeweightsofthehyperedgescontaining the root (there is a slight shift since the size of the block in σ is one less than the size of the edge containing the root), the third factor is the contribution of the vertex weight of the root itself, and the second factor is the contribution of all of the other vertex and edge weights combined. By the 2nd partition identity, from Corollary3.5,thefirstfactorisequalto k−1 kk−i,andbytheinductivehypothesis i−1 the second factor is equal to n−1 h (s ). Using the fact that k−1 n−k(cid:0) [n](cid:1) (cid:0) (cid:1) k−1 n−1 n−1 n−1 n−i = = , i−1 k−1 i−1,k−i,n−k i−1 k−i (cid:18) (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19) χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 9 the sum of these weights can be rewritten as n−1 n−i kk−ih (s )xi . i−1 k−i n−k [n] n+1 (cid:18) (cid:19)(cid:18) (cid:19) A similar formula holds when any other vertex is selected as root. Finally, it only remainsto eliminate the dependence ofthis sumonk, i,andthe choice of a root vertex. One form of Abel’s identity, Equation 1, is n−i h (s )kk−i =(s +n)n−i, k−i n−k [n] [n] k (cid:18) (cid:19) X where we have substituted s for x, i for y, n−i for n, n−k for i, and k−i [n] for j. Thus, summing over all possible values of k we find that the sum of the weights over all hypertrees with root vertex n+1 and root degree i is equal to n−1 (s +n)n−ixi . Summingoverallpossiblevaluesofi,factoringoutasingle i−1 [n] n+1 x and applying the binomialtheorem we find that the sum of the weights of all n+1 (cid:0) (cid:1) hypertreeswithrootn+1isx (s +n+x )n−1 =x (s +n)n−1. Finally, n+1 [n] n+1 n+1 [n+1] summing over the possible choices of the root vertex gives s (s +n)n−1 [n+1] [n+1] which is precisely h (s ) as desired. This completes the inductive step when n [n+1] k =1 and the proof. (cid:3) As is often the case,we canuse the identity establishedfor rootedhypertrees to establish a similar identity for unrooted hypertrees. Definition3.10(Weightofahyperforest). Ifτ isan(unplanted)hyperforest,then the weight of an edge in τ is as before (i.e. (e−1)e−2 where e is its size) but the weight of the vertex i is now xval(i)−1 where val(i) is its valence. The edge weight i of τ is the product of the weights of its edges, E-Weight(τ)= (e−1)(e−2). e∈EdgYeSizes(τ) The vertex weight of τ is the product of the weights of its vertices, V-Weight(τ)=xval(1)−1xval(2)−1···xval(n)−1, 1 2 n whichiscloselyrelatedtothe“degreesequencemonomial”ofaplantedforest. The weight of τ is Weight(τ)=E-Weight(τ)·V-Weight(τ), so it is still the product of τ’s edge and vertex weights. Notice that these definitions almost completely agree with those given in Defi- nition 3.8. In particular, if τ is a rooted hypertree on [n] rooted at vertex i, then its weightwhen viewedasa rootedhypertree is x times its weightwhenviewedas i an unrooted hypertree. This is because val(j)−1=degj except at the root. As a consequence, if τ is a hypertree and τ is the hypertree τ with root vertex i, then i the sum of the rooted weights of the τ is s times the weight of τ. i [n] Theorem 3.11 (A hypertree identity). When the weight of a hypertree is defined as above, the sum of these weights over all hypertrees on [n+1] is a function of the linear symmetric function. More specifically, (5) Weight(τ)=(s +n)n−1 [n+1] τ∈HXTn+1 χ(Wh(G1∗···∗Gn))=χ(G1∗···∗Gn)n−1 10 Proof. By the remark made above, the sum of the rooted weights over all rooted hypertrees on [n+1] is equal to s times the sum of the weights over all (un- [n+1] rooted)hypertrees on [n+1]. The formula now follows fromthe secondformula in the statement of Theorem 3.9. (cid:3) Here are two small examples that illustrate the equality. Example 3.12 (Low dimensional cases). When n = 2, the poset HT has four 3 elements and the four terms on the lefthand side are 1·x , 1·x , 1·x and 2·1. 1 2 3 Thus the total is x +x +x +2 as predicted by the righthand side. 1 2 3 There are four types of hypertrees in HT , and 29 elements total in the poset. 4 There is one element consisting of a single hyperedge (Type A); twelve elements consisting of two hyperedges (Type B); twelve elements that are simplicial arcs (Type C); and four elements that are simplicial trees containing a central trivalent vertex(TypeD).(ThesearedrawninFigure3of[MM04].) Startingonthelefthand side,wehavethattheelementoftypeAcontributes32,theelementsoftypeB add 6(x +x +x +x ), the elements of type C add 2(x x +x x +x x +x x + 1 2 3 4 1 2 1 3 1 4 2 3 x x +x x ) and the elements of type D add x2+x2+x2+x2. So for n=3 the 2 4 3 4 1 2 3 4 total is (x +x +x +x +3)2 as expected. 1 2 3 4 4. Euler, McCullough and Miller Our Euler characteristic results follow from a computation using the action of outer Whitehead automorphism groups on certain contractible complexes intro- duced by McCullough and Miller [MM96]. We recall relevant facts about Euler characteristics of groups and about these McCullough-Miller complexes. 4.1. Euler characteristics. Becausethehomotopytypeofanasphericalcomplex is determined by its fundamental group, it makes sense to define the Euler char- acteristic of a group G as the Euler characteristic of any finite K(G,1). However, a group does not have to be of finite type to have a well defined Euler character- istic. A group G is of finite homological type if G has finite vcd and for every i and every G-module M that is finitely generatedas an abelian group,H (G,M) is i finitely generated. This holds, for example, if G is VFL, that is, has a finite index subgroup H where Z admits a finite free resolution as a trivial ZH-module. The Euler characteristic can be defined for any group of finite homological type. To complete the proofs of Theorems A, B, and C, we need some basic facts about Euler characteristics of groups. The following results are parts (b) and (d) of Theorem 7.3 in Chapter IX of [Br94]. Theorem 4.1. Let G be a group of finite homological type. 1. If H is a subgroup of finite index in G then χ(H)=χ(G)·[G:H]. 2. If 1→K →G→Q→1 is a short exact sequence of groups (with K and Q of finite homological type) then χ(G)=χ(K)·χ(Q). Our approach to computing the Euler characteristics of Whitehead automor- phism groups is via the standard formula for equivariant Euler characteristics (see [Br74] and §IX.7 of [Br94]).