## FINITE PERMUTATION GROUPS WITH FEW ORBITS UNDER THE ACTION ON THE POWER SET

ALEXANDER BETZ, MAX CHAO-HAFT, TING GONG, THOMAS MICHAEL KELLER, ANTHONY TER-SAAKOV, AND YONG YANG

Abstract. We study the orbits under the natural action of a permutation group G ≤ S n on the powerset P ( { 1 , . . . , n } ). The permutation groups having exactly n +1 orbits on the powerset can be characterized as set-transitive groups (see Definition 1.2) and were fully classified in [2]. In this paper, we establish a general method that allows one to classify the permutation groups with n + r set-orbits for a given r , and apply it to integers 2 ≤ r ≤ 15 with the help of the computer algebra system GAP [6].

## 1. Introduction

↦

↦

Definition 1.1 (Beaumont and Peterson, [2]) . Given an integer 0 ≤ t ≤ n , a permutation group G on n letters is called t-set-transitive if for all t -element subsets S, T ⊆ N , there exists g ∈ G such that gS = T .

Throughout the paper, we let n ≥ 2 denote a positive integer and let N = { 1 , . . . , n } . 1 By a permutation group on n letters we mean a subgroup G of S n endowed with the natural action ( g, x ) → gx := g x ( ) : G × N → N . We call n the degree of the permutation group G . The action of G on N induces an action of G on P ( N ), given by ( g, X ) → gX = { gx : x ∈ X } : G × P ( N ) → P ( N ). In this case, the elements being acted on are subsets of N . Accordingly, we shall call the orbits under this action set-orbits . Note that for all g ∈ G and X ⊆ N , | gX | = | X | . Since there are n + 1 distinct sizes of subsets of N , it follows that there are at least n + 1 distinct set-orbits. Additionally, this shows that all sets in the same set-orbit will have the same cardinality. A set-orbit containing sets of size t will be called a t -set-orbit . For a given permutation group G on n letters, the number of distinct t -set-orbits under the action of G on P ( N ) will be denoted by s t ( G ) and the total number of set-orbits will be denoted by s G ( ). Clearly s G ( ) = ∑ n s =0 s t ( G ).

In terms of the action of G on P ( N ), we see that G is t -set-transitive if and only if s t ( G ) = 1. In other words, a t -set-transitive group is a permutation group with exactly one t -setorbit. Clearly, all permutation groups are 0-set-transitive and n -set-transitive. A1-set-transitive permutation group is simply transitive on N .

Definition 1.2 (Beaumont and Peterson, [2]) . A permutation group G on n letters is called set-transitive if G is t -set-transitive for all integers 0 ≤ t ≤ n .

Set-transitive groups were studied as early as 1944 by Neumann and Morgenstern [12]. In [2], Beaumont and Peterson proved that a set-transitive permutation group on n letters, with n / ∈ { 5 6 9 , , } , always contains the alternating group A n . There has also been significant research devoted to bounding the number of set-orbits s G ( ) of a degree n permutation group G . A trivial lower bound is s G ( ) ≥ 2 n / G | | . In [5], Cameron proved that if G has order exp( o n ( 1 2 / )), then s G ( ) = (2 n / G | | )(1 + o (1)). In [1], Babai and Pyber showed that if G does not contain A l ( l &gt; t ≥ 4) as a composition factor, then log 2 s G ( ) n ≥ c t for some positive constant c . In the

1 We exclude case n = 1 as the only group action on the set { } 1 is the trivial action.

same paper, they raised the following question: what is inf( log 2 s G ( ) n ) over all solvable degree n permutation groups G ? This question was answered in a recent paper by Yang in [13].

On the other hand, there has been relatively little work done on the problem of classifying groups in terms of their number of set-orbits. Beaumont and Peterson successfully classified all set-transitive permutation groups in [2], and Kantor classified 2 , 3 4-set-transitive groups which , are not 2 , 3 4-transitive in [9]. , These classifications lend itself to a natural generalization in the following sense. Viewed in terms on the action of G on P ( N ), we see that G is set-transitive if and only if s G ( ) = n +1. Our paper seeks to completely classify the permutation groups G on n letters satisfying s G ( ) = n + , for small positive integers r r . The paper is laid out in the following manner. In Sections 1 and 2, we give necessary definitions and useful facts. In Section 3, we develop a general method mimicking the strategy in [2]. In Section 4, we exemplify the method by classifying groups with n +2, n +3, n +4, and n +5 set-orbits. Then we use GAP [6] to calculate all such groups for r ≤ 15. Before continuing, we state the following useful facts from [2] and [10].

Given a permutation group G on n letters:

- (1) If G contains a t -set-transitive subgroup H , then G is t -set-transitive.
- (2) If G is t -transitive, then G is s -set-transitive for all positive integers s ≤ t .
- (3) The symmetric group S n is set-transitive.
- (4) The alternating group A n is set-transitive for all n ≥ 3.

## 2. Main Theorems

- (5) If s t ( G ) = 1 for some 2 ≤ t ≤ ⌊ n 2 ⌋ , then G is primitive. 2

Theorem 3 in [2] states that if G is t -set-transitive, then G is ( n -t )-set-transitive for any integer 1 ≤ t ≤ n -1. It is easy to generalize this to the following observation:

Lemma 2.1. Let G be a permutation group on n letters and let 0 ≤ t ≤ n be an integer. Then s t ( G ) = s n -t ( G ) .

Note that there are n +1 distinct sizes of sets in P ( N ). Hence, if n is odd, there are an even number of distinct set sizes, and so Lemma 2.1 implies that a permutation group on n letters must have an even number of set-orbits. Therefore, if n is odd and a permutation group G on n letters has s G ( ) = n + , then r r will have to be odd as well. Now consider the situation where n is even and a permutation group G on n letters has an odd number of set-orbits. In this case, since s t ( G ) = s n -t ( G ) for all 0 ≤ t ≤ n , it follows that s n/ 2 ( G ) must be odd. We summarize these results in the following lemma.

