Rapid random generation of Lie algebras

Abstract of the research project Imagine that you are a toy puzzle maker. How would you create the best possible puzzle? The Rubik's Cube provides an excellent example. This puzzle has a huge number of possible initial states, but there is always a very short solution if we know how to find it. The excellence of the Rubik's Cube lies in its combination of three properties: it is not complex, it is complicated, and it is quickly solvable. Mathematically, puzzles with these same properties can be represented by abstracting symmetries, that is, with groups. The shortest length of a solution for such a puzzle is called the diameter of the group. Therefore, to understand the computational complexity of the basic building blocks of symmetries, we must understand the diameters of finite simple groups. The leading conjecture (Babai's conjecture) in this regard predicts that the diameter of a noncommutative finite simple group can be bounded above by a polynomial of the logarithm of the group size, with the degree of the polynomial being absolute and independent of the group itself. In other words, the diameters of the basic building blocks of symmetries are expected to be quite small, or alternatively, noncommutative finite simple groups are always quickly generated. The resolution of Babai's conjecture would theoretically provide rapid solutions to any problems involving invertible operations, which would have many diverse applications in mathematics and computer science. Babai's conjecture is still open. After the hard work of many distinguished mathematicians (including Fields Medalists and EMS Prize laureates), the conjecture is known for the family of matrix groups PSL_n(F_q) if n is of bounded size and q is unbounded. An important open case of Babai's conjecture is the family PSL_n(F_q), where n is unbounded and q is of bounded size. Classical matrix groups are closely related to their Lie algebras. Moving to Lie algebras linearizes many problems and makes them easier. In the proposed research project, we would like to take advantage of this and investigate the linearized version of Babai's conjecture for the Lie algebra sl_n(F_p) of matrices with trace 0 over a finite field. We estimate that this linearized problem is easier than the original Babai's conjecture while still capturing some of its complexity, so its resolution could offer new ideas for the original conjecture. To approach the conjecture about the rapid generation of sl_n(F_p), we will develop tools from probability that are classical in groups (random generation, random walks) but do not exist for Lie algebras over finite fields. These tools played a crucial role in results regarding Babai's conjecture for groups, so we expect that their development will pave the way towards rapid generation of Lie algebras, very likely even in simpler versions than in groups. The development of these tools is the main goal of our proposed research project. First, we will prove that randomly selected elements of sl_n(F_p) generate sl_n(F_p) with high probability (random generation). Then we will develop random walks in Lie algebras and describe them in detail in the case of sl_n(F_p). Finally, we will use random walks to study rapid random generation of sl_n(F_p) in the case of unbounded n.