Permutation groups whose non-identity elements have k fixed points

Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College London E1 4NS U.K.

                p.j.cameron@qmw.ac.uk

Abstract

In this note I prove an asymptotic structure theorem for groups with the property that any non-identity element fixes exactly k points. I also look briefly at the infinite analogue, and at a conjectured analogue for groups with prescribed sets of fixed-point numbers.

Let K be a set of non-negative integers. A permutation group G has type K if the number fix(g) of fixed points of every non-identity element g ∈ G belongs to K. This note concerns groups of type {k}, that is, those in which every non-identity element of G has exactly k fixed points. We could call such a group an equidistant permutation group, since it is an equidistant permutation array (see [8]) which is also a group.

To motivate what follows, here is the list of permutation groups of type {2}, due to Iwahori [3]:

(a) Any finite group G, acting with two global fixed points and an arbitrary number of regular orbits.

(b) Let A be an abelian group containing at most one involution, and let

G = ⟨A, t : t^{2} = 1, t^{−1}at = a^{−1} for all a ∈ A⟩.

If |A| is odd, then all elements of G \ A are conjugate; take two copies of the action of G on the cosets of ⟨t⟩. If |A| is even, then G \ A splits into two conjugacy classes, with representatives t and t′ say; take the actions of G on the cosets of ⟨t⟩ and ⟨t′⟩. Take also an orbit of length 2 affording the regular action of G/A. Of course, we can also add an arbitrary number of regular orbits.

(c) Let G be the rotation group of a regular tetrahedron, octahedron or icosahedron, acting on the set of vertices, edges and faces of the corresponding polyhedron. (This has type {2} since every rotation has an axis.) As usual we can add an arbitrary number of regular orbits. [Note that the examples under (b), with A cyclic, are dihedral groups acting on the vertices, edges and faces of a regular digon.]

The main theorem below shows that the same pattern holds for any value of k. We begin with a general result true for any type. Note that adding or deleting regular orbits of a group doesn’t change the type.

Proposition 1 Let K be a finite set of non-negative integers. Then a finite permutation group of type K has at most 2 max(K) − 1 non-regular orbits.

Proof. Assume, without loss, that G has no regular orbits. Let k = max(K), let s be the number of orbits, and let x_{i} be the order of the stabiliser of a point in the ith orbit (so that, by assumption, x_{i} ≥ 2 for all i). Then, by the Orbit-Counting Lemma,

s = \frac{1}{|G|} ∑_{g∈G} fix(g) ≤ \frac{1}{|G|}(n + (|G| − 1)k) < k + \frac{n}{|G|},

where n is the degree. Also, the length of the ith orbit is |G|/x_{i}. So

n = ∑_{i=1}^{s} \frac{|G|}{x_{i}} ≤ \frac{s|G|}{2},

so n/|G| ≤ s/2. Thus s < 2k, as claimed.

Theorem 2 Let G be a permutation group in which every non-identity element fixes exactly k points. Then there is a finite list L(k) of groups such that one of the following holds:

(a) G has a fixed set Δ of size k, and the kernel N of the action on Δ is semiregular outside Δ; or

(b) G belongs to the list L(k).

Furthermore, in case (a), if G acts non-trivially on Δ, then N is nilpotent; and if G^{Δ} has even order, then N is abelian.

Proof. The proof that (a) or (b) holds is by induction on k. If k = 1, then G has a unique non-regular orbit, necessarily a fixed point (else there would be elements with no fixed points). So (a) holds, and we can take L(1) to be empty.

Suppose the result is true for all numbers smaller than k, and let G satisfy the hypotheses. We distinguish three cases:

(i) G fixes a point;

(ii) G has an orbit Γ with 1 < |Γ| ≤ k;

(iii) all orbits of G are larger than k.

In case (i), we are done by induction (provided that we include L(k − 1) in L(k)). Assume that (ii) holds. If G acts faithfully on Γ, then G is one of the finitely many subgroups of the symmetric group S_{k}. So let N be the kernel of the action of G on Γ, and assume that N ≠ 1.

