Straight-line program

Template:Harryalerta In mathematics, more specifically in computational algebra, a straight-line program (SLP) for a finite group G =⟨S⟩ is a finite sequence L of elements of G such that every element of L belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses.

Intuitively, an SLP computing some g ∈ G is an efficient way of storing g as a group word over S; observe that if g is constructed in i steps , the word length of g may be exponential in i, but the length of the corresponding SLP is linear in i. Evidently, this has important applications in computational group theory (CGT).

Straight-line programs were introduced by Babai and Szemerédi in 1984 as a tool for studying the computational complexity of certain matrix group properties. Babai and Szemerédi prove that every element of a finite group G has an SLP of length O(log²|G|) in every generating set.

The constructive membership problem, for which an efficient solution is crucial to many group-theoretic algorithms, can be stated in terms of SLPs as follows. Given a finite group G =⟨S⟩and g ∈ G, find a straight-line program computing g over S. The constructive membership problem is often studied in the setting of black box groups. In a black box group, the elements are encoded by bit strings of a fixed length. Three oracles are provided for the group-theoretic functions of multiplication, inversion, and checking for equality with the identity. A black box algorithm is one which uses only these oracles. Hence, straight-line programs for black box groups are black box algorithms. A major advantage of black box algorithms is that they require no specific characteristics of the representations in which the input groups are given.

Explicit straight-line programs are given for a wealth of finite simple groups in the online ATLAS of Finite Groups, providing a valuable resource for researchers in CGT.

Definition

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) reaching (or 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. Namely, the evaluated value of w_i is itself when w_i is a symbol from S; the evaluated value of (w_j,-1) is the inverse of the evaluated value of w_j; the evaluated value of (w_j,w_k) is the product of the evaluated values of w_j and w_k.

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

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 $\cdot$ g_k for some j,k < i
3. g_i = g_j^-1 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.

From a computational perspective, the formal definition of a straight-line program as a sequence of expressions requires less memory and also allows straight-line programs to be constructed in one representation of G and evaluated in another, which is an important feature of some algorithms.

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. Observe that if g is given by a word of length n in S, then there is a straight line program of length at most n+|S| for g.

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 following is a straight-line program for λρ³:

1. λ
2. ρ
3. ρ²
4. ρ³
5. λρ³

1. λ is a generator.
2. ρ is a generator.
3. Second rule: (2).(2)
4. Second rule: (3).(2)
5. Second rule: (1).(4)

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

1. α
2. β
3. α²
4. α²β
5. α²βα
6. α²βαβ
7. α²βαβα²βαβ

1. (1 2 3 4 5 6)
2. (1 2)
3. (1 3 5)(2 4 6)
4. (1 3 5 2 4 6)
5. (1 4)(2 5 3 6)
6. (1 4 2 5 3 6)
7. (1 2 3)(4 5 6)

1. α is a generator
2. β is a generator
3. Second rule: (1).(1)
4. Second rule: (3).(2)
5. Second rule: (4).(1)
6. Second rule: (5).(2)
7. Second rule: (6).(6)

Applications

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.

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 group G has a first-order description of length O(log³|G|), and every finite simple group has a first-order description of length O(log|G|).

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₃₂$\cdot$E₃₂$\rtimes$C₃₁. This straight-line program can be found in the online ATLAS of Finite Group Representations.

1. a
2. b
3. ab
4. abb
5. ababb
6. ababbb
7. (abb)¹⁸
8. (abb)^-18
9. (abb)^-18b
10. (abb)^-18b(abb)¹⁸
11. (ababb)¹⁴
12. (ababb)^-14
13. (ababb)^-14ababbb
14. (ababb)^-14ababbb(ababb)¹⁴

1. a is a generator.
2. b is a generator.
3. Second rule: (1).(2)
4. Second rule: (3).(2)
5. Second rule: (3).(4)
6. Second rule: (5).(2)
7. Second rule iterated: (4) multiplied 18 times
8. Third rule: (7) inverse
9. Second rule: (8).(2)
10. Second rule: (9).(7)
11. Second rule iterated: (5) multiplied 14 times
12. Third rule: (11) inverse
13. Second rule: (12).(6)
14. Second rule: (13).(11)

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}.

Proof

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₁^α₁$\cdot$z₂^α₂$\cdot$…$\cdot$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:

• If K(i)^-1K(i) = G, declare s to take upon the value i and stop.
• Else, choose some z_i+1 ∈ G\K(i)^-1K(i) (which is non-empty) that minimises the "cost increase" c(i+1) - c(i).

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

We now need to prove two claims to guarantee the length of the process:

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₁^α₁$\cdot$z₂^α₂$\cdot$…$\cdot$z_i+1^α_i+1 = z₁^β₁$\cdot$z₂^β₂$\cdot$…$\cdot$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$\cdot$z_p-1^-α_p-1$\cdot$…$\cdot$z₁^-α₁$\cdot$z₁^β₁$\cdot$z₂^β₂$\cdot$…$\cdot$z_q^β_q, with p,q < r. Hence z_r ∈ K(r-1)^-1K(r-1), a contradiction.

Corollary 1. s ≤ lg|G|.

Claim 2. c(i+1) - c(i) ≤ 2i.

Proof. The Cayley graph of G is connected and if i < s, K(i)^-1K(i) ≠ G, then there is an element of the form g₁$\cdot$g₂ ∈ G\K(i)^-1K(i) with g₁ ∈ K(i)^-1K(i) and g₂ ∈ S.

It takes at most 2i steps to generate g₁ ∈ K(i)^-1K(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₁$\cdot$g₂ ∈ G\K(i)^-1K(i), 2i steps are sufficient.

Corollary 2. c(i) ≤ i² - i.

Since K(s)^-1K(s) = G, any g ∈ G can be written in the form k₁^-1$\cdot$k₂ with k₁^-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|)².