Computational Group Theory and Applications Workshop

September 23 - 25, 2024 @IHP, Paris

Organizers: Delaram Kahrobaei and Vladimir Shpilrain

Titles and Abstracts:

Christopher Battarbee, Problems in Computational Group Theory arising from Cryptanalysis: In the course of some recent cryptanalytic work, we encountered a number of interesting problems in computational group theory, including the computation of certain types of subgroups and applications of the constructive recognition problem. In this talk we detail some original results allowing for the resolution of these problems, as well as their application to cryptanalysis. This is joint work with several co-authors, a list of whom is available here.

Indira Chatterji, Distortion in fundamental groups of a graph of groups: I will recall the definition of a fundamental group of a graph of groups, explain how to use this construction to distort a group in another, and explain some geometric conditions that prevents distortion. Based on joint work with F. Gautero

Arman Darbinyan, Generalizations of the Dehn function for groups: quasi-isometries, and the word problem: In my talk, I will discuss a generalization of the Dehn function that allows geometric differentiation of finitely generated groups in terms of quasi-isometry. I will sketch some applications of it for constructing quasi-isometrically diverse classes of group and also will explain their link the to decidability of the word problem. Additionally, I will explain how one can extract geometric information from the Turing degree properties of those invariants.

Cornelia Drutu, Understanding infinite groups via their actions on Banach spaces: This talk will discuss various versions of fixed point properties, generalizing property (T), and of proper actions on Banach spaces, generalizing a-T-menability, relevant in many areas (e.g. for the Baum-Connes conjectures, in combinatorics, for the study of expander graphs, in ergodic theory, etc.) In particular, I will describe two notions of spectrum providing an optimal way to measure ``the strength'' of the property (T) that an infinite group may have, and what can be said about this spectrum, in particular for hyperbolic groups. I will also describe weak versions of a-T-menability for (acylindrically) hyperbolic groups and for mapping class groups. This is on joint work with Ashot Minasyan and Mikael de la Salle, and with John Mackay.

Bettina Eick, The conjugacy problem in GL(n,Z): The talk describes an algorithm to solve the conjugacy problem and compute centralizers in GL(n,Z). 

Ramón Flores, Walking back and forth the bridge between graphs and right-angled Artin groups: In the last years, thorough research has been conducted in order to understand graph properties in terms of group properties of the associated right-angled Artin group (RAAG). These properties should be intrinsic, in the sense that they should not depend on a concrete system of generators of the group. In this talk we will give a general review on the topic, with emphasis in planarity, self-complementarity and existence of surjections. In particular, we will highlight the crucial role of the cohomology algebra of the group in our approach. This is joint work with D. Kahrobaei and T. Koberda.

Harald Helfgott, Growth estimates and diameter bounds for linear algebraic groups (joint with Daniele Dona and Jitendra Bajpai): Babai's conjecture states that, for any finite simple non-abelian group G, the diameter of G is bounded by (log |G|)^C for some absolute constant C. By now, the conjecture is known for groups of Lie type of bounded rank; otherwise put, for those groups, we have bounds of the form diam(G)=O((log |G|)^{C_r}) with C_r and the implied constant depending only on the rank r. This is work that started with Helfgott (giving complete proofs for SL_2(F_p) and SL_3(F_p), together with more general material) and culminated with Breuillard-Green-Tao and Pyber-Szabó.

In the work of B-G-T and P-S, the bounds obtained on C_r increase very rapidly with r; in P-S, C_r has exponential-tower dependence on r, while B-G-T -which relies on ultrafilters - would need to be rephrased entirely to even reach that level.

We will discuss two kinds of improvements:

* by means of careful work on controlling exceptional loci of maps, bounding degrees, etc., and changing the inductive procedure first used  by Larsen-Pink, one can obtain a bound of type C_r << exp(r^c), c an absolute constant (really 2+epsilon);