Let |Γ| = l. Then every non-trivial element of N has k − l fixed points outside Γ. By the induction hypothesis, either N has a fixed set Γ′ of size k − l, or N is in the list L(k − l). In the second case, |G| is bounded; so assume the first. Let M be the kernel of the action of N on Γ′. Then M is semiregular outside Δ = Γ ∪ Γ′. If |M| ≤ (k − l), then again |G| is bounded. If not, then all orbits of N outside Δ are larger than k − l; so Δ is fixed by G, whence M is normal in G, and (a) holds.

The argument in case (iii) does not invoke the induction hypothesis, but bounds the order of G directly. It depends on the following number-theoretic fact.

Lemma 3 Given a positive integer n and a positive real number α, there exists a positive real number β = β(n, α) such that, for any positive integers x_{1}, …, x_{n},

(∑_{i=1}^{n} \frac{1}{x_{i}} < α) ⟹ (∑_{i=1}^{n} \frac{1}{x_{i}} ≤ α − β) .

Proof. The proof is by induction on n. For n = 1, let y be the smallest integer strictly greater than 1/α, and let β = α − 1/y. Then

\frac{1}{x} < α ⟹ x > \frac{1}{α}
⟹ x ≥ y
⟹ \frac{1}{x} ≤ \frac{1}{y} = α − β.

Now assume the result for n − 1, and let α > 0 be given. Suppose that ∑_{i=1}^{n}(1/x_{i}) < α. We may suppose that ∑_{i=1}^{n}(1/x_{i}) ≥ α/2; then there exists some i such that 1/x_{i} ≥ α/(2n), that is, x_{i} ≤ 2n/α. Suppose that this holds for i = n. Then ∑_{i=1}^{n−1}(1/x_{i}) < α − 1/x_{n}. For each of the ⌊2n/α⌋ possible values of x_{n}, there exists a value β = β(n − 1, α − 1/x_{n}) such that ∑_{i=1}^{n−1}(1/x_{i}) ≤ α − 1/x_{n} − β. So the result holds with the value

β = min{α/2, β(n − 1, α − 1/x) : x ≤ ⌊2n/α⌋}.

Now we return to the proof of the theorem in Case (iii). We may suppose that G has no regular orbits. Let G have degree n and order m.

By the Orbit-Counting Lemma, the number of orbits of G is

\frac{1}{|G|} ∑_{g∈G} fix(g) = (n + (m − 1)k)/m = k + (n − k)/m.

So m divides n − k. Let n = am + k. Then the number of orbits is a + k. Proposition 1 shows that a < k.

Let x_{i} be the order of the stabiliser of a point in the ith orbit, for i = 1, …, a + k. As in the proof of Proposition 1, ∑_{i=1}^{a+k}(m/x_{i}) = n = am + k. So

∑_{i=1}^{a+k} \frac{1}{x_{i}} = a + \frac{k}{m}.  (1)

Suppose that all orbits are bigger than k. Then x_{i} < m/k for all i. So

∑_{i=1}^{a+k−1} \frac{1}{x_{i}} < a.

By the Lemma, ∑_{i=1}^{a+k−1}(1/x_{i}) ≤ a − β(a + k − 1, a). This implies that

\frac{1}{x_{a+k}} ≥ \frac{k}{m} + β(a + k − 1, a) > β(a + k − 1, a).

Thus x_{a+k} < 1/β(a + k − 1, a). The same argument shows that each x_{i} is smaller than 1/β(a + k − 1, a).

So, for given values of k and a, there are only finitely many values for the left-hand side of Equation (1), and hence only finitely many values of m. Since a < k, we conclude that, for given k, there are only finitely many values of m, and conclusion (b) is established in this case.

