{'fraction_non_alphanumeric': 0.049444318439555456, 'fraction_numerical': 0.0052166024041732815, 'mean_word_length': 3.840285400658617, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Some measures of finite groups related to permutation bases

I define three"measures"of the complicatedness of a finite group in terms of bases in permutation representations of the group, and consider their relationships to other measures.


Introduction and history
The purpose of this paper is to define and investigate three functions which in some sense "measure" the complicatedness of a finite group. The functions are defined in minimax fashion in terms of base size in permutation representations of the group. The values of these measures for symmetric groups will be given.
I begin with a brief account of some similar measures, which are related to the new measures in various ways.
If f is a function from (isomorphism classes of) finite groups to natural numbers, let f ′ be the function defined by f ′ (G) = max{f (H) : H ≤ G}.
The function f ′ is necessarily monotonic: that is, if H ≤ G, then f ′ (H) ≤ f ′ (G). Conversely, if f is monotonic, then f = f ′ ; so every monotonic function is of this form.
An obvious function is d(G), the minimum number of generators of G. Now is is well-known that d(S n ) = 2; so this invariant is not very sensitive.
However, d ′ is more interesting. Babai [1] raised the question of determining d ′ (S n ). The motivation was computational group theory: if we are given an arbitrary (possibly very large) subset of S n , and want to know the size of the subgroup it generates, then we know that we can replace the given set by a set of size at most d ′ (S n ) generating the same subgroup. This suggests that we also want, if possible, an algorithmic method for finding such a minimum-size generating set.
Babai considered the related function l, where l(G) is the length of the longest chain of subgroups of G. Since, obviously, d(G) ≤ l(G), and l is monotonic, (that is, l(G) = l ′ (G)), we see that d ′ (G) ≤ l(G) for any group G. Babai proved that The exact value of S n was established by Cameron, Solomon and Turull [3]: where b(n) is the number of 1s in the base 2 representation of n. Jerrum [5] showed that d ′ (S n ) ≤ n − 1. His proof was algorithmic: given an arbitrary set of permutations, a set of at most n − 1 permutations generating the same subgroup can be found efficiently.
The exact value of d ′ (S n ) was established by McIver and Neumann [6]: Whiston [7] considered the invariant µ(G), the maximal size of an independent generating set for G, where a set is independent if none of its elements lies in the subgroup generated by the others. Since any independent set is an independent generating set for the subgroup it generates, µ ′ (G) is the maximum size of an independent subset of G. The parameter µ(G) appears in the work of Diaconis and Saloff-Coste [4] in the rate of convergence of the product replacement algorithm for finding a random element of a finite group.
Whiston showed that However, he observed that there are groups with µ ′ (G) > µ(G). Cameron and Cara [2] found all independent generating sets of size n − 1 in S n .

The base measures
Let G be a permutation group on Ω. A base for G is a sequence of points of Ω whose pointwise stabiliser is the identity. (Treating a base as a sequence rather than a set fits in with the use of bases in computational group theory, where the elements of a base are chosen in order.) A base is called irredundant if no point is fixed by the pointwise stabiliser of its predecessors; it is minimal if no point is fixed by the pointwise stabiliser of the other points in the sequence.
It is computationally a simple matter to choose an irredundant base; simply choose each base point to be a point moved by the stabiliser of the points previously chosen. It is less straightforward to choose a minimal base. Note that a base is minimal if and only if every re-ordering of it is irredundant. Now, given a finite group G, we define three numbers b 1 (G), b 2 (G), b 3 (G) as follows. In each case, the maximum is taken over all permutation representations of G (not necessarily faithful).
• b 1 (G) is the maximum, over all representations, of the maximum size of an irredundant base; • b 2 (G) is the maximum, over all representations, of the maximum size of a minimal base; • b 3 (G) is the maximum, over all representations, of the minimum base size.
Proof Given an irredundant base of size b 1 (G), the stabilisers of its initial subsequences form a properly descending chain of subgroups of length b 1 (G).
be a chain of subgroups of length l = l(G). Consider the action on the union of the coset spaces of the subgroups G i , and let α i be the point G i of the coset space (G : G i ). Then (α 1 , . . . , α l ) is an irredundant base. So l(G) ≤ b 1 (G).
We will see in the next section a connection between b 2 (G) and µ(G). I know much less about b 3 (G). One observation is the following: Proof Given any permutation representation of G, we can discard fixed points, so that G acts faithfully on each orbit. Now let b * 3 (G) be the maximum of the minimum base sizes over all transitive representations of G, and suppose that there is an intransitive representation with minimum base size greater than b * 3 (G). Now there exist at most b * 3 (G) points in an orbit whose stabiliser acts trivially on that orbit, and hence is trivial (since the action on the orbit is faithful), contrary to assumption. Now let b + 3 (G) be the maximum of the minimum base sizes over all primitive representations of G, and suppose that there is a transitive but imprimitive representation with base size greater than b + 3 (G). There are at most b + 3 (G) maximal blocks whose stabiliser acts trivially on the block system, and hence is trivial (since again the action is faithful), contrary to assumption.
This proposition does not hold for b 2 (G). For the group G = PSL(2, 7) ∼ = PSL (3, 2), a minimal base in any transitive representation has size at most 3. However, in the action on the points and lines of the projective plane of order 2, there is a minimal base of size 4, consisting of two points and two lines such that each point lies on one of the lines and each line passes through one of the points.

Boolean semilattices
The subgroups of the group G form a lattice L(G), with the operations H ∧ K = H ∩ K and H ∨ K = H, K . A meet-semilattice of L(G) is a collection of subgroups containing G and closed under ∧, while a joinsemilattice is a collection of subgroups containing the trivial group 1 and closed under ∨.
The Boolean lattice B(n) is the lattice of subsets of an n-set.
with the convention that K ∅ = G. We claim that all the subgroups K i are distinct. Suppose that two of them are equal, say K I = K J . By interchanging I and J if necessary, we may assume that there exists i ∈ I \ J. But then H i ≤ K J while H i ≤ K I , a contradiction. Now it is clear that K J ∩K J = K I∩J , so we have an embedding of B(n) as a meet-semilattice (where we have reversed the order-isomoprhism to simplify the notation).
The reverse implication is proved by an almost identical argument.
Note that the conditions of the proposition are not equivalent to embeddability of B(n) as a lattice. For example, if G is the quaternion group of order 8, then B(2) is embeddable as both a meet-semilattice and a joinsemilattice but not as a lattice. Conversely, suppose that we have a join-semilattice given by the subgroups H I for I ⊆ N. Choose g i / ∈ H N \{i} . Then clearly the elements g 1 , . . . , g n are independent.
(b) Let (α 1 , . . . , α n ) be a minimal base for G in some permutation representation. Let K i be the stabiliser of α i , and K I = i∈I K i for I ⊆ N = {1, . . . , n}. Then the subgroups K I form a meet-semilattice of G. The subgroupK N is the kernel of the permutation representation (by definition of a base), and so is a normal subgroup of G.
Conversely, suppose that we have a meet-semilattice given by the subgroups K I for I ⊆ N, such that K N is a normal subgroup fo G; the notation is chosen so that K I ∩ K J = K I∪J . Now consider the permutation representation on the union of the coset spaces of the subgroups K i = K {i} . Since the intersection of all these subgroups is normal, it is the kernel of the representation, and the points corresponding to the subgroups K i form a base. It is minimal, since the intersection of fewer than n of the subgroups is not equal to K N . I do not know a group where the inequality is strict. Resolving this is equivalent to the following question. Let n be maximal such that B(n) is embeddable as a meet-semilattice of L(G). Is there an embedding of B(n) for which the minimal element is normal?
Proof We have wwhere the first inequality holds because any base in the natural representation has size n − 1; the second is trivial; the third comes from the preceding Corollary; and the equality is Whiston's theorem.