Rank 3 Latin square designs

Alice Devillers^{∗} Université Libre de Bruxelles Département de Mathématiques - C.P.216 Boulevard du Triomphe B-1050 Brussels, Belgium

                    adevil@ulb.ac.be

and J.I. Hall Department of Mathematics Michigan State University East Lansing, MI 48824 USA

                   jhall@math.msu.edu

Version of: June 30, 2005

Abstract

A Latin square design whose automorphism group is transitive of rank at most 3 on points must come from the multiplication table of an elementary abelian p-group, for some prime p.

1 Introduction

We are interested in the classification of all proper partial linear spaces that admit a group of automorphisms acting with rank 3 on points. Significant progress has been made when the group is assumed to be primitive [5]. Here we consider the most basic imprimitive case.

A transversal design T D(k, n) is a partial linear space (P, L) in which P = ∪_{i=1}^{k}B_{i} is the disjoint union of k sets B_{i}, called blocks, each of size n, such that each line l of L meets each block B_{i} in exactly one point and every pair of points from different blocks lies within exactly one line.

A transversal design with n = 1 contains a single line. A transversal design with k = 1 is an empty graph, and a transversal design with k = 2 is a complete bipartite graph. No more need be said about these cases.

∗Chargé de Recherche of the Fonds National de la Recherche Scientifique (Belgium)

A transversal design with k = 3 is a Latin square design (also dual 3-net or dual lattice design). To see the connection with Latin squares, label the three blocks R (for “row”), C (for “column”), and E (for “entry”). Then we can construct an n × n Latin square by placing the entry e in the cell at row r and column c precisely when {r, c, e} ∈ L, with r ∈ R, c ∈ C, and e ∈ E. The construction can be reversed, so that every Latin square gives rise to a Latin square design.

If n is not 1, then the automorphism group of a Latin square design T D(3, n) (or indeed any transversal design with k ≥ 2) is not primitive, since it must respect the noncollinearity relation, whose equivalence classes are the various blocks. If the group is transitive, then it has rank at least 3 on points since the stabilizer of a point leaves invariant the remaining points of that block and the union of the remaining blocks.

We are after

( 1.1) Theorem. Let 𝕃 be a Latin square design T D(3, n). Then Aut (𝕃) has rank at most 3 on points if and only if n = p^{a} is a power of a prime and 𝕃 is isomorphic to the Thomsen design 𝕋(A) of an elementary abelian p-group A of order p^{a}.

Here, for a group G, the Thomsen design 𝕋(G) is the Latin square design with point set P = G×{R, C, E} and line set L = { (x_{R}, y_{C}, z_{E}) | xyz = 1 }. Its three blocks are G_{R} = G × R, G_{C} = G × C, and G_{E} = G × E. The associated Latin square is the multiplication table of G. Note that we have inverted the entries by taking xy = z^{−1} instead of xy = z. With this convention and an abelian group (G, +), the subscript permutations Sym(R, C, E) give automorphisms of 𝕋(G), since x + y + z = 0 if and only if z + x + y = 0, and so forth.

Some of the arguments used for the classification of rank 3 Latin square designs go through for rank 3 transversal designs T D(k, n) with arbitrary line size k (≥ 3), but the corresponding generalization of Theorem 1.1 would require new ideas as well. All conclusions known to us are related to rank 3 translation planes. It is elementary that k ≤ n + 1 with equality if and only if we have a dual affine plane. A rank 3 dual affine plane must be Desarguesian [7, 4.3.16]. The next case is that of T D(n, n), which are affine planes with one parallel class distinguished as the set of blocks. Rank 3 affine planes of this sort are translation planes and have been classified but need not be Desarguesian. In particular (see [3]), the likeable Walker plane of order 25 gives an example of a rank 3 transversal design T D(25, 25) with nonsolvable rank 3 automorphism group that admits shears but does not have a shear block. (See Section 2 for the appropriate definitions.)

A related result is

( 1.2) Theorem. (Bailey [2]) Let 𝕃 be a Latin square design. Then Aut^{∘}(𝕃) has at most four orbits on ordered pairs of distinct lines if and only if 𝕃 is 𝕋(A) where either A is an elementary abelian 2-group or A is cyclic of order 3.

