Black box group

Algebraic structure → Group theory Group theory
Basic notions Subgroup Normal subgroup Quotient group (Semi-)direct product Group homomorphisms kernel image direct sum wreath product simple finite infinite continuous multiplicative additive cyclic abelian dihedral nilpotent solvable List of group theory topics
Finite groups Classification of finite simple groups cyclic alternating Lie type sporadic Lagrange's theorem Sylow theorems Hall's theorem p-group Elementary abelian group Frobenius group Schur multiplier Symmetric group Sn Klein four-group V Dihedral group Dn Quaternion group Q Dicyclic group Dicn
Discrete groups Lattices Integers (Z) Lattice Modular groups PSL(2,Z) SL(2,Z)
Topological / Lie groups Solenoid Circle General linear GL(n) Special linear SL(n) Orthogonal O(n) Euclidean E(n) Special orthogonal SO(n) Unitary U(n) Special unitary SU(n) Symplectic Sp(n) G2 F4 E6 E7 E8 Lorentz Poincaré Conformal Diffeomorphism Loop Infinite dimensional Lie group O(∞) SU(∞) Sp(∞)
Algebraic groups Elliptic curve Linear algebraic group Abelian variety

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. 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,^[1] the Product Replacement Algorithm,^[2] and testing group commutativity.^[3]

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.^[4]

See also

• Implicit graph
• Matroid oracle

Notes

1. ↑ L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164–174.
2. ↑ 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. doi:10.1080/00927879508825509. 
3. ↑ Pak, Igor (2012). "Testing commutativity of a group and the power of randomization". LMS Journal of Computation and Mathematics. 15: 38–43. doi:10.1112/S1461157012000046. 
4. ↑ See Hоlt 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, FL, 2005. ISBN 1-58488-372-3
• Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. ISBN 0-521-66103-X.
• Kantor, William M.; Seress, Ákos (2001). Black Box Classical Groups. Memoirs of the American Mathematical Society. 708. American Mathematical Society. ISBN 0-8218-2619-0. ISSN 0065-9266.