View source for Straight-line program

In [[computer science]], a '''straight-line program''' is, informally, a [[computer program|program]] that does not contain any loop or any test, and is formed by a sequence of steps that apply each an [[operation (mathematics)|operation]] to previously computed elements.

This article is devoted to the case where the allowed operations are the operations of a [[group (mathematics)|group]], that is multiplication and inversion. More specifically a '''straight-line program''' ('''SLP''') for a finite group ''G'' =&nbsp;&lang;''S''&rang; 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''&nbsp;∈&nbsp;''G'' if ''g''&nbsp;∈&nbsp;''L'', where ''g'' is encoded by a word in ''S'' and its inverses.

Intuitively, an SLP computing some ''g''&nbsp;∈&nbsp;''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&nbsp;''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<ref>Babai, László, and Endre Szemerédi. "On the complexity of matrix group problems I." Foundations of Computer Science, 1984. 25th Annual Symposium on Foundations of Computer Science. IEEE, 1984</ref> 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<sup>2</sup>|''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''&nbsp;=&nbsp;&lang;''S''&rang; and ''g''&nbsp;∈&nbsp;''G'', find a straight-line program computing ''g'' over&nbsp;''S''. The constructive membership problem is often studied in the setting of [[black box group]]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]].

==Definition==

===Informal definition===
Let ''G'' be a finite group and let ''S'' be a subset of ''G''.  A  sequence ''L'' = (''g''<sub>1</sub>,...,''g''<sub>''m''</sub>) of elements of ''G'' is a ''straight-line program'' over ''S'' if each ''g''<sub>''i''</sub> can be obtained by one of the following three rules: 
# ''g''<sub>''i''</sub> ∈ ''S''
# ''g''<sub>''i''</sub> = ''g''<sub>''j''</sub> <math>\cdot</math> ''g''<sub>''k''</sub> for some ''j'',''k'' < ''i'' 
# ''g''<sub>''i''</sub> = ''g''{{su|b=''j''|p=−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''.

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''<sub>1</sub>,...,''w''<sub>''m''</sub>) such that for each ''i'', ''w''<sub>''i''</sub> is a symbol for some element of ''S'', or ''w''<sub>''i''</sub> = (''w''<sub>''j''</sub>,-1) for some ''j'' < ''i'', or ''w''<sub>''i''</sub> = (''w''<sub>''j''</sub>,''w''<sub>''k''</sub>) for some ''j'',''k'' < ''i'', such that ''w''<sub>''m''</sub> takes upon the value ''g'' when evaluated in ''G'' in the obvious manner.

The original definition appearing in <ref name = "Seress">Ákos Seress. (2003). Permutation Group Algorithms. [Online]. Cambridge Tracts in Mathematics. (No. 152). Cambridge: Cambridge University Press.</ref> requires that ''G'' =&lang;''S''&rang;. 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.<ref name = "Seress"/>

==Examples==

The [[dihedral group]]  D<sub>12</sub> 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 λρ<sup>3</sup>:

{{col-begin}}
{{col-break}}
# λ
# ρ
# ρ<sup>2</sup>
# ρ<sup>3</sup>
# λρ<sup>3</sup>
{{col-break}}
# λ is a generator.
# ρ is a generator.
# Second rule: (2).(2)
# Second rule: (3).(2)
# Second rule: (1).(4)
{{col-end}}

In S<sub>6</sub>, 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):

{{col-begin}}
{{col-break}}
# α
# β
# α<sup>2</sup> 
# α<sup>2</sup>β
# α<sup>2</sup>βα
# α<sup>2</sup>βαβ
# α<sup>2</sup>βαβα<sup>2</sup>βαβ 
{{col-break}}
# (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)
{{col-break}}
# α 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)
{{col-end}}

==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<sup>3</sup>|''G''|).<ref>{{cite journal
| last1=Nies | first1= André
| last2=Tent | first2=Katrin
| date=2017
| title=Describing finite groups by short first-order sentences
| journal=[[Israel Journal of Mathematics]]
| volume=221
| pages=85–115
| doi=10.1007/s11856-017-1563-2 | doi-access=free
| arxiv=1409.8390}}</ref>

