Preliminary version July 18, 1998

Linearly equivalent actions of solvable groups

B. de Smit and H. W. Lenstra, Jr.

Mathematisch Instituut Rijksuniversiteit Leiden Postbus 9512, 2300 RA Leiden Netherlands E-mail: desmit@wi.leidenuniv.nl Department of Mathematics # 3840 University of California Berkeley CA 94720–3840 USA E-mail: hwl@math.berkeley.edu

Abstract. We determine the positive integers n for which there exist a solvable group G and two non-conjugate subgroups of index n in G that induce the same permutation character. Key words: permutation character, Gassmann equivalence, arithmetical equivalence. 1991 Mathematics subject classification: 20C15, 20F16. Acknowledgements. The authors thank R. M. Guralnick, I. M. Isaacs, and C. Pomerance for their advice. The first author was supported by a fellowship from the Koninklijke Nederlandse Akademie van Wetenschappen. The second author was supported by the National Science Foundation under Grant No. DMS 9224205.

1. Introduction Let G be a group. A G-set is a finite set provided with a left action of G. For a G-set X and g ∈ G we write X^{g} = {x ∈ X : gx = x}. The permutation character of a G-set X is the function π_{X} from G to the ring ℤ of integers that sends g to the cardinality #X^{g} of X^{g}. We say that two G-sets X and Y are linearly equivalent if π_{X} = π_{Y}. By representation theory of finite groups, two G-sets X and Y are linearly equivalent if and only if the permutation modules ℂ^{X} and ℂ^{Y} are isomorphic as modules over the group ring ℂ[G]; here ℂ denotes the field of complex numbers.

Theorem 1. For every positive integer n the following are equivalent:

(1) there exist a finite solvable group G and two non-isomorphic transitive G-sets of cardinality n that are linearly equivalent;

(2) there are prime numbers p, q, r with pqr | n and p | q(q − 1).

If X is a transitive G-set and H is the stabilizer of a point in X then we have π_{X} = 1_{H}^{G}, i. e., the permutation character is the character of G induced by the trivial character 1_{H} of H. Thus condition (1) is equivalent to the existence of a solvable group G with two non-conjugate subgroups H and K of index n for which 1_{H}^{G} = 1_{K}^{G}.

Our interest in condition (1) stems from a number theoretic context. Let L and M be two algebraic numbers fields, and denote by X and Y the sets of field embeddings of L and M, respectively, in some algebraic closure ℚ̄ of the field ℚ of rational numbers. Then X and Y are transitive G-sets, where G is the Galois group of ℚ̄ over ℚ. By Galois theory, X and Y are isomorphic as G-sets if and only if L and M are isomorphic as fields. Moreover, X and Y are linearly equivalent if and only if L and M have the same zeta function; see [2, Exercise 6]. Number fields with the same zeta function are often called “arithmetically equivalent” [11].

By Theorem 1 a number field whose degree n does not satisfy (2) and that is solvable by radicals, is determined up to isomorphism by its zeta-function. To show that, conversely, every integer n that does satisfy (2) is the degree of two non-isomorphic solvable number fields with the same zeta-function, it suffices to combine Theorem 1 with Shafarevich’s claim that every finite solvable group can be realized as a Galois group over ℚ; see [10]. Alternatively, one may try to realize the groups constructed in Section 2 as Galois groups over ℚ.

In Section 2 we shall prove that (2) implies (1). In our construction we can choose G to be 3-step abelian. The G-sets we give are imprimitive. For the case that n is divisible by p^{3} for some prime p one can also use a 2-step abelian construction of Guralnick [5]. One may ask for which n condition (1) holds for a 2-step abelian group. The construction in Section 2 has benefited from [1], where it is proved that one can take exactly five non-isomorphic solvable groups in (1) for n = 12, if the actions are assumed to be faithful. Two of these groups are 2-step abelian, and the other three are only 3-step abelian.

In Sections 3 and 4 we shall prove the following theorem. We denote by φ the Euler phi-function. By an n-element in a finite group we mean an element whose order is built up from primes dividing n.

Theorem 2. Let n be a positive integer. Suppose that n is coprime to φ(n) or is of the form n = pq for prime numbers p and q. Let G be a finite solvable group acting transitively on a set X of cardinality n. Then for any G-set Y the following are equivalent:

(3) for all n-elements g ∈ G we have #X^{g} = #Y^{g};

(4) X and Y are linearly equivalent as G-sets;

(5) X and Y are isomorphic as G-sets.

Any positive integer n for which condition (2) fails, satisfies the hypothesis of Theorem 2. Therefore, the implication (1) ⇒ (2) of Theorem 1 follows from the implication (4) ⇒ (5) in Theorem 2.

The implications (5) ⇒ (4) ⇒ (3) of Theorem 2 are trivial. In Section 3 we prove the implication (3) ⇒ (5) in the case that n is coprime to φ(n), by induction on the number of prime factors of n. In Section 4 we prove (3) ⇒ (5) in the case n = pq.

