Two permutations can each move a great many points. If their moved sets meet in exactly one point, their commutator moves exactly three. Bochert’s theorem turns that local calculation into a bound on the order of a primitive permutation group.
There are two tasks. First, force a one-point overlap using only information about which points group elements move. Then use the 3-cycle it produces to recover information about the whole group.
Slide one support past the other
Keep u = (1 2)(4 6) fixed in red. The blue permutation v is a copy of u shifted around the eight points. At shift 1 their moved sets meet only at 2. Change the shift, or pick a starting point to trace the four operations in the commutator.
Shift the blue swaps
Rightmost-first trace
Why just three points move
The support of a permutation is the set of points it moves. Suppose the supports of u and v meet in the single point p. Write a = u(p) and b = v(p). These are three distinct points, since a is moved only by u and b only by v.
Apply products rightmost first, and write [u, v] = uvu−1v−1. Conjugating v by u relabels its cycles. On the support of v, the only label changed is p, which becomes a. Think of lifting p out of its cycle and inserting a in the same place.
Now apply v−1 followed by that edited v. Every arrow cancels except at the edit. Starting at p, the backward step reaches the predecessor of p, whose new successor is a. Starting at a, the backward step stays there and the new forward step goes to b. Starting at b, the backward step takes you to p, which the edited v now fixes. Thus
The overlap identifies where to look. The original permutations still supply the successors u(p) and v(p) and hence the actual cycle in the group.
Grow a 3-cycle into the alternating group
Suppose G contains a 3-cycle. Take its conjugates by every element of G and draw their supports as triples. The connected components, where triples connect by sharing a point, form a partition that G preserves. A primitive action is transitive and preserves only the partition into singletons and the partition with one part. Since a triple already puts three points together, primitivity forces the triples to connect the whole point set.
Here is why connectivity suffices. Start with one triple, whose cycle generates the alternating group on those three points. Suppose we have obtained all even permutations on a set W, fixing everything outside W, and a new triple meets W.
- Two shared points. If the third point is x, conjugate the new cycle by even permutations of W and use its inverse as needed. Even permutations of a set of size at least three act transitively on unordered pairs, so this gives all 3-cycles involving x and two points of W. Together with the cycles already in W these generate the alternating group on W ∪ {x}.
- One shared point. Write the new cycle as (a x y) with a ∈ W. Move a to a different point b of W by conjugation. The product (a x y)(b x y)−1 = (a x b) gives the two-point case and adds x. The original triple then adds y.
To see the generation fact used here, write an even permutation as pairs of swaps. Two identical swaps cancel. A pair with one shared point is a 3-cycle. A disjoint pair splits as (a b)(c d) = (a c b)(a c d). Thus 3-cycles generate every alternating group. Repeating the growth step along the connected triples shows that a primitive subgroup of Sn containing one 3-cycle contains An.
In the eight-point example, let c be the cycle that shifts every point one place. The group generated by u and c contains the blue copy v = cuc−1, hence the 3-cycle at shift 1. Its translates under c have supports on consecutive triples around the circle, so we can see connectivity directly. They generate A8. The shift c is an odd permutation, so the two original generators give all of S8.
Force the overlap with a smallest base
A base is a set of points whose pointwise stabilizer consists only of the identity. Equivalently, it meets the support of every nonidentity permutation in G. This lets us work with the supports as a family of subsets. Choose a base B of minimum size and suppose it has more than half the points.
- The complement C is smaller than B, so it misses the support of some nonidentity u. All points moved by u lie in B. Choose one of them, p.
- The set B with p removed also falls below the minimum base size. Some nonidentity v fixes each of its points. The support of v lies in C ∪ {p} and must include p, since it meets B.
So the supports meet exactly at p. The commutator yields a 3-cycle in G itself, and primitivity propagates it to all of An. Therefore a primitive group that does not contain An has a base of at most ⌊n/2⌋ points.
Count the possible images of a base
Order the b points of a smallest base. If two group elements agree on those points, applying one and then the inverse of the other fixes the base pointwise, so the two elements are equal. There are at most n!/(n − b)! ordered lists of distinct images. Insert the base bound.
Bochert’s bound. If G ≤ Sn is primitive and does not contain An, then
In degree 20, the index is at least 10! = 3,628,800. The factorial comes from the points left over after the images of a base have been specified.
The six-point action that attains the bound
In When one swap becomes three, the stabilizer of one perfect-matching factorization is a copy of S5 acting transitively on the original six points. Its order is 120. A nontrivial invariant partition would have three blocks of size two or two blocks of size three. The full groups preserving those partitions have orders (2!)³·3! = 48 and (3!)²·2! = 72, respectively. Both are too small, so the action is primitive.
This subgroup has index 6!/120 = 6 = 3!. It attains Bochert’s bound. Its smallest base has size three: the theorem supplies a base of at most three, and two points have only 6·5 = 30 possible ordered images, too few to distinguish 120 elements.
Sources
- Alfred Bochert, Ueber die Zahl der verschiedenen Werthe, die eine Function gegebener Buchstaben durch Vertauschung derselben erlangen kann, Mathematische Annalen 33 (1889), 584–590.
- Timothy C. Burness presents the minimum-base argument in Bases for permutation groups, Lecture 1. The use of a 3-cycle in a primitive group is the three-cycle case of Jordan’s theorem. Jordan’s 1871 paper