On the size of finite rational matrix semigroups
Christoph Haase (UCL, London)
Abstract: Given a finite set of $n \times n$ integer matrices $\mathcal M$ that generate a finite multiplicative semigroup $\overline{\mathcal M}$, I am going to present a recent result showing that any $M \in \overline{\mathcal M}$ is a product of at most $2^{O(n^2 \log n)}$ elements from $\mathcal M$. This bound immediately implies a bound on the cardinality of $\overline{\mathcal M}$.
I will provide a non-technical proof sketch demonstrating how the aforementioned bound can be obtained. In addition, I will discuss the history of this problem, its motivation, which is rooted in automata theory, related results that have appeared over the last decades, and open challenges.
The talk is based on joint work with Georgina Bumpus, Stefan Kiefer, Paul-Ioan Stoienescu and Jonathan Tanner from Oxford, which appeared at ICALP'20
computer science theorycombinatorics
Audience: researchers in the discipline
LA Combinatorics and Complexity Seminar
Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm
| Organizers: | Igor Pak*, Greta Panova |
| *contact for this listing |