The condition (3) on G-sets of cardinality n is apparently new. It is forced upon us by the inductive argument of Section 3, since (3) is all we can verify when the inductive assumption is to be invoked. Thus, in the case gcd(n, φ(n)) = 1, we do not know a proof of (4) ⇒ (5) that avoids the detour over (3). This is not true in the case n = pq. In fact, our proof of (3) ⇒ (5) for n = pq is based on the proof of (4) ⇒ (5) for n = pq, p ≠ q that was given by Guralnick and Wales [6].

We do not know whether (3) and (4) are equivalent when the condition on n is dropped, but G is still assumed to be solvable. As Guralnick pointed out to us, some condition on G is necessary: the group G = PSL(2, 11) has two subgroups of order 12 and index n = 55 whose permutation characters are distinct, while they both vanish on all non-trivial nelements. There is also a positive result: if G is any finite group acting transitively on two sets X and Y so that n = #X is a prime power coprime to #G/#X, then (3) and (4) are equivalent; see Isaacs [9].

In Section 5 we consider the set of integers n satisfying condition (1) of Theorem 1 without the assumption that G be solvable. Combining our results with those of Feit, Guralnick, and Wales, which depend on the classification of finite simple groups, we investigate the asymptotics of this set and its complement, and we implicitly list all of its elements up to 2000.

The following notation will be used throughout this paper. The cardinality of a set S is denoted by #S. For sets S and T we let S^{T} be the set of maps from T to S. For subsets S, T of a set we denote the set-theoretic difference {x ∈ S : x ∉ T } by S − T. Suppose that G is a group and that X is a G-set. The set of fix-points of X is denoted by Fix_{G} X; so for g ∈ G we have Fix_{⟨g⟩} X = X^{g}. The set of G-orbits of X is written as G\X. Let N be a normal subgroup of G. The N-orbits of X form a block structure for the G-action, so N\X has a G-set structure for which the natural map X → N\X respects the action of G. In addition, the induced map ℂ^{N\X} → ℂ^{X} is injective with image Fix_{N}(ℂ^{X}), so it gives rise to an isomorphism ℂ^{N\X} → Fix_{N}(ℂ^{X}) of ℂ[G]-modules.

2. Constructing examples Lemma. Let G be a finite group and let A be an abelian normal subgroup of G of prime index. Suppose X and Y are two G-sets each of which is isomorphic to A as an A-set. Write X̄ = G′\X and Ȳ = G′\Y, where G′ is the commutator subgroup of G. Then we have an equality π_{X} − π_{Y} = πX̄ − πȲ of maps from G to ℤ.

Proof. The permutation module ℂ^{X} over G decomposes as a direct sum of 1-dimensional eigenspaces for A, and G permutes these eigenspaces. Such an eigenspace is G-stable if and only if it is fixed pointwise by G′ = [G, A]. Thus, the sum of the G-stable eigenspaces has character πX̄, and the sum V_{X} of the other eigenspaces has character π_{X} − πX̄. Since [G : A] is prime, every g ∈ G with g ∉ A stabilizes only the G-stable eigenspaces. For such g ∈ G the action of g on V_{X} is therefore given by a matrix with only zeros on the diagonal. It follows that the character π_{X} − πX̄ of G is zero on G − A. The same holds for π_{Y} − πȲ, and since X and Y are A-isomorphic we deduce that π_{X} − πX̄ = π_{Y} − πȲ .

Proposition. Let p be a prime number, let k > 1 be an integer, and let m > 1 be a product of prime powers q that are 0 or 1 modulo p. Then there exist a 3-step abelian group G of order (pm)^{k}k and two non-isomorphic transitive G-sets of cardinality pmk that are linearly equivalent.

Proof. Let μ = μ_{p} be the group of pth roots of unity in ℂ. The subring of ℂ generated by μ is denoted by ℤ[μ]. If ζ ∈ μ and ζ ≠ 1, then 1 − ζ generates the unique ideal 𝔭 of ℤ[μ] of index p. By the assumption on the integer m there exists an ideal 𝔞 ⊂ 𝔭^{2} of ℤ[μ] with m = [𝔭^{2} : 𝔞].

The ideal A = 𝔭/𝔞 of the finite ring R = ℤ[μ]/𝔞 acts by translation on the subsets A and 1+A of R. The group μ acts on R by multiplication, and this action stabilizes the sets A and 1 + A. Thus, we obtain an induced action of the semidirect product B = A ⋊ μ of order p^{2}m on the sets X = A and Y = 1 + A of cardinality pm. The commutator subgroup B′ of B is given by B′ = 𝔭^{2}/𝔞, and it has order m. The quotient B-sets X̄ = B′\X and Ȳ = B′\Y have cardinality p. Note that πX̄ ≠ πȲ because μ acts trivially on X̄ but not on Ȳ. By the lemma we also have π_{X} ≠ π_{Y}.

