Homology, Homotopy and Applications, vol.7(1), 2005, pp.77–85

THE COMPLEX OF WORDS AND NAKAOKA STABILITY

MORITZ C. KERZ

(communicated by Charles Weibel)

Abstract We give a new simple proof of the exactness of the complex of injective words and use it to prove Nakaoka’s homology stability for symmetric groups. The methods are generalized to show acyclicity in low degrees for the complex of words in ”general position”.

Introduction

In this paper we show the vanishing of homology for various complexes of words and give an elementary, self-contained proof of Nakaoka stability (Theorem 2):

H_{m}(Σ_{n−1}, ℤ) = H_{m}(Σ_{n}, ℤ)

for n/2 > m where Σ_{n} denotes the permutation group of n elements. An elementary proof of this fact has not been available in the literature. In the first section the complex C_{∗}(m) of abelian groups is studied which in degree n is freely generated by injective words of length n. The alphabet consists of m letters. The complex C_{∗}(m) has the only non vanishing homology in degree m (Theorem 1). This is a result of F.D. Farmer [3] who connected it to properties of the associated poset of injective words and its CW-complex. Then, considering the action of the permutation group on the alphabet, a hyperhomology argument is used to deduce Nakaoka stability. In the second section – independent from the first – more general complexes of words are shown to have vanishing homology in low degrees. The proof is analogous to Theorem 1. A very general setting is used but the essential application is to the complex of words consisting of vectors in general position over a finite field. In fact this complex is shown to become exact in some fixed degree and fixed dimension of the vector space if only the base field has enough elements. This could be of interest for example for Suslin’s GL-stability [8] which works up to now only over infinite fields.

Received March 22, 2005, revised May 4, 2005; published on June 7, 2005. 2000 Mathematics Subject Classification: 18G35, 20J06. Key words and phrases: Complex of words, Homology Stability. \begin{matrix}c \\ ◯ \end{matrix} 2005, Moritz C. Kerz. Permission to copy for private use granted.

1. An elementary proof of Nakaoka stability

In this section we are concerned with the complex of injective words, denoted C_{∗}(m) (m ∈ N), and its homology. For n > 0 define C_{n}(m) as the abelian group freely generated by the injective words of length n with alphabet m = {1, 2, …, m}. Injective word means no element of our alphabet may appear twice in it. Set C_{0}(m) = ℤ. In what follows words are written in brackets, e.g. (1, 2) + (3, 1) ∈ C_{2}(3). The differential d : C_{n}(m) → C_{n−1}(m) for n > 1 is defined by

d(x_{1}, …, x_{n}) = ∑_{j=1}^{n}(−1)^{j+1}(x_{1}, …, x̂_{j}, …, x_{n}) ,

x_{1}, …, x_{n} ∈ m. Similarly d : C_{1}(m) → C_{0}(m) maps (x) to 1.

In the theory of posets and their associated CW-complexes the following theorem has a nice interpretation. The homology of C_{∗}(m) is equal to the simplicial homology of the (shellable) poset of injective words. Shellability reduces the simplicial homology groups to those of a wedge of m-spheres. We refer to [1], [3], [7] for exact definitions and statements.

Our proof of Theorem 1 is new and rather straightforward compared to Farmer’s original elementary proof.

Theorem 1. (Farmer [3]) The homology of C_{∗}(m) vanishes except in degree m.

We have to introduce some notations which will be used throughout the paper. An element c ∈ C_{n}(m) is called a term, if there exists an N ∈ ℤ and x_{1}, …, x_{n} ∈ {1, …, m} with c = N (x_{1}, …, x_{n}). As C_{∗}(m) has a canonical basis all our sum decompositions correspond to partitions of the basis. We also speak about the appearance of numbers in a an element of C_{n}(m). For example 2 appears in (2, 3) + 4 (5, 1) but 4 does not. Although our complex C_{∗}(m) has no obvious cup product, we have a partially defined product. If c ∈ C_{n}(m), c′ ∈ C_{l}(m) are terms, c = N (x_{1}, … x_{n}), c = M (x′_{1}, …, x′_{l}), we define c c′ := N M (x_{1}, …, x_{n}, x′_{1}, … x′_{l}) if the numbers x_{1}, …, x_{n}, x′_{1}, … x′_{l} are distinct. This construction extends bilinearly to arbitrary c ∈ C_{n}(m), c′ ∈ C_{l}(m) for which the numbers appearing in both of them are distinct. There is a Leibniz rule for c ∈ C_{n}(m) and c′ ∈ C_{l}(m) satisfying the latter condition.

