arXiv:1506.04187v2 [] 28 Dec 2015

A REDUCTION THEOREM FOR PRIMITIVE BINARY
PERMUTATION GROUPS
JOSHUA WISCONS
Abstract. A permutation group (X, G) is said to be binary, or of relational complexity 2, if for all n, the orbits of G (acting diagonally) on X 2
determine the orbits of G on X n in the following sense: for all x̄, ȳ ∈ X n ,
x̄ and ȳ are G-conjugate if and only if every pair of entries from x̄ is
G-conjugate to the corresponding pair from ȳ. Cherlin has conjectured
that the only finite primitive binary permutation groups are Sn , groups
of prime order, and affine orthogonal groups V ⋊ O(V ) where V is a
vector space equipped with an anisotropic quadratic form; recently he
succeeded in establishing the conjecture for those groups with an abelian
socle. In this note, we show that what remains of the conjecture reduces,
via the O’Nan-Scott Theorem, to groups with a nonabelian simple socle.

1. Introduction
This note focuses on binary permutation groups; that is, permutation
groups of relational complexity 2. The relational complexity of a group G
acting on a set X is the smallest k (if one exists) for which the orbits of G
on X k “determine” the orbits of G on X n for all n. The precise meaning of
“determine” will be made clear below, but whatever it is, one may rightly
believe that being binary is a rather restrictive hypothesis. Here, we address
the following conjecture of Cherlin, see [Che00, §3] and [Che, Conjecture 1].
Conjecture A. A finite primitive binary permutation group is either Sn
acting naturally on {1, . . . , n}, a cyclic group of prime order acting regularly,
or an affine orthogonal group V ⋊ O(V ) where V is a vector space equipped
with an anisotropic quadratic form and O(V ) is the full orthogonal group.
Relational complexity has its roots in Lachlan’s classification theory for
finite homogeneous structures (see [Lac84] or [KL87]); however, little was
known about relational complexity in specific cases until the work of Cherlin, Martin, and Saracino in [CMS96], which was followed-up by Saracino’s
remarkable and detailed analysis in [Sar99] and [Sar00]. More examples
were laid out in [Che00] where Conjecture A also took form. The recent
work [Che] of Cherlin establishes the conjecture for groups with an abelian
2010 Mathematics Subject Classification. Primary 20B15; Secondary 03C13.
Key words and phrases. primitive permutation groups, relational complexity.
This material is based upon work supported by the National Science Foundation under
grant no. OISE-1064446.
1

2

JOSHUA WISCONS

socle, i.e. affine groups, and here, using the O’Nan-Scott Theorem, we reduce what remains to the case of groups with a nonabelian simple socle, i.e.
almost simple groups. Specifically, we prove the following.
Theorem A. If G is a finite primitive binary permutation group, then either
(1) G is affine,
(2) G is almost simple, or
(3) G is a subgroup of a wreath product H wr Sm in its product action
where H is a primitive binary almost simple permutation group that
is not 2-transitive.
In light of Cherlin’s solution for groups of affine type, Theorem A reduces
Conjecture A to the following conjecture specific to the almost simple case.
Conjecture A′ . The only finite primitive binary permutation group with
a nonabelian simple socle is Sn in its natural action on {1, . . . , n}.
It is worth emphasizing that one should be able to say something interesting under a more general k-ary hypothesis, but it is not clear, at present,
what this might be. Our arguments do not seem to immediately generalize
beyond the binary case, so we have avoided the general setting, for now.
2. Preliminaries
We first fix some notation and conventions that will be used throughout
the article. From this point on, all groups are finite. A permutation group
is just a group with a fixed, faithful action on some set. To emphasize both
the group and the set, we may call (X, G) a permutation group to mean
that G is a group acting faithfully on the set X. We will often consider
the induced (diagonal) action of G on a power X n ; the orbits of G on X n
will be called n-types. For x̄, ȳ ∈ X n and H ≤ G, we say that x̄ and ȳ are
H-conjugate, denoted x̄ ∼H ȳ, if they lie in the same H-orbit. We denote
the pointwise stabilizer of a subset Y ⊆ X by GY . Unless otherwise stated,
groups will always act on the right.
2.1. Primitive groups. A permutation group (X, G) is primitive if X has
no proper nontrivial G-invariant equivalence relations. This is equivalent to
G acting transitively with all point stabilizers being maximal proper subgroups of G. Our main reference for primitive groups will be [DM96].
The analysis of primitive groups may be broken down according to the
structure of the socle of the group, i.e. the subgroup generated by all minimal normal subgroups. We will denote the socle of G by soc(G), and if G
is a primitive group, soc(G) will be a direct product of isomorphic simple
groups. We now give a very rough statement of the O’Nan-Scott Theorem;
one may see [DM96, Section 4.8] for more details. We will elaborate on the
various types as they arise in our analysis.