Lemma 2.2. Let G be a permutation group on n letters and suppose s G ( ) = n + r .

- (1) If r is even, then n is even.
- (2) If r is odd and n is even, then s n/ 2 ( G ) is odd.

Theorem 2.3. [Livingstone and Wagner, [10] ] Given a permutation group G on n letters and an integer 1 ≤ t ≤ n 2 , we have s t -1 ( G ) ≤ s t ( G ) .

Remark. This theorem implies that if 1 ≤ t &lt; ⌊ n 2 ⌋ -1 then s t ( G &gt; ) 1 only if s t -1 ( G &gt; ) 1. We will make frequent use of this fact in our classification.

Lemma 2.4. Let G be (⌊ n 2 ⌋ + k ) -set-transitive for a positive integer k . If there exists a prime p such that ⌊ n 2 ⌋ + k &lt; p ≤ n , then G is ( n -p +1) -transitive.

2 Throughout this paper, we let /floorleft x /floorright be the floor function.

Proof. By Theorem 7, Corollary 1 in [2], it suffices to show that p &gt; max (⌊ n 2 ⌋ + k, n -⌊ n 2 ⌋ -k ) = ⌊ n 2 ⌋ + . This is true by assumption, so we are done. k /intersectionsq /unionsq

Lemma 2.5. Let k be a positive integer and let G be a permutation group on n letters that does not contain A n . If there exists a prime p such that ⌊ n 2 ⌋ + k &lt; p &lt; 2 n 3 , then G is not (⌊ n 2 ⌋ + k ) -set-transitive.

Proof. Assume for contradiction that G is (⌊ n 2 ⌋ + k ) -set-transitive, then by Lemma 2.4 such a group G is ( n -p +1)-transitive. Since G does not contain A n , G is at most ( n 3 +1)-transitive (see [4, page 152]). Now notice that n -p +1 &gt; n -2 n 3 +1 since p &lt; 2 n 3 and since n -2 n 3 +1 = n 3 +1, we have reached a contradiction and thus are done. /intersectionsq /unionsq

Note that both Lemmas 2.4 and 2.5 hold for k = 0 when n is even. If we find a maximum k 0 for which there exists a prime p such that ⌊ n 2 ⌋ + k 0 &lt; p &lt; 2 3 n , then G cannot be ⌊ n 2 ⌋ + k set-transitive for any k ≤ k 0 . If n is odd and such a k 0 exists, then G is not ⌊ n 2 ⌋ +1 set-transitive. Thus it is not ⌊ n 2 ⌋ set-transitive either. These results are summarized in the following corollary.

Proof. If G is even, then the existence of such a nonnegative k 0 shows that there exists a prime p such that 1 2 + k ≤ n 2 + k 0 &lt; p &lt; 2 n 3 . By Lemma 2.5, G is not n 2 + k set-transitive. For the case of G being odd, a positive k 0 shows that there exists a prime p such that ⌊ n 2 ⌋ + k ≤ ⌊ n 2 ⌋ + k 0 &lt; 2 n 3 . Since this holds at least for k = 1, it holds for k = 0 since n -(⌊ n 2 ⌋ +1 = ) ⌊ n 2 ⌋ . /intersectionsq /unionsq

Corollary 2.6. Let G be a permutation group on n letters not containing A n , where n is even (odd). Let k 0 be the greatest nonnegative (positive) integer such that there exists a prime p with ⌊ n 2 ⌋ + k 0 &lt; p &lt; 2 n 3 . Then for all 0 ≤ k ≤ k 0 , G is not ⌊ n 2 ⌋ + k set-transitive.

Theorem 2.7. A permutation group G on n letters not containing A n is not ⌊ n 2 ⌋ + k settransitive for any positive integer values of k ≤ k 0 where k 0 is the largest integer such that 48 -n +1 2 ≤ k 0 ≤ 5 54 n -1 2 .

Proof. First note that 48 ≤ n +1 2 + k 0 . Due to a result by Breusch [3], which states that there exists a prime between x and 9 x 8 for x ≥ 48, there exists a prime p between n +1 2 + k 0 and 9 16 n + 9 8 k 0 + 9 16 . Note that p &gt; ⌊ n 2 ⌋ + k for all k ≤ k 0 . Since k 0 ≤ 5 54 n -1 2 , we have p &lt; 9 16 n + 9 8 k 0 + 9 16 ≤ 9 16 n + 9 8 ( 5 54 n -1 2 ) + 9 16 = 2 3 n. Thus by Lemma 2.5, G cannot be ⌊ n 2 ⌋ + k set-transitive for any k ≤ k 0 . /intersectionsq /unionsq

Remark. For k = 0 the theorem still holds true for even n . For odd n G , is not ⌊ n 2 ⌋ set-transitive when a positive k 0 exists because G will not be ⌊ n 2 ⌋ +1 set-transitive. This theorem is powerful as it shows that often sets of the same size lie in different orbits. The larger n is, the more set-orbits G will have. The theorem can be applied to make an upper bound on the amount of letters G can permute and have exactly n + r set-orbits. For example, the first value of n for which we get an applicable k 0 is n = 81, which gives k 0 = 7. This implies that a permutation group G on n letters not containing A n has at least 14 additional set-orbits, which leads to a corollary.

Corollary 2.8. If a permutation group G on n letters that does not contain A n has less than n +16 set-orbits, then n ≤ 81 .

The following Lemmas are in [1].

Lemma 2.9. If L ≤ G ≤ Sym(Ω) , then s G ( ) ≤ s L ( ) ≤ s G ( ) · | G : L | .

Lemma 2.10. Assume G is intransitive on Ω and has orbits Ω 1 , . . . , Ω m . Let G i be the restriction of G to Ω i . Then

$$s ( G ) \geq s ( G _ { 1 } ) \times \cdots \times s ( G _ { m } ).$$

Proof. Since G ≤ G 1 × · · · × G m we can apply Lemma 2.9. Clearly s G ( 1 × · · · × G m ) = s G ( 1 ) ×··· × s G ( m ). /intersectionsq /unionsq