Let Z be a finite group of order k. For any Z-set S the group operation on B makes B^{S} into a group. Moreover, Z acts on this group by group automorphisms: for z ∈ Z and f ∈ B^{S} we let (zf)(s) = f(z^{−1}s) whenever s ∈ S. Identifying B^{S} with ∏_{s∈S} B we see that multiplication in B^{S} is coordinate-wise, and that Z acts on B^{S} by permuting coordinates. We thus obtain actions of the wreath product B^{S} ⋊ Z on X × S and Y × S. We now take the Z-set S to be Z itself, on which Z acts by left multiplication. Since k > 1 we can choose an element z ∈ Z with z ≠ 1. We let α: S → S be the fix-point free Z-set automorphism given by right multiplication by z.

Let us fix an A-set isomorphism φ: X̄ → Ȳ. We define H to be the largest subgroup of B^{S} for which the bijection X̄ × S → Ȳ × S given by φ × α respects the action of H. Now let G = H ⋊ Z. If we choose Z to be abelian we obtain a 3-step abelian group G. We claim that #G = (pm)^{k}k and that the G-sets X × S and Y × S satisfy our conditions, i. e., they are transitive, non-isomorphic, and linearly equivalent.

For each s ∈ S the actions of H on X × {s} and Y × {s} factor through the map H → B sending h to h(s). Applying, for each s ∈ S, the lemma to the group B with its normal subgroup A, we find that there is an equality

π_{X×S} − π_{Y ×S} = π_{X̄×S} − π_{Ȳ ×S}

of functions on H. We know that X̄ × S and Ȳ × S are isomorphic as H-sets, so it follows that π_{X×S} = π_{Y ×S} on H. But on G − H these two permutation characters vanish because all elements of G − H act fix-point free on S. Therefore X × S and Y × S are linearly equivalent over G.

In order to compute #H we now give a more explicit description of H. Let CX̄ and CȲ be the images of B in the permutation groups of X̄ and Ȳ. Then CX̄ and CȲ are both of order p, and the map B → CX̄ × CȲ is surjective with kernel B′. The actions of A on X̄ and Ȳ provide isomorphisms A/B′ ≅ CX̄ and A/B′ ≅ CȲ, which give an isomorphism σ: CX̄ → CȲ. This isomorphism σ respects φ in the sense that for all c ∈ CX̄ we have an equality φ ^{∘} c = σ(c) ^{∘} φ of maps from X̄ to Ȳ. The condition for an element h ∈ B^{S} to lie in H is that for all s ∈ S the isomorphism σ sends the image of h(s) in CX̄ to the image of h(α(s)) in CȲ. It follows that the natural map ψ: H → CS ; Ȳ is surjective with kernel B^{′S}, so that #H = (pm)^{k}.

We now claim that for every s ∈ S the map H → B sending h to h(s) is surjective. To see this, suppose we are given b ∈ B, with image (b_{X}, b_{Y}) in CX̄ × CȲ. Define c ∈ CS ; Ȳ by

c(s) = b_{Y} , c(α(s)) = σ(b_{X}), c(t) = 1 for t ∈ S − {s, α(s)}.

Let h ∈ H be any element with ψ(h) = c. Then h(s) ∈ B maps to (b_{X}, b_{Y}) in CX̄ × CȲ. Multiplying h by a suitable element of B^{′S} we obtain an element h′ ∈ H with h′(s) = b. This proves the claim.

It follows that H acts transitively on X × {s} for each s ∈ S. Since Z acts transitively on S we conclude that X × S is a transitive G-set. The same holds for Y × S.

Let us now show that X×S and Y ×S are not G-isomorphic. Since #B′ = m > 1 there is an element h ∈ B^{′S} so that h(s) = 1 for a unique s ∈ S. We then have (X×S)^{h} = X×{s}. Using that π_{X} ≠ π_{Y}, we choose an element b ∈ B that does not fix the same number of points in X and Y. By the claim above there is an element h′ ∈ H with h′(s) = b. Then the subgroup of H generated by h and h′ does not fix the same number of points in X × S and Y × S. In particular, X × S and Y × S are not even isomorphic as H-sets. This proves the proposition.

We now prove (2) ⇒ (1) in Theorem 1. Suppose that n, p, q, and r are as in (2). Put m = q and k = n/(pq). Then m is a prime that is 0 or 1 modulo p, and k is at least 2 because r | k. The proposition now provides us with a solvable group G and two non-isomorphic linearly equivalent transitive G-sets of cardinality pmk = n.

3. The case that n and φ(n) are coprime In this section we prove the implication (3) ⇒ (5) of Theorem 2 for all positive integers n for which φ(n) is coprime to n. We start with some general remarks.

Let G be a finite group. If N is a normal subgroup of G, and X and Y are linearly equivalent G-sets, then the ℂ[G]-isomorphisms ℂ^{N\X} ≅ Fix_{N}(ℂ^{X}) ≅ Fix_{N}(ℂ^{Y}) ≅ ℂ^{N\Y} imply that N\X and N\Y are also linearly equivalent as G-sets. In particular, with N = G, we see that the number of G-orbits of X depends only on X up to linear equivalence.

Lemma 1. Let G be a solvable group acting faithfully and transitively on a finite set X of square-free cardinality n. Then we have

(a) the group G is annihilated by nφ(n).

Suppose that A is a non-trivial normal p-subgroup of G for some prime p. Then we have

(b) A is elementary abelian;

