In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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
In mathematics, computational group theory is the study of
group (mathematics), groups by means of computers. It is concerned
with designing and analysing algorithms and
data structures to compute information about groups. The subject
has attracted ...
, 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''(log
2, ''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 group
In computational group theory, a black box group (black-box group) is a group ''G'' whose elements are encoded by bit strings of length ''N'', and group operations are performed by an oracle (the "black box"). These operations include:
• takin ...
s. 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
The ''ATLAS of Finite Groups'', often simply known as the ''ATLAS'', is a group theory book by John Horton Conway, Robert Turner Curtis, Simon Phillips Norton, Richard Alan Parker and Robert Arnott Wilson (with computational assistance from J. ...
.
Definition
Informal definition
Let ''G'' be a finite group and let ''S'' be a subset of ''G''. A sequence ''L'' = (''g''
1,…,''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:
# ''g''
''i'' ∈ ''S''
# ''g''
''i'' = ''g''
''j'' ''g''
''k'' for some ''j'',''k'' < ''i''
# ''g''
''i'' = ''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 (''w''
1,…,''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
[Ákos Seress. (2003). Permutation Group Algorithms. nline Cambridge Tracts in Mathematics. (No. 152). Cambridge: Cambridge University Press.] 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
In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...
D
12 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 S
6, 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)
Applications
''Short descriptions of finite groups''. Straight-line programs can be used to study compression of finite groups via
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
. 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
3, ''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
In the area of modern algebra known as group theory, the Suzuki groups, denoted by Sz(22''n''+1), 2''B''2(22''n''+1), Suz(22''n''+1), or ''G''(22''n''+1), form an infinite family of groups of Lie type found by , that are simple for ''n'' ≥ 1. ...
, has rank 2 via generators ''a'' and ''b'', where ''a'' has order 2, ''b'' has order 4, ''ab'' has order 5, ''ab''
2 has order 25 and ''abab''
2''ab''
3 has order 25. The following is a straight-line program that computes a generating set for a maximal subgroup E
32·E
32⋊C
31. 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 . 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.
The idea of the proof is to construct a set ''Z'' = 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 over ''Z''. The set ''Z'' is constructed by inductively defining an increasing sequence of sets ''K''(''i'').
Let ''K''(''i'') = , 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'') = . Let ''K''(0) = and ''c''(0)=0. We define the set ''Z'' recursively:
* If ''K''(''i'')
−1''K''(''i'') = ''G'', declare ''s'' to take upon the value ''i'' and stop.
* Else, choose some ''z''
''i''+1 ∈ ''G''\''K''(''i'')
−1''K''(''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 an element of ''K''(''i'')
−1''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:
The next claim is used to show that the cost of every group element is within the required bound.
It takes at most 2''i'' steps to generate ''g''
1 ∈ ''K''(''i'')
−1''K''(''i''). There is no point in generating the element of maximum length, since it is the identity. Hence steps suffice. To generate ''g''
1·''g''
2 ∈ ''G''\''K''(''i'')
−1''K''(''i''), 2''i'' steps are sufficient.
We now finish the theorem. Since ''K''(''s'')
−1''K''(''s'') = ''G'', any ''g'' ∈ ''G'' can be written in the form ''k''·''k''
2 with ''k'',''k''
2 ∈ ''K''(''s''). By Corollary 2, we need at most steps to generate ''Z''(''s'') = ''Z'', and no more than steps to generate ''g'' from ''Z''(''s'').
Therefore .
References
{{reflist
Algebra