Generating infinite symmetric groups^{∗}

George M. Bergman

July 25, 2005

Abstract

Let S = Sym(Ω) be the group of all permutations of an infinite set Ω. Extending an argument of Macpherson and Neumann, it is shown that if U is a generating set for S as a group, respectively as a monoid, then there exists a positive integer n such that every element of S may be written as a group word, respectively a monoid word, of length ≤ n in the elements of U.

Some related questions and recent results are noted, and a brief proof is given of a result of Ore’s on commutators that is used in the proof of the above result.

1 Introduction, notation, and some lemmas on full moieties.

In [14, Theorem 1.1] Macpherson and Neumann show that if Ω is an infinite set, then the group S = Sym(Ω) is not the union of a chain of ≤ |Ω| proper subgroups. We will repeat the beautiful proof of that result, with modifications that will allow us to obtain along with it the result stated in the abstract. The present section is devoted to obtaining strengthened versions of the lemmas used in that proof.

Following the notation of [14], for Ω an infinite set, Sym(Ω), generally abbreviated S, will denote the group of all permutations of Ω, and such permutations will be written to the right of their arguments. For subsets Σ ⊆ Ω and U ⊆ S, the symbol U_{(Σ)} will denote the set of elements of U that stabilize Σ pointwise, and U_{{Σ}} the set {f ∈ U : Σf = Σ}. (In [14] this notation was used only for U a subgroup.) A subset Σ ⊆ Ω will be called full with respect to U ⊆ S if the set of permutations of Σ induced by members of U_{{Σ}} is all of Sym(Σ). The cardinality of a set X will be written |X|, and a subset Σ ⊆ Ω will be called a moiety if |Σ| = |Ω| = |Ω − Σ|.

Suppose Σ_{1} and Σ_{2} are moieties of Ω whose intersection is also a moiety, and whose union is all of Ω. Then [14, Lemma 2.3] says that if G is a subgroup of S = Sym(Ω) such that Σ_{1} and Σ_{2} are both full with respect to G, then G = S. To strengthen this result, we will consider subsets U, V ⊆ S, closed under inverses, such that Σ_{1} is full with respect to U and Σ_{2} with respect to V. By the lemma cited, ⟨U ∪ V ⟩ = S; our version of this result will bound the number of factors from U and V needed to get the general element of S.

Our proof will use the following fact, first proved by Ore [18]. Much stronger results have been proved since. In §4 we will give a self-contained proof of a statement of intermediate strength.

Lemma 1 ([18], cf. §4 below). For Ω an infinite set, every element f ∈ Sym(Ω) can be written as a commutator, f = g^{−1}h^{−1}gh (g, h ∈ Sym(Ω)).

Here now is the result on full moieties.

Lemma 2 (cf. [14, Lemma 2.3]). Suppose Σ_{1}, Σ_{2} are moieties of Ω whose intersection is a moiety, and whose union is all of Ω; and suppose U, V are subsets of S = Sym(Ω), each closed under inverses, such that Σ_{1} is full with respect to U and Σ_{2} is full with respect to V. Then S = (UV)^{4} V ∪ (V U)^{4} U.

∗2000 Mathematics Subject Classifications. Primary: 20B30. Secondary: 20B07, 20E15.

Preprint versions of this paper: http://math.berkeley.edu/∼ gbergman/papers/Sym Omega:1.{tex,dvi,ps} and arXiv:math.GR /0401304 .

Proof. Note that S_{(Ω−(Σ_{1} ∩Σ_{2}))} ≅ Sym(Σ_{1} ∩ Σ_{2}). By Lemma 1, any element f of the latter group may be written as a commutator f = g^{−1}h^{−1}gh. Since Σ_{1} is full with respect to U, we can find an element of U_{{Σ_{1}}} which behaves like g on Σ_{1} ∩ Σ_{2} and as the identity on Σ_{1} − Σ_{2}; likewise, we can find an element of V_{{Σ_{2}}} which behaves like h on Σ_{1} ∩ Σ_{2} and as the identity on Σ_{2} − Σ_{1}. Clearly the commutator of these elements behaves like f on Σ_{1} ∩ Σ_{2} and as the identity on Ω − (Σ_{1} ∩ Σ_{2}). Hence

(1) S_{(Ω−(Σ_{1} ∩Σ_{2}))} ⊆ UV UV.

Now |Σ_{1} ∩ Σ_{2}| = |Ω| = |Σ_{2} − Σ_{1}|, where the first equality holds because Σ_{1} ∩ Σ_{2} is a moiety and the second because Σ_{1} = Ω − (Σ_{2} − Σ_{1}) is one. Hence Sym(Σ_{2}) contains an element interchanging the subsets Σ_{1} ∩ Σ_{2} and Σ_{2} − Σ_{1}; hence V has an element which behaves that way on Σ_{2} (and in an unspecified manner on Σ_{1} − Σ_{2}). Conjugating (1) by such an element, we get

(2) S_{(Σ_{1})} ⊆ V UV UV V.