Here Aut^{∘}(𝕃) denotes the normal subgroup of Aut (𝕃) (having index at most 6) that leaves each block invariant. Three of the four orbits correspond to pairs that intersect in one of R, C, or E, and the fourth orbit consists of pairs of disjoint lines. We can extend Bailey’s result to

( 1.3) Theorem. Let 𝕃 be a Latin square design. Then Aut (𝕃) has one orbit on ordered pairs of distinct intersecting lines or Aut^{∘}(𝕃) has three orbits on ordered pairs of distinct intersecting lines if and only if 𝕃 is 𝕋(A) for A an elementary abelian p-group for some prime p.

Bailey’s proof of Theorem 1.2 is elementary, whereas our proofs of Theorems 1.1 and 1.3 use the classification of finite doubly transitive groups (see [4]). Bailey in fact only assumes that Aut^{∘}(𝕃) has at most four orbits on unordered pairs of distinct intersecting lines. We conjecture that a Latin square design whose automorphism group is transitive on each of the three sets

Λ_{B} = { {l_{1}, l_{2}} | l_{i} ∈ L, l_{1} ∩ l_{2} = b ∈ B } ,

for B ∈ {R, C, E}, must be 𝕋(A) for some elementary abelian p-group A. This includes Bailey’s original theorem and its obvious extension as in Theorem 1.3. It additionally covers Latin square designs admitting automorphism groups that are rank 3 on lines. The methods of this paper should extend to this situation, and we hope to return to its study at some later date.

If G ≤ Sym(Ω) and Δ ⊆ Ω, then G_{Δ} is the global stabilizer of Δ in G, G_{[Δ]} is the pointwise stabilizer in G of Δ, and G^{Δ} = G_{Δ}/G_{[Δ]} is the group induced by G on Δ. If Σ is a set of blocks of imprimitivity for G on Ω, then G_{[Σ]} is the normal subgroup of G stabilizing all blocks setwise and G^{Σ} = G/G_{[Σ]} is the group induced by G on Σ. In the Latin square design case above, G_{[Σ]} = Aut^{∘}(𝕃).

2 Shears and a characterization of the Thomsen design of a group

( 2.1) Lemma. Let 𝕋 = (P, L) be a transversal design T D(k, n) (with k ≥ 3) with block set Σ. For G ≤ Aut (𝕋) and block B ∈ Σ, the group G_{[Σ]} ∩ G_{[B]} is semiregular on each block D ≠ B.

Proof. If g ∈ G_{[Σ]} ∩ G_{[B]} fixes the point d ∈ D, then g fixes all lines l through d; so, as g ∈ G_{[Σ]}, it fixes all the points l ∩ B′ for B′ ∈ Σ with B ≠ B′ ≠ D. Therefore g fixes all points except possibly those of D. Replacing D by B′, we see that g also fixes D pointwise; so g = 1 as claimed.

Note that this is false if k = 2.

In the situation of the lemma, an element of the group G_{[Σ]} ∩ G_{[B]} is called a shear with axis B. The lemma says that the group of shears with axis B is semiregular on each block other than B. We say that B is a shear block if its group of shears is in fact regular on some other block and so on all other blocks.

The following is equivalent to a result of Praeger [8].

( 2.2) Theorem. Let 𝕃 be a Latin square design T D(3, n) possessing a shear block B with associated group of shears A. Then 𝕃 is isomorphic to the Thomsen design 𝕋(A).

Proof. We will define an isomorphism i from 𝕃 onto the Thomsen design 𝕋(A). The design 𝕃 has a shear block B. Let us call the two other blocks F and D. First choose a line l of 𝕃, and let f = l ∩ F, d = l ∩ D. If u is a point of 𝕃 in F, we know, since A acts regularly on F, that there exists exactly one element x ∈ A mapping f onto u. Define u^{i} = x_{R}. Similarly, if v ∈ D, there exists exactly one element y ∈ A mapping v onto d. Define v^{i} = y_{C}. Now consider w ∈ B. The line on w and d intersects F in t, say. If t^{i} = z_{R}, then we define w^{i} = (z^{−1})_{E}. It is easy to see that i is a bijection from the point set of 𝕃 to the point set of 𝕋(A). The only thing we need to check is that i maps any line of 𝕃 onto a line of 𝕋(A). So let us keep the notation above and assume {u, v, w} is a line of 𝕃. The image of this line under i is {x_{R}, y_{C}, (z^{−1})_{E}}. In order for this set to be a line of 𝕋(A), we need (xy)z^{−1} = 1. The shear y maps v onto d while fixing w, hence it maps the line {u, v, w} onto the line {t, d, w} and consequently u onto t. Thus f^{xy} = u^{y} = t, and the shear xy takes f to t. On the other hand, z also is a shear of A mapping f onto t. Since A acts regularly on F we must have xy = z, which is the equality we wanted.

