| Speaker: Stephen Glasby Affiliation: University of Western Australia Time: 15:00 Thursday, 7 October, 2021 Location: Zoom |
| Dr Who has been captured by the evil Celestial Toymaker. In order to be released, Dr Who must recognize a large finite classical group G (known only to the Toymaker) in under 5 minutes. The elements of G are not familiar dxd matrices over GF(q) preserving a certain non-degenerate form, but are encoded as long strings of 0s and 1s. Dr Who must recognize G (constructively in 5 minutes) and can only: 1. choose random elements of G, 2. multiply elements of G, 3. invert elements of G, and 4. test the order of elements of G. I shall first explain why the Toymaker's problem is central to computational group theory, and why a quick solution is highly desirable. In so doing, we will briefly review some key ideas for matrix group recognition before reducing the Toymaker's problem to the following geometric problem. Given two (small-dimensional) non-degenerate subspaces U, U' of a symplectic/unitary/orthogonal space V, what is the probability that the subspace U + U' is non-degenerate and of dimension dim(U) + dim(U')? (The sum U + U' is usually not perpendicular.) |