Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 2, 303-323.

Automorphic Subsets of the n-dimensional Cube

Gareth Jones, Mikhail Klin^{1}, Felix Lazebnik

Department of Mathematics, University of Southampton, Southampton SO17 1BJ,UK e-mail: gaj@maths.soton.ac.uk

Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, P. O. Box 653, 84105 Beer-Sheva, Israel e-mail: klin@cs.bgu.ac.il

Department of Mathematical Sciences, University of Delaware, Newark,Delaware, USA e-mail: fellaz@math.udel.edu

Abstract. An automorphic subset of the n-dimensional cube Q_{n} is an orbit of a subgroup of Aut(Q_{n}), acting on the vertices. We develop a theory of such subsets, and we show that those containing 0 coincide with the cwatsets introduced by Sherman and Wattenberg in response to a statistical result of Hartigan. Using this characterisation, together with results from finite group theory and number theory, we answer two questions on cwatsets posed by Sherman and Wattenberg, and we complete the proofs of some results outlined by Kerr. MSC 2000: 05C25, 20B25, 20E22. Keywords: automorphic subset, cwatset, Hamming distance, n-dimensional cube, permutation group, subgraph, wreath product

1. Introduction

Let V = Z_{2}^{n}, an n-dimensional vector space over the field Z_{2} = {0, 1}, or equivalently the vertex-set of the n-dimensional cube Q_{n}. Sherman and Wattenberg [18], motivated by a statistical result of Hartigan [11] (see also [1, 17]), introduced the concept of a cwatset, a set C ⊆ V which is ‘closed with a twist’ (the precise definition is given in Section 5).

1Partially supported by research grant No. 6782-1-95 from the Israeli Ministry of Science and Arts, and by the Department of Mathematics and Computing Sciences, University of the South Pacific, Suva, Fiji Islands.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2000 Heldermann Verlag

304 G. Jones, M. Klin, F. Lazebnik: Automorphic Subsets of the n-dimensional Cube

Their paper contains several open questions about the existence of cwatsets with certain properties. Our aim is to extend the notion of a cwatset to that of an automorphic subset of Q_{n}, namely an orbit of a subgroup of Aut(Q_{n}). We develop a general theory of such subsets, and characterise cwatsets as the automorphic subsets containing the vector 0 ∈ V. We use this theory to construct infinite series of cwatsets which provide negative answers to two questions posed in [18], and to complete some of the results on cwatsets outlined by Kerr in [14]. An extended version of this paper, discussing links with other areas of combinatorics, is available from the authors [13].

In Section 2 we establish the necessary background about the n-dimensional cube Q_{n} and its automorphism group E_{n}. Section 3 contains definitions of an automorphic subset of Q_{n} and of an automorphic orbit of E_{n}, and discusses their properties. In Section 4 we prove some of the assertions in [14], and we use some deep results from group theory and number theory to construct an infinite series of counterexamples to one of the questions posed by Sherman and Wattenberg. In Section 5 we recall the definition and basic properties of cwatsets from [18]; in Theorem 5.2 we relate cwatsets to automorphic sets, and then we briefly consider their connections with binary linear codes and with hypergraphs. In Section 6 we first give some definitions and examples which refine the notions of cyclic cwatsets and direct sum decompositions in [14, 18]; we then give a negative answer to a second question of Sherman and Wattenberg, constructing an infinite series of cwatsets which are not direct sums of cyclic and group cwatsets.

2. Preliminaries

The n-dimensional cube is a graph Q_{n} = (V, E) with vertex set V = Z_{2}^{n}, an n-dimensional vector space over the field Z_{2} = {0, 1} of integers mod (2); vertices u, v ∈ V form an edge {u, v} ∈ E if and only if the vectors u, v differ in exactly one coordinate. Thus each vertex v of Q_{n} has valency n, being adjacent to v + e_{i} for i = 1, …, n, where e_{i} = (0, … 0, 1, 0, …, 0) is the i-th standard basis vector of V.

The distance d(u, v) between vertices u, v ∈ V (the least number of edges in any path from u to v) is called the Hamming distance. If u = (u_{1}, …, u_{n}) and v = (v_{1}, …, v_{n}) then d(u, v) is the number of subscripts i such that u_{i} ≠ v_{i}; equivalently, d(u, v) is the weight (number of non-zero coordinates) of the vector v − u.

We define the distance graphs Q_{n}^{(i)}, where i = 1, …, n, to have vertex set V = Z_{2}^{n}, with vertices u, v adjacent in Q_{n}^{(i)} if and only if d(u, v) = i in Q_{n}. In particular, Q_{n}^{(1)} = Q_{n}. Each Q_{n}^{(i)} is a regular graph of valency \binom{n}{i}, and the edges of Q_{n}^{(1)}, …, Q_{n}^{(n)} form a partition of the edges of the complete graph with vertex set V.

In many applications, another interpretation of V is useful. Let U denote the power set P(N_{n}) of N_{n} = {1, 2, …, n}. This is a group with respect to the operation of symmetric difference A △ B := (A\B)∪(B\A); the empty set ∅ is the identity element, and each A ∈ U is its own inverse. For each A ∈ U we define the characteristic vector χ(A) = (a_{1}, …, a_{n}) ∈ V, where

