Factorization in finite groups

• Applicant: Professor Dr. Markus Lohrey
• Subject Area: Theoretical Computer Science
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 544679539

The algorithmic branch of finite group theory has numerous applications in mathematics and computer science e.g. in abstract algebra, graph isomorphism testing, quantum computing, automata theory, complexity theory and cryptography. Many algorithmic problems in these application areas ask about the existence of a specific factorization of a given group element. A famous example for a factorization problem is the membership problem for a finite group G. It asks whether a given element g of G can be written as a product of other given elements of G. Further factorization problems are obtained by posing additional restrictions on the allowed products that yield g. Such restrictions can be formulated by language theoretic means like for instance finite automata or context-free grammars. In the project we plan to study factorization problems for finite groups in a systematic way from different viewpoints: • We will investigate factorization problems under different algorithmic perspectives: worst case complexity, parameterized complexity, enumeration complexity, counting complexity and succinctness of descriptions. • We mainly want to work on factorization problems for permutation groups. Occasionally we will also consider black box groups. Thereby we will also consider algebraic and combinatorial subclasses of groups, that might lead to better algorithmic results. Natural candidates are abelian groups, nilpotent groups, solvable groups, or transitive permutation groups. • In order to specify the properties of the desired factorization of group elements, automata theoretic concepts are a natural approach. Finite automata and context-free grammars (and subclasses of these) have turned out to be useful for this in our previous work and will be applied in the project. We plan to implement some of our algorithms. Moreover, for intractable problems we want to test the applicability of modern SAT and QBF solver technology.

• DFG Programme: Research Grants