Lemma 2.11. Let G be a transitive permutation group acting on a set Ω where | Ω = | n . Let (Ω 1 , . . . , Ω m ) denote a system of imprimitivity of G with maximal block-size b (1 ≤ b &lt; n b ; = 1 if and only if G is primitive; bm = n ). Let N denote the normal subgroup of G stabilizing each of the blocks Ω i . Let G i = Stab G (Ω ) i , and denote s = ( s G 1 ) . Then

$$s ( G ) \geq \binom { s + m - 1 } { s - 1 }.$$

## 3. Outline of Methods

In this section we will outline a step-by-step method on how we fully classify groups with n + r set-orbits for 2 ≤ r ≤ 5 which can also be applied to classify groups with n + r set-orbits for even greater r . To outline our method we first reduce the amount of letters n on which G could act, then once we have a reasonable sized list we can test a number of specific permutation groups for the remaining n values. Throughout the whole method we assume that any permutation group we consider does not contain A n because if it did then s G ( ) = n +1. We will exemplify how to do some of the steps in the calculation sections of this paper.

Step 0. Choose the r value for which you want to classify all groups with s G ( ) = n + . Let r k 0 = ⌊ r -1 2 ⌋ and find the smallest n such that k 0 fits in the bounds specified by Theorem 2.7. The smallest n for which any k 0 appears is n = 81 with k 0 = 7. This is 'Step 0' because for any reasonable r , say r &lt; 16, we know that n ≤ 81.

Step 1. Now that we have an upper bound on n we can start eliminating some of the possible n . Right away, if r is even then we can eliminate all the odd n by Lemma 2.2. Since we need n + r set-orbits, we know that G cannot be s set-transitive for at most r -1 different set sizes s . This is where we can use Corollary 2.6. If n is odd then we need a k 0 value such that there is a prime n -1 2 + k 0 &lt; p &lt; 2 n 3 and 2 k 0 &gt; r -1. If n is even then we need a k 0 value such that there is a prime n 2 + k 0 &lt; p &lt; 2 n 3 and 2 k 0 + 1 &gt; r -1. This is because then we would know that s t ( G &gt; ) 1 for 2 k 0 different s values in the odd case, and 2 k 0 +1 different s values in the even case (due to the fact that s n 2 ( G ) = s n -n 2 ( G )). If we look at a table of primes and find any such p values for the necessary k 0 for a given n , then we can remove that n from the list of candidates.

Step 2: Miller's Method. Now we look at our remaining n values and apply a theorem of Miller [11, vol. III, p. 439] which states that if n = mp 0 + , r p 0 is prime, m ∈ N , p 0 &gt; m , r &gt; m , then a group G on n symbols, not containing A n , cannot be more than r -transitive. We decompose n so we have values of m p , 0 , and r that fit the conditions and we try to find a sufficiently small r . Using Lemmas 2.4 and 2.5, we see if we can find a small enough p such that ⌊ n 2 ⌋ + k 1 &lt; p ≤ n , then n -p +1 &gt; r will contradict that G is ⌊ n 2 ⌋ + k 1 set-transitive. For this, k 1 is the same as k 0 in the last step but it is not necessary that ⌊ n 2 ⌋ + k 1 &lt; 2 n 3 . If we reach a contradiction, then we can remove that n from the list.

Step 3. After applying Miller's Method we have reduced the number of possible groups on n letters that can have n + r set-orbits. We will now reduce the number of groups even further using the following argument. For a given n and r where r &lt; n -4, if s 2 ( G &gt; ) 1 then it follows that s G ( ) &gt; n + , in which case r G does not have n + set-orbits. Thus, we can assume r s 2 ( G ) = 1 which implies that G is primitive by Theorem 6 in [2]. Similarly, if r &lt; n -2, s 1 ( G &gt; ) 1 implies that s G ( ) &gt; n + , in which case r G does not have n + r set-orbits. By assuming s 1 ( G ) = 1 in this case, we know that G is transitive by Theorem 5 in [2]. In these two cases, we will use [7] to find the structure of the transitive groups. To reduce even further, we will introduce a fact from [2] which follows simply from the orbit stabilizer theorem.

## Fact 3.1. If a permutation group G on n letters is s set-transitive, then ( n s ) divides | G | .

Since we know s k 1 ( G ) = 1, then ( n k 1 ) must divide | G | . Under the above assumption, G is primitive or transitive, in which case one only needs to check a few groups. If the above restriction on r and n does not hold, then we cannot use the fact that s t ( G ) = 1 for any t . Under this situation, one must check all non-trivial subgroups of S n . We can use GAP to compute these cases.

Step 4: Computation. At this point, we have a list of possible n for the degree of G , and a list of possible groups for each n . Now we can simply run a GAP program to calculate s G ( ) for each candidate, and list out the ones that have s G ( ) = n + r as desired.

Remark. We will do this process by hand for r = 2 3 4 5 to exemplify the process and then use , , , a GAP program to go up to r = 15. Since we are going in a linear order for r = 2 3 4 5, we , , , will often run into the same group twice. An example of this is when we consider all primitive groups on eight letters such that ( ) 8 3 = 56 divides | G | , and in a later section we consider all primitive groups such that ( ) 8 2 = 28 divides | G | . We will not consider the same groups twice if we have already calculated s G ( ), but rather just list the groups we know have s G ( ) = n + r from previous sections and then only consider the groups whose order is divisible by 28 but not 56. There will be several different instances where we can use previous knowledge to reduce the possible number of groups with n + r set-orbits.

## 4. Groups With Few Set-Orbits

Groups with n +2 set-orbits Assume a group G on the set N = 1 { , . . . , n } has n +2 set-orbits. Looking at only even n and applying Step 1 with k 0 = 1, we are left with the following possibilities:

$$n = 2, 4, 6, 8, 1 0, 1 2, 1 4, 1 6, 2 4.$$

