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 either 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. This has important applications in computational group theory, by using SLPs to efficiently encode group elements as words over a given generating set.
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(log2|G|) in every generating set.
An efficient solution to the constructive membership problem is crucial to many group-theoretic algorithms. It 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. 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.
Explicit straight-line programs are given for a wealth of finite simple groups in the online ATLAS of Finite Groups.
Definition
Informal definition
Let G be a finite group and let S be a subset of G. A sequence L = (g1,…,gm) of elements of G is a straight-line program over S if each gi can be obtained by one of the following three rules: gi ∈ S gi = gj gk for some j,k < i gi = g 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 (w1,…,wm) such that for each i, wi is a symbol for some element of S, or wi = (wj,-1) for some j < i, or wi = (wj,wk) for some j,k < i, such that wm 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 D12 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 λρ3:
λ
ρ
ρ2
ρ3
λρ3
λ is a generator. ρ is a generator. Second rule: (2).(2) Second rule: (3).(2) Second rule: (1).(4)
In S6, 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):
α
β
α2
α2β
α2βα
α2βαβ
α2βαβα2βαβ
(1 2 3 4 5 6) (1 2) (1 3 5)(2 4 6) (1 3 5 2 4 6) (1 4)(2 5 3 6) (1 4 2 5 3 6) (1 2 3)(4 5 6)
α is a generator
β is a generator
Second rule: (1).(1) Second rule: (3).(2) Second rule: (4).(1) Second rule: (5).(2) Second rule: (6).(6)