(c) all orbits of A on X have cardinality p;

(d) p divides n.

Proof. We prove (b, c, d) first. All A-orbits of X have the same cardinality l because G acts transitively on X. Thus, this number l divides both n and the order of A. Since n is square-free and A acts faithfully, it follows that l = p and p | n, which is the content of (c) and (d). The image of A in the permutation group of X is therefore contained in a group generated by pairwise disjoint p-cycles. Using again that A acts faithfully, we deduce that A is elementary abelian. This shows (b).

We now prove (a) by induction on the number of prime factors of n. If n = 1 the statement is trivial, so assume that n > 1. Then G is non-trivial, and since G is solvable there is a non-trivial normal p-subgroup A of G for some prime number p. Let K be the kernel of the action of G on A\X. By (3) each A-orbit of X has size p. The normalizer in the symmetric group on p elements of a cyclic group of order p has order p(p − 1). Since any element of K normalizes the A-action on each A-orbit of X, it follows that K is annihilated by p(p − 1). But by the induction hypothesis, G acts on A\X through a group that is annihilated by (n/p)φ(n/p). Since φ(n) = (p − 1)φ(n/p) statement (a) follows.

Lemma 2. Let G be a solvable group acting faithfully and transitively on a finite set X of cardinality n for which n is coprime to φ(n). Suppose that A is a normal p-subgroup of G for some prime p. Then

(a) G has a normal Sylow p-subgroup;

(b) for every (n/p)-element s ∈ G the subset X^{s} of X is A-stable, and we have (X^{s})^{a} = X^{as} for all a ∈ A.

Proof. From gcd(n, φ(n)) = 1 it follows that n is squarefree. By Lemma 1 all A-orbits on X have cardinality p, and G acts on A\X through a group that is annihilated by (n/p)φ(n/p). By our assumption on n, this number is coprime to p, so a Sylow p-subgroup S of the kernel K of the action of G on A\X is a Sylow p-subgroup of G. Since K has orbits of size p, and K acts on each orbit through a group of order dividing p(p − 1) that has a normal subgroup of order p, the group S is normal and hence characteristic in K. Therefore S is normal in G.

To prove (b), let Z ⊂ X be an A-orbit that meets X^{as} for some a ∈ A. Then Z is s-stable. By Lemma 1(a), applied to the action of ⟨A, s⟩ on Z, we see that s^{p(p−1)} acts trivially on Z. But by our assumption on n, the order of s is coprime to p(p − 1), so that s acts trivially on Z. With a = 1, it follows that X^{s} is a union of A-orbits. Also, one finds that X^{as} ⊂ (X^{s})^{a} for any a ∈ A; the inclusion (X^{s})^{a} ⊂ X^{as} is trivial, so this proves (b).

Lemma 3. Let G be a finite solvable group acting on two finite sets X and Y of cardinality n. Assume that #X^{g} = #Y^{g} for all n-elements g ∈ G, and that G acts transitively on X. Then G acts transitively on Y and the kernel of the G-action on Y is equal to the kernel of the G-action on X.

Proof. For any positive integer n, a Hall n-subgroup of a finite group is a subgroup whose order is built up from primes dividing n and whose index is coprime to n. We will use that a solvable group G contains a Hall n-subgroup for every positive integer n; see [8, VI.1.8].

Let S be a Hall n-subgroup of G. For x ∈ X let S_{x} and G_{x} be the stabilizers of x in S and in G. We have

n = [G : G_{x}] | [G : S_{x}] = [G : S][S : S_{x}],

so n | [S : S_{x}], which implies that S acts transitively on X. Since X and Y are linearly equivalent over S, it follows that S acts transitively on Y as well. In particular, Y is a transitive G-set.

Let K be the kernel of the G-action on X and let N be the normal subgroup of G generated by the n-elements of K. Using that a surjective map of finite groups remains surjective when restricted to n-elements, one proves that [K : N] is coprime to n. By our assumption, N is also contained in the kernel of the action of G on Y, so that G/N acts on Y. Since K/N is normal in G/N and G/N acts transitively on Y, all orbits of K/N on Y have the same cardinality l. Thus l divides #Y = n, and it also divides #(K/N). It follows that l = 1 and that K acts trivially on Y. By the same argument, the kernel of the action of G on Y acts trivially on X. This proves Lemma 3.

Lemma 4. Let A be an abelian p-group, and let X and Y be linearly equivalent A-sets all of whose A-orbits have cardinality p. Then X and Y are isomorphic as A-sets.

Proof. Let B be a subgroup of A of index p. On each A-orbit of X the group B either acts transitively or trivially. The number n_{B}(X) of A-orbits of X that are A-isomorphic to A/B therefore satisfies

(p^{2} − p) · n_{B}(X) = p · #(B\X) − #X.

The right side depends only on X up to linear equivalence, so it follows that n_{B}(X) = n_{B}(Y) for all subgroups B of index p in A. This implies the lemma.

