Describing finite groups by short first-order sentences

We say that a class of finite structures for a finite first-order signature is r-compressible for an unbounded function r : N → N + 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 t...

Full description

Saved in:
Bibliographic Details
Published in:Israel journal of mathematics 2017-09, Vol.221 (1), p.85-115
Main Authors: Nies, André, Tent, Katrin
Format: Article
Language:English
Subjects:
Algebra
Analysis
Applications of Mathematics
Compressibility
Group Theory and Generalizations
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Sentences
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We say that a class of finite structures for a finite first-order signature is r-compressible for an unbounded function r : N → N + 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. As a corollary we obtain that the class of all finite transitive permutation groups is log 3 -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.
ISSN:0021-2172
1565-8511
DOI:10.1007/s11856-017-1563-2