A REDUCTION THEOREM FOR PRIMITIVE BINARY PERMUTATION GROUPS

3

Fact 2.1. Let (X, G) be a finite primitive permutation group. Set M :=
soc(G), and write M = T k for some simple group T . Then (X, G) is of one
of the following types.
Affine: M is abelian and acts regularly.
Regular nonabelian: M is nonabelian and acts regularly.
Almost simple: M is nonabelian simple and does not act regularly.
Diagonal: X may be identified with T k modulo the equivalence relation
given by the orbits of T acting diagonally on T k by left multiplication
(by the inverse); M acts coordinatewise by right multiplication.
Product: G is a subgroup of a wreath product H wr Sm in its product action
where H is primitive of almost simple or diagonal type and M =
(soc(H))m .
2.2. Relational complexity. We will define the relational complexity of
a permutation group below, but first, we mention the connection to homogeneous structures. Let X = (X; R1 , . . . , Rm ) be a relational structure;
that is, for each i, there is a positive integer ni for which Ri is an ni -ary
relation on X. Now, every Y ⊆ X gives rise to an induced substructure
Y ) where each RY is the restriction of R to Y , and
Y = (Y ; R1Y , . . . , Rm
i
i
the structure X is called (ultra)homogeneous if every isomorphism between
induced finite substructures can be extended to an automorphism of X.
Consider the Petersen graph as a structure (V ; E) with V being the set
of vertices and E the edge relation. It is not hard to see that (V ; E) is not
homogeneous since there exist independent triples of vertices that have a
common neighbor as well as independent triples that do not have a common neighbor. However, if we define a ternary relation N on V such that
(v1 , v2 , v3 ) ∈ N if and only if v1 , v2 , and v3 have a common neighbor, then
it can be shown that the expanded structure (V ; E, N ) is indeed homogeneous. Thus, although the Petersen graph is not homogeneous in the
language of graphs, it becomes homogeneous after adding in an appropriate
ternary relation. Moreover, the relation N is definable (in a first-order way,
without parameters) from E, so (V ; E, N ) is model-theoretically equivalent
to (V ; E).
Returning to the general setting, the relational complexity of X is defined
to be the least k (if one exists) such that X is equivalent to a homogeneous
e is
structure all of whose relations are k-ary. Note that if X is finite and if X
the expansion of X obtained by adding in, for all k ≤ |X|, the k-ary relations
e is homogeneous and
corresponding to the orbits of Aut(X) on X k , then X
equivalent to X. In fact, k ≤ |X| − 1 will do. As such, the relational
complexity of a finite relational structure is always defined and is at most
|X| − 1. The conclusion of the previous paragraph was that the relational
complexity of the Petersen graph is 3.
We now change our focus from X to Aut(X) and translate the study of
relational complexity into the language of permutation groups. We begin
with a preliminary definition.

4

JOSHUA WISCONS

Definition 2.2. Let (X, G) be a permutation group.
(1) Tuples x̄, ȳ ∈ X n are equivalent if they are G-conjugate, i.e. if they
are in the same n-type.
(2) Tuples x̄, ȳ ∈ X n are k-equivalent (k ≤ n) if every k-subtuple from
x̄ is G-conjugate to the corresponding k-subtuple from ȳ.
(3) We say that k-types determine n-types (k ≤ n) if for every x̄, ȳ ∈ X n ,
k-equivalence of x̄ and ȳ implies equivalence of x̄ and ȳ.
Definition 2.3. The relational complexity of a permutation group is the
smallest k for which k-types determine n-types for all n ≥ k.
Example 2.4. Every nontrivial permutation group has relational complexity at least 2. Indeed, assume that (X, G) is nontrivial, and let x 6= y ∈ X
be G-conjugate. Then the pairs (x, x) and (x, y) are 1-equivalent but not
2-equivalent.
Remark 2.5. With the previous example in mind, it is not hard to see that
the relational complexity of a nontrivial permutation group is the smallest
k ≥ 2 for which k-types determine n-types of tuples with pairwise distinct
entries for all n ≥ k. Indeed, if one assumes k-equivalence for k ≥ 2, then
repeated entries in the first tuple must match up with conjugate repeated
entries in the second. Certainly the repetitions may then be ignored.
Example 2.6. The natural action of Sn on {1, . . . , n} is binary, i.e. of
relational complexity 2. In light of the previous remark, this is a simple
consequence of Sn being n-transitive. In fact, one finds that the only ktransitive permutation group with relational complexity less than k + 1 is
Sn acting naturally on {1, . . . , n}. As such, the natural action of An on
{1, . . . , n} has relational complexity n − 1.
See [Che], [Che00], and [CMS96] for further background on relational
complexity (also known as arity).
3. Regular nonabelian type
We now begin our proof of Theorem A by moving through the various socle types laid out in Fact 2.1. We start with the case of a regular nonabelian
socle. Our goal is the following.
Proposition 3.1. Every finite primitive group of regular nonabelian type
has relational complexity at least 3.
We adopt the following setup for the remainder of the section; most of the
necessary information for this type can be found in [DM96, Theorem 4.7B].
Setup. Assume that (X, G) is a finite primitive group with a regular, nonabelian socle M . Since M acts regularly on X, we identify X with M , and
setting H := G1 , we have G = M ⋊ H with M acting on X by right translation and H acting by conjugation. Furthermore, M = T1 × · · · × Tk with
k ≥ 6 and each Ti isomorphic to a fixed nonabelian simple group T . (In this
case, G is isomorphic to a so-called twisted wreath product T twrϕ H.)

A REDUCTION THEOREM FOR PRIMITIVE BINARY PERMUTATION GROUPS

5

If a ∈ X, m ∈ M , and h ∈ H, we write the action of mh on a as
a · mh := (am)h so as to avoid confusion with the product amh in G. Note
that H acts on X as automorphisms, so in particular, (a−1 ) · h = (a · h)−1 .
We first work for an analog of [Che, Corollary 1.4]; this will be Lemma 3.3.
Lemma 3.2. If (a1 , a2 ), (b1 , b2 ) ∈ X 2 , then we have that (a1 , a2 ) ∼G (b1 , b2 )
−1
if and only if a1 a−1
2 ∼H b1 b2 .
Proof. If (a1 , a2 ) · mh = (b1 , b2 ) for some m ∈ M and h ∈ H, then
−1
−1
h
−1 h
(a1 a−1
2 ) · h = [(a1 m)(a2 m) ] · h = (a1 m) ((a2 m) ) = b1 b2 .
−1
Conversely, assume that (a1 a−1
2 ) · h = b1 b2 for some h ∈ H. Then g :=
−1
a2 hb2 takes a1 to b1 , and it is trivial to check that a2 · g = b2 .


Lemma 3.3. Assume (X, G) is binary. If a ∈ X and h ∈ H are such that
[a, a · h] = 1, then there exists an h′ ∈ H swapping a and a · h.
Proof. The conclusion of the lemma is precisely that (a, a · h) ∼H (a · h, a).
Since H acts on X as automorphisms, this is equivalent to showing that
(a, a−1 · h) ∼H (a · h, a−1 ), which is, of course, equivalent to showing that
(1, a, a−1 · h) ∼G (1, a · h, a−1 ). Now, the action is binary, so it suffices to
show that (1, a, a−1 ·h) is 2-equivalent to (1, a·h, a−1 ). Since h and h−1 fix 1,
the only nontrivial conjugacy to check is (a, a−1 · h) ∼G (a · h, a−1 ), but this
follows from the previous lemma and our assumption that [a, a · h] = 1. 
Definition 3.4. A subset of X (or tuple in X ℓ ) is called H-connected if all
elements of the subset (or entries of the tuple) are H-conjugate.
By [DM96, Theorem 4.7B(ii)], H acts transitively on the set {T1 , . . . , Tk }.
Thus for any a1 ∈ T1 there exist a2 , . . . , ak ∈ X such that each ai ∈ Ti
and {a1 , . . . , ak } is H-connected. Thus, we are guaranteed the existence
of (many) H-connected subsets of k commuting elements of X, and every
nontrivial a1 ∈ T1 can be extended to at least one such subset.
Lemma 3.5. Assume (X, G) is binary. If (a1 , . . . , aℓ ) is an H-connected
−1
tuple of commuting elements of X, then (a1 , . . . , aℓ ) ∼G (a−1
1 , . . . , aℓ ). Fur−1
−1
ther, if a1 and a−1
1 are H-conjugate, then (a1 , . . . , aℓ ) ∼H (a1 , . . . , aℓ ).
Proof. Let 1 ≤ i < j ≤ ℓ. Since ai and aj commute and are H-conjugate,
we apply Lemma 3.3 to see that there is an element of H swapping ai and
−1
−1
aj . Further, this implies that ai a−1
j is H-conjugate to aj ai = ai aj , so we
−1 −1
find that (ai , aj ) ∼G (ai , aj ) by Lemma 3.2. Since the action is binary,
−1
we conclude that (a1 , . . . , aℓ ) ∼G (a−1
1 , . . . , aℓ ).
Now assume that a1 is H-conjugate to a−1
1 . Since (a1 , . . . , aℓ ) is Hconnected, we find that ai is H-conjugate to a−1
for all 1 ≤ i ≤ ℓ. Thus,
i
for every i, we have that (1, ai ) ∼G (1, a−1
).
We
have already seen that
i
−1 −1
(ai , aj ) ∼G (ai , aj ) for all 1 ≤ i < j ≤ ℓ, so the fact that (X, G) is binary
−1
implies that (1, a1 , . . . , aℓ ) ∼G (1, a−1
1 , . . . , aℓ ). Of course, this is equivalent
−1
to (a1 , . . . , aℓ ) ∼H (a−1

1 , . . . , aℓ ).

6

JOSHUA WISCONS

The final ingredient for our proof of Proposition 3.1 is the following general
(and likely well-known) lemma.
Lemma 3.6. If T is a nonabelian simple group with an automorphism α of
order 2, then α inverts, but does not centralize, some element of T .
Proof. We work in T ⋊ hαi. Consider [T, α], as a set. It is easy to see that α
inverts every element of [T, α]. Now, towards a contradiction, assume that
[T, α] ⊆ C(α). If t ∈ T , then α centralizes αt α, so α commutes with αt .
We conclude that αT ⊆ C(α), and as the set αT is T -normal, we find that
αT ⊆ C(αT ). In particular, A := hαT i is abelian and T -normal. Further,
A is certainly nontrivial, so as T is nonabelian and simple, we see that
T ∩ A = 1. We conclude that A = hαi, so T centralizes α. Since α is
nontrivial, this is a contradiction.

of Proposition 3.1. Assume that the action is binary. We first claim that
NH (T1 )/CH (T1 ) contains an involution. Now, [DM96, Theorem 4.7B(iii)]
states that NH (T1 ) has a composition factor isomorphic to T1 , but in fact,
the proof shows that such a factor appears in NH (T1 )/CH (T1 ). By the
Feit-Thompson Theorem, NH (T1 )/CH (T1 ) contains an involution.
We may now apply the previous lemma to see that there exists an a1 ∈ T1
such that a1 6= a−1
and a1 is H-conjugate to a−1
1
1 . Extend a1 to an Hconnected tuple (a1 , a2 , . . . , ak ) with each ai ∈ Ti , and note that ai commutes with aj for all i and j. By Lemma 3.5, there is some h ∈ H taking
−1
(a1 , . . . , ak ) to (a−1
1 , . . . , ak ). Now, by [DM96, Theorem 4.7B(ii)], H acts
faithfully on {T1 , . . . , Tk }. Since h inverts some nontrivial element in each
Ti , we see that h must normalize each Ti . Thus, h = 1, so (a1 , . . . , ak ) =
−1

(a−1
1 , . . . , ak ). We have a contradiction.
4. Diagonal type
We now move to groups of diagonal type. We aim to prove the following.
Proposition 4.1. Every finite primitive group of diagonal type has relational complexity at least 3.
Information on groups of diagonal type can be found in [DM96, Section 4.5]. We fix the following setup.
Setup. Assume that (X, G) is a finite primitive group of diagonal type. For
some integer k ≥ 2, the socle of G is M := T1 × · · · × Tk where each Ti
is isomorphic to a fixed nonabelian simple group T . Fixing isomorphisms
of each Ti with T , we identify X with the set T1 × · · · × Tk modulo the
equivalence relation given by the orbits of T acting diagonally on X by left
multiplication (by the inverse); M acts coordinatewise by right multiplication. An arbitrary element of X is written [a1 , . . . , ak ] with each ai ∈ Ti
where [a1 , . . . , ak ] := {(t−1 a1 , . . . , t−1 ak ) : t ∈ T }. Set 1 := [1, . . . , 1] and
H := G1 . Then H acts on X as a subgroup of Aut T × Sk where Aut T acts
diagonally and Sk permutes the components. Further, H contains Inn T .

A REDUCTION THEOREM FOR PRIMITIVE BINARY PERMUTATION GROUPS

7

Our approach here will be similar to that for the regular nonabelian type
in that we will again find an element of the point stabilizer H that simultaneously “inverts” a large tuple from X. However, in this case, the entries
of the “inverted” tuple will all come from T1 ; where as, in the regular nonabelian case, different entries came from different Ti . As before, we first
derive an analog of [Che, Corollary 1.4].
Lemma 4.2. Assume (X, G) is binary. For any nontrivial t ∈ T1 and
s ∈ Inn T there is an h ∈ NH (T1 ) swapping [t, 1, . . . , 1] and [ts , 1, . . . , 1].
Proof. We aim to show that
(1, [t, 1, . . . , 1], [ts , 1, . . . , 1]) ∼G (1, [ts , 1, . . . , 1], [t, 1, . . . , 1])
as any element taking the first tuple to the second must necessarily lie in H,
hence in NH (T1 ) since H ≤ Aut T × Sk . Further, note that this equivalent
to showing that
(1, [t, 1, . . . , 1], [t−s , 1, . . . , 1]) ∼G (1, [ts , 1, . . . , 1], [t−1 , 1, . . . , 1]).
Now, we are assuming that the action is binary, so as H contains Inn T , it
is enough to note that the map
[a1 , a2 , . . . , ak ] 7→ [a1 ts , a2 t, . . . , ak t]
is an element of G, in fact M , that takes the pair ([t, 1, . . . , 1], [t−s , 1, . . . , 1])
to ([ts , 1, . . . , 1], [t−1 , 1, . . . , 1]).

of Proposition 4.1. Assume that (X, G) is binary. Let r ∈ T be the product
of two noncommuting involutions from T . Then, r is not an involution, and
r is T -conjugate to r −1 .
Let r1 be the element of T1 corresponding to r under our fixed isomorphism. Enumerate the conjugacy class of r1 in T1 as r1 , . . . , rn , and
set xi := [ri , 1, . . . , 1]. By the previous lemma, there exists an hi,j ∈
NH (T1 ) swapping xi and xj . Further, since each ri is T1 -conjugate to
ri−1 , Lemma 4.2 also shows that there exists a ki ∈ NH (T1 ) swapping xi
−1
and x−1
:= [ri−1 , 1, . . . , 1]. We now claim that there is an
i , where xi
h ∈ NH (T1 ) that simultaneously “inverts” every element of {x1 , . . . , xn },
−1
i.e. that (x1 , . . . , xn ) ∼NH (T1 ) (x−1
1 , . . . , xn ). As in the proof of Lemma 4.2,
−1
this is equivalent to showing (1, x1 , . . . , xn ) ∼G (1, x−1
1 , . . . , xn ). Since the
action is assumed to be binary, it only remains to verify that (xi , xj ) ∼G
−1
−1
(x−1
i , xj ), and setting m := (ri , rj , . . . , rj ) ∈ M , it is easily checked that
−1
(xi , xj )hij m = (x−1
i , xj ).
Let ĥ ∈ Aut(T ) be the automorphism of T corresponding to h, and let
C := r T . Since h simultaneously inverts the xi , it is not hard to see that ĥ
must invert every element of C, so when restricted to C, ĥ commutes with
Inn(T ). Thus, [Inn(T ), ĥ] centralizes C, but then [Inn(T ), ĥ] centralizes the
subgroup generated by C. As T is simple, we find that [Inn(T ), ĥ] centralizes

8

JOSHUA WISCONS

T , i.e. ĥ is a central automorphism. One easily computes that for all s, t ∈ T
−1 tĥ

(sĥ )t

ĥ

= ((tst−1 )ĥ )t = (t−1 )ĥ (tst−1 )ĥ tĥ = (t−1 tst−1 t)ĥ = sĥ ,

so t−1 tĥ ∈ Z(T ) for all t ∈ T . Since T is nonabelian and simple, we conclude that ĥ acts trivially on T , but as ĥ does not centralize r, we have a
contradiction.

5. Product type
Finally, we address product type.
Proposition 5.1. If G is a finite primitive binary group of product type
then G is a subgroup of H wr Sm in its product action where H is a primitive
binary almost simple permutation group that is not 2-transitive.
Here, in addition to drawing from [DM96], we also utilize [Kov89]. We
fix the following setup.
Setup. Assume that (X, G) is a finite primitive group of product type.
Identify X with Y k (with k ≥ 2) and G with a subgroup of W := H wr Sk
in its product action where H is a primitive subgroup of Sym(Y ) of almost
simple or diagonal type. Setting N := soc(H), we have M := soc(G) = N k .
Now, let π be the obvious projection from W to Sk , and set P to be the
image of G under π. Further, if W1 is the preimage under π of the stabilizer
of the first coordinate, then W1 factors as W1 = H × (H k−1 wr Sk−1 ), and
we let π1 be the projection of W1 onto the first factor H. Finally, set G1 to
be the image of (W1 ∩ G) under π1 .
We first highlight two important properties of P and G1 (see the discussion following [Kov89, (2.3)]).
Fact 5.2. The action of P on {1, . . . , k} is transitive; the action of G1 on
Y is primitive with soc(G1 ) = N .
We view the elements of X = Y k as row vectors and m-tuples of elements of X as m × k-matrices. The elements of the base group H k then act
“column-wise” on the matrices, and the top group permutes the columns.
The proof of Proposition 5.1 is essentially the following straightforward
lemma modulo one outstanding case that we address below.
Lemma 5.3 (see [CMS96, Theorem 1]). The relational complexity of (X, G)
is at least as big as the relational complexity of (Y, G1 ).
Proof. Let r be the relational complexity of (X, G); note that r ≥ 2. We now
consider (Y, G1 ) and show that r-types determine m-types for all m ≥ r.
Indeed, take two r-equivalent tuples c̄1 , c̄2 ∈ Y m viewed as m × 1 matrices.
Appealing to Remark 2.5, we also assume that neither c̄1 nor c̄2 have repeated entries. Fix y ∈ Y . Let c̄ be the the m × 1 matrix with each entry
equal to y, and form the m×k matrices A = ( c̄1 c̄ c̄ ··· c̄ ) and B = ( c̄2 c̄ c̄ ··· c̄ ).

A REDUCTION THEOREM FOR PRIMITIVE BINARY PERMUTATION GROUPS

9

Now, viewing A and B as elements of X m , we easily see that they are requivalent under the action of G (in fact W1 ∩ G). Thus, by assumption,
there is some g ∈ G taking A to B. Since the first columns of A and B are
the only nonconstant columns, it must be that g ∈ W1 ∩ G, so the image of
g in G1 takes c̄1 to c̄2 . Hence, the r-types of (Y, G1 ) determine m-types for
all m ≥ r, so the relational complexity of (Y, G1 ) is at most r.

of Proposition 5.1. Let (X, G) be as above, and now assume that the action
is binary. Thus, by the previous lemma (Y, G1 ) is binary. Additionally,
soc(G1 ) = soc(H) = N , and since H is a primitive group of almost simple
or diagonal type, the same is true of G1 . By Proposition 4.1, the second
option is not possible, so G1 is almost simple. It remains to show that
(Y, G1 ) is not 2-transitive.
Assume (Y, G1 ) is 2-transitive. Since (Y, G1 ) is binary, this implies that
G1 = Sym(Y ). We now give an explicit example showing that this in turn
implies that the 2-types of (X, G) do not determine the 4-types. Thus, the
action is not binary, which is a contradiction.
Since (X, G) is of product type, soc(G), hence N = soc(G1 ), is nonabelian,
so N = Alt(Y ) with |Y | ≥ 5. Thus, for every ȳ1 , ȳ2 ∈ Y k = X and
every g = h̄σ ∈ G (h̄ ∈ H k and σ ∈ Sk ), there is a g′ ∈ G such that
(ȳ1 , ȳ2 )g′ = (ȳ1 , ȳ2 )σ. Indeed, since G contains N k , the 2-transitivity of N
on Y implies that there is an m̄ ∈ Alt(Y )k for which (ȳ1 , ȳ2 )m̄h̄ = (ȳ1 , ȳ2 ).
Thus we say that G realizes P on pairs from X.
We now identify Y with {1, . . . , ℓ} for some natural number ℓ ≥ 5. Consider the following matrices representing two tuples in X 4 :


1
1
A=
3
3

1
2
3
4

1
2
3
4

···
···
···
···



1
1
1
2
 and B = 
3
3
4
4

1
2
3
3

1
2
3
4

···
···
···
···


1
2

3
4

We first claim that they are 2-equivalent, i.e. that any two rows from A
are G-conjugate to the corresponding two rows in B. Clearly we need only
check pairs of rows that include the fourth. Since (Y, N ) is 2-transitive, we
easily see that first and fourth as well as second and fourth rows of A are
simultaneously conjugate (using elements in N k ) to the corresponding rows
in B. Finally, we use our observation above that G realizes P on pairs from
X together with the fact that P is transitive on the coordinates to see that
G contains an element (only permuting coordinates) that takes the third
and fourth rows of A to the corresponding rows of B. We conclude that A
and B are 2-equivalent, but they have no chance to be 4-equivalent since the
“column patterns” are different. For example, the first column of A contains
precisely two distinct entries, so the image of A under an element of G must
also contain a column with precisely two distinct entries.


10

JOSHUA WISCONS

Acknowledgements
The author would like to acknowledge the warm hospitality of the Hausdorff Research Institute for Mathematics where the work in this article began in the fall of 2013 during the trimester program on Universality and
Homogeneity. The author is also grateful to Gregory Cherlin for the several
enlightening and enjoyable conversations about relational complexity while
in Bonn. Additionally, the author is thankful to the anonymous referee for
a very careful reading of the paper and many helpful suggestions.
References
[Che]

Gregory Cherlin. On the relational complexity of a finite permutation
group.
Accepted
in
J.
Algebraic
Combin.
Preprint,
math.rutgers.edu/~ cherlin/Paper/BinaryAffine.pdf.
[Che00] Gregory Cherlin. Sporadic homogeneous structures. In The Gelfand Mathematical Seminars, 1996–1999, Gelfand Math. Sem., pages 15–48. Birkhäuser Boston,
Boston, MA, 2000.
[CMS96] Gregory L. Cherlin, Gary A. Martin, and Daniel H. Saracino. Arities of permutation groups: wreath products and k-sets. J. Combin. Theory Ser. A, 74(2):249–
286, 1996.
[DM96] John D. Dixon and Brian Mortimer. Permutation groups, volume 163 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1996.
[KL87] Julia F. Knight and Alistair H. Lachlan. Shrinking, stretching, and codes for
homogeneous structures. In Classification theory (Chicago, IL, 1985), volume
1292 of Lecture Notes in Math., pages 192–229. Springer, Berlin, 1987.
[Kov89] L. G. Kovács. Primitive subgroups of wreath products in product action. Proc.
London Math. Soc. (3), 58(2):306–322, 1989.
[Lac84] A. H. Lachlan. On countable stable structures which are homogeneous for a
finite relational language. Israel J. Math., 49(1-3):69–153, 1984.
[Sar99] Dan Saracino. On a combinatorial problem from the model theory of wreath
products. I, II. J. Combin. Theory Ser. A, 86(2):281–305, 306–322, 1999.
[Sar00] Dan Saracino. On a combinatorial problem from the model theory of wreath
products. III. J. Combin. Theory Ser. A, 89(2):231–269, 2000.
Department of Mathematics, Hamilton College, Clinton, NY 13323, USA
E-mail address: jwiscons@hamilton.edu