Since the assumptions on Σ_{1} and Σ_{2} are symmetric, we also have the corresponding formula for S_{(Σ_{2})}, with U and V interchanged.

Now suppose we are given f ∈ S, which we wish to write as a product of elements of U and V.

We shall see, roughly, that a product of one element from U and one element of V suffices to distribute the elements of Ω between Σ_{1} and its complement exactly as f does. An application of an element of U will then put the elements that have been moved into Σ_{1} in exactly the desired places, and a final application of (2) will administer the coup de grâce.

The details: Note first that the set (Σ_{1} ∩ Σ_{2})f^{−1} must either contain |Ω| elements of Σ_{1} or |Ω| elements of Σ_{2}; without loss of generality assume the former. (This is the reason for the word “roughly” in the preceding paragraph. In the contrary case, the roles stated there for Σ_{1} and Σ_{2}, and likewise for U and V, will be reversed.) In particular, Σ_{1}f^{−1} contains |Ω| elements of Σ_{1}. Hence we can find a permutation a ∈ U_{{Σ_{1}}} which maps all elements of Σ_{1} which are not in Σ_{1}f^{−1} (if any) into Σ_{1} ∩ Σ_{2}, and which also maps into that set |Ω| elements of Σ_{1} which are in Σ_{1}f^{−1}. These conditions, and the fact that a ∈ U_{{Σ_{1}}} takes Ω − Σ_{1} to itself, together imply that a maps all elements of (Ω − Σ_{1})f^{−1} (both those in Σ_{1} and those in Ω − Σ_{1}) into Σ_{2}, and also takes |Ω| elements of Σ_{1}f^{−1} there. We can now choose b ∈ V_{{Σ_{2}}} which maps into Ω − Σ_{1} the images under a of all elements of (Ω − Σ_{1})f^{−1} and nothing else; i.e., such that (Ω − Σ_{1})f^{−1}ab = Ω − Σ_{1}. Taking complements, we have Σ_{1}f^{−1}ab = Σ_{1}, so as Σ_{1} is full with respect to U, we can find c ∈ U_{{Σ_{1}}} which agrees on Σ_{1} with the inverse of f^{−1}ab; i.e., such that f^{−1}abc ∈ S_{(Σ_{1})}. Now (2) applied to the inverse of the latter element gives us (abc)^{−1}f ∈ V UV UV V, so f ∈ (UV U)(V UV UV V) = (UV)^{4}V. As noted earlier, the roles of U and V may be the opposite of those we have assumed, giving the alternative possibility f ∈ (V U)^{4} U.

The result from [14] that we have just strengthened was used there to show that if a subgroup G ≤ S has a full moiety, then there exists x ∈ S such that ⟨G ∪ {x}⟩ = S. The version proved above yields the more precise statement:

Lemma 3 (cf. [14, Lemma 2.4]). If a subset U ⊆ S closed under inverses has a full moiety, then there exists x ∈ S of order 2 such that (Ux)^{7} U^{2}x ∪ (xU)^{7}xU^{2} = S.

Proof. Given a full moiety Σ_{1} for U, choose any moiety Σ_{2} ⊆ Ω such that Σ_{1} ∩ Σ_{2} is a moiety and Σ_{1} ∪ Σ_{2} = Ω. Since Ω − Σ_{1} and Ω − Σ_{2} are disjoint and both have the cardinality of Ω, we can find an element x of order 2 which interchanges those two sets, and hence also interchanges their complements, Σ_{1} and Σ_{2}. The fact that Σ_{1} is a full moiety for U makes Σ_{2} = Σ_{1} x a full moiety for x^{−1}Ux = x Ux. Setting x Ux = V, we may apply the preceding lemma. The expression (UV)^{4}V becomes (UxUx)^{4}xUx = (Ux)^{8}xUx = (Ux)^{7}UxxUx = (Ux)^{7}U^{2}x, while the other term is the conjugate of this by x, namely (xU)^{7}xU^{2}.

We conclude this section with a diagonal argument, using nothing but the definition of full moiety and basic set theory, which we extract virtually unchanged from the proof of [14, Theorem 1.1]:

Lemma 4. Let Ω be an infinite set, let S = Sym(Ω), and let (U_{i})_{i∈I} be any family of subsets of S such that ⋃_{I} U_{i} = S and |I| ≤ |Ω|. Then Ω contains a full moiety with respect to at least one of the U_{i}.

Proof. Since |Ω| is infinite and I ≤ |Ω|, we can write Ω as a union of disjoint moieties Σ_{i} (i ∈ I). If there are no full moieties with respect to U_{i} for any i, then in particular, for each i the set Σ_{i} is non-full with respect to U_{i}, so we can choose f_{i} ∈ Sym(Σ_{i}) which is not the restriction to Σ_{i} of a member of U_{i}. Now let f ∈ Sym(Ω) be the permutation whose restriction to each Σ_{i} is f_{i}. Then f cannot belong to any of the U_{i}, contradicting the assumption ⋃_{I} U_{i} = S, and completing the proof.