a_{i} = \{ \begin{matrix}1 & if i ∈ A, \\ 0 & if i ∉ A. \end{matrix}

This function χ : U → V is an isomorphism between the groups (U, △) and (V, +): if a = (a_{1}, …, a_{n}) ∈ V then χ^{−1}(a) = A = {i ∈ N_{n} | a_{i} = 1}. By using χ to identify U with V, we can regard a vertex of Q_{n} as a vector or a subset of N_{n}. If vertices a and b correspond to subsets A and B of N_{n}, then d(A, B) = d(a, b) = |A △ B|.

Another useful interpretation is to identify V with the set Z_{2}^{N_{n}} of all functions ϕ : N_{n} → Z_{2}, by regarding each a = (a_{1}, …, a_{n}) as a function i ↦ a_{i}, so that each subset A ∈ U corresponds to its characteristic function χ_{A}; under point-wise addition mod (2) these functions form a group isomorphic to (V, +). If vertices a and b correspond to functions ϕ = χ_{A} and ψ = χ_{B}, then d(ϕ, ψ) is the number of i such that ϕ(i) ≠ ψ(i).

Our first goal is to describe the automorphism group Aut(Q_{n}) of the graph Q_{n}; this is well-known, but for completeness we include the result. If we think of vertices as vectors, then V acts on itself by addition, each v ∈ V sending a vector a ∈ V to a + v, while S_{n} acts on V by permuting coordinates: each g ∈ S_{n} sends a = (a_{1}, …, a_{n}) to a^{g} = b = (b_{1}, …, b_{n}), where b_{j} = a_{i} whenever i^{g} = j, that is, (a_{1}, …, a_{n})^{g} = (a_{1^{g^{−1}}}, …, a_{n^{g^{−1}}}). Clearly V and S_{n} preserve the edges of Q_{n}, so we can regard them both as subgroups of Aut(Q_{n}). If v ∈ V and g ∈ S_{n} then (if we compose mappings from left to right) g^{−1}vg sends a to a + v^{g}; thus g^{−1}vg ∈ V, so V g = gV and hence the subset E_{n} = S_{n}V of Aut(Q_{n}) is a subgroup. It has V as a normal subgroup, with |S_{n} ∩ V | = 1, so E_{n} is a semi-direct product of V by S_{n}, a group of order 2^{n}n! with E_{n}/V ≅ S_{n}. The action of S_{n} by conjugation on V = Z_{2}^{n} is to permute the n direct factors ⟨e_{i}⟩ ≅ Z_{2} in the same way as it permutes N_{n}, so E_{n} is isomorphic to the wreath product Z_{2} wr S_{n} ≅ S_{2} wr S_{n} of S_{2} by S_{n}. (Traditional Russian and western notations for this group are S_{n} ≀ S_{2} and S_{2} ≀ S_{n}; to avoid confusion we have used the notation in [6]. The action of the wreath product described here is its primitive action of degree 2^{n}, as opposed to its imprimitive action of degree 2n on Z_{2} × N_{n}.)

For a useful equivalent description of E_{n}, we regard V as the set of functions ϕ : N_{n} → Z_{2}. Both S_{n} and S_{2} have actions on V = Z_{2}^{N_{n}}, induced by their actions on N_{n} and Z_{2}: each g ∈ S_{n} sends a function ϕ : N_{n} → Z_{2} to the function ϕ^{g} = g^{−1} ∘ ϕ : i ↦ ϕ(i^{g^{−1}}), and each f ∈ V = Z_{2}^{N_{n}} sends ϕ to ϕ^{f} = ϕ + f : i ↦ ϕ(i) + f(i). The group of permutations of V generated by S_{n} and S_{2} is their exponentiation E_{n} = S_{2} ↑ S_{n} [8]. Each element of E_{n} has a unique representation of the form σ = gf where g ∈ S_{n} and f (∈ V) is a function N_{n} → Z_{2}, and its action on V is given by

ϕ^{σ} = g^{−1} ∘ ϕ + f : i ↦ ϕ(i^{g^{−1}}) + f(i).

If we denote σ = gf by the pair (g, f), then the group structure of E_{n} is given by

(g, f)(g′, f′) = (gg′, f^{g′} + f′),
(g, f)^{−1} = (g^{−1}, f^{(g^{−1})}).

If we identify V with P(N_{n}), then the action of S_{n} on V is induced from its natural action on N_{n}, while V acts on itself by symmetric difference; thus if σ = (g, f), where f corresponds to F = f^{−1}(1) ⊆ N_{n}, then A^{σ} = A^{g} △ F for all A ⊆ N_{n}.

Theorem 2.1. Aut(Q_{n}) = E_{n}.

Proof. We have shown that E_{n} ≤ Aut(Q_{n}); since |E_{n}| = 2^{n}n!, it is therefore sufficient to prove that |Aut(Q_{n})| ≤ 2^{n}n!. To do this, we regard the vertices of Q_{n} as the subsets of N_{n}, with 0 = ∅. Now Aut(Q_{n}) acts transitively on the vertices (since its subgroup V does), so |Aut(Q_{n})| = 2^{n}|H| where H is the stabiliser in Aut(Q_{n}) of ∅. If we can prove that H ≤ S_{n} then |H| ≤ n!, as required.

Suppose, therefore, that h ∈ H. For each k, let M_{k} denote the set of vertices at distance k from ∅ (the k-element subsets of N_{n}). Since h fixes ∅, it permutes the set M_{1} of vertices adjacent to ∅; these are the 1-element subsets of N_{n}, so h acts on them as a permutation g ∈ S_{n}. Since S_{n} ≤ H we have hg^{−1} ∈ H. Now hg^{−1} fixes the vertices in M_{0} ∪ M_{1}, and by induction on k it fixes those in M_{k} for all k: if A ∈ M_{k} with k ≥ 2, then there are exactly k sets B_{1}, …, B_{k} ∈ M_{k−1} adjacent in Q_{n} to A, and A (= B_{1} ∪ ⋯ ∪ B_{k}) is the only set in M_{k} adjacent to each B_{i}; by the induction hypothesis, the vertices B_{1}, …, B_{k} are fixed by hg^{−1}, and hence (by its uniqueness) so is A. Thus hg^{−1} fixes every vertex in V, so it is the identity permutation, giving h = g ∈ S_{n} as required. □

Comments. 1. This shows that the stabiliser in Aut(Q_{n}) of the vertex ∅ = 0 is the subgroup S_{n}.

2. The graph Q_{n} is distance-transitive, that is, if u, v, u′, v′ ∈ V with d(u, v) = d(u′, v′) then there exists σ ∈ Aut(Q_{n}) such that u^{σ} = u′ and v^{σ} = v′. This is because the subgroup V of E_{n} is transitive on the vertices, and S_{n} is transitive on the set M_{k} of vertices at each distance k from ∅.

3. Subgraphs of Q_{n}

If X ⊆ V, we define Γ_{i} = Γ_{i}(X) to be the subgraph Q_{n}^{(i)}(X) of Q_{n}^{(i)} generated (or induced) by X. This graph has vertex set X, and its edges are those edges of Q_{n}^{(i)} whose incident vertices both lie in X. If we regard the integers i = 1, …, n as colours, then by colouring the edges of each Γ_{i} with colour i we obtain the complete coloured subgraph Γ = Γ(X) of Q_{n} generated by X.

For each X ⊆ V we define Stab(X) := { σ ∈ E_{n} | X^{σ} = X }, the subgroup of E_{n} which stabilises X. Our definitions imply that each σ ∈ Stab(X), restricted to X, induces automorphisms of the subgraphs Γ_{i}(X). The group H = Stab(X) induces a permutation group (\overline{H}, X) on X, which is a homomorphic image of the permutation group (H, V).

The complete coloured graph Γ = Γ(X) has automorphism group

G := ⋂_{i=1}^{n} Aut(Γ_{i}).

By our definitions, G contains \overline{H}, but in general these two groups may be different.

We now consider some examples. For notational convenience, we will often write a vector v = (v_{1}, …, v_{n}) ∈ V as v_{1} … v_{n}. Even more concisely, we will sometimes denote v by the integer ∑_{i=1}^{n} 2^{n−i}v_{i} whose binary representation is v_{1}v_{2} … v_{n}; thus the vertex (0, 1, 1) is denoted by 011, or by 3.

Example 3.1. Let n = 3 and X = {0, 3, 7} ⊂ V. The subgraphs Γ_{i} are shown in Figure 3.1. In this case G is the trivial group, and hence so is \overline{H}, while H = ⟨(0)(1, 2)(3)(4)(5, 6)(7)⟩ has order 2.

Figure 3.1

Example 3.2. Let n = 4 and X = {0101, 0110, 0011, 1010, 1001, 1100}. Each vertex in X has distance 4 from one vertex in X, and distance 2 from the remaining four. The subgraph Γ of Q_{4} generated by X therefore has edges of colours 2 and 4, with Γ_{2} an octahedron, and Γ_{4} its complement 3K_{2} (the disjoint union of three complete graphs K_{2}); thus G = Aut(Γ) = Aut(Γ_{2}) = Aut(Γ_{4}), and the latter is the wreath product S_{2} wr S_{3}, of order (2!)^{3} · 3! = 48, acting imprimitively with degree 6 on X.

To determine H we note that there are just two vertices of Q_{4}, namely v = 0000 and w = 1111, adjacent in Q_{4}^{(2)} to every vertex in X. It follows that H acts transitively on {v, w}, so |H : H_{v}| = 2. It is easy to see that H_{v} can be identified with S_{4} in its natural action on V (permuting coordinates), and H with S_{4} × S_{2}. Now H acts faithfully on X, so |\overline{H}| = |H| = 48 = |G| and hence \overline{H} ≅ H ≅ G. As a corollary, we have proved that the octahedral group and the groups S_{2} wr S_{3} and S_{4} × S_{2} are mutually isomorphic; indeed, Theorem 2.1 gives Aut(Q_{3}) = E_{3} = S_{2} wr S_{3}, so they are all isomorphic to E_{3}.

Example 3.3. Our examples so far have all satisfied \overline{H} = G, but the following example shows that this is not always the case. Let n = 7, with

X = {1100000, 1010000, 0110000, 0001100, 0001010, 0001001}.

The coloured graph Γ generated by X has edges of colours 2 and 4, with Γ_{2} ≅ 2K_{3} and Γ_{4} its complement K_{3,3} (a complete bipartite graph). Thus G = Aut(Γ) = S_{3} wr S_{2}, a group of order (3!)^{2} · 2! = 72 acting imprimitively with degree 6 on X. One can easily check that 0 is the only vertex in Q_{7} adjacent in Q_{7}^{(2)} to every vertex in X, so H stabilises 0 and is therefore a subgroup of S_{7} in its natural action on V. Now it is easy to see that H ≅ \overline{H} ≅ S_{3} × S_{3}, acting intransitively on X, so \overline{H} < G. (This example is simply a variation on the Whitney-Jung Theorem on the isomorphism of line graphs [9].)

With each subset X ⊆ V we associate its orbit Orb(X) := {X^{σ} | σ ∈ E_{n}}. The Orbit-Stabiliser Theorem gives

|Orb(X)| = \frac{2^{n}n!}{|H|}.

In Example 3.1, for instance, Orb(X) contains 24 triples, each consisting of two vertices adjacent in Q_{3} together with a vertex adjacent to neither of them. We will refer to two subsets in the same orbit, and their corresponding coloured complete subgraphs, as internally isomorphic, or similar.

A subset X ⊆ V and its corresponding subgraph Γ are called automorphic if (\overline{H}, X) is a transitive permutation group, in which case Orb(X) is an automorphic orbit. We are interested in classifying all automorphic subsets and subgraphs of Q_{n} up to (internal) isomorphism.

If X is an automorphic subset, then each Γ_{i} is a regular graph; we let k_{i} denote its valency, and define k_{0} = 1. We also define k = |X| and b = |Orb(X)|. The distance-transitivity of Q_{n} implies that the following parameters are well-defined:

r is the number of subsets in Orb(X) containing a given vertex in V (such as 0); λ_{i} is the number of subsets in Orb(X) containing a given pair u, v of elements of X such

that the edge {u, v} has colour i.

We now list some basic properties of these parameters; the proofs are simple exercises.

Proposition 3.1. If X is an automorphic set in Q_{n} then

(1) 1 ≤ k ≤ 2^{n};

(2) b = 2^{n}n!/|H|;

(3) k divides |\overline{H}|, |H| and 2^{n}n!;

(4) ∑_{k=0}^{n} k_{i} = k;

(5) vr = bk;

(6) k_{i}r = \binom{n}{i}λ_{i}. (Hint: show that bkk_{i} = 2^{n}\binom{n}{i}λ_{i} and then apply (5).) □

One can enumerate the orbits of E_{n} on subsets of V using cycle indices. The cycle index of any permutation group G is the polynomial

z(G) = \frac{1}{|G|} ∑_{g∈G} z(g),

where

z(g) = x_{1}^{i_{1}}x_{2}^{i_{2}} … x_{m}^{i_{m}}

if g has i_{k} cycles of each length k. Replacing each variable x_{i} in z(G) with 1 + x^{i}, we obtain a generating function f(x) = ∑_{i} a_{i}x^{i}, where a_{i} is the number of orbits of G on i-element subsets.

Example 3.4. The cycle index of E_{3}, acting on V = Z_{2}^{3}, is

z(E_{3}) = \frac{1}{48}(x_{1}^{8} + 6x_{1}^{4}x_{2}^{2} + 8x_{1}^{2}x_{3}^{2} + 13x_{2}^{4} + 8x_{2}x_{6} + 12x_{4}^{2}),

so

f(x) = 1 + x + 3x^{2} + 3x^{3} + 6x^{4} + 3x^{5} + 3x^{6} + x^{7} + x^{8},

and E_{3} has f(1) − f(0) = 21 orbits on the nonempty subsets of V. By detailed examination, one finds that only 10 of these 21 orbits are automorphic. In the following table, the set X in row i is an automorphic set from the i-th orbit; the elements of X are decimal representations of binary expansions.

\begin{matrix}# & k & X & b & r & k_{1} & k_{2} & k_{3} & λ_{1} & λ_{2} & λ_{3} & |\overline{H}| & |H| & |G| \\ 1 & 1 & \{0\} & 8 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 6 & 1 \\ 2 & 2 & \{0,1\} & 12 & 3 & 1 & 0 & 0 & 1 & 0 & 0 & 2 & 4 & 2 \\ 3 & 2 & \{0,3\} & 12 & 3 & 0 & 1 & 0 & 0 & 1 & 0 & 2 & 4 & 2 \\ 4 & 2 & \{0,7\} & 4 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 12 & 2 \\ 5 & 3 & \{0,3,5\} & 8 & 3 & 0 & 2 & 0 & 0 & 2 & 0 & 6 & 6 & 6 \\ 6 & 4 & \{0,1,4,5\} & 6 & 3 & 1 & 2 & 0 & 2 & 1 & 0 & 8 & 8 & 8 \\ 7 & 4 & \{0,1,6,7\} & 6 & 3 & 1 & 1 & 1 & 1 & 1 & 3 & 8 & 8 & 8 \\ 8 & 4 & \{0,3,5,6\} & 2 & 1 & 0 & 3 & 0 & 0 & 1 & 0 & 24 & 24 & 24 \\ 9 & 6 & \{0,2,3,4,5,7\} & 4 & 3 & 2 & 2 & 1 & 2 & 2 & 3 & 12 & 12 & 12 \\ 10 & 8 & V & 1 & 1 & 3 & 3 & 1 & 1 & 1 & 1 & 48 & 48 & 48 \end{matrix}

Table 3.1: Automorphic orbits of E_{3}

A natural problem is to find all possible sizes k of automorphic subsets of Q_{n} for each n. Proposition 3.1 shows that k ≤ 2^{n} and k | 2^{n}n!, but are these simple necessary conditions also sufficient? The answer is (trivially) yes for n ≤ 2, and Table 3.1 confirms this for n = 3. For n = 4 the conditions are satisfied by k = 1, 2, 3, 4, 6, 8, 12, 16, and one can find a k-element automorphic subset in each case.

We will show that for n ≥ 5 these conditions are insufficient. Our first counterexamples are based on simple combinatorial principles.

Proposition 3.2. Let k = 2^{n} − 2^{n−4}, where 5 ≤ n ≤ 14. Then k ≤ 2^{n} and k divides 2^{n}n!, but there is no automorphic subset X ⊆ V with k elements.

Proof. Clearly k ≤ 2^{n}, and k = 2^{n−4} · 15 divides 2^{n}n! for all n ≥ 5. If X is a k-element subset of V, then the subgraph Γ(X) must have a vertex of valency less than the valency n of Q_{n}, for otherwise the connectedness of Q_{n} gives X = V. If X is automorphic then Γ(X) is regular, of valency less than n, so each of the k vertices in X is adjacent in Q_{n} to a vertex v ∈ V \ X. Now there are 2^{n−4} such vertices v, each of valency n, so by counting edges we get k ≤ n2^{n−4} and hence n ≥ 15, against our hypothesis. □

In Section 4 we will use more advanced methods to construct infinitely many counterexamples.

4. Group-theoretic analysis of automorphic subsets

The mapping φ : E_{n} → S_{n}, σ = (g, f) ↦ g is an epimorphism, with ker(φ) = V. For any H ≤ E_{n}, let H̃ denote φ(H). The Orbit-Stabiliser Theorem implies that if X is an automorphic subset and H = Stab(X), then

k = |X| = |H : H_{x}|

where H_{x} is the subgroup of H fixing some x ∈ X.

Lemma 4.1. k = |H̃ : H̃_{x}| · |H ∩ V |.

Proof. Using ker(φ|_{H}) = H ∩ V and ker(φ|_{H_{x}}) = {0} ⊂ V, we have

k = |H : H_{x}| = \frac{|H|}{|H_{x}|} = \frac{|H̃| · |ker(φ|_{H})|}{|H̃_{x}| · |ker(φ|_{H_{x}})|} = \frac{|H̃|}{|H̃_{x}|} · |ker(φ|_{H})| = |H̃ : H̃_{x}| · |H ∩ V |. □

Corollary 4.2. If k is odd then H ∩ V = {0} and k = |H̃ : H̃_{x}|.

Proof. Since H ∩ V is a subgroup of V, its order is a power of 2, so Lemma 4.1 gives |H ∩ V | = 1 and the result follows. □

The subgroup S_{n} of E_{n} is the stabiliser of 0, and as such it is conjugate in E_{n} to the stabiliser of any other vertex, so we have a conjugacy class of subgroups isomorphic to S_{n}. There are 2^{n−1} subgroups in this conjugacy class, each fixing two antipodal vertices. We are interested in whether this is the only conjugacy class of subgroups isomorphic to S_{n}.

Example 4.1. When n = 2 we have E_{2} ≅ D_{4}, the dihedral group of order 8 (the symmetry group of a square). This has five subgroups isomorphic to S_{2}, forming three conjugacy classes: one consists of the two stabilisers of vertices, and the other two consist of one and two subgroups of V.

Example 4.2. If n = 3 then, in addition to the conjugacy class of vertex-stabilisers, E_{3} has a second class of subgroups isomorphic to S_{3}. If we regard Q_{3} as the vertices and edges of a regular solid in R^{3}, then its symmetry group is E_{3} ≅ S_{4} × S_{2} (see Example 3.2). The rotation group, corresponding to S_{4}, acts naturally on the four diagonals (edges in Q_{3}^{(3)}), so it has four subgroups isomorphic to S_{3}, each preserving a diagonal. These subgroups have orbits of length 2 and 6 on V, so they are not vertex-stabilisers.

Example 4.3. The above example generalises to higher dimensions, though the concept of a rotation is no longer valid. The stabiliser in E_{n} of the vertex 0 consists of the automorphisms σ = (g, 0) with g ∈ S_{n}. If v denotes the vector 11 … 1 at maximum distance n from 0, then the elements of E_{n} preserving the diagonal {0, v} are those of the form σ = (g, f) where g ∈ S_{n} and f ∈ {0, v}, forming a subgroup isomorphic to S_{n} × S_{2}; those σ with g even and f = 0, or with g odd and f = v, form a subgroup isomorphic to S_{n} which does not stabilise any vector. We have therefore found two conjugacy classes of subgroups of E_{n} isomorphic to S_{n}; in each case, the normaliser of such a subgroup is S_{n} × S_{2}, so the number of subgroups in each conjugacy class is equal to the index |E_{n} : S_{n} × S_{2}| = 2^{n−1}.

Theorem 4.3. If n = 3 or n ≥ 5, then the subgroups described in Example 4.3 are the only subgroups S ≤ E_{n} isomorphic to S_{n}. If n = 4 then there are 16 additional subgroups S ≅ S_{4}, each satisfying |S ∩ V | = 4.

Proof. We will use the cohomology of groups; [2] or [12, I.16–I.17] are good references.

Let n ≥ 3 and let S be any subgroup of E_{n} isomorphic to S_{n}. Now V is a normal subgroup of E_{n}, so S ∩ V is a normal subgroup of S; being a subgroup of V, it has order a power of 2. For n ≠ 4 the only proper normal subgroups of S_{n} are the alternating group A_{n} (of order n!/2) and the trivial subgroup, while S_{4} also has a normal Klein four-group K, so either |S ∩ V | = 1 or S ∩ V ≅ K with n = 4.

Suppose first that |S ∩ V | = 1. Now V is normal in E_{n}, so SV is a subgroup of E_{n} of order |S| · |V |/|S ∩ V | = 2^{n}n! ; thus SV = E_{n}, so S is a complement for V in E_{n}. In general, conjugacy classes of complements for abelian normal subgroups can be studied using cohomology theory, as follows.

Any group G, acting by automorphisms on an abelian group A (so that A is a G-module) determines a sequence of cohomology groups H^{i}(G, A), i ≥ 1; in particular, if GA denotes the semi-direct product (split extension) of A by G, then the conjugacy classes of complements for A in GA are in one-to-one correspondence with the elements of H^{1}(G, A) (see [2, IV.2.3] or [12, I.17.3(a)]). In our case, this implies that the conjugacy classes of complements for V in E_{n} = S_{n}V correspond to the elements of H^{1}(S_{n}, V). Now S_{n} acts on V = Z_{2}^{n} by conjugation, permuting the n standard basis vectors, so that V is the natural permutation module for S_{n} over Z_{2}. The permutation module M for any transitive group G is isomorphic to the induced G-module N^{G} obtained from the trivial 1-dimensional module N for a point-stabiliser in G, so in our case V ≅ Z_{2}^{S_{n}}, where Z_{2} is a trivial S_{n−1}-module. Shapiro’s Lemma [2, III.6.2] states that if a G-module A is the induced module B^{G} obtained from some H-module B, where H ≤ G, then H^{1}(G, A) ≅ H^{1}(H, B). (Strictly speaking, Shapiro’s Lemma applies to coinduced modules, but for finite groups G these are the same as induced modules [2, III.5.9].) In our case, we therefore have H^{1}(S_{n}, V) ≅ H^{1}(S_{n−1}, Z_{2}). If B is a trivial H-module, then H^{1}(H, B) ≅ Hom (H, B), the group of homomorphisms H → B [2, III.1, Exercise 2]. For n ≥ 3 there are just two homomorphisms S_{n−1} → Z_{2}, so |H^{1}(S_{n}, V)| = 2 and there are just two conjugacy classes of complements for V in E_{n}; these are the classes described in Example 4.3, and we have shown that for n ≠ 4 they provide the only subgroups of E_{n} isomorphic to S_{n}.

There remains the case where n = 4 and S ∩ V is a Klein four-group normal in S. Then φ(S) ≅ SV/V ≅ S/(S ∩ V) ≅ S_{3}, so SV = φ^{−1}(T) where T is a subgroup of S_{4} isomorphic to S_{3}. There are four such subgroups T ≤ S_{4}, namely the stabilisers of 1, 2, 3 and 4, so there are four corresponding subgroups SV ≤ E_{4}, each a semi-direct product T V of V by T. Since T acts on V by fixing one of its four standard basis vectors and permuting the other three as S_{3}, it follows that T V ≅ S_{2} × (S_{2} wr S_{3}) ≅ S_{2} × S_{2} × S_{4} (see Example 3.2 for the last isomorphism). This group has four subgroups isomorphic to S_{4}: in addition to the direct factor S_{4}, three others may be obtained from this one by multiplying the elements of S_{4} \ A_{4} by one of the three involutions in the factor S_{2} ×S_{2} (this is an adaptation of the construction in Example 4.3). Since each such subgroup S is contained in a unique subgroup SV = T V, we obtain 16 subgroups S with |S ∩ V | = 4; each has normaliser SV, of index 4 in E_{4}, so there are four groups in each of four conjugacy classes of such subgroups. □

The combinatorial interpretation of the extra subgroups for n = 4 is that there are four ways of expressing V as a direct sum V_{1} ⊕ V_{3} of 1- and 3-dimensional subspaces by choosing a partition 1 + 3 = 4 of its standard basis vectors; in each case there is a subgroup E_{1} × E_{3} of E_{4} preserving this decomposition, with E_{3} (the symmetry group S_{2} wr S_{3} ≅ S_{4} × S_{2} of a cube) containing two subgroups isomorphic to S_{4}, and two others obtained by composing the elements of S_{4} \ A_{4} with the non-identity element of E_{1} ≅ S_{2}.

Lemma 4.4. If G is a subgroup of E_{n} with an orbit of odd length in V, then G fixes a vertex v ∈ V.

Proof. For each subset X of V, define v(X) = ∑_{x∈X} x ∈ V. Each g ∈ S_{n} acts on V as a linear transformation, so

v(X^{g}) = ∑_{x∈X} x^{g} = ( ∑_{x∈X} x)^{g} = v(X)^{g}.

Each f ∈ V acts on V as a translation x ↦ x + f, so

v(X + f) = ∑_{x∈X}(x + f) = ( ∑_{x∈X} x) + |X|f = \{ \begin{matrix}v(X) & if |X| is even, \\ v(X) + f & if |X| is odd. \end{matrix}

Thus if |X| is odd and σ = (g, f) ∈ E_{n} then v(X^{σ}) = v(X)^{σ}, and in particular if σ leaves X invariant then it fixes v(X). It follows that if a subgroup G of E_{n} has an orbit X of odd length then v(X) is fixed by G. □

(This result is a discrete analogue of the classical result that any finite group of isometries of R^{n} has a fixed-point: this is the centroid, or average, of the points in some orbit, found by adding these points and then dividing by the number of them. In our case, with coefficients in Z_{2} rather than R, we need the number of points to be odd in order that this averaging can take place. The proof we have given is an adaptation of an earlier proof shown to us by M. Muzychuk.)

Theorem 4.5. (Kerr’s bound) If X is an automorphic subset of Q_{n} and |X| is odd, then

|X| ≤ \binom{n}{⌊\frac{n}{2}⌋}.

Proof. Let G be the stabiliser of X in E_{n}. Since |X| is odd, Lemma 4.4 implies that G has a fixed-point in V. By replacing G with a suitable conjugate we may assume that this point is 0. Then G is contained in the stabiliser S_{n} of 0, so X, which is an orbit of G, is contained in an orbit of S_{n} on V. These orbits are the sets M_{i} of i-element subsets of N_{n} for 0 ≤ i ≤ n, with |M_{i}| = \binom{n}{i}, so |X| is bounded above by the greatest of these binomial coefficients, which corresponds to i = ⌊n/2⌋. □

This result was stated, though without a complete proof, in [14]. For example, it implies that there are no automorphic k-element subsets of Q_{n} for

a. n = 5, k = 15, b. n = 6, k = 45, c. n = 7, k = 45, 63, 105, and so on, even though these values of n and k satisfy the conditions k ≤ 2^{n} and k | 2^{n}n! given by Proposition 3.1.

In the remainder of Section 4 we use more advanced results on finite groups to improve on Kerr’s non-existence result. For background details, see [6, 16, 19].

For each prime p the affine general linear group AGL_{1}(p) consists of the affine transformations

σ = σ_{a,b} : x ↦ ax + b

of the field Z_{p}, where a, b ∈ Z_{p} and a ≠ 0. This is a doubly transitive permutation group of degree p and order p(p − 1). If K is any subgroup of the multiplicative group Z_{p}^{∗} = Z_{p} \ {0}, then

H = {σ_{a,b} | a ∈ K, b ∈ Z_{p}}

is a transitive group of degree p and order kp, where k = |K| divides p − 1; such groups H, called affine groups, are in a sense the most ‘typical’ transitive groups of prime degree. More precisely, we have:

Burnside’s Theorem. Each transitive permutation group of prime degree is an affine group or is doubly transitive.

(Note that AGL_{1}(p) is affine and doubly transitive.) This theorem was first proved by Burnside in [3] (see also [4]), using representation theory. The most elementary proof is in [7] which, together with the editorial remarks in [20], gives further references and historical details.

Proposition 4.6. Let p be any prime distinct from 11 and 23, and not of the form (q^{d} − 1)/(q − 1) where q is a prime-power and d ∈ N, d ≥ 2. Then the only transitive permutation groups of degree p are S_{p}, A_{p} and affine groups.

Proof. One consequence of the classification of finite simple groups is that the doubly transitive finite permutation groups are all known [5, 6]. Among them, the only groups of prime degree p are the affine group AGL_{1}(p), the symmetric group S_{p}, the alternating group A_{p}, three groups P SL_{2}(11), M_{11} and M_{23} of degrees p = 11, 11 and 23 respectively, and certain subgroups of P ΓL_{d}(q) where p = (q^{d} − 1)/(q − 1) for some prime-power q and d ≥ 2. (Full details of these groups can be found in the sources given above.) Burnside’s Theorem now completes the proof. □

Lemma 4.7. There are infinitely many primes p satisfying the hypotheses of Proposition 4.6.

Proof. The following argument is based on Cameron’s outline proof of his Proposition 7.2 in [5]. The Prime Number Theorem [10, §1.8 and Ch. XXII] states that the number π(x) of primes n ≤ x satisfies

π(x) ∼ \frac{x}{log x} as x → +∞.

We shall show that the set of primes of the form n = (q^{d} − 1)/(q − 1), where q = p^{e} is a prime-power and d ≥ 2, is significantly less dense than the set of all primes. (In fact, it is not known whether there are infinitely many primes of this form.)

First suppose that d = 2, so n = q + 1. If n is prime then q must be even, so p = 2 and n = 2^{e} + 1. If n ≤ x then e < log_{2} x, so the number of such primes n ≤ x is O(log x). (These are the Fermat primes, of which only five are known to exist.)

Now suppose that d ≥ 3. Then n > q^{d−1} ≥ p^{2}, so the number of primes p for which n ≤ x is

O(π(\sqrt{x})) = O(\begin{matrix}√ & \overline{x} \\ log & \sqrt{x} \end{matrix}) = O(\frac{\sqrt{x}}{log x}).

For any such p, we have (d−1)e < log_{p} n = O(log x), so the number of pairs d, e giving n ≤ x is O((log x)^{2}). (In fact, it is O(log x · log log x), but the weaker estimate is sufficient here.) It follows that the number of integers n ≤ x of the form (q^{d} − 1)/(q − 1) with d ≥ 3 is

O(\frac{\sqrt{x}}{log x}) · O((log x)^{2}) = O(\sqrt{x} log x).

Taking the cases d = 2 and d ≥ 3 together, we see that the number of primes n ≤ x of the form (q^{d} − 1)/(q − 1) is O(\sqrt{x} log x). Since

\frac{\sqrt{x} log x}{π(x)} ∼ \frac{(log x)^{2}}{\sqrt{x}} → 0 as x → +∞,

‘most’ primes (and in particular, infinitely many) do not have the form (q^{d} − 1)/(q − 1), so the result immediately follows. □

The smallest odd primes satisfying the hypotheses of Proposition 4.6 are 19, 29, 37, …

Theorem 4.8. There are infinitely many pairs of integers (k, n) such that 1 ≤ k ≤ 2^{n} and k divides 2^{n}n!, but there is no automorphic subset X ⊆ Q_{n} with |X| = k.

Proof. If there is an automorphic subset X where |X| = k is odd, then by Corollary 4.2 there are subgroups H̃_{x} ≤ H̃ ≤ S_{n} with |H̃ : H̃_{x}| = k. It is therefore sufficient to produce infinitely many pairs (k, n), satisfying the hypotheses of the theorem, for which k is odd and S_{n} has no pair of subgroups S ≥ T with |S : T | = k.

By Proposition 4.6 and Lemma 4.7, there are infinitely many odd primes n such that the only transitive groups of degree n are S_{n}, A_{n} and affine groups. Given such a prime n, choose an odd integer m such that 2 < m < (n − 1)/2 and m does not divide n − 1. For instance, we can take m = (n − 3)/2 or (n − 5)/2 as n ≡ 1 or 3 mod (4). We then define k = mn, so k is odd, k | 2^{n}n! and k ≤ 2^{n}.

Now suppose that T ≤ S ≤ S_{n}, with |S : T | = k, so that both m and n divide |S|. Since n is prime, S contains an n-cycle and is therefore a transitive group of degree n. It cannot be a subgroup of AGL_{1}(n), since this has order n(n − 1) which is not divisible by m; thus S = S_{n} or A_{n}, and |T | = n!/k = (n − 1)!/m or n!/2k = (n − 1)!/2m respectively.

In either case, n does not divide |T |, so T is intransitive. If T has an orbit of length n−1, then T is contained in S ∩ S_{n−1} (= S_{n−1} or A_{n−1}) with index m; since 2 < m < n − 1, this is impossible by the simplicity of A_{n−1}. Hence T ≤ S ∩ (S_{r} × S_{n−r}) for some r = 2, 3, …, n − 2, so |S : T | ≥ \binom{n}{r} ≥ \binom{n}{2}, which is impossible since m < (n − 1)/2. □

The smallest value of n provided by the proof of Theorem 4.8 is n = 19: here one can take m = 5 or 7, so that Q_{19} contains no automorphic subsets of size k = 95 or 133.

5. Cwatsets and hypergraphs

Motivated by definitions introduced in [18], we now restrict our attention to automorphic subsets containing 0.

Sherman and Wattenberg [18] define a subset C ⊆ V to be a cwatset (closed with a twist) if, for each c ∈ C, there exists g ∈ S_{n} such that C + c = C^{g}. For example, any additive subgroup C ≤ V is a cwatset: take g = e (the identity permutation) for each c ∈ C. Since each g ∈ S_{n} fixes 0, and since c + c = 0 for each c ∈ V, it is clear that each nonempty cwatset contains 0.

Just as we defined the projection φ : E_{n} → S_{n} by σ = (g, f) ↦ g, we now define a projection π : E_{n} → V by σ = (g, f) ↦ f. Note that 0^{σ} = 0^{g} + f = f, so we have π(σ) = 0^{σ}. Although φ is a homomorphism, π is not.

Proposition 5.1. A nonempty subset C ⊆ V is a cwatset if and only if it is the image π(G) of some subgroup G ≤ E_{n} under the projection π : E_{n} → V, σ ↦ 0^{σ}.

For the proof, which is elementary, see Proposition 6 of [18].

Theorem 5.2. A nonempty subset C ⊆ V is a cwatset if and only if C is an automorphic subset of V containing 0.

Proof. We have to show that C is a cwatset if and only if it is the orbit of 0 under some subgroup G ≤ E_{n}. Since π(σ) = 0^{σ} we have π(G) = 0^{G} for each G ≤ E_{n}, so the result is just a restatement of Proposition 5.1. □

Corollary 5.3. If C is a nonempty cwatset and H = Stab(C) then |C| = |H : H_{0}| = |H|/|H_{0}|.

Proof. This is a direct application of the Orbit-Stabiliser Theorem. □

While the results proved earlier for automorphic subsets remain valid for cwatsets, we can use the special nature of cwatsets to deduce extra information. Recall from Section 3 that subsets X_{1} and X_{2} of V are similar if X_{1}^{σ} = X_{2} for some σ ∈ E_{n}. We regard the classification of cwatsets up to similarity as the main problem of the theory of cwatsets. As defined in Section 3, the invariant b = b(C) of a cwatset C is just the number of subsets of V similar to C. Similarly, Theorem 5.2 implies that the invariant r = r(C) defined in Section 3 is the number of cwatsets similar to C.

Proposition 5.4. (a) Two cwatsets C_{1} and C_{2} are similar if and only if C_{1}^{g} = C_{2} for some g ∈ S_{n}.

(b) The number r of cwatsets similar to a k-element cwatset C is given by

r = \frac{bk}{2^{n}} = \frac{n!}{|H_{0}|}.

Proof. The proof of (a) follows easily from the definition of a cwatset, and then the Orbit-Stabiliser Theorem, applied to S_{n}, gives r = n!/|H_{0}|. Alternatively, one can deduce this formula from r = bk/2^{n} (Proposition 3.1(5)), using b = |E_{n} : H| and k = |H : H_{0}|. □

The origins of cwatsets go back to statistics (see the references in [18] and especially [11]), where they are used for the construction of confidence intervals for the mean or median of certain random variables. Roughly speaking, statisticians need subsets X of V = P(N_{n}) (sets of samples) which are ‘smooth’ in the sense that certain parameters of each element of X are equal. The existence of a subgroup of E_{n} acting transitively on X guarantees this. For technical reasons one also wants ∅ ∈ X, so cwatsets satisfy the required conditions. This raises two intriguing questions. Although the concept of a cwatset is sufficient, is it also a necessary condition for this statistical smoothness? Secondly, although we have taken an essentially group-theoretic approach to cwatsets, can they be axiomatised purely combinatorially, thus leading to an alternative approach which might give additional insight into their properties and applications? For a discussion of such an approach, see Section 7 of [13].

We will now consider the simplest class of cwatsets, namely the subgroups of V, called group cwatsets, or simply groups.

For any cwatset C, we define d = d(C) = min {i | 1 ≤ i ≤ k and k_{i} ≠ 0}.

Proposition 5.5. (a) If C is a group cwatset of order k then k = 2^{l} for some l = 0, 1, …, n.

(b) The number of group cwatsets of order 2^{l} in V is

[{n \atop l}]_{2} = \frac{(2^{n} − 1)(2^{n−1} − 1) … (2^{n−l+1} − 1)}{(2^{l} − 1)(2^{l−1} − 1) … (2 − 1)}.

(c) If C is a k-element group cwatset, then k ≤ 2^{n−d+1}.

Proof. Part (a) is an application of Lagrange’s Theorem. In (b), the numerator counts all bases for such group cwatsets C (sets of l linearly independent vectors) in the n-dimensional vector space V, and the denominator counts those bases generating a particular C. In (c), the parameter d is simply the minimum size of any nonempty subset in C ⊆ V = P(N_{n}); if A_{1}, A_{2} are distinct subsets of N_{d−1} (and thus elements of V) then the cosets C △ A_{1} and C △ A_{2} of C in V are distinct, so |P(N_{d−1})| ≤ |V : C| giving k ≤ 2^{n}/2^{d−1} = 2^{n−d+1}. □

For each prime-power q, the Gaussian coefficient [{n \atop l}]_{q} is the number of l-dimensional subspaces in an n-dimensional vector space over the field of order q; it is given by replacing each 2 with q in the formula in Proposition 5.5(b) (see [15], for instance). Taking the limit as q → 1, we obtain the binomial coefficient \binom{n}{l}.

In coding theory, a binary code of length n is a nonempty subset of V, the vectors being regarded as codewords; a binary linear code is a subgroup of V, that is, a group cwatset. In this case, the parameter d is the minimum distance of C, and the bound in Proposition 5.5(c) is known as the Singleton bound. The codes attaining this bound form an interesting class, the simplest example of which is given in row 8 of Table 3.1: the vertex set of a tetrahedron contained in Q_{3}. Thus automorphic sets and cwatsets form a generalisation of linear codes, a theory where algebraic arguments have been successfully combined with purely combinatorial reasoning. We finish our remarks on codes with an example.

Example 5.1. If n = 4 then by Proposition 5.5(b) there are 15 · 7/3 · 1 = 35 group cwatsets C of order k = 4. Now Proposition 5.5(c) gives d(C) ≤ 3, but in fact this bound is not attained; this is shown by the description of the 35 cwatsets in following table. Each row represents the similarity class of some group cwatset C in V = P(N_{4}). The numbers k_{i} can be interpreted as the coefficients of the weight enumerator polynomial of C.

#  C  k_{1} k_{2} k_{3} k_{4}  r  d
1 {∅, {1}, {2}, {1, 2}}  2 1 0 0  6  1
2 {∅, {1}, {2, 3}, {1, 2, 3}}  1 1 1 0  12  1
3 {∅, {1}, {2, 3, 4}, {1, 2, 3, 4}} 1 0 1 1  4  1
4 {∅, {1, 2}, {2, 3}, {1, 3}}  0 3 0 0  3  2
5 {∅, {1, 2}, {3, 4}, {1, 2, 3, 4}} 0 2 0 1  4  2
6 {∅, {1, 2}, {1, 3, 4}, {2, 3, 4}} 0 1 2 0  6  2

Total: 35

Table 5.1: Group cwatsets in Q_{4} with k = 4 elements

Here we introduce yet another notion which is suitable for studying cwatsets. A hypergraph is a pair H = (Ω, E), where Ω is a (finite) set and E is a family of subsets of Ω. The set Ω, which we will identify with N_{n}, is the set of vertices of H, while elements of E are called hyperedges. Since Ω is fixed, H is uniquely determined by E, and we can write H = H(E); if no misunderstanding can arise, we will use the same notation for H and E, regarding H as a set of subsets of N_{n}. In particular, each cwatset determines a hypergraph: according to the notation introduced in Section 3, it has k_{i} hyperedges of size i, where i = 0, …, n, and ∑_{i=0}^{n} k_{i} = k. (See Table 5.1 for some examples.)

Two hypergraphs H_{1} = H(E_{1}) and H_{2} = H(E_{2}) on Ω = N_{n} are isomorphic if there is some g ∈ S_{n} such that A ∈ E_{1} if and only if A^{g} ∈ E_{2}. It follows from Proposition 5.4(a) that two cwatsets C_{1} and C_{2} are similar if and only if the corresponding hypergraphs H(C_{1}) and H(C_{2}) are isomorphic. Thus the classification of cwatsets up to similarity is equivalent to the classification of hypergraphs up to isomorphism.

As mentioned in the Introduction, we aim to answer two questions posed in [18]. We have (in effect) already answered the second question: if k ≤ 2^{n} and k divides 2^{n}n!, does Q_{n} necessarily contain cwatsets of order k ? The results in Section 4 give a negative answer, both for this and for the more general question about the existence of automorphic subsets. The first question posed in [18] involves further concepts, which we will discuss in the next section.

6. Cyclic cwatsets

In addition to group cwatsets, Sherman and Wattenberg [18] defined another simple class of cwatsets as follows: take any g ∈ S_{n} and f ∈ V, and let C = C(g, f) = {f_{1}, f_{2}, …} ⊆ V, where f_{1} = f and f_{l} = (f_{l−1})^{g} + f for l ≥ 2. They proved that C is a cwatset, called a cyclic cwatset.

Example 6.1. We repeat their example for n = 3: taking g = (1, 2, 3) ∈ S_{3} and f = 100 ∈ V, we have C((1, 2, 3), 100) = {100, 110, 111, 011, 001, 000}.

The following result is the analogue of Theorem 5.2 for the special case of cyclic cwatsets.

Proposition 6.1. A subset C ⊆ V is a cyclic cwatset if and only if there is a cyclic subgroup S ≤ E_{n} such that C = 0^{S}.

Proof. Given a cyclic cwatset C = C(g, f) = {f_{1}, f_{2}, …}, let S be the cyclic subgroup ⟨σ⟩ of E_{n} generated by σ = (g, f). Then f_{1} = f = 0^{σ}, and f_{l} = f_{l−1}^{σ} for all l ≥ 2, so C is the orbit of S containing 0. Conversely, if S = ⟨σ⟩ for some σ = (g, f) ∈ E_{n}, then 0^{S} is the cyclic cwatset C(g, f). □

For instance, the cyclic cwatset C(g, f) considered in Example 6.1 is the orbit of the cyclic subgroup S ≤ E_{3} generated by the element σ = (g, f), where g = (1, 2, 3) and f = 100.

Proposition 6.2. If S = ⟨σ⟩ ≤ E_{n} and φ(σ) = g ∈ S_{n}, then |S| = m or 2m where m is the order of g.

Proof. The epimorphism φ : E_{n} → S_{n}, (g, f) ↦ g restricts to an epimorphism φ|_{S} : S → S̃, where S̃ = ⟨g⟩ has order m. Now ker(φ|_{S}) = S ∩ V is a cyclic subgroup of V, so it has order ε = 1 or 2, and hence |S| = ε|S̃| = m or 2m. □

Corollary 6.3. (Sherman and Wattenberg [18]) Let C be a cyclic cwatset C(g, f), and let k = |C|. Then k divides 2m, where m is the order of g.

Proof. The proof of Proposition 6.1 implies that C is an orbit of S = ⟨σ⟩, where σ = (g, f). The result now follows from Corollary 5.3 and Proposition 6.2. □

Example 6.2. We look for the smallest dimension of a noncyclic cwatset. One can check that all cwatsets of dimension n ≤ 3 are cyclic. Now let n = 4 and

C = {0000, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1011, 1100, 1101, 1111}.

The graph Γ_{1} = Γ_{1}(C) generated by C is shown in Figure 6.1.

Figure 6.1

We note the following properties:

• Γ_{1} is a hexagonal prism, so Aut(Γ_{1}) ≅ D_{6} × S_{2} where D_{6} denotes the dihedral group of order 12, the symmetry group of a hexagon; in fact Aut(Γ_{1}) ≤ Aut(Γ_{i}) for i = 2, 3, 4, so if Γ = Γ(C) then G = Aut(Γ) = Aut(Γ_{1}) ≅ D_{6} × S_{2}, a group of order 24.

• The group H = Stab(C) contains an automorphism σ = (e, 0100) with no fixed points.

• The ‘upper’ and ‘lower’ subgraphs of Γ_{1}, lying in the hyperplanes v_{2} = 0 and v_{2} = 1 of Q_{4}, are two hexagons transposed by σ.

• The six vertices of each hexagon form an automorphic subset of its hyperplane Q_{3}, isomorphic to the subset in line 9 of Table 3.1 (see also Example 6.1)

• H ≅ \overline{H} ≅ G ≅ D_{6} × S_{2}.

Thus C is the orbit of H on V containing 0000, so it is a cwatset. However, D_{6} × S_{2} has no cyclic subgroups of order 12 (its elements have orders 1, 2, 3 and 6), so C is not the orbit of any cyclic subgroup of E_{4}, and is therefore not a cyclic cwatset.

This cwatset C was found by J. Kerr [14], using a computer. Our input is the proof that C is a non-cyclic cwatset, and the visual interpretation. We will return to this example later.

Example 6.3. Here we consider another example from [14]. Again let n = 4, but now let

C = {0000, 0011, 0110, 1111, 1100, 1001}.

To illustrate various techniques presented in this paper, we will treat this example in two different ways. In particular, we will show that C is cyclic.

Figure 6.2

First we consider the hypergraph H(C) = {∅, {3, 4}, {2, 3}, {1, 2, 3, 4}, {1, 2}, {1, 4}}. The vertices of weight 2 generate a quadrilateral, with automorphism group H_{0} ≅ D_{4} of order 8. It follows that

k = 6, r = \frac{n!}{|H_{0}|} = 3, b = \frac{2^{n}r}{k} = 8 and |H| = \frac{2^{n}n!}{b} = 48.

Figure 6.2 shows the graph Γ_{2} = Γ_{2}(C), and we see from this that |G| = 48. Note that |\overline{H}_{0}| = 8, and hence |\overline{H}| = 48.

Secondly, we consider the subset X = {0101, 0110, 0011, 1010, 1001, 1100} in Example 3.2. If f = 0101 ∈ V then the automorphism σ = (e, f) of Q_{4} satisfies X^{σ} = X + f = C, so X and C are similar and have the same group-theoretic properties. In particular, H is the symmetry group S_{4} × S_{2} of an octahedron. This has a cyclic subgroup C_{3} × S_{2} ≅ C_{6} which permutes the six vertices regularly, so C is a cyclic cwatset (correcting the claim in [14]). In fact, C = C(g, f′) where g = (1, 3, 2)(4) ∈ S_{4} and f′ = 0011 ∈ V.

So far, we have met two classes of cwatsets: group cwatsets and cyclic cwatsets. Further examples can be constructed using the direct sum operation ⊕. First, we give a simple illustration.

Example 6.4. Let C_{1} = {0000, 0100} and C_{2} = {0000, 0010, 0011, 1011, 1001, 1000}. Clearly these are both 4-dimensional cwatsets, contained in the subspaces v_{1} = v_{3} = v_{4} = 0 and v_{2} = 0 of V. If C is the cwatset in Example 6.2, then every c ∈ C has a unique representation of the form c = c_{1} + c_{2}, where c_{i} ∈ C_{i}. We therefore write C = C_{1} ⊕ C_{2}, the direct sum of C_{1} and C_{2}.

We now give the general definition of a direct sum of cwatsets. If I is any d-element subset of N_{n}, then by choosing a bijection N_{d} → I one can embed Q_{d} in Q_{n}; its vertices form the subspace P(I) of V (= P(N_{n})) defined by the equations v_{i} = 0 for all i ∉ I. In particular, any d-dimensional cwatset C ⊆ Q_{d} can be embedded in Q_{n} in this way.

More generally, if N_{n} = I_{1} ˙∪ ⋯ ˙∪ I_{m} is a partition of N_{n} into nonempty disjoint subsets I_{i} with d_{i} elements, then we have a decomposition

V = P(I_{1}) ⊕ ⋯ ⊕ P(I_{m})

of V as a direct sum of d_{i}-dimensional subspaces P(I_{i}), each defined by setting coordinates from N_{n} \ I_{i} equal to 0. If C_{i} is a d_{i}-dimensional cwatset for each i = 1, …, m, we can regard it as a subset of P(I_{i}), and we can form the direct sum

C = C_{1} ⊕ ⋯ ⊕ C_{m} ⊆ V,

consisting of the elements c = c_{1} + ⋯ + c_{m} where c_{i} ∈ C_{i}; this representation of c is unique, so |C| = |C_{1}| … |C_{m}|. For instance, the decomposition C = C_{1} ⊕ C_{2} in Example 6.4 arises from using the partition N_{4} = {2} ˙∪ {1, 3, 4} to embed Q_{1} and Q_{3} in Q_{4}.

A more restricted definition of the direct sum of cwatsets was introduced by Sherman and Wattenberg in [18], taking I_{1}, …, I_{m} to be consecutive subintervals of N_{n}; by permuting coordinates, they then obtain the decompositions considered above.

Proposition 6.4. Any direct sum of cwatsets is a cwatset.

Proof. Let C = C_{1} ⊕ ⋯ ⊕ C_{m} ⊆ V, as above. Since each C_{i} is a cwatset it contains the zero element of Q_{d_{i}}, so C contains their sum, the zero vector of V. The embeddings of Q_{d_{1}}, …, Q_{d_{m}} in Q_{n} embed E_{d_{1}}, …, E_{d_{m}} as subgroups which generate their direct product in E_{n}. Let H_{i} = Stab(C_{i}) ≤ E_{d_{i}}, and let H = H_{1} × ⋯ × H_{m} ≤ E_{n}. Since each C_{i} is an orbit of H_{i}, it follows that C is an orbit of H, so it is an automorphic subset and hence a cwatset by Theorem 5.2. □

In Examples 6.2 and 6.4 we considered a cwatset which is neither a group nor cyclic, though it is a direct sum of two cyclic cwatsets (one of which is also a group). Since any direct sum of group cwatsets is another group cwatset, the most general direct sum of group and cyclic cwatsets has the form

C = A ⊕ C_{1} ⊕ ⋯ ⊕ C_{m},

where A is a group and each C_{i} is a cyclic cwatset. Sherman and Wattenberg [18, p. 113], ask whether every cwatset has this form. To the best of our knowledge, this question is still open. We will give a negative answer, showing that there are infinitely many cwatsets which are not direct sums of groups and cyclic cwatsets.

Theorem 6.5. Suppose that w and n are integers such that 0 < w < n, and there are distinct odd primes p and q dividing \binom{n}{w} with p + q > n. Then there exists a cwatset C ⊆ Q_{n} with

\binom{n}{w} elements, which is not a direct sum of groups and cyclic cwatsets.

Proof. Let B be the set of all vectors of weight w in Q_{n}, where w and n satisfy the hypotheses of the theorem, and let C = B + b for some b ∈ B. Since B is an orbit of S_{n} (the stabiliser of 0 in E_{n}), C is an orbit of a conjugate of S_{n} (the stabiliser of b), so C is an automorphic subset; since C contains b + b = 0, it is a cwatset by Theorem 5.2. We have |C| = |B| = \binom{n}{w}, divisible by p and q.

Now suppose that C has a direct sum decomposition C = A ⊕ C_{1} ⊕ ⋯ ⊕ C_{m}, where A is a group and each C_{i} is a cyclic cwatset. Then |C| = |A| · ∏_{i} |C_{i}|, with |A| a power of 2, so there must exist i and j such that p divides |C_{i}| and q divides |C_{j}|. If i = j then since C_{i} is cyclic, E_{n} contains an element of order divisible by pq, and hence its epimorphic image S_{n} contains commuting elements g and h of orders p and q. If i ≠ j then the definition of the direct sum implies that C_{i} and C_{j} are isomorphic to cwatsets in Q_{d} and Q_{e} where d + e ≤ n; since C_{i} and C_{j} are cyclic, S_{d} and S_{e} contain elements of orders p and q, so S_{n} (which contains S_{d} × S_{e}) again contains commuting elements g and h of orders p and q. In either of these two cases, g must have a cycle of length p on either the fixed-points or the q-cycles of h in N_{n}, giving p + q ≤ n or pq ≤ n respectively. Both of these contradict our hypothesis that p + q > n, so C does not have a decomposition of the given form. □

Example 6.5. The integers n = 6 and w = 2 satisfy the conditions of Theorem 6.5, with p = 3 and q = 5, so there is a 6-dimensional counterexample with |C| = \binom{6}{2} = 15; similarly one can take n = 7 and w = 2, with p = 3, q = 7 and |C| = 21.

Lemma 6.6. There are infinitely many pairs of integers w and n which satisfy the hypotheses of Theorem 6.5.

Proof. There are infinitely many primes p. By Bertrand’s Postulate (a theorem of Chebyshev, see [10, §22.3 and notes for Ch. XXII]), if p > 3 there is a prime q such that p < q < 2p − 2. Thus there exist infinitely many pairs of primes p and q such that 2 < p < q < 2p−1. Taking w = p − 1 and n = q we then have p + q > n. Since max (w, n − w) = max (p − 1, q − p + 1) < p < q ≤ n we have pq | \binom{n}{w}, so w and n satisfy the required hypotheses. □

This, together with Theorem 6.5, yields infinitely many cwatsets C giving negative answers to Sherman and Wattenberg’s question. For instance, one can take p = 5 and q = 7, giving w = 4 and n = 7, so that |C| = 35.

Acknowledgements. Our interest in cwatsets originated in the discussion of this notion by the second and third authors in 1994 in Newark, when M. Klin visited the Department of Mathematical Sciences, University of Delaware. This paper was begun in January 1997, when G. A. Jones and F. Lazebnik were guests of the Department of Mathematics and Computer Science, Ben-Gurion University of the Negev. The kind hospitality of both universities is gratefully acknowledged. We thank G. Sherman for sending us a copy of Kerr’s report [14], and for his continued and stimulating interest in our work, M. Muzychuk for showing us a proof of Lemma 4.4, and I. J. Leary for some helpful discussions concerning group cohomology.

References

[1] Atkins, J. E.; Sherman, G. J.: Sets of typical subsamples. Statistics and Probability Letters 14 (1992), 115–117.

[2] Brown, K. S.: Cohomology of Groups. Springer-Verlag, New York 1982.

[3] Burnside, W.: On some properties of groups of finite order. Proc. London Math. Soc. 33 (1900), 162–185.

[4] Burnside, W.: Theory of Groups of Finite Order. Second edition, Cambridge University Press, Cambridge 1911.

[5] Cameron, P. J.: Permutation groups and finite simple groups. Bull. London Math. Soc. 13 (1981), 1–22.

[6] Dixon, J. D.; Mortimer, B.: Permutation Groups. Springer, Berlin 1996.

[7] Dress, A. W. M.; Klin, M. H.; Muzichuk, M. E.: On p-configurations with few slopes in the affine plane over F_{p} and a theorem of W. Burnside’s. Bayreuther Math. Schr. 40 (1992), 7–19.

[8] Harary, F.: Exponentiation of permutation groups. Amer. Math. Monthly 66 (1959), 572–575.

[9] Harary, F.: Graph Theory. Addison-Wesley, Reading 1969.

[10] Hardy, G. H.; Wright, E. M.: Introduction to the Theory of Numbers. Fifth edition, Oxford University Press, Oxford 1979.

[11] Hartigan, J. A.: Using subsample values as typical values. Amer. Stat. Assoc. J. 64 (1969), 1303–1317.

[12] Huppert, B.: Endliche Gruppen I. Springer-Verlag, Berlin 1967.

[13] Jones, G. A.; Klin, M.; Lazebnik, F.: Introduction to the theory of automorphic subsets of the n-dimensional cube. Preprint No. 309, Faculty of Mathematical Studies, University of Southampton 1998.

[14] Kerr, J.: Hypergraph Representations and Orders of Cwatsets. Rose-Hulman Institute of Technology, Technical Report 93-02, 1993.

[15] Lint, J. H. van; Wilson, R. M.: Course in Combinatorics. Cambridge University Press, Cambridge 1992.

[16] Rotman, J. J.: Introduction to the Theory of Groups. Fourth edition, Springer-Verlag, Berlin 1995.

[17] Sherman, G. J.: Confidence intervals from groups. Math. Mag. 65 (1992), 118–122.

[18] Sherman, G. J.; Wattenberg, M.: Introducing … cwatsets! Math. Mag. 67 (1994), 109–117.

[19] Wielandt, H. W.: Finite permutation groups. Academic Press, New York 1964.

[20] Wielandt, H. W.: Mathematische Werke – Mathematical Works I: Group Theory. (Eds. B. Huppert and H. Schneider), de Gruyter, Berlin 1994.

Received October 20, 1998