''Straight-line programs computing generating sets for maximal subgroups of finite simple groups''. The online ATLAS of Finite Group Representations<ref>{{Cite web|url=http://brauer.maths.qmul.ac.uk/Atlas/v3/|title = ATLAS of Finite Group Representations - V3}}</ref> 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''<sup>2</sup> has order 25 and ''abab''<sup>2</sup>''ab''<sup>3</sup> has order 25. The following is a straight-line program that computes a generating set for a maximal subgroup E<sub>32</sub>·E<sub>32</sub>⋊C<sub>31</sub>. This straight-line program can be found in the online ATLAS of Finite Group Representations.

{{col-begin}}
{{col-break}}
{{not a typo|
# ''a''
# ''b''
# ''ab''
# ''abb''
# ''ababb''
# ''ababbb''
# (''abb'')<sup>18</sup>
# (''abb'')<sup>−18</sup>
# (''abb'')<sup>−18</sup>''b''
# (''abb'')<sup>−18</sup>''b''(''abb'')<sup>18</sup>
# (''ababb'')<sup>14</sup>
# (''ababb'')<sup>−14</sup>
# (''ababb'')<sup>−14</sup>''ababbb''
# (''ababb'')<sup>−14</sup>''ababbb''(''ababb'')<sup>14</sup>}}
{{col-break}}
{{not a typo|
# ''a'' is a generator.
# ''b'' is a generator.
# Second rule: (1).(2)
# Second rule: (3).(2)
# Second rule: (3).(4)
# Second rule: (5).(2)
# Second rule iterated: (4) multiplied 18 times
# Third rule: (7) inverse
# Second rule: (8).(2)
# Second rule: (9).(7)
# Second rule iterated: (5) multiplied 14 times
# Third rule: (11) inverse
# Second rule: (12).(6)
# Second rule: (13).(11)
}}
{{col-end}}

==Reachability theorem==
The reachability theorem states that, given a finite group ''G'' generated by ''S'', each ''g'' ∈ ''G'' has a maximum cost of {{math|(1&nbsp;+ lg{{mabs|''G''}})<sup>2</sup>}}. 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<sup>r</sup> ≤ ''k''}.

The idea of the proof is to construct a set ''Z'' = {''z''<sub>1</sub>,...,''z''<sub>''s''</sub>} 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 {{math|2{{mabs|''Z''}}}} over ''Z''. The set ''Z'' is constructed by inductively defining an increasing sequence of sets ''K''(''i'').

Let ''K''(''i'') = {''z''<sub>1</sub><sup>''α''<sub>1</sub></sup>·''z''<sub>2</sub><sup>''α''<sub>2</sub></sup>·...·''z''<sub>''i''</sub><sup>''α''<sub>''i''</sub></sup> : ''α''<sub>''j''</sub> ∈ {0,1}}, where ''z''<sub>''i''</sub> 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''<sub>1</sub>,...,''z''<sub>''i''</sub>}. Let ''K''(0) = {1<sub>''G''</sub>} and ''c''(0)=0. We define the set ''Z'' recursively:
* If ''K''(''i'')<sup>−1</sup>''K''(''i'') = ''G'', declare ''s'' to take upon the value ''i'' and stop.
* Else, choose some ''z''<sub>''i''+1</sub> ∈ ''G''\''K''(''i'')<sup>−1</sup>''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'')<sup>−1</sup>''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:

{{math theorem|name=Claim 1|1= If ''i'' < ''s'' then {{math|1={{mabs|''K''(''i''+1)}} = 2{{mabs|''K''(''i'')}}}}.}}

{{Math proof|1= It is immediate that {{math|1={{mabs|''K''(''i''+1)}} ≤ 2{{mabs|''K''(''i'')}}}}. Now suppose for a contradiction that {{math|1={{mabs|''K''(''i''+1)}} < 2{{mabs|''K''(''i'')}}}}. By the pigeonhole principle there are ''k''<sub>1</sub>,''k''<sub>2</sub> ∈ ''K''(''i''+1) with ''k''<sub>1</sub> = ''z''<sub>1</sub><sup>''α''<sub>1</sub></sup>·''z''<sub>2</sub><sup>''α''<sub>2</sub></sup>·...·''z''<sub>''i''+1</sub><sup>''α''<sub>''i''+1</sub></sup> = ''z''<sub>1</sub><sup>''β''<sub>1</sub></sup>·''z''<sub>2</sub><sup>''β''<sub>2</sub></sup>·...·''z''<sub>''i''+1</sub><sup>''β''<sub>''i''+1</sub></sup> = ''k''<sub>2</sub> for some ''α''<sub>''j''</sub>,''β''<sub>''j''</sub> ∈ {0,1}. Let ''r'' be the largest integer such that ''α''<sub>''r''</sub> ≠ ''β''<sub>''r''</sub>. Assume WLOG that ''α''<sub>''r''</sub> = 1. It follows that ''z''<sub>''r''</sub> = ''z''<sub>''p''</sub><sup>−''α''<sub>''p''</sub></sup>·''z''<sub>''p''-1</sub><sup>−''α''<sub>''p''-1</sub></sup>·...·''z''<sub>1</sub><sup>−''α''<sub>1</sub></sup>·''z''<sub>1</sub><sup>''β''<sub>1</sub></sup>·''z''<sub>2</sub><sup>''β''<sub>2</sub></sup>·...·''z''<sub>''q''</sub><sup>''β''<sub>''q''</sub></sup>, with ''p'',''q'' < ''r''. Hence ''z''<sub>''r''</sub> ∈ ''K''(''r''−1)<sup>−1</sup>''K''(''r''&nbsp;−&nbsp;1), a contradiction.}}

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

{{math theorem|name=Claim 2| {{math|1=''c''(''i'') ≤ ''i'' <sup>2</sup> − ''i''}}.}}

{{Math proof|1= Since ''c''(0)=0 it suffices to show that ''c''(''i''+1) - ''c''(''i'') ≤ 2''i''. The [[Cayley graph]] of ''G'' is connected and if ''i'' < ''s'', ''K''(''i'')<sup>−1</sup>''K''(''i'') ≠ ''G'', then there is an element of the form {{math|1=''g''<sub>1</sub>·''g''<sub>2</sub> ∈ ''G'' \ ''K''(''i'')<sup>−1</sup>''K''(''i'')}} with ''g''<sub>1</sub> ∈ ''K''(''i'')<sup>−1</sup>''K''(''i'') and ''g''<sub>2</sub> ∈ ''S''.}}

It takes at most 2''i'' steps to generate ''g''<sub>1</sub> ∈ ''K''(''i'')<sup>−1</sup>''K''(''i''). There is no point in generating the element of maximum length, since it is the identity. Hence {{math|1=2''i'' −1}} steps suffice. To generate ''g''<sub>1</sub>·''g''<sub>2</sub> ∈ ''G''\''K''(''i'')<sup>−1</sup>''K''(''i''), 2''i'' steps  are sufficient.

We now finish the theorem. Since ''K''(''s'')<sup>−1</sup>''K''(''s'') = ''G'', any ''g'' ∈ ''G'' can be written in the form ''k''{{su|b=1|p=−1}}·''k''<sub>2</sub> with ''k''{{su|b=1|p=−1}},''k''<sub>2</sub> ∈ ''K''(''s''). By Corollary 2, we need at most {{math|''s''<sup>2</sup> − ''s''}} steps to generate ''Z''(''s'') = ''Z'', and no more than {{math|1=2''s'' − 1}} steps to generate ''g'' from ''Z''(''s'').

Therefore {{math|1=''c''(''g''{{!}}''S'') ≤ ''s''<sup>2</sup> + ''s'' − 1 ≤ lg<sup>2</sup>{{mabs|''G''}} + lg{{mabs|''G''}} − 1 ≤ (1 + lg{{mabs|''G''}})<sup>2</sup>}}.

==References==
{{reflist}}

[[Category:Group theory]]
[[Category:Computational complexity theory]]