2 Chains of subsets of Sym(Ω).

Let us begin by recovering [14, Theorem 1.1]. Our statement will be the contrapositive of that in [14]. I also include parenthetically the corresponding statement with chains of submonoids in place of chains

of subgroups. As we will see, this follows trivially from the result on chains of subgroups; but it took me a long time to discover that trivial argument.

Theorem 5 ([14, Theorem 1.1]). If Ω is an infinite set and (G_{i})_{i∈I} a chain of subgroups (or more generally, submonoids) of S = Sym(Ω), with ⋃_{i∈I} G_{i} = S and |I| ≤ |Ω|, then G_{i} = S for some i ∈ I.

Proof. Lemma 4 shows that Ω has a full moiety with respect to some G_{i}, hence assuming the G_{i} are subgroups, Lemma 3 shows that S = ⟨G_{i} ∪ {x}⟩ for some x ∈ S. Since the G_{j} form a chain with union S, there is some j ≥ i with x ∈ G_{j}, hence G_{j} ⊇ G_{i} ∪ {x}, hence G_{j} = S.

If the G_{i} are merely submonoids, we apply the result of the preceding paragraph to (G_{i} ∩ G_{i}^{−1})_{i∈I}, which is clearly a chain of subgroups with union S.

Now for our new result.

Theorem 6. Suppose Ω is an infinite set, and U a generating set for Sym(Ω) as a group (respectively, as a monoid). Then there exists a positive integer n such that every element of Sym(Ω) is represented by a group word (respectively, a monoid word) of length ≤ n in the elements of U.

Proof. Here it suffices to prove the monoid case, since the group words in the elements of U are just the monoid words in the elements of U ∪ U^{−1}.

So assume U generates S as a monoid. For i = 1, 2, …, let U_{i} = (U ∪ {1})^{i} ∩ (U^{−1}∪ {1})^{i}. By assumption the sets (U ∪ {1})^{i} have union S, hence so do their inverses, (U^{−1} ∪ {1})^{i}, hence so do the intersections U_{i}. Since ℵ_{0} ≤ |Ω|, Lemma 4 says that Ω has a full moiety with respect to some U_{i}. By Lemma 3 there exists x ∈ S such that S = (U_{i} x)^{7} U_{i}^{2} x ∪ (xU_{i})^{7}xU_{i}^{2}, which we see is contained in (U_{i} ∪ {x})^{17}. Taking a j ≥ i such that x ∈ U_{j}, we get (U ∪{1})^{17j} = ((U ∪{1})^{j})^{17} ⊇ (U_{i} ∪{x})^{17} = S.

One may ask whether for a given set Ω, there is some single n as in Theorem 6 that works for every generating set U. To see that this is not so, let Ω = ℚ/ℤ, and let us give this set the natural metric, of diameter 1/2, under which the distance between two cosets of ℤ is the minimum of the distances between their members, as real numbers. (In other words, let us use the metric on Ω = ℚ/ℤ induced by the arclength metric on ℝ/ℤ.) Fixing an integer n, let U denote the set of permutations of Ω which move all elements by distances < 1/(2n) . Clearly, U^{n} ≠ Sym(Ω). However, I claim that U is a generating set for Sym(Ω) as a group (and indeed, since it is closed under inverses, as a monoid).

Note first that if Σ is the image in Ω of any interval of length < 1/(2n) in ℚ, then U contains S_{(Ω−Σ)}, the group of permutations that act arbitrarily on Σ and fix all elements outside it. Now we can cover Ω with a finite number of successive overlapping sets Σ_{1}, Σ_{2}, …, Σ_{r} of this sort, and then use Lemma 2 to conclude inductively that ⟨U⟩ ⊇ S_{(Ω−(Σ_{1}∪...∪Σ_{i}))} for i = 1, …, r, hence that ⟨U⟩ ⊇ S_{(Ω−(Σ_{1}∪...∪Σ_{r}))} = S_{(∅)} = S, as claimed.

3 Questions, examples, remarks, and related literature.

The statement of [14, Theorem 1.1] = Theorem 5 above, unlike that of Theorem 6, depends on the cardinal |Ω|. Let us, for the purposes of this section, weaken that statement to one that holds independent of this cardinal, by using the obvious lower bound ℵ_{0} ≤ |Ω|. Then that theorem can be looked at as saying, for every infinite set Ω, that Sym(Ω) belongs to the class of groups G satisfying (3) If G is written as the union of a chain of subgroups G_{0} ≤ G_{1} ≤ … indexed by ω, then for

some n, G_{n} = G.

Theorem 6, similarly, says that Sym(Ω) belongs to the class of groups G satisfying

(4) If G is generated as a group by a subset U, then for some n, every element of G is represented by a group word of length ≤ n in the elements of U.

Clearly (3) also holds for all finitely generated groups, and (4) for all finite groups. Thus, in a strange way, the groups Sym(Ω) resemble finite groups.