To exemplify Step 2, we will show one of the calculations done. Since 24 = 1 × 19+5, then G is at most 5-transitive. Using k 1 = 1 we need to find the smallest prime p such that 13 &lt; p ≤ 24, so p = 17. Thus, if G was 13 set-transitive, then it would be n -p + 1 = 8-transitive, which would contradict that it is at most 5-transitive. Thus, we know a permutation group on 24 letters cannot have s G ( ) = n +2.

We spare the reader from having to see any more of these calculations. At the end of this method, we are left with

$$n = 2, 4, 6, 8, 1 2.$$

Before continuing to Step 3, we take care of the trivial case of n = 2. The only permutation groups on 2 letters are the trivial group and S 2 . It happens that the trivial group has s G ( ) = 4, so we must include it. We will no longer consider n = 2 for any r .

Now we move on to Step 3. We consider transitive groups on 4 letters and primitive groups on 6 8 12 letters such that 15 56 792 divides the group orders, respectively. , , , ,

Now we move on to Step 4 (computation). We show all of the groups for which s G ( ) = n + 2 in the following table. For the GAP ID we let nTr be TransitiveGroup(n,r), nPr be PrimitiveGroup(n,r). We let nSr be ConjugacyClassesSubgroups( S n )[r].

|   n | G          |   | G | | GAP ID   |
|-----|------------|---------|----------|
|   2 | 1          |       1 | 2S1      |
|   4 | C 4        |       4 | 4T1      |
|   4 | D 8        |       8 | 4T3      |
|   6 | PSL(2 , 5) |      60 | 6P1      |
|   8 | AGL(1 , 8) |      56 | 8P1      |
|   8 | AΓL(1 , 8) |     168 | 8P2      |
|   8 | PGL(2 , 7) |     336 | 8P5      |
|   8 | ASL(3 , 2) |    1344 | 8P3      |
|  12 | M 12       |   95040 | 12P2     |

Groups with n +3 set-orbits From the previous computations we know that C 2 × C 2 on 4 letters and PSL(2 7) on eight letters have , s G ( ) = n +3.

For Step 1, we use a k 0 value of 2 for odd n and 1 for even n . We find primes in the necessary range and are left with

$$n = 3, 4, \dots, 1 6, 1 9, 2 3, 2 4, 2 5, 4 3.$$

Applying Step 2, we are left with

$$n = 3, 4, 5, 6, 7, 8, 9, 1 1, 1 2.$$

For n = 3, we check all subgroups of S 3 . For n = 4 5 we check the transitive groups. , For n = 6 7 8 9 11 12 , , , , , we check primitive groups with order divisible by 15 21 56 84 330 792, , , , , , respectively. Note that for the even n we are already done from the previous section. We show the results for all groups with n +3 set-orbits in a table, using the same GAP identification key as in the previous section.

|   n | G          |   | G | | GAP ID   |
|-----|------------|---------|----------|
|   3 | C 2        |       2 | 3S2      |
|   4 | C 2 × C 2  |       4 | 4T2      |
|   5 | C 5        |       5 | 5T1      |
|   5 | D 10       |      10 | 5T2      |
|   7 | AGL(1 , 7) |      42 | 7P4      |
|   7 | PSL(3 , 2) |     168 | 7P5      |
|   8 | PSL(2 , 7) |     168 | 8P4      |
|  11 | M 11       |    7920 | 11P6     |

Groups with n +4 set-orbits We know that the same numbers we were unable to remove in the earlier sections will reappear. Since for even numbers we need k 0 = 2, the following n 's can no longer be removed using Step 1: n = 18 22 34 42. , , , So we must continue with

$$n = 4, 6, 8, 1 0, 1 2, 1 4, 1 6, 1 8, 2 2, 2 4, 3 4, 4 2.$$

After Step 2 we have only

$$n = 4, 6, 8, 1 0, 1 2.$$

So we must check all subgroups of S 4 , the transitive groups on 6 letters, and the primitive groups on 8 10 12 letters that whose order is divisible by 28 120 495. , , , , We do not recheck the primitive groups on 8 letters divisible by 56.

The table of all groups with s G ( ) = n +4 is listed below.

|   n | G                                  |   | G | | GAP ID   |
|-----|------------------------------------|---------|----------|
|   4 | C 3                                |       3 | 4S4      |
|   4 | S 3                                |       6 | 4T8      |
|   6 | C 3 × S 3                          |      18 | 6T5      |
|   6 | S 4                                |      24 | 6T8      |
|   6 | S 3 × S 3                          |      36 | 6T9      |
|   6 | ( C 3 × C 3 ) /multicloseright C 4 |      36 | 6T10     |
|   6 | C 2 × S 4                          |      48 | 6T11     |
|   6 | ( C 3 × C 3 ) /multicloseright D 8 |      72 | 6T13     |
|  10 | PGL(2 , 9)                         |     720 | 10P4     |
|  10 | PΓL(2 , 9)                         |    1440 | 10P7     |

Groups with n +5 set-orbits From previous sections we have found five groups with n +5 set-orbits. For even n we continue to use k 0 = 2, and for odd n we take k 0 = 3. After Step 1 &amp; 2 we have the same even numbers as in the above section, so n = 4 6 8 10 12. , , , , The odd numbers after Step 1 will be the same as in the n +3 case, but now we must add n = 17 21 33 41. , , , We must apply Step 2 to the odd numbers

$$n = 5, 7, 9, 1 1, 1 3, 1 5, 1 7, 1 9, 2 1, 2 3, 2 5, 3 3, 4 1, 4 3.$$

After applying Step 2 we have

$$n = 4, 5, 6, 7, 8, 9, 1 0, 1 1, 1 2.$$

Note that once again, we handled all the necessary computations for the even n in the previous section. So we must check all subgroups of S 5 , the transitive subgroups of S 7 , and the primitive groups on 9 11 letters whose order is divisible by 36 , , 165 but not 84 330, respectively. , We list all groups with n +5 set-orbits in the table below.