d(c c′) = d(c) c′ + (−1)^{n}c d(c′)

Proof of Theorem 1. The exactness in degree 0 is clear. For the rest we use induction on m. For the case m = 2 we have to check that

C_{2}(2) ⟶ C_{1}(2) ⟶ ℤ

is exact. But ker(d : C_{1}(2) → ℤ) is generated by elements of the form

(x) − (x′) = d (x, x′)

with x ≠ x′.

For the induction step we use a straightforward lemma.

Lemma 1. If we have a number x ∈ {1, …, m} which does not appear in a cycle c ∈ C_{n}(m), it is a boundary.

Proof. According to the Leibniz rule c = c + (x) d(c) = d((x) c), since d(c) = 0.□

Given an arbitrary cycle c of degree n < m we have to show that in order to apply the lemma we can eliminate a number from c by adding boundaries. Therefore we will push a fixed number x ∈ {1, …, m} to the right until it vanishes from the cycle. If x appears somewhere in the cycle at the first entry, write

c = ∑_{j}(x) c_{j} + c′

with terms c_{j} and c′ does not have x at the first entry. To each c_{j} choose a number x_{j} ∈ {1, …, m}, x_{j} ≠ x which does not appear in c_{j}.

c − d(∑_{j}(x_{j}) (x) c_{j}) = c′ + ∑_{j}(x_{j}) c_{j} − (x_{j}) (x) dc_{j}

Now x does not appear at the first entry anymore. The next steps until the vanishing of x are similar. Suppose x does not appear at the first i > 0 entries of c. Now we can write

c = ∑_{j} s_{j} (x) c_{j} + c′

with distinct terms c_{j}, the s_{j} have length i, x does not appear in s_{j} and x does not appear at the first i + 1 entries of c′. One calculates:

0 = d c = ∑_{j} [(d s_{j}) (x) c_{j} + (−1)^{i}s_{j} c_{j} + (−1)^{i+1}s_{j} (x) d c_{j}] + d c′ .

If we forget those terms in the last equation for which x does not appear at the i-th entry, this equation implies d s_{j} = 0 for all j. Since length(s_{j}) = i < m−length((x) c_{j}), there are by induction s′_{j} with d s′_{j} = s_{j} and such that the following products make sense.

z := ∑_{j} s′_{j} (x) c_{j}

In the cycle

c − d z = c′ − ∑_{j} [(−1)^{i+1}s′_{j} c_{j} + (−1)^{i}s′_{j} (x) d c_{j}]

x does not appear at the first i + 1 entries. Finally, x vanishes completely from our cycle and we are in the situation where we can apply Lemma 1. □

Using the corresponding two hyperhomology spectral sequences for the natural action of the symmetric group Σ_{m} on our complex C_{∗}(m) (cf [2]) one can now obtain a stability result due to Nakaoka.^{†}

Theorem 2. (Nakaoka [5]) H_{m}(Σ_{n−1}) = H_{m}(Σ_{n}) for m < n/2.

Proof. We use induction on n . It is well known for n = 3.

H_{1}(Σ_{2}) = H_{1}(Σ_{3}) = ℤ/(2)

For n ⩾ 4 define C′_{l}(n) := C_{l+1}(n) for l ⩾ 0. Then

H_{m}(Σ_{n}, ℤ) = H_{m}(Σ_{n}, C′_{∗}(n))

when m < n − 1 because of Theorem 1 and a standard spectral sequence argument [2]. The second spectral sequence of the bi-complex gives for E_{∗,∗}^{1}:

⋯
H_{2}(Σ_{n}, C′_{0}) H_{2}(Σ_{n}, C′_{1}) ⋯ H_{2}(Σ_{n}, C′_{n−2}) H_{2}(Σ_{n}, C′_{n−1})
H_{1}(Σ_{n}, C′_{0}) H_{1}(Σ_{n}, C′_{1}) ⋯ H_{1}(Σ_{n}, C′_{n−2}) H_{1}(Σ_{n}, C′_{n−1})
H_{0}(Σ_{n}, C′_{0}) H_{0}(Σ_{n}, C′_{1}) ⋯ H_{0}(Σ_{n}, C′_{n−2}) H_{0}(Σ_{n}, C′_{n−1})

Using Shapiro’s Lemma we get:

⋯
H_{2}(Σ_{n−1}) H_{2}(Σ_{n−2}) ⋯ H_{2}(Σ_{1}) 0
H_{1}(Σ_{n−1}) H_{1}(Σ_{n−2}) ⋯ H_{1}(Σ_{1}) 0
H_{0}(Σ_{n−1}) H_{0}(Σ_{n−2}) ⋯ H_{0}(Σ_{1}) ℤ

The horizontal arrows can be computed as 0, 1, 0, 1, ⋯, since they are the sums of the signs in d′_{1}, d′_{2}, · · ·. We have E_{i,0}^{2} = H_{i}(Σ_{n−1}) for i ⩾ 0. By our global induction some d : E_{i,j}^{1} → E_{i,j−1}^{1} are isomorphism. Especially, E_{i−1,2}^{2} = 0 for n/2 > i and

E_{i,j}^{2} = 0 for i < \frac{n − j − 1}{2}, 0 < j < n − 1 .

For n/2 > i only the first column on the diagonal (E_{k,l})_{k+l=i} survives. In fact E_{i,0}^{∞} = E_{i,0}^{2} = H_{i}(Σ_{n−1}) for n/2 > i, because the differentials that could kill these groups come from E_{i−l,l+1}^{⩾2} = 0 for l > 0. Finally, H_{i}(Σ_{n−1}) = H_{i}(Σ_{n}) for n/2 > i. □

2. Words in general position

Let n = {i|1 ⩽ i ⩽ n}. We associate to every (nonempty) set X a complex F (X)_{∗}, the so-called complex of words with alphabet X, as follows:

(F (X))_{n} = ℤ < {f : n → X} >
d_{n}(f) = ∑_{k=1}^{n}(−1)^{n+1}f ∘ δ_{k} .

†Hendrik Maazen gives another prove of Nakaoka’s stability in his dissertation. I have to thank Wilberd van der Kallen for this remark.

Here δ_{k} : [n] → [n + 1] are the coface maps