Condition (3) on a non-finitely-generated group is commonly expressed by saying that G has uncountable cofinality, and is known to hold in many cases. Some works on cofinalities of groups are [5], [9], [13], [19],

[22] and [21]; see also other papers cited in [9]. Whether or not G is finitely generated, (3) is equivalent to the condition that the fixed point set construction on G -sets commutes with direct limits over countable index sets [1, end of §2]. In fact, it was the wish to give in [1] an example of a non-finitely-generated group having this property that led me to read [14], eventually resulting in this note. The analog of condition (3) for modules has been studied under many different names; cf. [11, p.895, top paragraph].

In response to a question posed in an earlier version of this note, Droste and Göbel [9] have obtained a general technique for showing that certain sorts of structures containing many isomorphic copies of themselves have automorphism groups satisfying (3) and (4); in particular, they find that (3) and (4) hold for the groups of all self-homeomorphisms of the Cantor set, of the rational numbers, and of the irrational numbers, and for the group of Borel automorphisms of the real numbers. Droste and Holland [10] obtain the same conclusions for the automorphism group of any doubly homogeneous totally ordered set, and Tolstykh [23], [24] proves (4), and, insofar as it was not already known, (3), for the automorphism groups of infinite-dimensional vector spaces and various sorts of relatively free groups. In the final remark of [23] he suggests an approach to showing that the full automorphism groups of free objects in other well-behaved varieties of algebras have this property. Mesyan [15] obtains analogous results for endomorphism rings of infinite direct sums and products of a module, and Cornulier [6, Proposition 4.4] does the same for the Boolean ring of subsets of an infinite set; he also shows in [6, Theorem 3.1] that any ω_{1}-existentially closed group satisfies (3) and (4).

Let us note some general facts about conditions (3) and (4). It is not hard to see that both properties are preserved under taking homomorphic images, and that (3) is also preserved under group extensions and under passing to groups finitely generated over G. To get some similar results for (4), we will want

Lemma 7. Let H < G be groups and U a generating set for G. Suppose that for some n ≥ 0, every right coset of H in G contains a group word of length ≤ n in the elements of U. Then the set of elements of H that can be written as words of length ≤ 2n + 1 in the elements of U generates H.

Proof. Let V be a set of right coset representatives for H in G consisting of words of length ≤ n in U, with the coset H represented by the element 1, and let r : G → V be the retraction collapsing each coset to its representative. Let W denote the set of elements of H that can be written as words of length ≤ 2n + 1 in the elements of U.

For any v ∈ V and u ∈ U ∪ U^{−1}, note that vu = (vu r(vu)^{−1})r(vu). Since r(vu) by definition lies in the same right coset as vu, the factor vu r(vu)^{−1} lies in H, and since v and r(vu), as members of V, each have length ≤ n in the elements of U, that factor has length ≤ 2n + 1, and so lies in W. Thus, V (U ∪ U^{−1}) ⊆ W V. It follows that ⋃_{i} W^{i}V is closed under right multiplication by U ∪ U^{−1}, hence equals the whole group G. We now intersect the equation ⋃_{i} W^{i}V = G with H. This has the effect of discarding elements on the left-hand side having right factors from V other than 1, and so gives ⋃_{i} W^{i} = H, completing the proof.

We can now show that (4) is preserved under group extensions. Given a short exact sequence 1 → H → G → E → 1 where H and E satisfy (4), and a generating set U for G, the fact that E satisfies (4) yields an n as in the hypothesis of Lemma 7. The conclusion of that lemma, combined with the fact that H satisfies (4), shows that all elements of H can be written as words of length ≤ m in the elements of U for some m. It follows that all elements of G can be written as words of length ≤ n + m. A similar application of that lemma shows that (4) is preserved under passing to overgroups in which G has finite index.

Clearly, a countable group satisfies (3) if and only if it is finitely generated, while an infinite group that is finitely generated can never satisfy (4). In particular, (4) is not preserved under passing to groups finitely generated over G. Neither property is preserved under passing to normal subgroups, since for Ω a countably infinite set, the subgroup of Sym(Ω) consisting of permutations that move only finitely many elements is normal, but satisfies neither (3) nor (4).

In response to a question posed in an earlier version of this preprint, Khélif has announced in [12] that (3), and also the conjunction of (3) and (4), are preserved under passing to subgroups of finite index, but that (4) alone is not.

A question that, to my knowledge, is still unanswered is

Question 8. Are there any countably infinite groups that satisfy (4)?

One can show that every non-finitely-generated abelian group can be mapped surjectively either onto a group Z_{p^{∞}}, or onto an infinite direct sum Z_{p_{1}} ⊕ Z_{p_{2}} ⊕ ... for (not necessarily distinct) prime numbers p_{1}, p_{2}, …. Neither of the latter sorts of groups satisfy (3) or (4), so no non-finitely-generated abelian group has either of these properties.