Finally, suppose that we are in case (a), and that G acts non-trivially on Δ. Choose an element g ∈ G which induces on Δ a permutation of prime order p. Since g^{p} has more fixed points than g, we must have g^{p} = 1, so g has order p. This is true for every element of N⟨g⟩ \ N. Now a theorem of Kegel [5] shows that N is nilpotent.

Note that, since N is nilpotent, g normalises every Sylow subgroup of N, and acts fixed-point-freely on the Sylow q-subgroups for q ≠ p. By a theorem of Higman [2], the nilpotency class of the Sylow q-subgroups is bounded by a function of p for q ≠ p. Hence, if two different primes p, p′ divide |G^{Δ}|, then the nilpotency class of N is bounded by a function of k.

Suppose that only one prime p divides G^{Δ}. Let g ∈ G \ N have order p, as above. Then g fixes a point in a non-trivial N-orbit Δ′. Then

|C_{N}(g)| ≤ |C_{N^{Δ′}}(g)| = | Fix(g) ∩ Δ′| ≤ k.

A theorem of Khukhro [6] shows that N has a normal subgroup whose index and nilpotency class are bounded by functions of k.

However, if G^{Δ} has even order, then we can choose the prime p to be 2. In this case, we have g^{2} = (gn)^{2} = 1 for all n ∈ N, so that g inverts N, and N is abelian.

The main question which remains unanswered is to find an explicit upper bound for the degree or order of a permutation group of type {k} which has no regular orbit and no fixed set of size k. (The proof of the theorem doesn’t easily provide such a bound; but as we have seen, for k = 2, the correct bound for the degree is 62. See [4] for the case k = 3.)

Another problem is to decide whether, if G^{Δ} ≠ 1, the nilpotency class of N is bounded by a function of k.

There is in general no infinite version of Theorem 2. Ol’šanskiǐ [9] has constructed, for large primes p, Tarski monsters: these are infinite groups G with the property that all non-trivial proper subgroups have order p and are conjugate. Such a group, acting by conjugation on one of its p−1 non-trivial conjugacy classes, is transitive and has type {1}. However, for locally finite groups, we have an exact analogue:

Theorem 4 Let G be an infinite locally finite permutation group of type {k}. Then G has a fixed set Δ of cardinality k, whose pointwise stabiliser N is semiregular outside Δ. Moreover, if G acts non-trivially on Δ, then N is hypercentral, nilpotent-by-finite and (hence) soluble.

Proof. Any finite subgroup H of G of order greater than that of any of the groups in case (b) of Theorem 2 has a fixed set Δ of size k and is semiregular outside Δ. Now any element of G\H, together with H, generates a larger finite subgroup, so fixes Δ. The first part of the theorem follows.

Any finite set S of elements of N, together with any one element of G \ N, generate a finite group F satisfying the hypothesis and conclusion (a) of Theorem 2. The intersection of this finite group F with N is nilpotent. So S is contained in a finite nilpotent group. Thus, N is locally nilpotent. Moreover, all these finite subgroups F ∩ N are nilpotent of bounded class by finite of bounded order, and hence soluble of bounded derived length, by Khukhro’s Theorem; so N is soluble (with derived length bounded by a function of k), and also nilpotent-by-finite (with the class of the normal subgroup and order of the factor group bounded by functions of k).

It follows from our earlier remarks that, if at least two primes divide |G^{Δ}|, then N is nilpotent (with class bounded by a function of k). Also, of course, if |G^{Δ}| is even, then N is abelian. Is it true in general that N is nilpotent if G^{Δ} ≠ 1?

Is there any analogue of the main theorem for groups of given type K, where K contains more than one non-negative integer? Most potential analogues are refuted by examples. One conjecture to which I know of no counterexamples is the following. A base for a permutation group G is a sequence of points whose pointwise stabiliser is the identity.

Conjecture. Let G be a permutation group having type K, where |K| > 1. Then either G has a base of cardinality |K|, or G is one of a finite list L(K) of permutation groups.

It may even be true that ‘almost all’ |K|-tuples of points of X are bases, in the sense that the proportion of such tuples which are not bases tends to zero as |X| → ∞.

