DESCRIPTIVE COMPLEXITY OF FINITE ABELIAN GROUPS

作者：Gomaa Walid^*

来源：International Journal of Algebra and Computation, 2010, 20(8): 1087-1116.

DOI：10.1142/S0218196710006047

• Ehrenfeucht-Fraisse games
• abelian groups
• descriptive complexity
• definability
• expressibility

We investigate the descriptive complexity of finite abelian groups. Using Ehrenfeucht-Fraisse games we find upper and lower bounds on quantifier depth, quantifier alternations, and number of variables of a first-order sentence that distinguishes two finite abelian groups. Our main results are the following. Let G(1) and G(2) be a pair of nonisomorphic finite abelian groups. Then there exists a positive integer m that divides one of the two groups' orders such that the following holds: (1) there exists a first-order sentence phi that distinguishes G(1) and G(2) such that phi is existential, has quantifier depth O(logm), and has at most 5 variables and (2) if phi is a sentence that distinguishes G(1) and G(2) then phi must have quantifier depth Omega(log m). These results are applied to (1) get bounds on the first-order distinguishability of dihedral groups, (2) to prove that on the class of finite groups both cyclicity and the closure of a single element are not first-order definable, and (3) give a different proof for the first-order undefinability of simplicity, nilpotency, and the normal closure of a single element on the class of finite groups (their undefinability were shown by Koponen and Luosto in an unpublished paper).

• 出版日期2010-12