It is shown in [13] that the direct product of any family of copies of a nonabelian finite simple group satisfies (3). In [6, §4] this is strengthened to say that the direct product of any family of copies of a finite perfect group satisfies (3) and (4), while [9, Lemma 3.5] shows that the same is true of the direct product of any family of copies of Sym(ω) . These results suggest the general question of when (3) and (4) are inherited by products. They are both inherited by finite products, by our observations on group extensions. That they are not always inherited by infinite products is shown by any infinite direct product of nontrivial finite abelian groups: the factors, as finite groups, satisfy both conditions, but the product, a non-finitely-generated abelian group, satisfies neither. The same technique can be used to show the failure of these conditions for certain direct products of perfect groups, using the fact that an infinite product of perfect groups may be non-perfect. Khélif has announced the existence of a direct product of groups such that each factor satisfies (4) and the product is perfect but which still does not satisfy (4).

We saw in the proof of Theorem 5 that (3) implies the corresponding condition with “subgroups” replaced by “submonoids”. The same implication for the negations of these conditions is clear, so the group and monoid versions of (3) are equivalent. For (4), the proof of Theorem 6 showed that the statement for generation as a monoid implied the statement for generation as a group. In this case, we can also get the converse if we assume (3). For suppose the group G satisfies (3) and (4), and that U is a generating set for G as a monoid. As in the proof of Theorem 6, let U_{i} = (U ∪ {1})^{i} ∩ (U^{−1}∪ {1})^{i} (i ∈ ω). These sets form a chain with union G, hence so do the subgroups ⟨U_{i}⟩, hence by (3), some ⟨U_{j}⟩ is equal to G; so by (4), there is an n such that all elements of G are group words of length ≤ n in elements of U_{j}. By construction, U_{j} is closed under inverses, so these group words reduce to monoid words, so G = (U_{j})^{n} ⊆ ((U ∪ {1})^{j})^{n} = (U ∪ {1})^{jn}, as claimed. However, the results announced in [12] on subgroups of finite index imply that there are groups satisfying (4) but not (3), leading to

Question 9. Among groups satisfying (4) but not (3), are there any which do not satisfy the analog of (4) obtained by replacing “generated as a group” and “group word” with “generated as a monoid” and “monoid word”? Any which do satisfy that condition?

We saw at the end of §2 that though Sym(Ω) satisfies (4), there is no single n that works for all generating sets U. On the other hand, Shelah [20] constructs an uncountable group G in which every generating set U satisfies U^{240} = G.

We record two easily reformulations of the conjunction of (3) and (4).

Lemma 10. For any group G, the following conditions are equivalent:

(i) G satisfies both (3) and (4). (ii) If U_{0} ⊆ U_{1} ⊆ … ⊆ U_{i} ⊆ … is a chain of subsets of G, indexed by the natural numbers and having union G, such that U_{i} = (U_{i})^{−1} for all i, and such that for all i, j there exists some k with U_{i}U_{j} ⊆ U_{k}, then some U_{i} is equal to G. (iii) If L is a natural-number-valued function on G such that for all g, h ∈ G one has L(g^{−1}) = L(g) and L(gh) ≤ L(g) + L(h), then L is bounded above.

Functions L as in (iii) above are studied in geometric group theory. (Further conditions are generally assumed, in particular, that the number of g ∈ G with L(g) ≤ n is finite and grows at most exponentially in n. Under this assumption, L is known to be approximable by the function giving the length of g with respect to some finite generating set of an overgroup of G [17]. Of course, such a finiteness condition cannot be satisfied when G is an uncountable group such as we are considering.) In [6, §2], condition (iii) above is translated as saying that every isometric action of G on a metric space has bounded orbits, and it is deduced that isometric actions of G on certain sorts of metric spaces must in fact have fixed points.

A property of finite groups G that does not hold for the groups Sym(Ω) is

(5) Every subset of U ⊆ G which generates G as a group generates G as a monoid.

To see the failure of (5) in Sym(Ω) for countable Ω, we may take for U a submonoid M as in the next result.

Lemma 11. Let Ω be any countable totally ordered set without least or greatest element, and let M be the monoid {g ∈ Sym(Ω) : (∀α ∈ Ω) αg ≥ α}. Then Sym(Ω) = M M^{−1}M.

Proof. Given f ∈ Sym(Ω), I claim that we can find g, h ∈ Sym(Ω) such that for all α ∈ Ω,

(6) α ≤ αg ≥ αh ≤ αf.

From this it will follow that g, h^{−1}g, h^{−1}f ∈ M, whence f = g(h^{−1}g)^{−1}(h^{−1}f) ∈ M M^{−1}M, as desired.

To get g and h satisfying (6), let an enumeration of the elements of Ω be chosen. (We will not introduce a notation for this enumeration, but simply speak of “the first element with respect to our enumeration such that ...”. In particular, “ ≤ ” will continue to denote the given ordering of Ω, not the ordering corresponding to our enumeration.) We shall now construct recursively for each i ∈ ω a 3 -tuple (α_{i}, β_{i}, γ_{i}) of elements of Ω; these will eventually be the 3 -tuples (α, αg, αh) (α ∈ Ω).