Before moving to the main proof in this section, we recall a property of the Fitting group of a solvable group. A finite group is said to be nilpotent if it is a product of groups of prime power orders. Two normal subgroups of a finite group G whose orders are powers of distinct prime numbers, centralize each other. One deduces that G has a unique maximal normal nilpotent subgroup F, which is called the Fitting group of G. We will use that for a finite solvable group G the centralizer of F in G is contained in F, so that G/F canonically embeds into the group Out F of outer automorphisms of F. We refer to [8, III.4.2] for a proof.

Proposition. Let n be a positive integer for which φ(n) is coprime to n. Let G be a finite solvable group acting transitively on a set X of cardinality n. Suppose that G also acts on a finite set Y and that for all n-elements g ∈ G we have #X^{g} = #Y^{g}. Then X and Y are isomorphic as G-sets.

Proof. We prove this by induction on the number of primes dividing the square-free number n. If n = 1 the result is trivial.

By Lemma 3 the G-set Y is transitive, and the kernels of the G-actions on X and on Y are the same. Since all n-elements of a quotient of G are images of n-elements of G, we may assume that G acts faithfully on both X and Y.

Let F be the Fitting group of G. We see from Lemma 1(a, d), that F is the product of elementary abelian normal subgroups of G of prime power orders, and that all primes dividing #F also divide n. First consider the case that F is cyclic. Then the order of F divides n. The group G/F embeds into Out F, and Aut F has order coprime to n, so [G : F] is coprime to n. But n divides #G, so we must have #F = n. It follows that the point stabilizers in G of points in X and Y are complements to F. Since #F is coprime to [G : F] we have H^{1}(G/F, F) = 0, so all such point stabilizers are conjugate; cf. [13, Chap. I, §5.2]. We conclude that X and Y are isomorphic as G-sets if F is cyclic.

Now assume that F is not cyclic. Then there is a prime number p for which G has a non-cyclic normal p-subgroup. By Lemma 2(a) the group G contains a normal non-cyclic Sylow p-subgroup A. Lemma 1 implies that A is elementary abelian, and that the orbits of A on X and on Y all have cardinality p.

We come to the key step of the proof, which is to consider a ‘block’ of X consisting of elements with the same stabilizer in A. More precisely, take x_{0} ∈ X, let B be the stabilizer of x_{0} in A, and let X_{0} = Fix_{B} X. For g ∈ G we have gx_{0} ∈ X_{0} if and only if B is contained in the stabilizer of gx_{0} in A, which is gBg^{−1}; this occurs if and only if g belongs to the normalizer G_{0} of B in G. Hence G_{0} acts transitively on X_{0} and contains the stabilizer of x_{0} in G. We put n_{0} = #X_{0} = n/[G : G_{0}]. The group B is non-trivial because A is not cyclic. Since B acts faithfully on X it follows that n_{0} < n.

Since G_{0} normalizes B, it acts also on Y_{0} = Fix_{B} Y. We shall apply the induction hypothesis to G_{0} acting on X_{0} and Y_{0}. For this, we need to check that #X_{0}^{g} = #Y_{0}^{g} for any n_{0}-element g ∈ G_{0}. Let g be such, and write g = ts for suitable powers t and s of g so that t is a p-element and s is an (n/p)-element. Note that t ∈ A because A is the normal Sylow p-subgroup of G. Since A is normal, as is an n-element for any a ∈ A, so we have #X^{as} = #Y^{as}. By Lemma 2(b) this implies that X^{s} and Y^{s} are linearly equivalent A-sets, so by Lemma 4 they are isomorphic as A-sets. Therefore we have # Fix_{⟨t,B⟩}(X^{s}) = # Fix_{⟨t,B⟩}(Y^{s}). But again from Lemma 2(b), we have

X_{0}^{g} = Fix_{⟨ts,B⟩} X = Fix_{⟨t,s,B⟩} X = Fix_{⟨t,B⟩}(X^{s}),

and likewise Y_{0}^{g} = Fix_{⟨t,B⟩}(Y^{s}). It follows that #X_{0}^{g} = #Y_{0}^{g}, as desired.

Now the induction hypothesis implies that X_{0} and Y_{0} are isomorphic as G_{0}-sets. The stabilizer H of x_{0} in G is contained in G_{0}, so H stabilizes a point in Y_{0}. Thus, both X and Y are G-isomorphic to G/H. This completes the proof of the proposition, and the proof of the implication (3) ⇒ (5) of Theorem 2 in the case n is coprime to φ(n).

4. The case n = pq In this section we prove the implication (3) ⇒ (5) of Theorem 2 for the remaining case. We let n = pq for two not necessarily distinct prime numbers p and q. We have a solvable group G acting transitively on a set X of cardinality n. It is also given that G acts on a finite set Y and that for all n-elements g ∈ G we have #X^{g} = #Y^{g}. We shall prove that X and Y are isomorphic as G-sets.

As in the proof of the proposition in Section 3, we may assume that the action of G is faithful and transitive on both X and Y. We will first treat two special cases, and then deduce the general case.

Case 1. There is an abelian normal subgroup A of G that acts transitively on X.