|   n | G                        |   | G | | GAP ID   |
|-----|--------------------------|---------|----------|
|   3 | 1                        |       1 | 3S1      |
|   4 | C 2 × C 2                |       4 | 4S6      |
|   5 | A 4                      |      12 | 5S14     |
|   5 | S 4                      |      24 | 5S17     |
|   6 | C 2 × A 4                |      24 | 6T6      |
|   6 | S 4                      |      24 | 6T7      |
|   7 | C 7 /multicloseright C 3 |      21 | 7P3      |
|   9 | ASL(2 , 3)               |     216 | 9P6      |
|   9 | AGL(2 , 3)               |     432 | 9P7      |
|  10 | M 10                     |     720 | 10P6     |

Remaining Computations We indeed classify all the cases till r = 15 using the same method. The cases of 12 ≤ r ≤ 15 require some additional work. In each of these cases we could check all subgroups of S n ( n ≤ 11) using GAP. Since our computers cannot use GAP to compute all subgroups of S n ( n ≥ 12), we will use Lemmas 2.10 and 2.11 to eliminate non-transitive or imprimitive subgroups of S n . It's important to note that for transitive and primitive subgroups of S n we can still use GAP since GAP's built in library has all primitive groups of degree less than or equal to 4096. We shall discuss the case when r = 12 in detail and then list the results for 13 ≤ r ≤ 15 as the process will be very similar.

In the case r = 12, note that we may check the number of set-orbits of all the subgroups of S n ( n ≤ 11) using GAP, and we can also check all the transitive and primitive subgroups of S n for n not too large. We will discuss how to handle the case when n = 12, and the other possible n values can be checked in a similar way.

Assume the action of group G is not transitive, then the 1-set-orbits will be partitioned into at least 2 orbits. Assume it is partitioned into at least 3 orbits, then s 1 ≥ 3 and by Theorem 2.3, we have s i ≥ 3 for 1 ≤ i ≤ 11. Thus s G ( ) ≥ 3 · 11 + 2 = 35 = 12 + 23, and this is impossible. Then assume the 1-set-orbits is partitioned in two, then G can be a subgroup of S 1 × S 11 , S 2 × S 10 , S 3 × S 9 , S 4 × S 8 , S 5 × S 7 , S 6 × S 6 . By Lemma 2.10 we check that in the corresponding cases, the set-orbits will be at least 24 , 33 40 45 48 49. , , , , In which case the only possibility is a subgroup of S 1 × S 11 , and in this case, G is either S 11 or A 11 .

Assume the action of group G is transitive but not primitive, note that 12 = 2 · 6, 3 · 4, 4 · 3, or 6 · 2, and by applying Lemma 2.11, we see that all the cases will lead to more set-orbits.

Assume the action of group G is transitive and primitive, we use GAP to run through all the possible primitive groups of degree 12 and we see none of them satisfy the requirement.

We list all the results in the next few tables.

Groups with n +6 set-orbits:

|   n | G                        |   | G | | GAP ID   |
|-----|--------------------------|---------|----------|
|   4 | C 2                      |       2 | 4S2      |
|   6 | A 4                      |      12 | 6S31     |
|   6 | C 5 /multicloseright C 4 |      20 | 6S38     |
|   6 | A 5                      |      60 | 6S50     |
|   6 | S 5                      |     120 | 6S53     |

Groups with n +7 set-orbits:

