Black box group explained

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:

• taking a product g·h of elements g and h,
• taking an inverse g⁻¹ of element g,
• deciding whether g = 1.

This class is defined to include both the permutation groups and the matrix groups. The upper bound on the order of G given by |G| ≤ 2^N shows that G is finite.

Applications

The black box groups were introduced by Babai and Szemerédi in 1984.^[1] They were used as a formalism for (constructive) group recognition and property testing. Notable algorithms include the Babai's algorithm for finding random group elements,^[2] the Product Replacement Algorithm,^[3] and testing group commutativity.^[4]

Many early algorithms in CGT, such as the Schreier–Sims algorithm, require a permutation representation of a group and thus are not black box. Many other algorithms require finding element orders. Since there are efficient ways of finding the order of an element in a permutation group or in a matrix group (a method for the latter is described by Celler and Leedham-Green in 1997), a common recourse is to assume that the black box group is equipped with a further oracle for determining element orders.^[5]

See also

• Implicit graph
• Matroid oracle

Notes

1. Book: Babai. L.. Szemeredi. E.. 25th Annual Symposium on Foundations of Computer Science, 1984 . On the Complexity of Matrix Group Problems I . 1984. 229–240. 10.1109/SFCS.1984.715919. 0-8186-0591-X.
2. L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164–174.
3. Frank Celler . Charles R. Leedham-Green . Scott H. Murray . Alice C. Niemeyer . E.A. O'Brien . 1995 . Generating random elements of a finite group . Communications in Algebra . 23 . 3 . 4931–4948 . 10.1080/00927879508825509 . 10.1.1.43.2250 .
4. Pak . Igor . Igor Pak . 2012 . Testing commutativity of a group and the power of randomization . LMS Journal of Computation and Mathematics . 15 . 38–43 . 10.1112/S1461157012000046 . free .
5. See Holt et al. (2005).

References

• Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, Florida, 2005.
• Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. .
• Book: William Kantor . Black Box Classical Groups . Memoirs of the American Mathematical Society . 0065-9266 . 708 . William M. . Kantor . Ákos . Seress . . 2001 . 978-0-8218-2619-5 .