Since A is transitive and abelian, any element a of A that fixes a point in X fixes all points of X, so that a = 1. Therefore X and Y are both A-isomorphic to the A-set A. This readily implies that A is equal to its own centralizer in G. In other words, the canonical map G/A → Aut(A) is injective. Note that Aut A is isomorphic to 𝔽_{p}^{∗} × 𝔽_{q}^{∗}, to GL_{2}(𝔽_{p}), or to (ℤ/p^{2}ℤ)^{∗}. By switching p and q if p > q we can achieve that p = q or q ∤ # Aut A. Let S ⊂ G be the preimage in G of a Sylow p-subgroup of G/A. Then S/A is cyclic and [G : S] is coprime to n = pq.

The elements of S are n-elements, so X and Y are linearly equivalent over S. But X and Y have cyclic point stabilizers in S, and therefore X and Y are isomorphic as S-sets. This implies that point stabilizers in G of X and Y give classes in H^{1}(G/A, A) that restrict to the same element of H^{1}(S/A, A). But this restriction map is injective, because [G : S] and #A are coprime [13, Chap. I, §2.4]. This completes the proof for Case 1.

Case 2. There is a normal p-subgroup A of G that is not cyclic, and whose orbits on X have cardinality p.

We first prove that the G-sets X̄ = A\X and Ȳ = A\Y are isomorphic. If g ∈ G is a q-element then X and Y are linearly equivalent as ⟨g, A⟩-sets, so X̄ and Ȳ are also linearly equivalent as ⟨g, A⟩-sets, and #X̄^{g} = #Ȳ^{g}. It follows from the proposition in Section 3, applied to G acting on X̄ and Ȳ, that X̄ and Ȳ are isomorphic as G-sets. From #Y/#Ȳ = #X/#X̄ = p we see that all orbits of A on Y have cardinality p. By Lemma 4 of Section 3 it follows that X and Y are isomorphic as A-sets.

As in the proof in Section 3, we now consider a block of X consisting of elements with the same stabilizer in A. Let x_{0} ∈ X, and let B be the stabilizer of x_{0} in A. As in the previous section, B is non-trivial because A is not cyclic, and # Fix_{B} X is a divisor of n = pq that is smaller than n. Also, Fix_{B} X is a union of A-orbits, so p divides # Fix_{B} X. It follows that # Fix_{B} X = p and that Ax_{0} = Fix_{B} X. Applying an A-isomorphism X → Y, we find y_{0} ∈ Y with Ay_{0} = Fix_{B} Y.

Let H be the stabilizer of x_{0} in G. The group H normalizes H ∩ A = B, so it acts on Fix_{B} X = Ax_{0} and on Fix_{B} Y = Ay_{0}. Therefore H fixes the elements x̄_{0} and ȳ_{0} of X̄ and Ȳ. Since X̄ ≅_{G} Ȳ it follows that X̄ − {x̄_{0}} ≅_{H} Ȳ − {ȳ_{0}}.

Let S be a Sylow p-subgroup of H. The group B acts transitively on each A-orbit in X − Ax_{0} and Y − Ay_{0}. Since S contains B, this implies that all S-orbits of X − Ax_{0} and Y − Ay_{0} are closed under the action of A. It follows that S has the same number of orbits on the four sets X − Ax_{0}, X̄ − {x̄_{0}}, Ȳ − {ȳ_{0}}, and Y − Ay_{0}. Because X and Y are linearly equivalent over S, the number of S-orbits on X and Y is also the same. It follows that S has the same number of orbits on Ax_{0} and Ay_{0}. But S is a p-group fixing x_{0}, and since #Ax_{0} = #Ay_{0} = p, the group S acts trivially on Ax_{0} and Ay_{0}.

The action of H on Ay_{0} is therefore an action on a set of p elements that normalizes the group generated by a p-cycle, and whose Sylow p-subgroup acts trivially. That is only possible if H fixes a point in Ay_{0}, so that the G-sets X, Y, and G/H are all isomorphic. This completes the proof of Case 2.

Proof of the general case. We consider the Fitting subgroup F of G. First suppose that F acts transitively on X. If the center Z of F acts transitively on X then we are done by Case 1. So suppose Z does not act transitively on X. The primes p and q divide the order of the center Z of F, because they divide #F, and Z acts freely on X. It follows that #Z = p = q, and that F is a p-group. Thus Z\X has cardinality p, and F acts transitively on Z\X through a group of order p. Let A be the kernel of this action. Then A is normal in G of order #F/p, and it contains Z. Since its orbits on X have cardinality p and A acts faithfully on X, the group A is elementary abelian. Because F is non-abelian, we have p^{3} | #F and p^{2} | #A. Hence A is non-cyclic, and Case 2 applies.

Now suppose that F does not act transitively on X. Since G/F embeds into Out F we know that F ≠ {1}, so all F -orbits in X have the same prime cardinality, which, after possibly switching p and q, we may assume to be p. If F is non-cyclic then Case 2 applies, so assume that F is cyclic of order p. Then Out F and therefore G/F are also cyclic, and we have p ∤ [G : F]. It follows that G has only one subgroup S of index q, so that all points in F \X or F \Y have stabilizer S in G. The point stabilizers in G of points in X or Y are contained in S, so they are complements of F in S. But such point stabilizers are then conjugate in S because H^{1}(S/F, F) = 0. Thus X and Y are isomorphic as G-sets. This completes the proof of Theorem 2.