* by means of further changes to the overall strategy, plus dimensional bounds specific to tori and conjugacy classes (not completely dissimilarly from Helfgott's work previous to B-G-T and P-S), we can give polynomial bounds on C_r.

In particular, for any classical Chevalley group G=G(F_q) of rank r with q not too small with respect to r,

diam(G) <= (log |G|)^{O(r^4)}

More generally, we show similar bounds hold for reductive linear algebraic groups over finite fields, and the same methods should carry over to all groups of Lie type.

Corentin Le Coz, Tillich-Zémor hash functions using SLn(Fp): Group theoretic hash functions are obtained by performing a walk in a Cayley graph. Since the first example by Zémor in 1991, it has been an active field of research. During my talk, discuss current existing platforms and attacks and speak about a joint work with Christopher Battarbee, Ramon Flores, Thomas Koberda and Delaram Kahrobaei. We have constructed hash functions using the groups SLn(Fp) as platforms. This gives many examples of group theoretic hash functions combining quick mixing properties and high girth, which give rise to good properties of hash functions. Finally, I will discuss possible developments on simplicial complexes of higher dimensions. This is joint work with Christopher Battarbee, Ramón Flores, Thomas Koberda and Delaram Kahrobaei. 

Keivan Mallahi-Karai, Polynomiality phenomenon for families of p-groups: Let $\mathfrak{g} $ denote a nilpotent Lie algebra defined over the ring of integers. For a prime $p$, denote $G_p$ the p-group associated to  the finite (nilpotent) Lie algebra $\mathfrak{g} \otimes_{ \mathbb{Z}}  \mathbb{F}_p$ via the Lazard correspondence. 

Research in the last few years have shown the certain quantitates (e.g. the faithful dimension) attached to $G_p$ are given by functions that are piecewise polynomials in $p$ over Frobenius sets. In this talk I will discuss various questions of this flavor as well as an application to construction of secret sharing schemes. This is based on various joint works with Mohammad Bardestani, Dima Rumiantsau, Hadi Salmasian, and a work with Delaram Kahrobaei. 

Conchita Martinez-Perez, On coherent Artin groups: A group is coherent if all its finitely generated subgroups are finitely presented. C. Droms has shown that a right angled Artin group is coherent precisely when the defining graph is chordal and later, together with B. Servatius and H. Servatius, they show that this is also equivalent to the derived group being free. For general Aartin groups, Gordon and Wise have characterized coherence in terms of the defining graph and we show that this is also equivalent to the derived group being free. 

Coherent Artin groups are acylindrical hyperbolic. We also consider this property for subgroups which are subgroups of even Artin groups of FC type and generalice a result by Minasyan and Osin for right angled Artin groups. This is a joint work with Jone López de Gámiz

Carmine Monetta, Characterizing Finite Groups via Graph Invariants:  In this presentation, we examine graphs associated with finite groups, where the vertices correspond to the elements of the group itself. The aim of this talk is to present several results that characterize classes of finite groups through the invariants of the associated graph.

Emmanuel Rauzy, Groups with presentations in EDT0L: The EDT0L class of languages was shown to have numerous applications in the study of countable groups, starting with work of Ciobanu, Diekert and Elder.

We provide a new use of EDT0L languages, via the notion of EDT0L presentation of a group. We show how to compute marked hyperbolic quotients of groups given by EDT0L presentations, by relying on the notion of equational Noetherianity. 

This is joined work with Laurent Bartholdi and Leon Pernak. 

Alexander Ryba, The tensor decomposability problem: We discuss methods to determine whether an absolutely irreducible representation of a finite group can be decomposed as a tensor product of representations.

Dmytro Savchuk, Simultaneous conjugacy search problem in self-similar contracting groups: We study the simultaneous conjugacy search problem (SCSP) in the class of self-similar contracting groups. This class of groups contains extraordinary examples like Grigorchuk group, which is known to be non-linear. The groups in this class admit a natural normal form based on the notion of a nucleus portrait and admit a fast polynomial time algorithm solving the word problem. While for some groups in the class the conjugacy search problem has been studied, there are many groups for which no such algorithms are known. We discuss benefits and drawbacks of using these groups in cryptography and provide computational analysis of variants of the length based attack on SCSP for some groups in the class, including Grigorchuk group. Additionally, we discuss another effective heuristic attack on SCSP for contracting groups acting on a binary tree. The talk is based on two projects joint with Delaram Kahrobaei, Arsalan Malik, and Luciana Scuderi and Kerry Seekamp.

Vladimir Shpilrain, Growth in products of matrices: Let A and B be 2x2 matrices. Let w(A, B) be a word of length n. After evaluating w(A, B) as a product of matrices, we get a 2x2 matrix, call it W. The problems that we consider are: What is the largest (by the absolute value) possible entry of W, over all w(A, B) of length n, as a function of n? What is the expected absolute value of the largest (by the absolute value) entry in a random product of n matrices, where each matrix is A or B with probability 0.5?

Antonio Tortora, For what algebraic systems does a useful privacy homomorphism exist?: A ring, of course! Eventually even a group, or a module. In this talk we will present some solutions for homomorphic encryption, which can also adopted for functional encryption.

James B. Wilson,  Efficient tools for tensors: Several difficult problems in complexity and cryptography can be stated as problems with tensors and hidden field equations Including quantum-resistance signature schemes of Blaser et. al., and cryptographic schemes of Patron and others.  Many of these questions are in fact problems studied for independent reasons in the area of group isomorphism.  For the past decade, several  groups  have leveraged linear algebra and Lie theory methods to make substantial practical and complexity breakthroughs on tensor computations. I will detail the these applications, summarize the results, and give a survey of the available methods.

Andrzej Zuk, Automata, groups and differential equations: We present a construction which associates to differential equations discrete groups. In order to establish this relation we use automata and random walks on ultra discrete limits.