To define (α_{i}, β_{i}, γ_{i}), let us, if i is divisible by 3, take for α_{i} the first element of Ω with respect to our enumeration which has not been chosen as α_{j} at any previous step (i.e., for 0 ≤ j < i), let us then take for β_{i} any element of Ω which was not chosen as β_{j} at a previous step and which is ≥ α_{i}, and for γ_{i} any element not chosen as γ_{j} at a previous step which is both ≤ β_{i} and ≤ α_{i} f. On the other hand, if i ≡ 1 (mod 3), we start by taking for β_{i} the first element of Ω with respect to our enumeration which was not chosen as β_{j} at any previous step, then take for α_{i} any element not previously chosen as an α_{j} which is ≤ β_{i}, and for γ_{i} any element not previously chosen as a γ_{j} which is both ≤ β_{i} and ≤ α_{i} f. Finally, when i ≡ 2 (mod 3), we take for γ_{i} the first element with respect to our enumeration that has not yet been used as a γ_{j}, for α_{i} any element not previously chosen as an α_{j} such that α_{i} f ≥ γ_{i} (which is possible because there are infinitely many elements ≥ γ_{i}), and for β_{i} any element not previously chosen in that role which is both ≥ α_{i} and ≥ γ_{i}.

Clearly this construction uses each element of Ω once and only once in each position; hence the set of pairs (α_{i}, β_{i}) is the graph of a permutation g ∈ Sym(Ω), and the set of pairs (α_{i}, γ_{i}) is the graph of a permutation h ∈ Sym(Ω). The conditions we imposed on our choices at each step insure that (6) holds.

(In the above lemma we can drop the countability assumption, if we replace the hypothesis of no least or greatest element by the assumption that each element of Ω has |Ω| elements above it and |Ω| elements below it. The assumption that the ordering is total can also be weakened to say that it is upward and downward directed.)

It would be interesting to know what sorts of groups satisfy (5), other than those whose elements all have finite order. One such group is the infinite dihedral group.

My first attempts to prove the statements about submonoids of S in Theorems 5 and 6 revolved around trying to remove from Lemmas 2 and 3 the hypotheses on closure under inverses. Those hypotheses are required by our proof of Lemma 2, since inverses are needed to form commutators and conjugates. Though a different method eventually gave the monoid cases of those theorems, it would still be interesting to know the answer to

Question 12. Are versions of Lemma 2 and/or 3 (possibly using longer products of x, U and V) true without the hypothesis that U and V are closed under inverses?

We shall note a weak result in this direction at the end of the next section.

We remark, finally, that it is easy to adapt the method of proof of Theorem 5 to give an apparently more general statement, in which the chain of subgroups G_{i} indexed by a set I of cardinality ≤ |Ω| is replaced by any directed system of subgroups G_{i} indexed by such a set, again having S as union. However, that result in fact follows easily from the theorem as stated. For given such a directed system, let {G_{i} : i ∈ κ} be a subset thereof whose union generates S, having least cardinality κ among such subsets, and indexed by that cardinal. Then {⟨ ⋃_{i<j} G_{i}⟩ : j < κ} forms a chain of proper subgroups of S, which, unless κ is finite, will have union S. This would contradict Theorem 5; so κ is finite, and the finite family {G_{i} : i ∈ κ} will be majorized by a member of the original directed system, which thus equals S.

Further results on the groups Sym(Ω) are obtained in [3].

Added July 2005: It is shown in [2, §6] that S = Sym(Ω) has the property that its countable direct power S^{ω} is finitely generated over the diagonal image Δ(S) ⊆ S^{ω}, and that this property (for general finitary algebras in the sense of universal algebra, and for groups in particular) is strictly stronger than the conjunction of (3) and (4).

4 Appendix: Writing every element of Sym(Ω) as a commutator.

In proving Lemma 2, we called on the result of [18] that every element of an infinite symmetric group is a commutator. Now a commutator is an element obtained by dividing an element by a conjugate, (g^{−1}hg)^{−1}h; moreover, it is clear that in a symmetric group, every element is conjugate to its inverse; so a commutator in a symmetric group can be described as a product of two elements in the same conjugacy class. Almost a decade after [18] appeared, it was shown that in an infinite symmetric group there in fact exist single conjugacy classes whose square is the whole group. In a series of papers by several authors, culminating in [16] (which describes this history), the conjugacy classes having this property were precisely characterized.

We shall give a self-contained proof of this property for one such conjugacy class in Lemma 14 below, then use the fact that Sym(Ω) is the square of a conjugacy class to get a result related to Question 12.

Definition 13. For Ω an infinite set, we shall call an element f ∈ Sym(Ω) replete if it has |Ω| orbits of each positive cardinality ≤ ℵ_{0} (including 1). For a subset Σ ⊆ Ω of cardinality |Ω|, we shall say that f is replete on Σ if Σf = Σ and the restriction of f to Σ is a replete permutation of Σ.