5. Non-solvable groups and asymptotic results Write R for the set of positive integers n for which there exists a group G with two nonisomorphic linearly equivalent transitive G-sets of cardinality n. In Theorem 1 we described the subset S of R that consists of those n that arise from solvable groups G. It turns out that both S and R have density 1 in the set of positive integers. We will make this more precise below.

In order to produce elements in R − S we describe two additional constructions of groups G with two non-isomorphic linearly equivalent transitive G-sets. Let L be a finite field, q its cardinality, and let V be a vector space over L of dimension d ≥ 2. We put G = GL V. Every element g ∈ G fixes the same number of elements in V and its dual V^{∗} = Hom_{L}(V, L). This implies that V −{0} and V^{∗}−{0} are linearly equivalent transitive G-sets of cardinality q^{d} − 1. For any divisor m of q − 1 we can divide out by the action of a subgroup of index m in L^{∗}. This leads to two linearly equivalent transitive G-sets of cardinality m(q^{d} − 1)/(q − 1). It is easy to check that these G-sets are not isomorphic if and only if m + d ≥ 4. Multiplying the groups and sets by any group of order k ≥ 1 we find that the set

T = {km(q^{d} − 1)/(q − 1) : q is a prime power, d ≥ 2, m | q − 1, m + d ≥ 4, k ≥ 1}

is a subset of R.

For the second construction we take G = PSL(2, L) where L is a finite field in which 6 ≠ 0 so that q = #L is ±1 modulo 5. A result of Dickson [8, II.8.27] implies that G contains a subgroup H that is isomorphic to A_{5}. We now let K be a conjugate of H by an element of PGL(2, L) that is not contained in G. We claim that G/H and G/K are non-isomorphic linearly equivalent G-sets. Let us sketch a proof. Linear equivalence follows from the fact that for each l ∈ {2, 3, 5} all subgroups of order l in G are conjugate. Now suppose that G/H and G/K are isomorphic, so that H and K are conjugate. Then one first proves that the centralizer of H in PGL(2, L) is trivial. The normalizer of H in PGL(2, L) is bigger than the normalizer of H in G, and it injects to Aut A_{5} = S_{5}. So this injection is an isomorphism. But since in S_{5} any two elements of order 5 are conjugate, it follows that some element of order 5 in G is PGL(2, L)-conjugate to its square. Lifting this element to SL(2, L) and considering its eigenvalues one readily obtains a contradiction. This proves the claim. It follows that the set

U = {kq(q^{2} − 1)/120 : q is a prime power coprime to 6, q ≡ ±1 mod 5, k ≥ 1}.

is contained in R. Unfortunately, this does not give much more information than the inclusion S ∪ T ⊂ R that we knew already, since U − (S ∪ T ) is contained in the set of multiples of 11 and 29 · 59, which arise from q = 11 and q = 59.

The three constructions tell us that S ∪ T ∪ U ⊂ R. We do not know if equality holds. The combined results of Feit, Guralnick, and Wales [4, 5, 6] say that

(∗)  {n ∈ R : n is the product of at most two primes} ⊂ T ∪ U

if the classification of finite simple groups is valid. This represents our only tool in proving that integers do not belong to R.

We now come to the asymptotic results. For two positive real-valued functions f, g that are defined on ℝ_{≥a} for some a ∈ ℝ, we say that f(x) ≲ g(x) as x → ∞ if lim sup_{x→∞} f(x)/g(x) ≤ 1, and we say that f(x) ∼ g(x) as x → ∞ if lim_{x→∞} f(x)/g(x) = 1. We write log^{k} for the k-fold iteration log ^{∘} … ^{∘} log for any positive integer k, and γ for Euler’s constant.

Proposition. We have

(a)  #{n ≤ x : n ∈ R} ∼ #{n ≤ x : n ∈ S} ∼ x

and

(b)  \frac{x log^{2} x}{log x} ≲ #\{n ≤ x : n ∉ R\} ≤ #\{n ≤ x : n ∉ S\} ∼ \frac{xe^{−γ}}{log^{3} x}

for x → ∞, assuming (∗) for the first inequality in (b).

We sketch the proof of the proposition. By Theorem 1 every positive integer n outside S satisfies n = pq, for primes p and q, or gcd(n, φ(n)) = 1. These two properties have known asymptotic behavior: we have

#\{n ≤ x : n = pq for primes p, q\} ∼ \frac{x log^{2} x}{log x} as x → ∞

by Theorem 437 in Hardy and Wright [7], and

#\{n ≤ x : n ≥ 1, gcd(n, φ(n)) = 1\} ∼ \frac{xe^{−γ}}{log^{3} x} as x → ∞

by Erdős [3]. Since for every real number ϵ > 0 we have (log^{2} x)/ log x ≲ ϵ/ log^{3} x as x → ∞, the rightmost “∼” in (b) follows. The second inequality in (b) is trivial. The results in (a) follow immediately because 1/ log^{3} x tends to zero as x → ∞.