|   n | G                                                                                                                      |   | G | | GAP ID   |
|-----|------------------------------------------------------------------------------------------------------------------------|---------|----------|
|   5 | C 4                                                                                                                    |       4 | 5S6      |
|   5 | S 3                                                                                                                    |       6 | 5S10     |
|   5 | C 6                                                                                                                    |       6 | 5S11     |
|   5 | D 8                                                                                                                    |       8 | 5S12     |
|   5 | D 12                                                                                                                   |      12 | 5S15     |
|   6 | D 12                                                                                                                   |      12 | 6S33     |
|   7 | S 5                                                                                                                    |     120 | 7S89     |
|   7 | A 6                                                                                                                    |     360 | 7S93     |
|   7 | S 6                                                                                                                    |     720 | 7S94     |
|   8 | ((( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 2 ) /multicloseright C 2 ) /multicloseright C 3                         |     192 | 8T38     |
|   8 | ((( C 2 × C 2 × C 2 ) /multicloseright ( C 2 × C 2 )) /multicloseright C 3 ) /multicloseright C 2                      |     192 | 8T40     |
|   8 | ((( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 3 ) /multicloseright C 2 ) /multicloseright C 3                         |     288 | 8T42     |
|   8 | (((( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 2 ) /multicloseright C 2 ) /multicloseright C 3 ) /multicloseright C 2 |     384 | 8T44     |
|   8 | (( A 4 × A 4 ) /multicloseright C 2 ) /multicloseright C 2                                                             |     576 | 8T45     |
|   8 | ( A 4 × A 4 ) /multicloseright C 4                                                                                     |     576 | 8T46     |
|   8 | ( S 4 × S 4 ) /multicloseright C 2                                                                                     |    1152 | 8T47     |
|   9 | ( C 3 × C 3 ) /multicloseright C 8                                                                                     |      72 | 9T15     |
|   9 | ( C 3 × C 3 ) /multicloseright QD 16                                                                                   |     144 | 9T19     |
|  12 | M 11                                                                                                                   |    7920 | 12P1     |

## Groups with n +8 set-orbits:

|   n | G                                                                                                 |   | G | | GAP ID   |
|-----|---------------------------------------------------------------------------------------------------|---------|----------|
|   4 | C 2                                                                                               |       2 | 4S3      |
|   6 | C 6                                                                                               |       6 | 6S17     |
|   8 | (( C 2 × C 2 × C 2 ) /multicloseright ( C 2 × C 2 )) /multicloseright C 3                         |      96 | 8S242    |
|   8 | (( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 2 ) /multicloseright C 3                            |      96 | 8S247    |
|   8 | ((( C 2 × C 2 × C 2 ) /multicloseright ( C 2 × C 2 )) /multicloseright C 3 ) /multicloseright C 2 |     192 | 8S268    |
|   8 | ((( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 2 ) /multicloseright C 3 ) /multicloseright C 2    |     192 | 8S270    |
|   8 | A 7                                                                                               |    2520 | 8S293    |
|   8 | S 7                                                                                               |    5040 | 8S294    |
|  12 | PSL(2 , 11) /multicloseright C 2                                                                  |    1320 | 12T218   |

Groups with n +9 set-orbits:

|   n | G                                                                      |   | G | | GAP ID   |
|-----|------------------------------------------------------------------------|---------|----------|
|   5 | C 2 × C 2                                                              |       4 | 5S5      |
|   6 | C 2 × A 4                                                              |      24 | 6S40     |
|   6 | S 4                                                                    |      24 | 6S41     |
|   6 | C 2 × S 4                                                              |      48 | 6S49     |
|   7 | A 5                                                                    |      60 | 7S81     |
|   8 | (( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 3 ) /multicloseright C 2 |      96 | 8S240    |
|   9 | ( C 3 × C 3 ) /multicloseright Q 8                                     |      72 | 9S370    |
|   9 | A 8                                                                    |   20160 | 9S551    |
|   9 | S 8                                                                    |   40320 | 9S552    |
|  10 | S 6                                                                    |     720 | 10T32    |

## Groups with n +10 set-orbits:

|   n | G                                  |   | G | | GAP ID   |
|-----|------------------------------------|---------|----------|
|   6 | C 5                                |       5 | 6S14     |
|   6 | S 3                                |       6 | 6S16     |
|   6 | C 3 × C 3                          |       9 | 6S28     |
|   6 | D 10                               |      10 | 6S29     |
|   6 | ( C 3 × C 3 ) /multicloseright C 2 |      18 | 6S35     |
|   6 | C 3 × S 3                          |      18 | 6S37     |
|   6 | S 3 × S 3                          |      36 | 6S45     |
|   8 | GL(2 , 3)                          |      48 | 8S216    |
|  10 | A 6                                |     360 | 10S1396  |
|  10 | PSL(2 , 8)                         |     504 | 10S1448  |
|  10 | PSL(2 , 8) /multicloseright C 3    |    1512 | 10S1539  |
|  10 | A 9                                |  181440 | 10S1590  |
|  10 | S 9                                |  362880 | 10S1591  |
|  12 | PSL(2 , 11)                        |     660 | 12T179   |

## Groups with n +11 set-orbits:

|   n | G                                                                                                                         |   | G | | GAP ID   |
|-----|---------------------------------------------------------------------------------------------------------------------------|---------|----------|
|   5 | C 3                                                                                                                       |       3 | 5S4      |
|   5 | S 3                                                                                                                       |       6 | 5S9      |
|   7 | D 14                                                                                                                      |      14 | 7S48     |
|   7 | C 2 × ( C 5 /multicloseright C 4 )                                                                                        |      40 | 7S75     |
|   7 | S 5                                                                                                                       |     120 | 7S87     |
|   7 | C 2 × A 5                                                                                                                 |     120 | 7S88     |
|   7 | C 2 × S 5                                                                                                                 |     240 | 7S92     |
|   8 | SL(2 , 3)                                                                                                                 |      24 | 8S154    |
|   9 | ( C 2 × C 2 × C 2 ) /multicloseright C 7                                                                                  |      56 | 9S355    |
|   9 | (( C 3 × C 3 × C 3 ) /multicloseright C 3 ) /multicloseright C 2                                                          |     162 | 9S457    |
|   9 | (( C 3 × C 3 × C 3 ) /multicloseright C 3 ) /multicloseright C 2                                                          |     162 | 9S458    |
|   9 | ( C 2 × C 2 × C 2 ) /multicloseright ( C 7 /multicloseright C 3 )                                                         |     168 | 9S462    |
|   9 | (( C 3 × C 3 × C 3 ) /multicloseright C 3 ) /multicloseright ( C 2 × C 2 )                                                |     324 | 9S497    |
|   9 | PSL(3 , 2) /multicloseright C 2                                                                                           |     336 | 9S499    |
|   9 | ((( C 3 × C 3 × C 3 ) /multicloseright ( C 2 × C 2 )) /multicloseright C 3 ) /multicloseright C 2                         |     648 | 9S522    |
|   9 | ((( C 3 × C 3 × C 3 ) /multicloseright ( C 2 × C 2 )) /multicloseright C 3 ) /multicloseright C 2                         |     648 | 9S524    |
|   9 | (((( C 3 × C 3 × C 3 ) /multicloseright ( C 2 × C 2 )) /multicloseright C 3 ) /multicloseright C 2 ) /multicloseright C 2 |    1296 | 9S534    |
|   9 | ( C 2 × C 2 × C 2 ) /multicloseright PSL(3 , 2)                                                                           |    1344 | 9S535    |
|  10 | ( C 5 × C 5 ) /multicloseright (( C 4 × C 4 ) /multicloseright C 2 )                                                      |     800 | 10S1496  |
|  10 | ( C 2 × C 2 × C 2 × C 2 ) /multicloseright S 5                                                                            |    1920 | 10S1542  |
|  10 | C 2 × (( C 2 × C 2 × C 2 × C 2 ) /multicloseright A 5 )                                                                   |    1920 | 10S1543  |
|  10 | C 2 × (( C 2 × C 2 × C 2 × C 2 ) /multicloseright S 5 )                                                                   |    3840 | 10S1561  |
|  10 | ( A 5 × A 5 ) /multicloseright C 2                                                                                        |    7200 | 10S1569  |
|  10 | ( A 5 × A 5 ) /multicloseright ( C 2 × C 2 )                                                                              |   14400 | 10S1576  |
|  10 | ( A 5 × A 5 ) /multicloseright C 4                                                                                        |   14400 | 10S1577  |
|  10 | ( A 5 × A 5 ) /multicloseright D 8                                                                                        |   28800 | 10S1584  |
|  11 | A 10                                                                                                                      | 1814400 | 11S3091  |
|  11 | S 10                                                                                                                      | 3628800 | 11S3092  |

Groups with n +12 set-orbits:

|   n | G                                                           | | G |   | GAP ID   |
|-----|-------------------------------------------------------------|---------|----------|
|   4 | 1                                                           | 1       | 4S1      |
|   6 | C 4 × C 2                                                   | 8       | 6S24     |
|   6 | D 8                                                         | 8       | 6S27     |
|   6 | D 8 × C 2                                                   | 16      | 6S34     |
|   8 | C 7 /multicloseright C 6                                    | 42      | 8S196    |
|   8 | PSL(3 , 2)                                                  | 168     | 8S264    |
|  10 | ( C 5 × C 5 ) /multicloseright C 8                          | 200     | 10S1311  |
|  10 | ( C 5 × C 5 ) /multicloseright ( C 8 /multicloseright C 2 ) | 400     | 10S1418  |
|  10 | ( C 2 × C 2 × C 2 × C 2 ) /multicloseright A 5              | 960     | 10S1504  |
|  10 | ( C 2 × C 2 × C 2 × C 2 ) /multicloseright S 5              | 1920    | 10S1541  |
|  12 | A 11                                                        | 11!/2   |          |
|  12 | S 11                                                        | 11!     |          |

## Groups with n +13 set-orbits:

|   n | G                                                                | | G |   | GAP ID   |
|-----|------------------------------------------------------------------|---------|----------|
|   5 | C 2 × C 2                                                        | 4       | 5S7      |
|   6 | D 8                                                              | 8       | 6S26     |
|   7 | C 7                                                              | 7       | 7S23     |
|   7 | C 3 × S 3                                                        | 18      | 7S51     |
|   7 | C 5 /multicloseright C 4                                         | 20      | 7S53     |
|   7 | S 4                                                              | 24      | 7S63     |
|   7 | C 3 × A 4                                                        | 36      | 7S71     |
|   7 | ( C 3 × C 3 ) /multicloseright C 4                               | 36      | 7S73     |
|   7 | S 3 × S 3                                                        | 36      | 7S74     |
|   7 | C 2 × S 4                                                        | 48      | 7S78     |
|   7 | A 4 × S 3                                                        | 72      | 7S82     |
|   7 | ( C 3 × A 4 ) /multicloseright C 2                               | 72      | 7S83     |
|   7 | C 3 × S 4                                                        | 72      | 7S84     |
|   7 | ( S 3 × S 3 ) /multicloseright C 2                               | 72      | 7S85     |
|   7 | S 4 × S 3                                                        | 144     | 7S90     |
|   8 | ( C 4 × C 4 ) /multicloseright C 2                               | 32      | 8S181    |
|   8 | (( C 4 × C 4 ) /multicloseright C 2 ) /multicloseright C 2       | 64      | 8S226    |
|   8 | (( C 4 × C 4 × C 4 ) /multicloseright C 4 ) /multicloseright C 2 | 64      | 8S227    |
|   8 | (( C 4 × C 4 × C 4 ) /multicloseright C 4 ) /multicloseright C 2 | 64      | 8S228    |
|   8 | ( D 8 × D 8 ) /multicloseright C 2                               | 128     | 8S259    |
|   8 | C 2 × S 5                                                        | 240     | 8S272    |
|   8 | C 2 × A 6                                                        | 720     | 8S286    |
|   8 | S 6                                                              | 720     | 8S287    |
|   8 | C 2 × S 6                                                        | 1440    | 8S292    |
|   9 | C 9 /multicloseright C 6                                         | 54      | 9S354    |
|   9 | PSL(3 , 2)                                                       | 168     | 9S460    |
|  11 | PSL(2 , 11)                                                      | 660     | 11S2754  |
|  13 | A 12                                                             | 12!/2   |          |
|  13 | S 12                                                             | 12!     |          |

## Groups with n +14 set-orbits:

|   n | G                                                                      |   | G | | GAP ID   |
|-----|------------------------------------------------------------------------|---------|----------|
|   6 | S 3                                                                    |       6 | 6S19     |
|   6 | A 4                                                                    |      12 | 6S30     |
|   6 | S 4                                                                    |      24 | 6S44     |
|   8 | C 2 × A 4                                                              |      24 | 8S157    |
|   8 | ( C 2 × C 2 × C 2 ) /multicloseright C 4                               |      32 | 8S176    |
|   8 | C 2 × S 4                                                              |      48 | 8S214    |
|   8 | (( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 2 ) /multicloseright C 2 |      64 | 8S229    |
|   8 | S 5                                                                    |     120 | 8S257    |
|  10 | ( C 5 × C 5 ) /multicloseright D 8                                     |     200 | 10S1305  |
|  10 | ( C 5 × C 5 ) /multicloseright Q 8                                     |     200 | 10S1307  |

|   10 | ( C 5 × C 5 ) /multicloseright ( C 4 × C 2 )                                    | 200     | 10S1309   |
|------|---------------------------------------------------------------------------------|---------|-----------|
|   10 | (( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 5 ) /multicloseright C 4          | 320     | 10S1386   |
|   10 | ( C 5 × C 5 ) /multicloseright (( C 4 × C 2 ) /multicloseright C 2 )            | 400     | 10S1419   |
|   10 | C 2 × ((( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 5 ) /multicloseright C 4 ) | 640     | 10S1472   |
|   14 | A 13                                                                            | 13! / 2 |           |
|   14 | S 13                                                                            | 13!     |           |

Groups with n +15 set-orbits

|   n | G                                                                        | | G |   | GAP ID   |
|-----|--------------------------------------------------------------------------|---------|----------|
|   5 | C 2                                                                      | 2       | 5S3      |
|   6 | C 2 × C 2 × C 2                                                          | 8       | 6S22     |
|   6 | D 8                                                                      | 8       | 6S23     |
|   7 | C 2 × A 4                                                                | 24      | 7S60     |
|   7 | S 4                                                                      | 24      | 7S67     |
|   7 | S 4                                                                      | 24      | 7S70     |
|   8 | S 4                                                                      | 24      | 8S158    |
|   9 | ( C 3 × C 3 ) /multicloseright C 6                                       | 54      | 9S352    |
|   9 | ( C 3 × C 3 × C 3 ) /multicloseright C 3                                 | 81      | 9S401    |
|   9 | (( C 3 × C 3 ) /multicloseright C 3 ) /multicloseright ( C 2 × C 2 )     | 108     | 9S425    |
|   9 | (( C 3 × C 3 × C 3 ) /multicloseright C 3 ) /multicloseright C 2         | 162     | 9S459    |
|   9 | (( C 3 × C 3 × C 3 ) /multicloseright ( C 2 × C 2 ) /multicloseright C 3 | 324     | 9S496    |
|   9 | ( S 3 × S 3 × S 3 ) /multicloseright C 3                                 | 648     | 9S523    |
|   9 | C 2 × A 7                                                                | 5040    | 9S548    |
|   9 | S 7                                                                      | 5040    | 9S549    |
|   9 | C 2 × S 7                                                                | 10080   | 9S550    |
|  10 | (( C 2 × C 2 × C 2 × C 2 ) /multicloseright C 5 ) /multicloseright C 4   | 320     | 10S1385  |
|  13 | M 12                                                                     | 95040   | /star    |
|  15 | A 14                                                                     | 14! / 2 |          |
|  15 | S 14                                                                     | 14!     |          |

- /star Here M 12 acts transitively on 12 elements (with 14 set-orbits in this action) and trivially on the other element.

## 5. Closing Remarks

Now that a general method is developed for calculating all groups with n + r orbits where r is not too large. The GAP code used for the calculation is available at [8]. We have successfully classified all the cases for r ≤ 15. We remark that by far the most computationally taxing step is finding all the subgroups of S n . If one could come up with a method to circumvent this, the classification could go much farther. Another computationally taxing step is calculating how many set-orbits a large group has. If both of these steps can be improved upon, the classification could go further.

## Acknowledgements

This research was conducted under NSF-REU grant DMS-1757233 by Betz, Chao-Haft, Gong, and Ter-Saakov during the Summer of 2019 under the supervision of Keller and Yang. The authors gratefully acknowledge the financial support of NSF and also thank Texas State University for providing a great working environment and support. Keller and Yang were also partially supported by grants from the Simons Foundation (#280770 to Thomas M. Keller, #499532 to Yong Yang). The authors are grateful to the referee for the valuable suggestions which greatly improved the manuscript.

## References

- [1] L. Babai and L. Pyber, Permutation groups without exponentially many orbits on the power set, J. Comb. Theory A 66 (1998), 160-168.
- [2] R.A. Beaumont and R.P. Peterson, Set-transitive permutation groups, Canad. J. Math. 7 (1955), 35-42.
- [3] R. Breusch, Zur Verallgemeinerung des Bertrandschen Postulates, das zwischen x and 2 x stets Primzahlen liegen, [To generalize Bertrand's postulate, which is always a prime between x and 2 x ] Math. Z. 34 (1932), 505-526.
- [4] W. Burnside, Theory of Groups , Cambridge, 1897.
- [5] P. J. Cameron, Regular orbits of permutation groups on the power set, Discrete Math. 62 (1986), 307-309.
- [6] The GAP Group, GAP -Groups, Algorithms, and Programming, Version 4.11.0; 2020. (https://www.gap-system.org)
- [7] https://people.maths.bris.ac.uk/ ∼ matyd/GroupNames/T31.html.
- [8] https://www.math.txstate.edu/research-conferences/summerreu/yang documents.html.
- [9] W.M. Kantor, k -homogeneous groups, Math. Z. 124 (1972), 261-265.
- [10] D. Livingstone and A. Wagner, Transitivity of finite permutation groups on unordered sets, Math. Z. 90 (1965), 393-403.
- [11] G.A. Miller, Collected works , vols 1 and 3, Urbana, 1935 and 1946.
- [12] O.Morgenstern and J. von Neumann, Theory of Games and Economic Behavior , Princeton, Univ. Press, Princeton, NJ, 1947.
- [13] Y. Yang, Solvable permutation groups and orbits on power sets, Comm. Algebra 42 (2014), 2813-2820.

Department of Mathematics, Le Moyne College, 1419 Salt Springs Road, Syracuse, NY 13214 Email address : betzas@lemoyne.edu

Department of Mathematics, Harvey Mudd College, 340 East Foothill Boulevard, Claremont, CA 91711

Email address : mchaohaft@g.hmc.edu

Department of Mathematics, University of Notre Dame, 255 Hurley, Notre Dame, IN 46556 Email address : tgong@nd.edu

Department of Mathematics, Texas State University, 601 University Drive, San Marcos, TX 78666

Email address : keller@txstate.edu

Department of Mathematics &amp; Statistics, Boston University, 111 Cummington Mall, Boston, MA 02215

Email address : antter@bu.edu

Department of Mathematics, Texas State University, 601 University Drive, San Marcos, TX 78666

Email address : yang@txstate.edu
Alexander Betz Max Chao-Haft Ting Gong Thomas Michael Keller Anthony Ter-Saakov Yong Yang
Finite Permutation Groups with Few Orbits Under the Action on the Power Set
We study the orbits under the natural action of a permutation group $G
\subseteq S_n$ on the powerset $\mathscr{P}(\{1, \dots , n\})$. The permutation
groups having exactly $n+1$ orbits on the powerset can be characterized as
set-transitive groups and were fully classified in \cite{BP55}. In this paper,
we establish a general method that allows one to classify the permutation
groups with $n+r$ set-orbits for a given $r$, and apply it to integers $2 \leq
r \leq 15$ using the computer algebra system GAP.