Note that a permutation of Ω that is replete on a subset Σ ⊆ Ω of cardinality |Ω| is necessarily replete on Ω.

The replete permutations of Ω clearly form a conjugacy class, so it will suffice to prove

Lemma 14. Every permutation f of an infinite set Ω is the product of two replete permutations.

Proof. Given f, let us choose a moiety Σ_{0} of Ω such that f moves only finitely many elements from Σ_{0} to Ω − Σ_{0} or from Ω − Σ_{0} to Σ_{0}. That there exists such a Σ_{0} is immediate if Ω is uncountable, for we can break Ω into two families of |Ω| orbits each, and take for Σ_{0} the union of one of these families. If Ω is countable, we can use the same method if f has infinitely many orbits, and can also get the same conclusion in an obvious way if f has more than one infinite orbit. If it has exactly one infinite orbit, α_{0} ⟨f ⟩, and finitely many finite orbits, then we can take Σ_{0} = {α_{0}f^{n} : n ≤ 0}; clearly f moves exactly one element out of Σ_{0}, and none into it.

After choosing Σ_{0}, let us split Ω − Σ_{0} into two disjoint moieties Σ_{1} and Σ_{2}, so that Σ_{1} contains the finitely many elements of (Σ_{0}f ∪ Σ_{0}f^{−1}) − Σ_{0}. I claim that if g_{0} is any permutation of Σ_{0} and g_{2} any permutation of Σ_{2}, then there exists a permutation h of Ω such that fh agrees on Σ_{0} with g_{0}, while h agrees on Σ_{2} with g_{2}. Indeed, this pair of conditions specifies the values of h on the two disjoint sets Σ_{0}f and Σ_{2} in a one-to-one fashion, and both the set on which it leaves h unspecified and the set of elements that it does not specify as values for h are of cardinality |Ω|. Hence the former set can be mapped bijectively to the latter, and the resulting bijection will serve to complete the definition of h. (We have used Σ_{1} as a “Hilbert’s Hotel” in case Σ_{0}f ≠ Σ_{0}.)

Now if we take for g_{0} and g_{2} replete permutations of Σ_{0} and Σ_{2} respectively, then h will be replete on Σ_{2}, hence replete, while fh will be replete on Σ_{0}, hence replete. Thus f = (fh)h^{−1} is a product of two replete permutations, as we wished to show.

(In [8, Theorem 3.1(a)] the same result is proved for a different conjugacy class, that of permutations with |Ω| infinite orbits and no finite orbits, also by an unexpectedly simple argument. However, it takes some work to isolate that argument from the lengthier proofs of other results that are being carried out there simultaneously. A different sort of generalization of Ore’s result is obtained in [7] and papers cited there, which characterize the group words w which are “universal” in infinite permutation groups, in the sense established for the word x^{−1}y^{−1}xy by Ore’s result.)

We shall now show that the proofs of Lemmas 2 and 3 can be adapted to the situation where U and V are not assumed closed under inverses if we allow ourselves to use, along with multiplication, the right conjugation operation

(7) g^{h} = h^{−1}g h.

Lemma 15 (cf. Lemma 3). Let Ω be an infinite set, and U ⊆ S = Sym(Ω) a subset with respect to which some moiety of Ω is full. Then there exist x, y ∈ S, with x of order 2, such that

(8) S = (Ux)^{3}(y^{U})^{2} x ∪ x(Ux)^{3}(y^{U})^{2}.

Sketch of proof. Let Σ_{1} be a full moiety for U, let Σ_{2} be a moiety such that Σ_{1} ∩ Σ_{2} is a moiety and Σ_{1} ∪ Σ_{2} = Ω, let x ∈ S be an involution such that Σ_{1} x = Σ_{2}, and let y ∈ S_{(Σ_{2})} be an element such that the group S_{(Σ_{2})} ≅ Sym(Ω − Σ_{2}) is the square of the conjugacy class of y in that group. Such a y exists by Lemma 14 above, or the results in the papers cited. Combining this property of y with the fact that Σ_{1}, and hence its subset Ω − Σ_{2}, is full with respect to U, we conclude that S_{(Σ_{2})} ⊆ (y^{U})^{2}; hence, conjugating by x,

(9) S_{(Σ_{1})} ⊆ x(y^{U})^{2} x.

Now let V = x Ux. Since Σ_{1} is a full moiety under U, Σ_{2} will be a full moiety under V. Using the technique of proof of Lemma 2, with (9) in place of (2), we get (8).

I am grateful to Peter Biryukov, Manfred Droste, Dugald Macpherson, Gadi Moran, Peter Neumann and Marc Rieffel for helpful information on the relevant literature.

References

[1] George M. Bergman, Direct limits and fixed point sets, to appear, J. Algebra. Preprint, 28 pp., http://math.berkeley.edu/∼ gbergman/papers/dirlimfix.{tex,dvi,ps}, arXiv:math.CT/0306127 .