δ_{k}(j) = \{ \begin{matrix}j & if 1 ⩽ j < k \\ j + 1 & if k ⩽ j \end{matrix} .

It is immediate that the homology of F (X) vanishes. For if c ∈ F (X)_{n} is a cycle, c = d((x_{0}) c) for arbitrary x_{0} ∈ X (the notational convention is explained below Theorem 1). For given X certain subcomplexes of F (X) can be used in hyperhomology spectral sequences as above, if their homology vanishes to some extent. These subgroups are determined by conditions which one could call ”general position conditions”. For applications cf [8], [9]. It could be asked, how to explain the fact that the vanishing of homology is not affected by these conditions. In order to give a general result we translate the proof of Theorem 1 into our more complicated setting.

Examples

(i) Let X be a finite set. The complex of injective words is (F_{G^{inj}}(X))_{n} := {f ∈ F (X)_{n}|f injective}. According to Theorem 1 the homology of this subcomplex is zero except in degree m = card(X) where

rank (H_{m}(F (X)_{∗})) = (−1)^{m}(1 − ∑_{i=0}^{m−1}(−1)^{i}m(m − 1) ⋯ (m − i)) .

This equals the number of fixed point free permutations of X.

(ii) Let k be a field and V a k-vector space. The complex of vectors in general position is (F_{G^{vec}}(V))_{n} := {f ∈ F (V)_{n}|f in general position}. A sequence of vectors x_{1}, … x_{n} ∈ V is said to be in general position if no nontrivial linear combination of zero

a_{1} x_{1} + ⋯ + a_{n} x_{n} = 0

with a_{i} ∈ k and at most dim(V) many nonvanishing a_{i} exists.

If k is infinite the complex is exact. A general vanishing result is contained in our main theorem.

We introduce axioms for elements of a given (nonempty) set X to be in general position relative to some other elements.

Definition 1 (General position). Let G_{l,m} be relations in l + m variables from X; l > 0, m ⩾ 0. The family (G_{l,m})_{l,m∈ℕ} is called a general position relation if the following properties are satisfied.

Let x, y, z be finite sequences of elements of X of length l, m, n:

(i) G_{n,m} is symmetric in the first n and last m arguments.

(ii) If G_{l+m,n}(x, y; z) then G_{l,m+n}(x; y, z). If G_{l,m+n}(x; y, z) then G_{l,n}(x; z).

(iii) If G_{l,m+n}(x; y, z) and G_{m,n}(y; z) then G_{l+m,n}(x, y; z).

For fixed G we say x is in G-general position to y iff G_{l,m}(x; y). Given x ∈ F (X)_{l} and y ∈ F (X)_{m} we say x is in G-general position to y if every term of x is in G-general postition to every term of y (for l = 0 we demand nothing).

Definition 2. Given a finite sequence b of elements of X the corresponding complex of words in general position to b is (F_{G}(X; b))_{n} := {f ∈ F (X)_{n}|f is in G-general position to b}.

Before we can state the main theorem we have to introduce an invariant which determines an upper bound for the vanishing of the homology of F_{G}(X).

Definition 3. Given a general position relation G we define |G| to be the smallest natural number n ⩾ 0 such that there is a sequence x of elements of X with length(x) = n such that there is no further element in X which is in general position to x.

Examples

(i) Example (i) is induced by saying x is in G^{inj}-general position to y if the underlying sets of x and y are disjoint and the entries of x are distinct. We have |G^{inj}| = card(X).

(ii) Example (ii) is induced by saying (x_{1}, …, x_{i}) is in G^{vec}-general position to (y_{1}, …, y_{j}) if for all a_{l} ∈ k, l = 1, …, i + j, and only dim(V) many of them nonvanishing

a_{1} x_{1} + ⋯ + a_{i} x_{i} + a_{i+1} y_{1} + ⋯ + a_{i+j} y_{j} = 0

implies a_{l} = 0 for all l ∈ {1, …, i}.

If card(k) = ∞ or dim(V) = ∞ then |G^{vec}| = ∞.

Unfortunately the exact value of |G^{vec}| is not known for all finite dimensional vector spaces over finite fields. The following lemma comprises what is known.

Lemma 2. (a) For dim(V) ⩾ card(k) we have |G^{vec}| = dim(V) + 1.

(b) For dim(V) = 2 we have |G^{vec}| = card(k) + 1.

Proof of (a). Let n = dim(V) + 1 and (e_{i})_{1⩽i⩽n−1} be a basis of V. First we show |G^{vec}| ⩾ n. Otherwise we had a sequence (x_{i})_{1⩽i⩽n−1}, x_{i} ∈ V, such that there does not exist a vector x ∈ V in G^{vec}-general position to (x_{i}). This can only be true, if (x_{i}) is a basis of V. But if it is a basis, the element x_{1} + x_{2} + ⋯ + x_{n−1} would be in general position to it. Contradiction. Now the sequence f = (e_{1}, …, e_{n−1}, e_{1} + e_{2} + ⋯ + e_{n−1}) is maximal in the sense of Definition 3. To see this we have to show there is no vector x = a_{1} e_{1}+⋯+a_{n−1} e_{n−1}, a_{i} ∈ k, in G^{vec}-general position to f. If there is an index j such that a_{j} = 0, x is obviously not in general postion to f. But if no coefficient in x vanishes two of them have to be equal since dim(V) ⩾ card(k). In case a_{1} = a_{2} we can write

x = a_{1} (e_{1} + ⋯ + e_{n−1}) + (a_{3} − a_{1}) e_{3} + ⋯ (a_{n−1} − a_{1}) e_{n−1} .

This shows f is in fact maximal.

Proof of (b). For dim(V) = 2 we have x ∈ V in G^{vec}-general position to y ∈ V iff x ≠ 0 ≠ y and [x] ≠ [y] ∈ ℙ_{k}(V). So |Gen^{vec}| is simply the number of k-rational points in ℙ_{k}(V). □

Question. What is |G^{vec}| for 2 < dim(V) < card(k)?

Now the main theorem reads as follows.

Theorem 3. For a set X with general position condition G and a finite sequence a = (a_{1}, …, a_{l}) of elements of X the corresponding homology groups H_{m}(F_{G}(X; a)) vanish for m ⩽ (|G| − l − 1)/2.

In contrast to Theorem 1 one should notice that it is in general not possible to erase the factor 1/2 from the inequality of the theorem. It is left to the reader to find a counter-example.

Corollary 1. For fixed m, d ⩾ 0 we have H_{m}(F_{G^{vec}}(k^{d})) = 0 for almost all finite fields k.

Proof. A simple cardinality argument shows

lim_{card(k)→∞} |G^{vec}| = ∞

for fixed dimension of the underlying vector space and variable base field k. Now Corollary 1 follows from Theorem 3. □

Proof of Theorem 3. Denote the degree by m. Exactness at m = 0 is trivial. We proceed by induction on m ⩾ 1. Let c be a cycle in F_{m}(X; a_{1}, …, a_{l}).

Case m = 1: We can suppose c = (x) − (x′). Because 1 ⩽ (|G| − l − 1)/2 we have l + 2 < |G| so that there exists y ∈ X in G-general position to (x, x′, a_{1}, …, a_{l}). According to Definition 1(iii) (y, x, x′) is in G-general position to (a_{1}, …, a_{l}) and it is allowed to write d((y) c) = c.

Induction step: Fix x ∈ X in G-general position to (a_{1}, …, a_{l}). The simplest case is c in G-general position to (x, a_{1}, …, a_{l}). Here we can apply a construction similar to Lemma 1; we have c = d((x) c), since (x) c is in G-general position to (a_{1}, …, a_{l}). We reduce to this case by changing c by boundaries. To be more precise we introduce a number I(c) ∈ {0, …, m} which is m, iff the above applies, that is c in G-general position to (x, a_{1}, …, a_{l}). By adding boundaries we will see that we can increase I(c). For g ∈ (F_{G}(X; a))_{n} we define I(g) ∈ {0, …, n} as the the greatest natural number i ⩽ n such that π_{i}(v) is in G-general position to (x, π′_{i}(v), a_{1}, …, a_{l}) for any term v of g (π_{i} denotes the projection to the first i entries and π′_{i} the projection to the last n − i entries).

Reduction to I(c) > 0: Suppose I(c) = 0. Let c = ∑_{j} x_{j} with x_{j} terms. Choose for every j a y_{j} ∈ X with y_{j} in G-general position to (x, x_{j}, a_{1}, …, a_{l}). This is possible, since

length(x, x_{j}, a_{1}, …, a_{l}) = 1 + m + l < |G| .

Clearly

I(c − d(∑_{j}(y_{j}) x_{j})) > 0 .

Now suppose m > I(c) > 0: Write

c = ∑_{j} s_{j} x_{j} + x′

such that exactly those terms v of c for which I(v) > I(c) are in x′, length(s_{j}) = I(c) and all x_{j} are distinct terms.

Lemma 3. d(s_{j}) = 0 for all j .

Proof. The terms v of d(c) such that I(v) < I(c) are exactly the terms of d(s_{j}) x_{j}. In order to see this, notice that for a term v of d(c) we have I(v) = I(c) − 1 iff the I(c)-th entry of v is not in G-general position to (x, π′_{I(c)}(v), a_{1}, …, a_{l}). Now projecting the identity 0 = d(c) to the terms v with I(v) < I(c) we get 0 = ∑_{j} d(s_{j}) x_{j}. Lemma 3 is proven since the x_{j} are distinct terms. □

According to our assumtion s_{j} is in G-general position to (x, x_{j}, a_{1}, …, a_{l}). By induction on m we know there exist s′_{j} with d(s′_{j}) = s_{j} and s′_{j} in G-general position to (x, x_{j}, a_{1}, …, a_{l}), because 2i + [(m − i) + l + 1] ⩽ 2m + l ⩽ |G| − 1.

Now

I(c − d(∑_{j} s′_{j} x_{j})) = I(x′ + (−1)^{I(c)}s′_{j} d(x_{j}))
> I(c) .

This finishes the reduction to I(c) = m and therefore the induction step to length(c) = m is accomplished by applying the standard trick mentioned at the beginning of the proof. □

Theorem 3 could be useful in the generalization of Suslin’s GL-stability [8] to finite fields. A thorough treatment seems to indicate the following result:

(i) Given m ⩾ 0 and n ⩾ m we have H_{m}(GL_{n}(k)) = H_{m}(GL_{n+1}(k)) for almost all finite fields k. (ii) For m ⩾ 0 the map H_{m}(GL_{m−1}(k)) → H_{m}(GL_{m}(k)) is surjective for almost all finite fields k. In fact Quillen proved – using other methods – that H_{m}(GL_{n}(k)) → H_{m}(GL_{n+1}(k)) is an isomorphism for all fields k with more than 2 elements and n > m [6]. Similar results with weaker bounds are due to Maazen and van der Kallen [4].

Acknowledgement The above results were obtained in the Seminar Müller-Stach 2004 at the University of Mainz. I am indebted to Philippe Elbaz-Vincent, Stefan Müller-Stach, Oliver Petras, Wilberd van der Kallen and Volkmar Welker for their comments. Especially I have to thank Volkmar Welker for his hospitality in Marburg.

References

[1] Björner, Anders; Wachs, Michelle On lexicographically shellable posets. Trans. Amer. Math. Soc. 277 (1983), no. 1, 323–341.

[2] Brown, Kenneth S. Cohomology of groups. Corrected reprint of the 1982 original. Graduate Texts in Mathematics, 87. Springer-Verlag, New York, 1994

[3] Farmer, Frank D. Cellular homology for posets. Math. Japon. 23 (1978/79), no. 6, 607–613.

[4] van der Kallen, Wilberd Homology stability for linear groups. Invent. Math. 60 (1980), no. 3, 269–295.

[5] Nakaoka, Minoru Decomposition theorem for homology groups of symmetric groups. Ann. of Math. (2) 71 1960 16–42.

[6] Quillen, Daniel; unpublished.

[7] Stanley, Richard P. Combinatorics and commutative algebra. Second edition. Progress in Mathematics, 41. Birkhäuser Boston, Inc., Boston, MA, 1996.

[8] Suslin, A. A. Homology of GL_{n}, characteristic classes and Milnor K-theory. Algebraic K-theory, number theory, geometry and analysis (Bielefeld, 1982), 357–375, Lecture Notes in Math., 1046, Springer, Berlin, 1984.

[9] Suslin, A. A. K_{3} of a field, and the Bloch group. Proc. Steklov Inst. Math. 1991, no. 4, 217–239.

This article may be accessed via WWW at http://www.rmi.acnet.ge/hha/ or by anonymous ftp at

ftp://ftp.rmi.acnet.ge/pub/hha/volumes/2005/n1a5/v7n1a5.(dvi,ps,pdf)

Moritz C. Kerz mokerz@students.uni-mainz.de

Institut für Mathematik (Fachbereich 8) Johannes Gutenberg-Universität Mainz Staudingerweg 9 55099 Mainz Germany