skip to main content

Logic Seminar

Tuesday, March 8, 2016
3:00pm to 4:00pm
Add to Cal
Describing finite groups by short first-order sentences
Andre Nies, Professor, Computer Science, University of Auckland,

We say that a class of finite structures for a finite first-order signature is R-compressible for an unbounded function R on the natural numbers if each structure G in the class has a first-order description of size at most O(R(|G|)). We show that the class of finite simple groups is log-compressible, and the class of all finite groups is log-cubed compressible. 

The  results rely on the classification of finite simple groups, the bi-interpretability of the twisted Ree groups with finite difference fields,  the existence of  profinite presentations with few relators for finite groups, and group cohomology. We also indicate why the results are close to optimal. 
Joint work with Katrin Tent (Israel J. of Maths, to appear). 

For more information, please contact Alexander Kechris by email at [email protected] or visit