Submission date: 30 September 2014

Abstract:

We say that a class of finite structures for a finite signature is r-compressible 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 3 -compressible. The first result relies on the classification of finite simple groups, and the bi-interpretability of the small Ree groups with finite difference fields. We also indicate why these results are close to optimal.

Mathematics Subject Classification: 03B70, 20D99

Keywords and phrases:

Full text arXiv 1409.8390: pdf, ps.