We next verify some homogeneity properties for Thomsen designs of groups, particularly those of elementary abelian groups as discussed in Theorems 1.1 through 1.3

( 2.3) Lemma. Let G be a group and set 𝕃 = 𝕋(G). Then the following bijections are in Aut(𝕃). Indeed the automorphims α_{g} and σ_{h} are in Aut^{∘}(𝕃).

(1) α_{g}: x_{B} ⟶ \{ \begin{matrix}x_{R} & if B = R \\ (xg)_{C} & if B = C \\ (g^{−1}x)_{E} & if B = E \end{matrix} , where g ∈ G.

(2) σ_{h}: x_{B} ⟶ (x^{h})_{B} for B ∈ {R, C, E}, where h ∈ Aut(G).

(3) τ: x_{B} ⟶ \{ \begin{matrix}x_{E} & if B = R \\ x_{R} & if B = C \\ x_{C} & if B = E \end{matrix} .

(4) ρ: x_{B} ⟶ \{ \begin{matrix}(x^{−1})_{R} & if B = R \\ (x^{−1})_{E} & if B = C \\ (x^{−1})_{C} & if B = E \end{matrix} .

( 2.4) Proposition. Let 𝕃 = 𝕋(G) be the Thomsen design of the group G ≠ 1.

(1) Aut (𝕃) is transitive on the points of 𝕃, and the stabilizer of a point in the block B is transitive on the points not in B. The subgroup Aut^{∘}(𝕃) is transitive on lines and on each block.

(2) If additionally G is an elementary abelian p-group, then Aut (𝕃) is rank 3 on the points of 𝕃 and has one orbit on ordered pairs of distinct intersecting lines. Its subgroup Aut^{∘}(𝕃) has three orbits on ordered pairs of distinct intersecting lines.

(3) If additionally the elementary abelian p-group is either a 2-group or has order 3, then Aut^{∘}(𝕃) is transitive on ordered pairs of disjoint lines.

Proof. (1) Let A be the subgroup of H = Aut^{∘}(𝕃) generated by all the α_{g}, which is transitive on C and E. Then the subgroup generated by A and τ is transitive on the points of 𝕃, while the subgroup generated by A and ρ stabilizes Id_{R} and is transitive on C ∪ E. The group H ≥ A^{τ} is transitive on R, and H ≥ A can map the line {Id_{R}, Id_{C}, Id_{E}} onto any line through Id_{R}.

(2) Suppose in addition that G is a nontrivial elementary abelian p-group, which we identify with the additive group of the field 𝔽_{q}. For 0 ≠ a ∈ G, let μ(a) be the automorphism of G given by x ↦ a.x. Using σ_{μ(a)} for all choices of a, we see that the stabilizer in Aut^{∘}(𝕃) of 0_{R} is transitive on R\{0_{R}}. Therefore Aut (𝕃) is rank 3 on the points of 𝕃.

Since τ normalizes line-transitive H, it remains to prove that the stabilizer in H of L = {0_{R}, 0_{C}, 0_{E}} is transitive on all other lines through 0_{R}. The automorphism σ_{μ(a)} stabilizes L and maps the line {0_{R}, 1_{C}, −1_{E}} onto {0_{R}, a_{C}, −a_{E}}. As any line through 0_{R} is of this form, this proves (2).

(3) By (1) the group H is transitive on lines, so we need only prove that the stabilizer in H of L = {0_{R}, 0_{C}, 0_{E}} is transitive on all lines disjoint from L.

When q = 3, there are only two lines disjoint from L, namely {1_{R}, 1_{C}, 1_{E}} and {2_{R}, 2_{C}, 2_{E}}. These are switched by σ_{μ(2)}, which belongs to H and also stabilizes L.

When q = 2^{n}, Aut (G) contains GL(n, 2), which is 2-transitive on G \ {0}. Let {a_{R}, b_{C}, (a + b)_{E}} and {c_{R}, d_{C}, (c + d)_{E}} be two lines disjoint from L. (This means a, b, c, and d are nonzero with a ≠ b and c ≠ d.) Then there exists an automorphism h of G stabilizing 0 (of course), mapping a onto c and b onto d. Then σ_{h} ∈ H maps the first line onto the second and fixes L, giving the desired conclusion.

3 Basics

The first two results are elementary.

( 3.1) Proposition. Let G be rank 3 and imprimitive on Ω with block set Λ. Then G^{Λ} is 2-transitive on Λ and G^{B} is 2-transitive on each block B of Λ.

( 3.2) Lemma. Let G ≤ Aut ((P, L)) be rank 3 on the points of the proper partial linear space (P, L). Then G is transitive on ordered pairs of collinear points and, in particular, is transitive on the line set L and 2-transitive on each line.

Therefore the groups we will be examining are pasted together from 2-transitive groups. The following result of Burnside provides the basic case division. (Recall that the socle of a group G, written Soc(G), is the product of all its minimal normal subgroups.)

( 3.3) Theorem. (Burnside [4, Theorem 4.3].) If finite G ≤ Sym(Ω) is 2-transitive on the set Ω, then the socle of G is its unique minimal normal subgroup and we have one of

(1) Soc(G) is nonabelian simple and is primitive on Ω;

(2) Soc(G) is an elementary abelian p-group, for some prime p, and is regular on Ω.

In the first case G is almost simple and in the second case G is affine, indeed, p-affine.

The results we use from the classification of finite 2-transitive groups are collected in

( 3.4) Proposition. Let finite G ≤ Sym(Ω) be 2-transitive on the set Ω with |Ω| > 2.

(1) Assume that we are in the almost simple case. Then G has a unique minimal normal 2-transitive subgroup N. This N has at most two nonisomorphic representations as a 2-transitive group of this degree.

The group N is equal to the simple socle Soc(G) except when G = N is P ΓL_{2}(8) acting 2-transitively on 28 points and Soc(G) equals P SL_{2}(8), which has index 3 and is primitive of rank 4. The group P SL_{2}(8) has only one isomorphism class of faithful permutation representations of degree 28.

(2) Assume that we are in the p-affine case. Let M have index at most 2 in G.

If M contains more than two conjugacy classes of complements to the regular normal subgroup O_{p}(G) = O_{p}(M), then, for each point b of Ω, the subgroup E = Soc(G_{b}) = Soc(M_{b}) is a simple group Sp_{2m}(q) or G_{2}(q) with even q(≥ 4). In this case, E has orbits of different lengths on each class of complements to O_{p}(M) in O_{p}(M)E.

Proof. (1) Almost all of this can be found in [4, Table 7.4]. A degree 28 permutation representation of P SL_{2}(8) has as point stablizer the normalizer of a Sylow 3-subgroup and so is uniquely determined.

(2) Assume that M has more than two classes of complements to V = O_{p}(M) = O_{p}(G). If M has index 2 in G, then G still has more than one class of complements. From [4, Table 7.3], we learn that E = Soc(M_{b}) = Soc(G_{b}) is Sp_{2m}(q) or G_{2}(q) with 4 ≤ q even and that V is 𝔽_{q}^{2m} or 𝔽_{q}^{6}, respectively. Here M_{b} is a fixed complement to V in M. Set m = 3 when E is G_{2}(q). For (2) it remains to calculate orbit lengths for E on each class of complements.

The subgroup V E is itself 2-transitive on Ω and contains exactly q conjugacy classes of complements by [6]. By standard cohomological results, there is a uniquely determined 𝔽_{q}E-module W ≥ V = [W, E] with dim_{𝔽_{q}}(W/V) = dim_{𝔽_{q}}(H^{1}(E, V)) = 1 and such that the semidirect product W E has a unique conjugacy class of complements to W. These q^{2m+1} complements are the E^{w}, for w ∈ W. The V E-class containing E^{w} is (E^{w})^{V} = (E^{V})^{w} of size q^{2m}, and so the action of E on a class of complements is isomorphic to its action on the corresponding coset V + w of V. If the coset is V itself then the orbit lengths are 1 and q^{2m} − 1, so we are done in this case and now need only treat cosets V + w ≠ V.

First consider E of type Sp_{2m}(q). Let Q be a nondegenerate quadratic form defined on a 𝔽_{q}-space W_{0} of dimension 2m + 2. In the full isometry group O(W_{0}, Q), the stabilizer of the nonsingular 1-space X is R × O_{2m+1}(q), where R is the reflection subgroup of order 2 with center X. As q is a power of 2 at least 4, the perfect factor O_{2m+1}(q) is isomorphic to Sp_{2m}(q), acts trivially on X, and can be identified with E. The 𝔽_{q}E-module W can then be taken to be W_{0}/X with V = X^{⊥}/X.

Let V + w (≠ V) be a coset of V in W. Then the stabilizer of w in E is equal to the centralizer in O(W_{0}, Q) of the nondegenerate 2-space U of W_{0} spanned by X and w_{0} (a preimage of w). This subgroup of E is O_{2m}^{ϵ}(q), of Witt type ϵ = + or − depending upon whether U^{⊥} is a hyperbolic or elliptic hyperplane of X^{⊥}. Hyperplanes of both types exist in X^{⊥}, so it is possible to choose w_{0}, representing a member of V + w, to realize either type as U^{⊥}. That is, in the coset V + w it is possible to find representatives with E-orbit length |Sp_{2m}(q): O_{2m}^{+}(q)| and representatives with E-orbit length |Sp_{2m}(q): O_{2m}^{−}(q)|. These numbers are different, completing (2) in the symplectic case.

The argument for G_{2}(q) with q a power of 2 (at least 4) is similar. Let W_{0} be an 8-dimensional split Cayley algebra over 𝔽_{q} admitting composition with respect to the nondegenerate hyperbolic quadratic form Q. We can again take W to be W_{0}/X with V = X^{⊥}/X, where X is the nonsingular 1-space spanned by the identity element of the algebra W_{0}. The automorphism group E ≃ G_{2}(q) of the algebra W_{0} is then naturally a subgroup of the corresponding subgroup Sp_{6}(q) of the previous two paragraphs. Again the stabilizers in E of hyperbolic and elliptic hyperplanes of X^{⊥} have different orders (see [1, Theorems 1 and 3]) and so give rise to E-orbits of different length in cosets of V in W.

4 Rank 3 Latin square designs

Let 𝕃 = (P, L) be a Latin square design with block set Σ = {R, C, E}. Set G = Aut (𝕃) and M = G_{[Σ]} = Aut^{∘}(𝕃).

Let S_{B} = G_{[Σ]} ∩ G_{[B]}, the group of shears with axis B ∈ Σ, and let S be the subgroup generated by all the S_{B} for B ∈ Σ.

Consider two hypotheses:

( 4.1) Hypothesis. G is rank 3 on the points of P.

and

( 4.2) Hypothesis. M has exactly three orbits on ordered pairs of intersecting distinct lines from L.

We then have easily

( 4.3) Proposition.

(1) Under Hypothesis 4.1:

(i) For all blocks B, G^{B} is 2-transitive on B and contains M^{B} with index at most 2;

(ii) For each point b and block B with b ∉ B, the stabilizer M_{b} is transitive on B.

(2) Under Hypothesis 4.2:

(i) For all blocks B, M^{B} is 2-transitive on B;

(ii) For each point b and block B with b ∉ B, the stabilizer M_{b} is transitive on B.

In view of the similarities in the proposition, we treat the two hypotheses simultaneously. Theorems 1.1 and 1.3 follow immediately from Proposition 2.4 and

( 4.4) Theorem. Let 𝕃 be a proper Latin square design satisfying one of the Hypotheses 4.1 or 4.2. Then 𝕃 is 𝕋(A) for some elementary abelian p-group A.

( 4.5) Lemma. A Latin square design T D(3, n) with n ∈ {1, 2, 3} is 𝕋(A) for A cyclic of order n.

Proof. This result is trivial for n = 1 and well-known for n = 2, 3. Indeed any T D(3, 2) is a dual affine plane of order 2, and any T D(3, 3) is an affine plane of order 3 with one parallel class identified as blocks.

We may therefore assume that 𝕃 is a T D(3, n) with n ≥ 4.

( 4.6) Lemma. For each block B, the group M^{B} is primitive on B.

Proof. Under (4.2) this is immediate. Under (4.1) this also holds as M^{B} has index at most 2 in 2-transitive G^{B} ≤ Sym(B).

( 4.7) Lemma. For some block B, the subgroup S_{B} is nontrivial.

Proof. Assume, for a contradiction, that S = 1, so that M is faithful on each block B.

First suppose that G^{B} is almost simple. Therefore by Proposition 3.4(1) Soc(M)(≃ Soc(G^{B})) is simple, and Soc(M) is either 2-transitive on each D ∈ Σ or Soc(M) ≃ P SL_{2}(8) is primitive on the 28 points of each D. Again by Proposition 3.4(1), there are at most two possibilities, up to isomorphism, for the permutation groups (Soc(M), B) with B ∈ Σ. In particular, since |Σ| = 3, there are at least two blocks, B and D (say), on which Soc(M) has isomorphic representations. For a point b ∈ B, the point stablizer Soc(M)_{b} also then fixes a unique point d ∈ D and so a unique line, namely the line l on b, d. However M_{b} normalizes Soc(M)_{b}, which fixes a unique line l on b; so M_{b} also fixes l. But this is a contradiction, since M_{b} is transitive on the lines through b.

The proof in the affine case is similar to the almost simple case. By primitivity (Lemma 4.6), for a point b ∈ B, the only point of B that is stabilized by M_{b} is b itself.

Arguing as before, we are done if two of the representations of M on the various B ∈ Σ are isomorphic. Therefore by Proposition 3.4(2) we are done unless, for each b ∈ B, the subgroup Soc(M_{b}) is Sp_{2m}(q) or G_{2}(q) with q even and at least 4. Again, the stabilizer M_{b} is transitive on the lines through b and normalizes Soc(M_{b}), so the orbits of Soc(M_{b}) on the lines through b must have uniform length. This in turn implies that the orbits of Soc(M_{b}) on each block not containing b also have uniform length. But that is not the case by Proposition 3.4(2).

Proof of Theorem 4.4:

For some block B we have S_{B} ≠ 1 by Lemma 4.7. Let D be a block other than B. By Lemma 2.1, S_{B} ∩ M_{[D]} = 1 and S_{B} = S_{B}/S_{B} ∩ M_{[D]} ≃ S_{B}^{D} is semiregular, nontrivial, and normal in M^{D}. As M^{D} is primitive by Lemma 4.6, S_{B}^{D} is actually regular on D. That is, B is a shear block for 𝕃. By Theorem 2.2, 𝕃 is isomorphic to 𝕋(S_{B}). Here S_{B}^{D} ≃ S_{B} is regular and subnormal in 2-transitive G^{D} or M^{D} and so is an elementary abelian p-group by Theorem 3.3. This gives the theorem.

References

[1] M. Aschbacher, Chevalley groups of type G_{2} as the group of a trilinear form, J. Algebra 109 (1987), 193–259.

[2] R.A. Bailey, Latin squares with highly transitive automorphism groups. J. Austral. Math. Soc. Ser. A 33 (1982), 18–22.

[3] M. Biliotti, N.L. Johnson, The non-solvable rank 3 affine planes, J. Combin. Theory Ser. A 93 (2001), 201–230.

[4] P.J. Cameron, “Permutation Groups,” London Mathematical Society Student Texts 45, Cambridge University Press, Cambridge, 1999.

[5] A. Devillers, Finite partial linear spaces having a primitive rank 3 group of almost simple type, manuscript 2003.

[6] W. Jones, B. Parshall, On the 1-cohomology of finite groups of Lie type, In: “Proceedings of the Conference on Finite Groups (Univ. Utah, Park City, Utah, 1975),” Academic Press, New York, 1976, 313–328.

[7] M.J. Kallaher, Translation planes, in: “Handbook of Incidence Geometry,” North-Holland, Amsterdam, 1995, 137–192,

[8] C.E. Praeger, A note on group Latin squares, J. Combin. Math. Combin. Comput. 5 (1989), 41–42.