It remains to show the first inequality in (b). Let Q be the set of products of two primes. By Theorem 437 from [7], quoted above, it suffices to show that R ∩ Q is “negligible” by comparison with Q, in the sense that

\frac{#\{n ≤ x : n ∈ R ∩ Q\}}{#\{n ≤ x : n ∈ Q\}} → 0 as x → ∞.

Let P be the set of prime numbers, and put V = {(q^{d} − 1)/(q − 1) : q is a prime power, d ≥ 3\}. If (q^{d} − 1)/(q − 1) ≤ x, with d ≥ 3 and q ≥ 2, then one has q^{d−1} ≤ x, so q ≤ \sqrt{x} and d − 1 ≤ (log x)/ log 2. This implies that #\{n ≤ x : n ∈ V\} ≤ \sqrt{x} · (log x)/ log 2, which shows that V ∩ P and V ∩ Q are negligible by comparison with P and Q, respectively. Writing F for the set of Fermat primes, one deduces from (∗) in a straightforward manner that R ∩ Q is contained in the union of the three sets

{29 · 59},  V ∩ Q,  {pq : p ∈ P, q ∈ {11} ∪ F ∪ (V ∩ P)}.

The first two of these sets are negligible by comparison with Q. Also, from the fact that each of {11}, F, and V ∩ P is negligible by comparison with P, it follows by an easy argument that the third set is negligible by comparison with Q as well. The proposition follows.

We finally illustrate our knowledge of R by considering small numbers. It was first shown by Perlis [12] that 7 and 8 are the two smallest elements of R. The elements of T ∪ U below 100 that are not in S are

\begin{matrix}7, 11, 13, 14, 15, 21, 22, 26, 31, 33, 35, 39, \\ 4 & 9, 51, 55, 57, 62, 65, 73, 77, 85, 91, 93. \end{matrix}

By (∗) the following are not in R:

\begin{matrix}9, 10, 17, 19, 23, 25, 29, 34, 37, 38, 41, 43, 46, 47, 53, 58, \\ 5 & 9, 61, 67, 69, 71, 74, 79, 82, 83, 86, 87, 89, 94, 95, 97. \end{matrix}

In [6] this list is given up to 40, with 34 omitted by mistake. At the time of [6] it was unknown whether 18 ∈ R. We now know that 18 ∈ S ⊂ R, and that the list above is equal to {7, 8, ⋯, 100} − R. With the help of (∗) it is not hard to find {n ∈ R : n ≤ 2000} explicitly. The subset S ∪ T ∪ U of R contains 1303 elements up to 2000, of which 1083 are in S. The remaining 697 numbers up to 2000 are products of at most two prime numbers, so that (∗) implies that they are not in R.

Below 4000 there are only 8 values of n for which we cannot decide whether n ∈ R only on the basis of (∗) and the inclusion S ∪ T ∪ U ⊂ R:

\begin{matrix}2001 = 3 · 23 · 29 & 3335 = 5 · 23 · 29 \\ 2185 = 5 · 19 · 23 & 3515 = 5 · 19 · 37 \\ 2755 = 5 · 19 · 29 & 3567 = 3 · 29 · 41 \\ 2829 = 3 · 23 · 41 & 3657 = 3 · 23 · 53. \end{matrix}

References

1. W. Bosma, B. de Smit, Arithmetically equivalent fields of small degree, in preparation.

2. J. W. S. Cassels and A. Fröhlich (eds), Algebraic number theory, Academic Press, London, 1967.

3. P. Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. 12 (1948), 75–78.

4. W. Feit, Some consequences of the classification of finite simple groups, pp. 175–181 in: B. Cooperstein and G. Mason (eds), The Santa Cruz conference on finite groups 1979, Proc. Sympos. Pure Math. 37, Amer. Math. Soc., Providence, RI, 1980.

5. R. M. Guralnick, Subgroups inducing the same permutation representation, J. Algebra 81 (1983), 312–319.

6. R. M. Guralnick and D. B. Wales, Subgroups inducing the same permutation representation, II, J. Algebra 96 (1985), 94–113.

7. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, fourth edition, Oxford University Press, London, 1971.

8. B. Huppert, Endliche Gruppen I, Grundlehren Math. Wiss. 134, Springer-Verlag, Berlin, 1967.

9. I. M. Isaacs, Fixed points and Π-complements in Π-separable groups, Arch. Math. (Basel) 39 (1982), 5–8.

10. V. V. Ishkhanov, B. B. Lur′e, and D. K. Faddeev, The embedding problem in Galois theory, Transl. Math. Monogr. 165, Amer. Math. Soc., Providence, RI, 1997 [translation of 1990 Russian original].

11. N. Klingen, Arithmetical similarities, Oxford University Press, Oxford, 1998.

12. R. Perlis, On the equation ζ_{K}(s) = ζ_{K′}(s), J. Number Theory 9 (1977), 342–360.

13. J-P. Serre, Cohomologie galoisienne, Lecture Notes in Math. 5, fifth edition, Springer-Verlag, Berlin, 1994.