Straight line program

Informal Definition

Let G be a finite group and let S be a subset of G. A sequence L = (g₁,…,g_m) of elements of G is a straight-line program over S if each g_i can be obtained by one of the following three rules:

1. g_i ∈ S
2. g_i = g_j ⋅ g_k for some j,k < i
3. g_i = g−1
   j for some j < i.

The straight-line cost c(g|S) of an element g ∈ G is the length of a shortest straight-line program over S computing g. The cost is infinite if g is not in the subgroup generated by S.

A straight-line program is similar to a derivation in predicate logic. The elements of S correspond to axioms and the group operations correspond to the rules of inference.

Formal definition

Let G be a finite group and let S be a subset of G. A straight-line program of length m over S computing some g ∈ G is a sequence of expressions (w₁,…,w_m) such that for each i, w_i is a symbol for some element of S, or w_i = (w_j,-1) for some j < i, or w_i = (w_j,w_k) for some j,k < i, such that w_m takes upon the value g when evaluated in G in the obvious manner.

The original definition appearing in requires that G =〈S〉. The definition presented above is a common generalisation of this.

From a computational perspective, the formal definition of a straight-line program has some advantages. Firstly, a sequence of abstract expressions requires less memory than terms over the generating set. Secondly, it allows straight-line programs to be constructed in one representation of G and evaluated in another. This is an important feature of some algorithms.

Examples

The dihedral group D₁₂ is the group of symmetries of a hexagon. It can be generated by a 60 degree rotation ρ and one reflection λ. The leftmost column of the following is a straight-line program for λρ³:

In S₆, the group of permutations on six letters, we can take α=(1 2 3 4 5 6) and β=(1 2) as generators. The leftmost column here is an example of a straight-line program to compute (1 2 3)(4 5 6):

Applications

Short descriptions of finite groups. Straight-line programs can be used to study compression of finite groups via first-order logic. They provide a tool to construct "short" sentences describing G (i.e. much shorter than |G|). In more detail, SLPs are used to prove that every finite simple group has a first-order description of length O(log|G|), and every finite group G has a first-order description of length O(log³|G|).

Straight-line programs computing generating sets for maximal subgroups of finite simple groups. The online ATLAS of Finite Group Representations provides abstract straight-line programs for computing generating sets of maximal subgroups for many finite simple groups.

Example: The group Sz(32), belonging to the infinite family of Suzuki groups, has rank 2 via generators a and b, where a has order 2, b has order 4, ab has order 5, ab² has order 25 and abab²ab³ has order 25. The following is a straight-line program that computes a generating set for a maximal subgroup E₃₂ ⋅ E₃₂ ⋊ C₃₁. This straight-line program can be found in the online ATLAS of Finite Group Representations.

Reachability theorem

The reachability theorem states that, given a finite group G generated by S, each g ∈ G has a maximum cost of (1 + lg|G|)². This can be understood as a bound on how hard it is to generate a group element from the generators.

Here the function lg(x) is an integer-valued version of the logarithm function: for k≥1 let lg(k) = max{r : 2^r ≤ k}.

The idea of the proof is to construct a set Z = {z₁,…,z_s} that will work as a new generating set (s will be defined during the process). It is usually larger than S, but any element of G can be expressed as a word of length at most 2|Z| over Z. The set Z is constructed by inductively defining an increasing sequence of sets K(i).

Let K(i) = {z₁^α₁ ⋅ z₂^α₂ ⋅ … ⋅ z_i^α_i : α_j ∈ {0,1}}, where z_i is the group element added to Z at the i-th step. Let c(i) denote the length of a shortest straight-line program that contains Z(i) = {z₁,…,z_i}. Let K(0) = {1_G} and c(0)=0. We define the set Z recursively:

By this process, Z is defined in a way so that any g ∈ G can be written as an element of K(i)⁻¹K(i), effectively making it easier to generate from Z.

We now need to verify the following claim to ensure that the process terminates within lg(|G|) many steps:

Claim 1. If i < s then |K(i+1)| = 2|K(i)|.

Proof. It is immediate that |K(i+1)| ≤ 2|K(i)|. Now suppose for a contradiction that |K(i+1)| < 2|K(i)|. By the pigeonhole principle there are k₁,k₂ ∈ K(i+1) with k₁ = z₁^α₁ ⋅ z₂^α₂ ⋅ … ⋅ z_i+1^α_i+1 = z₁^β₁ ⋅ z₂^β₂ ⋅ … ⋅ z_i+1^β_i+1 = k₂ for some α_j,β_j ∈ {0,1}. Let r be the largest integer such that α_r ≠ β_r. Assume WLOG that α_r = 1. It follows that z_r = z_p^−α_p ⋅ z_p-1^−α_p-1 ⋅ … ⋅ z₁^−α₁ ⋅ z₁^β₁ ⋅ z₂^β₂ ⋅ … ⋅ z_q^β_q, with p,q < r. Hence z_r ∈ K(r-1)⁻¹K(r − 1), a contradiction.

The next claim is used to show that the cost of every group element is within the required bound.

Claim 2. c(i) ≤ i ² − i.

Proof. Since c(0)=0 it suffices to show that c(i+1) - c(i) ≤ 2i. The Cayley graph of G is connected and if i < s, K(i)⁻¹K(i) ≠ G, then there is an element of the form g₁ ⋅ g₂ ∈ G \ K(i)⁻¹K(i) with g₁ ∈ K(i)⁻¹K(i) and g₂ ∈ S.

It takes at most 2i steps to generate g₁ ∈ K(i)⁻¹K(i). There is no point in generating the element of maximum length, since it is the identity. Hence 2i  −1 steps suffice. To generate g₁ ⋅ g₂ ∈ G\K(i)⁻¹K(i), 2i steps are sufficient.

We now finish the theorem. Since K(s)⁻¹K(s) = G, any g ∈ G can be written in the form k−1
1 ⋅ k₂ with k−1
1,k₂ ∈ K(s). By Corollary 2, we need at most s² − s steps to generate Z(s) = Z, and no more than 2s − 1 steps to generate g from Z(s).

Therefore c(g|S) ≤ s² +  s − 1 ≤ lg²|G|  + lg|G| − 1 ≤ (1 + lg|G|)².