[2] George M. Bergman, Two statements about infinite products that are not quite true, Preprint, July 2005, 16 pp. at http://math.berkeley.edu/∼ gbergman/papers/P vs cP.{tex,dvi,ps,pdf}.

[3] George M. Bergman and Saharon Shelah, Closed subgroups of the infinite symmetric group, to appear, Algebra Universalis, issue in honor of Walter Taylor. Preprints at http://math.berkeley.edu /∼ gbergman/papers/Sym Omega:2.{tex,dvi,ps}; publication 823 at http://shelah.logic.at ; arXiv: math.GR/0401305 .

[4] Stephen Bigelow, Supplements of bounded permutation groups, J. Symbolic Logic 63 (1998) 89–102. MR 99b:20007.

[5] Peter Biryukov, Automorphism groups of homogeneous Boolean spaces, preprint, 14pp. (Author’s e-mail address: stbpa@ic.kemsu.ru .)

[6] Yves de Cornulier, Strongly bounded groups and infinite powers of finite groups, to appear, Communications in Algebra. Preprint, 8 pp. at http://www.eleves.ens.fr/home/decornul/FHpasT3.pdf , arXiv/math.GR/0411466.

[7] Randall Dougherty and Jan Mycielski, Representations of infinite permutations by words. II, Proc. Amer. Math. Soc. 127 (1999) 2233–2243. MR 99j:20002.

[8] Manfred Droste, Classes of universal words for the infinite symmetric groups, Algebra Universalis 20 (1985) 205–216. MR 87d:20049.

[9] Manfred Droste and Rüdiger Göbel, Uncountable cofinalities of permutation groups, J. London Math. Soc. (2) 71 (2005), 335–344. MR 2122432.

[10] Manfred Droste and W. Charles Holland, Generating automorphism groups of chains, Forum Mathematicum, 17 (2005) 699–710.

[11] Robert El Bashir, Tomáš Kepka and Petr Němec, Modules commuting (via Hom) with some colimits, Czechoslovak Math. J. 53 (128) (2003) 891–905. MR 2004i:16002.

[12] Anatole Khélif, A propos de la propriété de Bergman, announcement, 4 pp., June 2005 (superseding earlier 1-page announcement, On the Bergman property.) Author’s e-mail address: khelif@logique. jussieu.fr .

[13] Sabine Koppelberg and Jacques Tits, Une propriété des produits directs infinis de groupes finis isomorphes, C. R. Acad. Sci. Paris Sér. A 279 (1974) 583–585. MR 51#13058.

[14] H. D. Macpherson and Peter M. Neumann, Subgroups of infinite symmetric groups, J. London Math. Soc. (2) 42 (1990) 64–84. MR 92d:20006. (Note: It is pointed out in [4] that Theorem 1.2 of this paper requires additional set-theoretic hypotheses for some κ.)

[15] Zachary Mesyan, Generating endomorphism rings of infinite direct sums and products of modules, J. Alg. 283 (2005) 364–366. MR 2005g:16057.

[16] Gadi Moran, Conjugacy classes whose square is an infinite symmetric group, Trans. Amer. Math. Soc. 316 (1989) 493–522. MR 91a:20005.

[17] A. Yu. Ol’shanskii, Distortion functions for subgroups, pp. 281–291 in Geometric Group Theory Down Under (Canberra, 1996), de Gruyter, Berlin, 1999. MR 2000j:20077.

[18] Oystein Ore, Some remarks on commutators, Proc. Amer. Math. Soc. 2 (1951) 307–314. MR 12, 671e.

[19] Gabriel Sabbagh, Sur les groupes que ne sont pas réunion d’une suite croissante de sous-groupes propres, C. R. Acad. Sci. Paris Sér. A-B 280 (1975) A763–A766. MR 51#3270.

[20] Saharon Shelah, On a problem of Kurosh, Jónsson groups, and applications, pp. 373–394 in Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), Stud. Logic Foundations Math., 95, North-Holland, Amsterdam-New York, 1980. MR 81j:20047.

[21] Simon Thomas, Cofinalities of infinite permutation groups, pp.101–120 in Advances in algebra and model theory (Essen, 1994; Dresden, 1995) Algebra Logic Appl., v.9, 1997. MR 2000a:20005.

[22] Simon Thomas, The cofinalities of the infinite-dimensional classical groups, J. Algebra 179 (1996) 704–719. MR 96k:20005.

[23] Vladimir Tolstykh, Infinite-dimensional general linear groups are groups of universally finite width, preprint, March 2004, 6 pp.. (Author’s e-mail addresses: tvlaa@rambler.ru , vtolstykh@yeditepe.edu.tr .)

[24] Vladimir Tolstykh, On Bergman’s property for the automorphism groups of relatively free groups, preprint, June 2004, 14 pp.. (Author’s e-mail addresses as shown for [23].)

George M. Bergman Department of Mathematics University of California Berkeley, CA 94720-3840 USA gbergman@math.berkeley.edu