The theorem of Blichfeldt [1] and Kiyota [7] shows that the order of a permutation group G with degree n and type K is bounded by a polynomial in n of degree |K|. (Precisely, |G| divides ∏_{k∈K}(n − k).) There are examples which meet or are close to this bound. Thus, we cannot expect to find bases with fewer than |K| points.

The conjecture is false for |K| = 1. For example, a group in case (b) in Iwahori’s list (quoted at the start of the paper) has no base of size 1 unless it has a regular orbit. The weaker assertion that, apart from a finite number of exceptions, there is a point x whose stabiliser has order bounded by a function of k follows from Theorem 2 as follows. Clearly the finitely many exceptions under (b) can be ignored. In case (a), let N be the pointwise stabiliser of the fixed k-set, and x a point in a regular N-orbit, so that G_{x} ∩ N = 1. Then

G_{x} ≅ G_{x}N/N ≤ G/N,

so |G_{x}| ≤ |G/N| ≤ k! .

On the other hand, the conjecture is obviously true for the case where K = {0, 1, …, k − 1}. It is easy to see that it holds for K = {0, 2}, since a point stabiliser fixes one further point and acts regularly on the remaining points. Pretzel and Schleiermacher [10] showed that it is true for transitive groups of type {0, 3} (the exceptional groups having degree 9 or 27), and their result is easily extended to arbitrary groups of this type.

If the conjecture turns out to be false, then the weaker conjecture that, with finitely many exceptions, there is a sequence of size |K| whose pointwise stabiliser has order bounded by a function of K, might be true. As we saw, this holds also when |K| = 1.

Acknowledgement I am grateful to L. G. Kovács, M. Pettet and D. E. Taylor for correspondence about Kegel’s theorem.

Added in proof It follows from a result of E. Khukhro, On locally nilpotent groups admitting a splitting automorphism of prime order, Mat. Sb. 130 (1986), 120–127, that, if G is a finite or locally finite group satisfying the hypotheses of Theorem 2, and G acts non-trivially on the fixed set Δ of size k, then the kernel N of the action of G on Δ is nilpotent, with class bounded by a function of k. This answers a question posed in the paper. I am grateful to Andrei Jaikin for this reference.

References

[1] H. F. Blichfeldt, A theorem concerning the invariants of linear homogeneous groups, with some applications to substitution groups, Trans Amer. Math. Soc. 5 (1904), 461–466.

[2] G. Higman, Groups and rings having automorphisms without fixed points, J. London Math. Soc. 32 (1957), 321–334.

[3] N. Iwahori, On a property of a finite group, J. Fac. Sci., Univ. Tokyo 11 (1964), 47–64.

[4] N. Iwahori and T. Kondo, On finite groups admitting a permutation representation P such that Tr P (σ) = 3 for all σ ≠ 1, J. Fac. Sci., Univ. Tokyo 11 (1965), 113–144.

[5] O. H. Kegel, Die Nilpotenz der H_{p}-Gruppen, Math. Z. 75 (1961), 373– 376.

[6] E. I. Khukhro, Finite p-groups admitting an automorphism of order p with a small number of fixed points, Math. Notes 38 (1985), 867–870 (translation from Mat. Zametki 38 (1985), 652–657).

[7] M. Kiyota, An inequality for finite permutation groups, J. Combinatorial Theory (A) 27 (1979), 119.

[8] A. Mahmoodi and P. J. Schellenberg, Equidistant permutation arrays, pp. 326–328 in C. J. Colbourn and J. H. Dinitz (eds.), The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, 1996.

[9] A. Yu. Ol’šanskiǐ, An infinite group with subgroups of prime order, Izv. Akad. Nauk. SSSR Ser. Mat. 44 (1980), 309–321.

[10] O. Pretzel and A. Schleiermacher, On permutation groups whose nontrivial elements have at most three fixed points, Proc. Lond. Math. Soc.

(3) 31 (1975), 1–20.